![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей:
=
.
Свойство системы ограничений транспортной задачи: ранг системы векторов ― условий транспортной задачи равен N = т + п — 1.
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы-условия, соответствующие положительным координатам, линейно независимы.
Ввиду того, что ранг системы векторов ― условий транспортной задачи равен т+п— 1, опорное решение не может иметь отличных от нуля координат более т+п —1. Число отличных от нуля координат невырожденного опорного решения равно т+п— 1, а для вырожденного опорного решения меньше т+п —1.
Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку хij, т.е. стоящая в i -й строке и j -м столбце, имеет номер (i, j). Каждой клетке с номером (i, j)соответствует переменная хij, которой соответствует вектор-условие Аij.
Для того чтобы избежать трудоемких вычислений при проверке линейной независимости векторов-условий, соответствующих положительным координатам допустимого решения, вводят понятие цикла. Циклы также используются для перехода от одного опорного решения к другому.
Циклом называется такая последовательность клеток таблицы транспортной задачи (i 1, j 1), (i 1, j 2), (i 2, j 2), …, (iк, j 1), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.
Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 90°. Простейшие циклы изображены на рис. 6.1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.
![]() |
Теорема (о взаимосвязи линейной зависимости векторов ― условий и возможности образования цикла).Для того чтобы система векторов ― условий транспортной задачи была линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно выделить часть, которая образует цикл.
Следствие. Допустимое решение транспортной задачи Х= (хij), i = 1, 2,..., m, j= 1, 2,..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.
Дата публикования: 2015-11-01; Прочитано: 321 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!