Транспортной задачи

Необходимое и достаточное условия разрешимости

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

Прежде чем перейти к понятию опорного решения остановимся на основных теоремах транспортной задачи.

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

=.

Свойство системы ограничений транспортной задачи: ранг системы векторов ― условий транспортной задачи равен N = т + п — 1.

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

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

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

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

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

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

Рис. 6.1.

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

Следствие. Допустимое решение транспортной задачи Х= (х_ij), i = 1, 2,..., m, j= 1, 2,..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Дата добавления: 2014-01-04