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

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. Очевидно, что найденный план неоптимален и целесообразно перейти к другому опорному плану, в котором на соответствующем маршруте появится ненулевая пе-