Файл: М.А. Тынкевич Решение транспортной задачи методом Данцига.pdf

6

ревозка Xij= Θ >0. Выбор максимально возможного значения Θ определяется естественным требованием неотрицательности компонент нового плана.

В приведенном примере обнаружилось ∆ 34=2>0. В новом плане бе-

рем X34=Θ >0 и ищем т.н. минимизирующую цепочку по базису, которая обеспечивает сохранение баланса по строкам и столбцам плана:

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

Θ=2 (при этом выборе сохраняется неотрицательность компонент плана

и одна из бывших базисных компонент X32 уходит из базиса). Очевидно, что значение целевой функции (транспортные затраты) при переходе к

плану X1 уменьшается на Θ ∆ 34=2 2=4.

Найденный план опять-таки проверяем на оптимальность. Строим в соответствии с базисными его компонентами систему уравнений, решаем

2.4. Замечания

1. Если для найденного оптимального плана обнаружилась неполо-

жительность всех ∆ ij и при этом присутствует нулевое значение ∆ ij для какой-то небазисной составляющей, то можно утверждать не только опти-

мальность этого плана, но и существование других оптимальных пла-

нов (переход к плану, где соответствующая компонента равна Θ , не сопровождается изменением значения целевой функции) .

2.При решении задач транспортного типа на максимум выбор начального опорного плана производится, в частности, по правилу не минимального, а максимального элемента матрицы.

3.При решении задач транспортного типа на максимум признак оп-

тимальности определяется условиями сопряженной задачи ui+vj≥ Cij и требованием неотрицательности всех ∆ ij.

7

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

2.5. Пример решения задачи методом Данцига

Рассмотрим еще один пример.

Пусть требуется решить задачу минимизации транспортных затрат при следующих данных:

того) потребителя и получаем видоизмененные условия задачи:

Ищем начальный опорный план методом минимального элемента матрицы (на шестой столбец можно и не обращать внимания):

min Cij=C15=С22=С34=1 X15=min(20,5)=5, X25=X35=0; без учета пятого столбца - min Cij= С22=С34=1 X22=min(10,10)=10, X12=X32=0 и X21=X23=X24=X26=0; без учета к тому же второго столбца и второй стро-

ки имеем: min Cij=С34=1 X22=min(10,5)=5, X14=0 ; очередное минимальное значение стоимости совпадает с С33=2 , откуда следует X33=min(10-5,10)=5, X31=X36=0 ; теперь уже однозначно определяются оставшиеся элементы первой строки:

Полученный план является вырожденным (число положительных

компонент равно 7 < m+n-1=3+6-1=8). Можно прибегнуть к ε -методу, рассмотренному выше, или попытаться для включения в базис подобрать нулевую перевозку так, чтобы не возникало замкнутой цепочки по базису и по возможности ее стоимость была как можно меньшей. Для данного случая таковыми являются X21 или X12 (принципиально недопустимы X36, X35, X31, X14); включаем в число базисных X12=0:

Отсюда видно, что найденный план X1 оптимален, но не единствен-

ный, так как для небазисной компоненты обнаруживается ∆ 23=0. Второй оптимальный план получается в виде:

(можно предложить здесь и другой оптимальный план, отличающийся нулевой базисной перевозкой X13=0).

3. Задачи

Найти решение транспортных задач минимизации и максимизации