Начальный опорный план - в левом нижнем углу клеток

2. Проверка опорного плана на оптимальность.

Проверка на оптимальность осуществляется с помощью потенциалов во вновь составленной таблице.

Постр.						U
Пост.
	7	4 +
	6					-1
						-2
V

ПРАВИЛО 1: для всех занятых клеток должно быть:

u _i + v _j = c _{i j} (1)

(сумма потенциалов равна стоимости)

ПРАВИЛО 2: для всех свободных клеток должно быть:

u _i + v _j ≤ c _{i j} (2)

Условие оптимальности нарушено в клетке (1, 2)!

Итак, полученный опорный план не оптимален!

Экономический смысл потенциалов:

Потенциалы u и v можно рассматривать как платежи поставщиков и потребителей некоторому третьему лицу- назовем его ‘ перевозчиком”.

Формула (2) означает, что при оптимальном плане перевозок стороны не хотят переплачивать сверх установленного тарифа.

С другой стороны, перевозчик, установив оптимальный план, хочет получить максимум, т.е. весь тариф полностью (формула (1)).

3. Переход к новому опорному плану, лучшему, чем предыдущему.

Находим клетку, в которой условие оптимальности нарушено в наибольшей степени. В нашем случае это клетка (1,2). Далее

а) помечаем эту клетку знаком + и строим цикл, начинающийся и заканчивающийся в этой же клетке.

Дата добавления: 2014-12-27