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

Терема 1. Ранг системы ограничений ТЗ (1) равен m + n -1.

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

Любое допустимое решение ТЗ записываются в ту же таблицу, что и исходные данные. Клетки таблицы ТЗ, в которых находятся отличные от нуля или базисные нулевые перевозки, называются базисными клетками. В остальных клетках (свободные неизвестные) тоже будут стоять нулевые перевозки, но их записывать не будем.

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

Циклом называется такая последовательность клеток ТЗ, в которой две и только две соседние клетки расположены в одной строке или столбце.

Цикл изображают в таблице ТЗ в виде замкнутой ломаной линии.

Теорема 2. Пусть отмечены точками m + n клеток ТЗ, где m ³2, n ³2.Тогда всегда можно построить цикл из этих клеток.

Набор клеток, из которых нельзя построить цикл называется ациклическим.

Теорема 3. Для того чтобы допустимое решение было опорным, необходимо чтобы набор базисных клеток таблицы был ациклическим.

Вопросы для самоконтроля

1. Сформулируйте задачу в общем виде.

2. Укажите математическую модель транспортной задачи в общем виде?

3. Какая модель транспортной задачи называется открытой.

4. Какая модель транспортной задачи называется закрытой.

5. Какие клетки в транспортной задаче являются базисными, а какие свободными.

6. Что такое цикл? Какой цикл называется ациклическим?

Лекция 6 Методы решения транспортных задач с правильным балансом

1) Метод северо-западного угла

2) Переход от одного опорного решения к другому. Метод потенциалов

3) Пример решения транспортной задачи