- •Этапы решения
- •Транспортная задача. Постановка задачи.
- •Опорный план.
- •Методы поиска опорного плана. Метод северо-западного угла.
- •Методы поиска опорного плана. Метод потенциалов.
- •Методы поиска опорного плана. Метод минимального тарифа (элемента).
- •Методы поиска опорного плана. Метод Фогеля.
- •Критерий оптимальности транспортной задачи (Условие оптимальности опорного плана?).
- •Алгоритм перехода к новому опорному плану (алгоритм перехода к нехудшему опорному плану?).
- •Транспортная задача с ограничениями на пропускную способность (решение транспортной задачи с ограничениями?).
- •Метод фогеля
- •Метод ближайшего соседа
- •Вопрос 18.
Транспортная задача. Постановка задачи.
Классическая транспортная задача ЛП формулируется следующим образом:
Имеется m пунктов производства (поставщиков) и n пунктов
потребления (потребителей) однородного продукта. Заданы величины:
- объем производства (запас) i-го поставщика, i=1, m;
- объем потребления (спрос) j-го потребителя, i=1, n;
- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.
Требуется составить такой план перевозок, при котором спрос
всех потребителей был бы выполнен и при этом общая стоимость всех
перевозок была бы минимальна.
Математическая модель транспортной задачи имеет вид
Транспортная задача, в которой суммарные запасы и суммарные потребности
совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой модели.
В случае, когда суммарные запасы превышают суммарные
потребности, т.е. вводится фиктивный n+1 потребитель, потребности которого
В случае, когда суммарные потребности превышают суммарные
запасы, т.е. , вводится фиктивный m+1 поставщик, запасы которого
Стоимость перевозки единицы груза до фиктивного потребителя и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к закрытой модели.
Опорный план.
Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:
Базисными клетками транспортной таблицы являются клетки с отличными от нуля положительными перевозками, остальные клетки - свободные. Базисные клетки образуют опорный план транспортной задачи, если выполняются два условия:
1) сумма перевозок в каждой строке равна запасу в данной
строке;
2) сумма перевозок в каждом столбце равна соответствующему
столбцу спросу
Опорный план транспортной задачи содержит не более n+m-1
отличных от нуля перевозок
Опорный план называется вырожденным, если число ненулевых перевозок
меньше и n+m-1.
Опорный план - невырожденный, если число
ненулевых перевозок равно n+m-1.
Методы поиска опорного плана. Метод северо-западного угла.
Рассмотрим "северо-западный угол" незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю.
Возможны три случая.
Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его запас равен нулю, поэтому
При этом неудовлетворенный спрос в первом пункте потребления равен
то есть спрос первого потребителя полностью удовлетворен и поэтому
а остаток продукта в первом пункте производства равен
из рассмотрения можно исключить и поставщика, и потребителя. Однако при этом план получается вырожденным, поэтому условно считается, что выбывает только поставщик,
а спрос потребителя остается неудовлетворенным и равным нулю.
После этого рассматриваем северо-западный угол оставшейся незаполненной части таблицы и повторяем те же действия. В результате, через n+m-1 шагов получим опорный план.
Пример
Найти опорный план транспортной задачи
В таблице, обведенной двойной чертой, указаны объемы перевозок, полученные методом северо-западного угла. При этом небазисные нулевые перевозки не проставлены. Справа и внизу таблицы содержатся последовательно меняющиеся объемы возможных запасов и спросов. В число базисных перевозок вошла нулевая перевозка , так как на предыдущем шаге и по п.3 метода считается выбывшим только поставщик, а неудовлетворенный спрос второго потребителя равен