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

Теорема 8.1. Если для некоторого опорного плана ТЗ существуют числа (потенциалы поставщиков) и числа (потенциалы потребителей), такие что (8.1) для (клетка заполнена) и (8.2) для (клетка пуста) , то план является оптимальным.

Для заполненных клеток составляется система, которая содержит n+m– 1 уравнение и n+m неизвестных. Поэтому полагается, что , а затем находятся остальные переменные.

Для свободных клеток определяются числа . Если , то условия теоремы выполнены, план оптимален. Если же , то план не оптимален, и его следует улучшить.

Проверим на оптимальность план, полученный по методу минимального элемента:

Для составим систему уравнений:

,

, Пусть , =0,

, = -4, =0,

, =-2, =1,

, =4.

.

Для подсчитаем значения выражений:

,

,

,

,

,

.

Так как получена положительная разность , то план не оптимален.

Дата добавления: 2014-01-13