Опорное решение транспортной задачи

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

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

Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находится отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные – незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку , т.е. стоящая в i-й строке и j-м столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная , которой соответствует вектор-условие .

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

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

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 90⁰. Простейшие циклы изображены на рисунке 1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

* * * * * *

* * * *

* * * * * *

Рис 1.

Дата добавления: 2015-06-30; просмотров: 172; Нарушение авторских прав

Мы поможем в написании ваших работ!