2015-07-21
490
Классическая транспортная задача ЛП формулируется следующим образом.
Имеется m пунктов производства (поставщиков) и n пунктов
потребления (потребителей) однородного продукта. Заданы величины:
- объем производства (запас) i-го поставщика, i=1, m;
- объем потребления (спрос) j-го потребителя, i=1, n;
- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.
Требуется составить такой план перевозок, при котором спрос
всех потребителей был бы выполнен и при этом общая стоимость всех
перевозок была бы минимальна.
Математическая модель транспортной задачи имеет вид
Транспортная задача, в которой суммарные запасы 
и суммарные потребности 
совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой.
В случае, когда суммарные запасы превышают суммарные потребности, т.е.
вводится фиктивный n+1 потребитель, потребности которого 
В случае, когда суммарные потребности превышают суммарные
|
|
|
запасы, т.е. 
, вводится фиктивный m+1 поставщик, запасы которого 
Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика
полагают равными нулю, так как груз в обоих случаях не перевозится.
Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к закрытой модели.
Билет 29
Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).
Общий принцип определения оптимального плана транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.
Билет 30
| Алгоритм решения задачи о назначениях | |
| Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1. Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов: 1 этап: 1 Формализация проблемы в виде транспортной таблицы 2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки 3 Повторить ту же процедуру для столбцов Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью. Оптимальное значение целевой функции в этом случае равно нулю. 2 этап: 1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки. 2 Зачеркнуть оставшиеся нулевые значения данного столбца 3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным Если окажется, что имеется несколько нулей, которым не соответствуют назначения, и которые остались незачеркнутыми, необходимо: 4 Найти столбец, содержащий только одно нулевое значение, в его клетку помещается один элемент. 5 Зачеркнуть оставшиеся нули в данной строке 6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6 Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3. 3 этап: (Если решение является недопустимым) 1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице 2 Найти наименьший из элементов, через которые не проходит ни одна прямая 3 Вычесть его из всех элементов, через которые не проходят прямые 4 Прибавить его ко всем элементам, лежащим на пересечении прямых 5 Элементы, через которые проходит только одна прямая, оставить неизменными В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново. Пример решения задачи Компания имеет 4 сбытовых базы и 4 заказа, которые необходимо доставить потребителям. Складские помещения каждой из баз достаточны для размещения любого из этих заказов. |
|
|
|
