Может ли быть решена транспортная задача как обычная задача линейного программирования?


Скачать 183.76 Kb.
НазваниеМожет ли быть решена транспортная задача как обычная задача линейного программирования?
Дата публикации05.05.2013
Размер183.76 Kb.
ТипВопрос
userdocs.ru > Спорт > Вопрос
1, Назначение транспортной задачи – определить объём перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок.

2, Может ли быть решена транспортная задача как обычная задача линейного программирования? – да, может, но при этом приходится реализовывать более сложные алгоритмы.

3, Общее представление транспортной задачи. - безымянный.png

4, Какая транспортная модель называется несбалансированной? – когда суммарный объём предложений не равен общему объёму спроса на товары

5, Как несбалансированную транспортную задачу сделать сбалансированной? – путём ввода фиктивных пунктов назначения или отправления.

6, Этапы Алгоритма решения транспортной задачи.

Шаг 1: определяем начальное базисное решение допустимое решение и переходим к шагу 2.

Шаг 2: на основании условия оптимальности симплекс – метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности , вычисления заканчиваются, иначе – к 3 шагу.

Шаг 3: с помощью условия допустимости симплекс – метода среди текущих базисных переменных определяем исключаемую . Затем находим новое базисное решение и к шагу 2.

7, Как определяется количество базисных переменных в начальном базисном решении? – по формуле: кол. отправных пунктов + кол. Пунктов назначения -1 (m-n-1)

8, Какие методы используются для построения начального решения в транспортных моделях? В чем их отличия?

Метод севера – западного угла

Метод наименьшей стоимости

Метод Фогеля

Различие этих методов заключается в качестве начального решения т.е. удалённости решения от оптимального.

9, Метод северо-западного угла. Выполнение начинается с верхней левой ячеики (северо-западного угла) транспортной таблицы, т.е. с переменной хи.

Шаг 1. Переменной хи присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.

Шаг 2. Вычеркивается строка (или столбец) с полностью реализованным предложением (с удовлетворенным спросом). Это означает, что в вычеркнутой строке (столбце) мы не будем присваивать значения остальным переменным (кроме переменной, определенной на первом этапе). Если одновременно удовлетворяются спрос и предложение, вычеркивается только строка или только столбец.

Шаг 3. Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому этапу.

10, Метод наименьшей стоимости. Метод наименьшей стоимости.’ Данный метод находит лучшее начальное решение, чем метод северо-западного угла, поскольку выбирает переменные, которым соответствуют наименьшие стоимости. Сначала по всей транспортной таблице ведется поиск ячейки с наименьшей стоимостью. Затем переменной в этой ячейке присваивается наибольшее значение, допускаемое ограничениями на спрос и предложение. (Если таких переменных несколько, выбор произволен.) Далее вычеркивается соответствующий столбец или строка, и соответствующим образом корректируются значения спроса и предложений. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается или строка, или столбец (точно так же, как в методе северо-западного угла). Затем просматриваются не вычеркнутые ячейки, и выбирается новая ячейка с минимальной стоимостью. Описанный процесс продолжается до тех пор, пока не останется лишь одна не вычеркнутая строка или столбец.

11, Метод Фогеля. Метод Фогеля. Данный метод является вариацией метода наименьшей стоимости и в общем случае находит лучшее начальное решение. Алгоритм этого метода состоит из следующих шагов.

Шаг 1. Для каждой строки (столбца), которой соответствует строго положительное предложение (спрос), вычисляется штраф путем вычитания наименьшей стоимости из следующей но величине стоимости в данной строке (столбце).

Шаг2. Выделяется строка или столбец с наибольшим штрафом. Если таковых несколько, выбор произволен. Из выделенной строки или столбца выбирается переменная, которой соответствует минимальная стоимость, и ей присваивается наибольшее значение, позволяемое ограничениями. Затем в соответствии с присвоенным значением переменной корректируются величины оставшегося неудовлетворенным спроса и нереализованного предложения. Строка или столбец, соответствующие выполненному ограничению, вычеркиваются из таблицы. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается только строка или только столбец, причем оставшейся строке (столбцу) приписывается нулевое предложение (спрос).

Шаг 3. а) Если не вычеркнута только одна строка или только один столбец с нулевым спросом или предложением, вычисления заканчиваются.

б) Если не вычеркнута только одна строка (столбец) с положительным предложением (спросом), в этой строке (столбце) методом наименьшей стоимости находятся базисные переменные, и вычисления заканчиваются.

в) Если всем не вычеркнутым строкам и столбцам соответствуют пулевые объемы предложения и спроса, методом наименьшей стоимости находятся нулевые базисные переменные, и вычисления заканчиваются.

г) Во всех остальных случаях необходимо перейти к и. 1.

12. Итерационный алгоритм решения транспортной задачи. Посли определения начального решения (с помощью одного из трех методов, описанных в предыдущем разделе) применяется алгоритм, позволяющий найти.

Шаг 1. На основе симплексного условия оптимальности среди текущего множества небазисных переменных определяется вводимая в базис переменная, которая может улучшить значение целевой функции. Если условие оптимальности выполняется для всех небазисных переменных, вычисления заканчиваются, в противном случае необходимо перейти ко второму этапу.

Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому этапу.

В методе потенциалов каждой строке / и каждому столбцу / транспортной таблицы ставятся в соответствие числа (потенциалы) и1 и V. Для каждой базисной переменной хч потенциалы и1 и у; (как показано в разделе 5.4) удовлетворяют уравнению

13. Метод потенциалов.

14, Как определяется вводимая в базис переменная в транспортной задаче. - Поскольку в транспортной задаче ведется поиск минимума стоимости перевозок, вводимой в базис будет переменная, имеющая наибольший положительный коэффициент в z-строке.

15, Как определяется исключаемая из базиса переменная в транспортной задаче - Исключаемая из базиса переменная определяется следующим образом. Обозначим через q количество груза, перевозимого по маршруту соответствующему вводимой переменной. Максимально возможное значение q определяем из следующих условий.

1. Должны выполняться ограничения на спрос и предложение.

2. Ни по какому маршруту не должны выполняться перевозки с отрицательным объемом грузов.

Эти условия позволяют найти значение q и определить исключаемую переменную.

Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной.

Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. Для любой вводимой переменной можно построить только один замкнутый цикл. Теперь найдем значение q. Для того чтобы удовлетворить ограничениям по спросу и предложению, надо поочередно отнимать и прибавлять q к значениям базисных переменных, расположенных в угловых ячейках цикла (не имеет значения направление обхода цикла: по часовой стрелке или против). Новые значения базисных переменных останутся неотрицательными, если значение q не будет превышать минимального значения базисной переменной, из которой вычитается q. Таким образом, q будет принимать минимальное значение базисной переменной цикла из которой происходит вычитание. При этом данная базисная переменная после вычитания примет значение 0. Это и будет выводимая переменная. Если одновременно несколько базисных переменных примут значение 0, то только одна из них (любая) выйдет из базиса.

16, Опишите задачу о назначениях. ‘'Лучший работник для выполнения данной работы — вот подходящее краткое описание задачи о назначениях. В этой задаче необходимо назначить работников на определенные работы; каждый работник может выполнять любую работу, хотя и о различной степенью мастерства. Если на некоторую работу назначается работник именно той квалификации, которая необходима для ее выполнения, тогда стоимость выполнения работы будет ниже, чем при назначении на данную работу работника неподходящей квалификации. Цель задачи — найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.

17, Для решения какой задачи используется венгерский метод? – для

18, Опишите этапы решения задачи венгерским методом. Шаг 1. На основе симплексного условия оптимальности среди текущего множества небазисных переменных определяется вводимая в базис переменная, которая может улучшить значение целевой функции. Если условие оптимальности выполняется для всех не- базисиых неременных, вычисления заканчиваются, в противном случае необходимо перейти ко второму этапу.

Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому этапу.

Сетевые модели

^ 1, Перечислите известные Вам сетевые оптимизационные алгоритмы. – 1) Алгоритм нахождения минимального остовного дерева. 2)Алгоритм поиска кратчайшего пути. 3)алгоритм определения максимального потока. 4)Алгоритм минимизации стоимости пути в сети с ограниченной пропускной способностью. 5)алгоритм определения критического пути.

2, Какими множествами описывается сеть? – Сеть состоит из множества узлов, связанных дугами или рёбрами. Таким образом сеть описывается парой множеств (N:A), где N – множество узлов, а А – множество рёбер.

3, Какое ребро называется направленным? – Ребро называется направленным или ориентированным, если в одном направлении возможен только положительный поток, а в противоположном – только нулевой.

4, Какое ребро называется ориентированным? - ?

5, Дайте определение понятия пути в сетевом моделировании. – Путем называется последовательность различных рёбер, соединяющих 2 узла, независимо от направления потока в каждом ребре.

6, Когда путь формирует цикл? – Путь формирует цикл, если начальный и конечный узлы совпадают.

7, Что значит ориентированный цикл? - Ориентированный цикл – Это цикл, в котором все дуги ориентированы в определённом направлении.

8, Дайте определение связной сети. – Связная сеть – это такая сеть, у которой любые 2 узла связаны по крайней мере 1 путём.

9, что называется деревом в сетевом моделировании? – Деревом называется связная сеть содержащая подмножество узлов исходной сети и не имеющая циклов.

10, что называется остовным деревом в сетевом моделировании? – Остовное дерево – это дерево содержащее все узлы сети.

11, Опишите процедуру выполнения алгоритма построения минимального остовного дерева. – Алгоритм построения минимального остовного дерева предполагает соединение всех узлов сети с помощью путей наименьшей длинны. агр.png

12, В чем состоит задача поиска кратчайшего пути?- задача поиска кратчайшего пути состоит в определении в транспортной сети кратчайшего пути между заданным исходным пунктом и пунктом назначения.

13, Перечислите известные Вам алгоритмы решения задачи поиска кратчайшего пути. В чем их различия?

1,Алгоритм Дейкстры 2,Алгоритм Флойда

Первый разработан для поиска кратчайшего пути между заданным исходным узлом и любым другим узлом сети Второй более общий и позволяет одновременно найти минимальные пути между любыми двумя узлами сети

14, Временные и постоянные метки в алгоритме Дейкстры. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.

15, Из каких этапов состоит вычислительная схема алгоритма Дейкстры?

Этап 0: Исходному узлу присваивается постоянная метка (0;-). Полагаем I -1.

Этап 1: а) Вычисляются временные метки для всех узлов j которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку ф2.pngф1.pngф.png

полученную от другого узла K, и если тогда метка заменяется на ф1.pngф3.png

Б) Если все узлы имеют постоянные метки, процесс вычисления заканчивается. В противном случае выбирается метка с наименьшим значением расстояния U, среди всех временных меток. Полfгаем I=r и повторяем этап i.ф4.png

16, Опишите в общем виде задачу о максимальном потоке. Задача о максимальном потоке заключается в нахождении потока такого, что величина потока максимальна.

17, Опишите метод перебора разрезов.

18, В чем заключается алгоритм нахождения максимального потока? – Идея данного алгоритма заключается в поиске сквозных путей с положительными потоками от источника к стоку.

19. Опишите в общем виде задачу нахождения потока наименьшей стоимости. Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.математически.png

20, Опишите математически сетевую модель.

21. Что представляет собой сетевая модель? - Сетевая модель представляет собой план выполнения некоторого комплекса взаимосвязанных работ (операций), заданного в специфической форме сети, графическое изображение которой называется сетевым графиком. - 22, Что называется сетевым графиком (здесь же)

23, Дайте определение понятия «работы» как главного элемента сетевой модели. - Работа – протяженный во времени процесс, требующий затрат ресурсов

24, Дайте определение понятия «событие» как главного элемента сетевой модели. - Событие это момент завершения какого-либо процесса, отражающий отдельный этап выполнения проекта.

25, Что называется исходным событием? - Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ.

26, Что называется завершающим событием? - Завершающее событие не имеет последующих работ и событий.

27, В чем заключается упорядочение сетевого графика? - ^ Упорядочение сетевого графика заключается в таком расположении событий и работ, при котором для любой работы предшествующее ей событие расположено левее и имеет меньший номер по сравнению с завершающим эту работу событием.

^ 28, Дайте определение понятия «Путь». - Путь любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы

^ 29, Какой путь называют критическим. - Наиболее продолжительный полный путь в сетевом графике называется критическим

30, Перечислите параметры событий. - Ранний срок свершения события; Поздний срок свершения события; Резерв времени события.

31, Как определяется ранний (или ожидаемый) срок tp(i) свершения i-го события? - ранний (или ожидаемый) срок tp(i) свершения i-го события определяется продолжительностью максимального пути, предшествующего этому событию: , событие i имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий j, то ранний срок свершения события i удобно находить по формуле: .

32, Поздний (или предельный) срок tп(i) свершения i-го события. - поздний (или предельный) срок tП(i) свершения i-го события равен: ,

33, Как определяется резерв времени R(i) i-го события? - ^ Резерв времени R(i) i-го события определяется как разность между поздним и ранним сроками его свершения: R(i) =tП(i) -tp(i).

34, Перечислите основные параметры работ. - Продолжительность работы; Ранний срок начала работы; Ранний срок окончания работы; Поздний срок начала работы; Поздний срок окончания работы; Полный резерв времени работы; Частный резерв времени работы первого вида; свободный резерв времени работы; Независимый резерв времени работы.

35, Что показывает полный резерв времени Rп(i, j) работы (i, j)? - ^ Полный резерв времени RП(i, j) работы (i, j) показывает, насколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится.

36, Частный резерв времени первого вида Ri работы (i, j). - ^ Частный резерв времени первого вида ri работы (i, j) есть часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события.

^ 37, Частный резерв времени второго вида. - Частный резерв времени второго вида, или свободный резерв времени Rc работы (i, j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события.

^ 38, Независимый резерв времени Rн, работы (i, j). - Независимый резерв времени Rн, работы (i, j) — часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки.

39, Имеют ли работы, лежащие на критическом пути, резервы времени. - Работы, лежащие на критическом пути, так же как и критические события, резервов времени не имеют.

^ Целочисленное программирование

1, Перечислите основные шаги алгоритма целочисленного программирования.

Шаг 1: «Ослабление» пространства допустимых решений задачи целочисленного программирования путём замены любой двоичной переменной «У» непрерывным ограничением 0=
Шаг 2: Решение задачи ЛП и определение оптимального решения.

Шаг 3: Имея полученное оптимальное решение, добавляем специальные ограничения, которые итерационным путём изменяют пространство допустимих решений задачи ЛП таким образом, что бы в коенчном счёте получилось оптимальное решение, удовлетворяющее требованиям целочисленности.

2, Перечислите общие методы генерирования специальных ограничений. – 1) Метод ветвей и границ; 2) Метод отсекающих плоскостей.

3, Опишите в общем виде метод отсекающих плоскостей в целочисленном программировании. – данный метод путём добавления отсечений (отсекающих плоскостей) преобразует пространство допустимых решений в выпуклый многогранник, вершина которого, соответствующая оптимуму, является целочисленной и представляет решение исходной задачи.

4, Опишите в общем виде метод ветвей и границ в целочисленном программировании. –

5, В чем отличия методов целочисленного программирования касательно их применения? –

6, Какой фактор наиболее важен, влияющий на процесс вычислений? –

7, Сформулируйте в общем виде задачу коммивояжера. – в «классической» формулировке коммивояжер пытается определить кратчайший маршрут для одноразового посещения n городов.

8, Применение метода ветвей и границ для решения задачи коммивояжера –

9, Применение метода отсекающих плоскостей для решения задачи коммивояжера. –

^ Модели динамического программирования (ДП)

1, Какое оптимальное решение определяет динамическое программирование. – динамическое программирование определяет оптимальное решение n – мерной задачи путём её декомпозиции на n – этапов, каждый из которых представляет подзадачу относительно одной переменной.

2, Фундаментальный принцип динамического программирования. – оптимальность.

3, Рекурентная природа вычислений динамического программирования. – вычисление задачи ДП рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей.

4, Состояние системы на этапе i. – это информация, связывающая этапы между собой, при этом оптимальное решение для оставшихся этапов могут применятся без повторной проверки того, как были получены решения на предыдущих этапах.

5, Принцип оптимальности.- на каждом этапе оптимальная стратегия определяется не зависимо от стратегий, использованных на предыдущем этапе.

6, Приводят ли к одному и тому же решению рекурентные алгоритмы прямой и обратной прогонки? Ответ объясните. – да приводит)

7, Основные элементы моделей динамического программирования. – 1) определение этапов; 2) определение на каждом этапе вариантов решений (альтернатив); 3) определение состояний на каждом этапе.

8, В чем состоит суть задачи о загрузке? – задача о рациональной загрузке транспорта которое имеет ограничения по грузоподъёмности.

9, Рекурентное уравнение процедуры обратной прогонки для общей задачи загрузки судна грузоподъемностью W предметов (грузов) n наименований.херня.png

10, Пошаговая процедура определения рекуррентного уравнения. - херня1.png

11, Опишите суть задачи планирования рабочей силы. – регулирование численности рабочих в период реализации проекта.

12, Основные элементы модели динамического программирования (задача планирования рабочей силы). – 1)номер недели i; 2)количество робочих , работающих на протяжении I – той недели; 3) количество робочих на протяжении (I-1) – й недели (этапа)

13, Рекурентное уравнение динамического программирования в задаче планирования рабочей силы. - херня2.png

14, Опишите суть задачи замены оборудования.- задача замены оборудования сводится к определению оптимального срока эксплуатации механизма.

15, Основные элементы модели динамического программирования (задача замены оборудования).1) этап i представленин порядковым номером года; 2) вариантами решений для i – го года есть альтернативы: продолжить эксплуатацию или заменить механизм в начале i – го года; 3) состоянием на i – м этапе есть срок эксплуатации t (возраст) механизма к началу i – го года.

16, Рекурентное уравнение динамического программирования в задаче замены оборудования. - херня3.png

17, Опишите суть задачи инвестирования. – разработать стратегию инвестиций на следующие Н – лет.

18, Основные элементы модели динамического программирования (задача инвестирования). 1)порядковый номер года i; 2) вариантами решений на i м этапе (для i-го года) есть суммы i1 и i2 инвестиций в первый и второй банк; 3) состоянием на i-м этапе есть сумма денег на начало i – го года, которые могут быть инвестированы.

19, Сформулируйте целевую функцию в задаче инвестирования.

20, Рекурентное уравнение динамического программирования в задаче инвестирования. - херня4.png

21, В чем заключается проблема размерности в задачах динамического программирования.

Похожие:

Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЗадача №2
Больной 28 лет жалуется на неприятный запах изо рта. Зубы полностью санированы. Что может быть причиной жалоб больного и как его...
Может ли быть решена транспортная задача как обычная задача линейного программирования? icon6. задача о рюкзаке
Циклический алгоритм целочисленного программирования
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЛабораторная работа №5 Транспортная логистика Задача Определение идеи фрахтовой ставки
Допус­тим, имеется другое судно, которое отличается только расходом мазута, который у него заметно меньше и составляет ql = 30 т....
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconКнига “Лучший, каким Вы можете быть в mlm” это книга о Вас и вашем...
Знать, что Вы хотите от жизни — это Ваша задача. Показать вам, как Вы сможете всего этого достичь с помощью Сетевого маркетинга —...
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconOverview лист 1 лист 2 Задача 1 Задача 2 Задача 3 Задача 4 2ндфл см Sheet 1: лист 1

Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЗадача взрослых помочь ребенку как можно быстрее запомнить буквы...
Ребенок только начинает изучать буквы. Это очень не легкая задача. Естественно, что на первых порах ребенок может путать буквы, это...
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЗадача Аудиторская фирма не должна принимать данное предложение и...
Задача Может аудиторская фирма так делать. Она оказывает аудиторские услуги и сопутствующие аудиту услуги, в данном случае это консультации...
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЗадача 4
Задача Определите объем реализуемой продукции исходя из данных, приведенных ниже
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconОбщая задача нелинейного программирования. Условия Куна-Таккера
Рассмотрим следующую задачу поиска экстремума функции многих переменных при наличии ограничений
Может ли быть решена транспортная задача как обычная задача линейного программирования? iconЗадача 1
...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница