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

Терема 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) Пример решения транспортной задачи

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

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

Пример. Для транспортной задачи составить первоначальный опорный план методом северо-западного угла.

ПН ПО	1		2		3			4		Запасы
А		1		3			4		2	100
	100
Б		1		5		8			3	250
	50		200
В		2		3		5			7	200
			0		100			100
Потреб- ности	150		200		100			100		550

X_опор.=(100, 0, 0, 0, 50, 200, 0, 0, 0, 0, 100, 100) или X_опор.=

Теорема 4. Решение ТЗ, построенное методом северо-западного угла, является опорным.