Транспортная задача линейного программирования

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


Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы-условия, соответствующие положительным координатам, линейно независимы.
Ввиду того, что ранг системы векторов условий транспортной задачи равен k + n- 1, опорное решение не может иметь отличных от нуля координат более k + n- 1. Число отличных от нуля координатневырожденного опорного решения равно k+ n- 1, а для вырожденного опорного решения меньше k + n- 1.
Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку хij т.е. стоящая в i-й строке и j-м столбце, имеет номер (i, j). Каждой клетке с номером (i, j)соответствует переменная хij, которой соответствует вектор-условиеAij.
Для того чтобы избежать трудоемких вычислений при проверке линейной независимости векторов-условий, соответствующих положительным координатам допустимого решения, вводят понятие цикла. Циклы также используются для перехода от одного опорного решения к другому.
Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), …,(ik,j 1 ), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.
Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена; ломаной линии на 90°. Простейшие циклы изображены на рисунке, где звездочкой отмечены клетки таблицы, включенные в состав цикла.
□ Теорема (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла). Для того чтобы система векторов-условий транспортной задачи была линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл.
Доказательство . Необходимость. Пусть система, состоящая из n векторов

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

Пусть λ1 ≠0. Вектор. имеет две равные единице координаты с номерами i1, и k+j1, остальные координаты равны нулю. В равенство (6.10) должен также входить вектор, у которого одна из этих координат равна единице и который следует умножить на коэффициент 1 чтобы обеспечить равенство нулю этой координаты в линейной комбинации векторов. Пусть таким вектором будет вектор ,. Однако он имеет, кроме того, координату с номером k+j2, равную единице. Следовательно, в равенство (6.10) должен также входить вектор с такой же единичной координатой и т.д.
В выбранной подобным образом последовательности векторов должен найтись вектор  у которого второй индекс совпадает со вторым индексом первого вектора. Данной последовательности векторов соответствует совокупность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2),…,(i k ,j1), которая образует цикл.
Достаточность. Пусть из соответствующих векторам А ij клеток (i, j) выбрана последовательность клеток, образующих цикл (i1,j1), (i1,j2), (i2,j2),…, (i k ,j1). Нетрудно видеть, что

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

Метод вычеркивания


Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.
Пусть допустимое решение транспортной задачи, которое имеет k + n - 1 отличную от нуля координату, записано в таблицу. Чтобы данное решение было опорным, векторы-условия, соответствующие положительным координатам, должны быть линейно независимыми. Для этого занятые решением клетки таблицы должны быть расположены так, чтобы из них нельзя было образовать цикл.
Строка или столбец таблицы с одной занятой клеткой не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждой строке или в столбце. Следовательно, можно вычеркнуть сначала либо все строки таблицы, содержащие по одной занятой клетке, либо все столбцы, содержащие по одной занятой клетке, далее, вернуться к столбцам (строкам) и продолжить их вычеркивание. Если в результате вычеркиваний все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов-условий линейно независима, а решение является опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов-условий линейно зависима, а решение не является опорным.
Ниже приведены примеры «вычеркиваемого» (опорного) и «невычеркиваемого» (неопорного) решений;
загрузка...