Решение транспортной задачи методом Данцига-Вулфа

Применим метод декомпозиции к Т-задаче: (33)

(34) (35) " Х_ij³ 0. (36)

Использование этого метода целесообразно, если m < < n или m> > n. Оба варианта решаются идентично. Они отличаются только распределением условий между основной и вспомогательной задачами. Рассмотрим случай, когда m < < n. Тогда основная задача формируется по условиям пунктов отправления. Следовательно, множество D ₀ описывается ограничениями (34), а D₁ – условиями (35) и (36). Множество D₁ представляет собой выпуклый многогранник (ограниченность вытекает из условий). Поэтому любую точку в D₁ можно представить в виде линейной комбинации его вершин: (37) S Z_v =1; (38) " Z_v ³ 0, (39)

где X^v_ij – координаты v -ой вершины. Подставим (37) в (33) и (34):

. Введем обозначения: (40) (41)

Тогда основная задача запишется в виде (42)

(43) (44) " Z_v ³ 0. (45)

Суммируя (43) и используя подстановки (41) и (35), получаем в левой части

в правой части Получаем откуда для сбалансированной задачи следует Поэтому при решении основной задачи условие (44) из модели исключается.

Для определения статуса текущего базисного решения основной задачи необходимы относительные оценки. Для построения вспомогательной задачи сделаем ряд преобразований: D _v = p^TP _v - s_v =

Так как основная задача решается на минимум, то оптимальному статусу соответствуют неположительные оценки. Поэтому нужно искать максимальную оценку. Если она окажется не больше нуля, то все оценки неположительны и признак оптимальности выполнился. В противном случае необходимо продолжить решение основной задачи.

Задача ставится так:

Вместо поиска максимума на дискретном множестве вершин перейдем к эквивалентной задаче поиска на всем непрерывном множестве D₁:

(46) (47) " X _ij ³ 0.(48)

Эта задача является вспомогательной. В оптимальном решении этой задачи

Вспомогательная задача включает одну группу условий (47). Каждая переменная входит в такие условия только один раз. Поэтому равенства (47) оказываются независимыми и вспомогательная задача распадается на n простейших независимых задач, каждая из которых имеет всего одно условие: (49)

(50) " X _ij ³ 0.(51)

Критерий вспомогательной задачи равен сумме критериев этих задач: (52)

Оптимальное решение задачи (49)-(51), как линейной, находится на границе. При этом только одна переменная не равна нулю (базис имеет размерность 1). Поэтому ее решение состоит в определении максимального коэффициета в критерии (49). Пусть максимум достигается на индексе i*, то есть

Тогда имеем следующее решение задачи (49)-(51): X^v_i*j = b_j, X^v_ij =0, " i, i ¹ i*, (53)

и максимальная оценка определится как .

Если L ^* _всп £ 0, то положительных оценок нет и текущее решение основной задачи будет оптимальным.

При L^*_всп > 0 начинается новая итерация:

1. пo (41) и (40) находим Р _v и s_v;

2. вычисляем элементы направляющего столбца как коэффициенты разложения вектора Р _v по текущему базису: a _v = P ^-1_B P _v;

3. проводим симплекс-преобразование основной задачи, в результате которого получаем новое решение и новую обратную матрицу;

4. вычисляем p ^T= s ^T_B P ^-1_B;

5. решаем вспомогательную задачу: вычисляем разности , находим оптимальные решения n задач (49)-(51) и максимальную оценку основной задачи.

Из рассмотренной вычислительной схемы следует, что эффективность метода тем выше, чем сильнее неравенство m < < n или m> > n.