18. Составление опорного допустимого плана перевозок

Для определения опорного плана существует несколько методов: метод северо-западного угла (диагональный метод), метод наименьшей стоимости(минимального элемента), метод двойного предпочтения и метод аппроксимации Фогеля.

Метод минимальной стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. 

Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.5). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке A₁ , B₄ ) так какA₁ = b₄, 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A₂ , B₁ и в клетке A₃ , B₅. Заполняем любую из них, например A₂ , B₁. Имеем 200 < 250, следовательно, записываем в нее 200 и исключаем из рассмотрения столбец B₁. В клетку A₃ , B₅ записываем 200 ед. и исключаем из рассмотрения строку A₃ . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен план  X = (X₁₄ = 100; X₂₁ = 200; X₂₂ = 50; X₃₅= 200, X₄₂ = 150; X₄₃ = 100; X₄₅ = 50),  остальные значения переменных равны нулю.

Таблица 2.5

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость:  Z = 100*1+200*2+50*7+200*2+150*8+100*12+50*13= 4300 (ед)  Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

19. Критерий оптимальности решения транспортной задачи

План транспортной задачи является оптимальным, если для всех свободных клеток таблицы перевозок значение критерия оптимальности d_ij<=0. Если для всех свободных клеток таблицы перевозок критерий оптимальности d_ij<0, то этот план перевозок является единственным. Если для некоторых свободных клеток таблицы перевозок критерий оптимальности d_ij=0, то этот оптимальный план перевозок не является единственным. Наконец, если имеются свободные клетки, для которых критерий оптимальности d_ij>0, то полученный план перевозок не является оптимальным.

Если u_i и v_j удовлетворяют условиям u_i + v_j = c_ij для занятых клеток и все оценки свободных клеток D_ij <0, то найденное решение оптимально.

20. Нахождение оптимального решения с помощью циклических перевозок

Циклы также используются для перехода от одного опорного решения к другому. 

Циклом называется такая последовательность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂), …,(i_k,j ₁ ), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце. 

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена; ломаной линии на 90°. Простейшие циклы изображены на рисунке, где звездочкой отмечены клетки таблицы, включенные в состав цикла.  □ Теорема (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла). Для того чтобы система векторов-условий транспортной задачи была линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл.  Доказательство . Необходимость. Пусть система, состоящая из n векторов

линейно зависима. Тогда существует такой ненулевой набор чисел  , что справедливо равенство

 

Пусть λ₁ ≠0. Вектор . имеет две равные единице координаты с номерами i₁, и k+j₁, остальные координаты равны нулю. В равенство (6.10) должен также входить вектор, у которого одна из этих координат равна единице и который следует умножить на коэффициент -λ₁ чтобы обеспечить равенство нулю этой координаты в линейной комбинации векторов. Пусть таким вектором будет вектор  ,. Однако он имеет, кроме того, координату с номером k+j₂, равную единице. Следовательно, в равенство (6.10) должен также входить вектор с такой же единичной координатой и т.д. 

В выбранной подобным образом последовательности векторов должен найтись вектор   у которого второй индекс совпадает со вторым индексом первого вектора.

Данной последовательности векторов соответствует совокупность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂),…,(i _k ,j₁), которая образует цикл.  Достаточность. Пусть из соответствующих векторам А _ij клеток (i, j) выбрана последовательность клеток, образующих цикл (i₁,j₁), (i₁,j₂), (i₂,j₂),…, (i _k ,j₁). Нетрудно видеть, что ,  

Отсюда следует линейная зависимость рассматриваемой системы торов. Теорема доказана полностью. ■   Следствие. Допустимое решение транспортной задачи X=(x_ij),i= 1,2, ..., k ;     j= 1, 2, ..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.