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

2

и полагаем Ci,n+1=0 при всех i (естественно, мы не будем ничего ему возить). При превышении спроса над предложением аналогично вводим

“фиктивного” m+1-го поставщика объема

2. Метод Д. Данцига

Рассматриваемый метод представляет компактную форму симплексной процедуры, избавляющей от необходимости оперировать с матрицами

размерности m+n на mn. Здесь предварительно обеспечивается закрытость модели (при необходимости вводится фиктивный поставщик или потребитель), выбирается начальный опорный план, проверяется на оптимальность и при отсутствии таковой осуществляется переход к другому опорному плану, более близкому к оптимальному.

2.1. Выбор начального опорного плана

Заметим, что всякий опорный план транспортной задачи может содержать не более m+n-1 положительных компонент [1]. Опорные планы, в которых положительных составляющих меньше m+n-1, называются вы-

рожденными.

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

Возьмем для примера задачу с тремя пунктами производства соответственно 5 , 8 и 7 единиц продукта и четырьмя потребителями c одинаковым спросом, равным 5 (нетрудно убедиться в закрытости модели и отсутствии необходимости ввода фиктивных поставщиков и потребителей).

Пусть затраты определяются матрицей:

3

2.1.1. Метод “северо-западного угла”

Начинаем с “северо-западного угла”, т.е. с клетки (1,1), и берем X11=min(a1,b1)=min(5,5)=5 (максимально возможная перевозка при соответствующем предложении и спросе).

X22=min(a2,b2)=min(8,5)=5. Очевидно,

что тогда X32=0. Затем отыскиваем X23=min(a2-X22,b3)=min(8-5,5)=3 и X24=0. Так как осталась нерассмотренной лишь одна строка компонент плана, то порядок выбора не имеет значения и получаем значения X33 и

X34.

Затраты на реализацию этого плана поставок равны

4 5+3 5+6 3+4 2+5 5=86.

2.1.2. Метод минимального элемента матрицы стоимостей

Здесь порядок выбора определяется правилом: ставить максимально возможную перевозку на самый “дешевый” маршрут.

Здесь минимальный элемент матрицы С равен С24=2. Соответст-

венно берем X24=min(a2,b4)=min(8,5)=5 и X14=X34 =0.

Минимальный элемент матрицы стоимостей (без четвертого столб-

находим значения X32=2 и X33=5, обнаруживая затраты для этого плана,

равные 4 5+3 3+2 5+8 2+4 5=75.

Однако нельзя утверждать, что этот метод всегда лучше метода се- веро-западного угла.

2.1.3. Проблема вырожденности и ее решение

Обратите внимание на то, что число положительных компонент в обоих планах равно 5 <m+n-1=3+4-1=6, т.е. оба плана вырожденные. Последующая проверка плана на оптимальность требует построения и

4

решения m+n-1 уравнений, соответствующих базисным компонентам плана. В случае же вырожденных планов трудно отличить нулевую базисную перевозку от нулевой небазисной.

Для задач большой размерности (m,n>20 30) и при компьютерной

реализации можно воспользоваться ε -приемом (ε > 0 сравнительно малое число) : перед поиском начального опорного плана увеличить все значе-

ния ai на ε и какое-нибудь из значений bj на mε .

Например, при поиске по минимальному элементу матрицы полу-

X21=X23=0;

X11=min(5+ε ,5+3ε )=5+ε , X12=X13=0 и затем X31=(5+3ε )-(5+ε )=2ε ,

X31 = 2-ε , X33=5.

Таким образом приходим к выводу, что к числу базисных следует отнести нулевую составляющую плана X31.

Для задач небольшой размерности, решаемых вручную, можно и не прибегать к ε -приему, а просто включать в число базисных нулевые пере-

2.2. Проверка плана на оптимальность

Для рассматриваемой классической транспортной задачи можно запи-

5

Из второй теоремы двойственности известно, что в случае оптималь-

ных планов в каждой паре двойственных условий {Xij≥ 0, ui+vj≤ Cij} условию, выполняемому строгим неравенством, соответствует условие, выполняемое как строгое равенство.

Соответственно возникает идея для проверки найденного плана X0 на оптимальность: m+n-1 его базисным перевозкам сопоставить требования ui+vj=Cij, получая тем самым систему m+n-1 уравнений с m+n неизвестными, которую можно решить с точностью до константы. Если при найденных значениях двойственных переменных условия ui+vj≤ Cij вы-

полняются и для небазисных Xij=0 (все значения ∆ ij= ui+vj-Cij≤ 0), то найденный план оптимален. В противном случае отыскивается другой опорный план, более близкий к оптимальному.

Базисным перевозкам сопоставляем систему уравнений:

u1+v1=4 , u1+v2=5 , u2+v2=3, u2+v4=2 , u3+v2=8 , u3+v3=4,

которую решаем, приняв u1=0, с последующим вычислением остальных сумм двойственных переменных.

Построение этой системы и ее решение реализуем в достаточно удобной табличной форме:

2.3. Переход к другому опорному плану

Как известно из теоретического обоснования симплексной процедуры [1], переход к новому опорному плану X(Θ ) сопровождается изменением значения целевой функции

L(X(Θ ))=L(X0) - Θ ∆ ij .

Предположим, что нашлось некоторое ∆ ij >0. Очевидно, что найденный план неоптимален и целесообразно перейти к другому опорному плану, в котором на соответствующем маршруте появится ненулевая пе-

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. Задачи

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