Признак оптимальности опорного плана

Пусть дана задача:

(10.9)

(10.10)

(10.11)

Пусть известен некоторый опорный план, т.е. существует с базисом . Вычислим значения линейной формы и ограничений в точке

, (10.12)

Умножим равенство слева на и получим

(10.13)

Условие (10.10) можно записать

,

т.е.

Умножая последнее равенство слева на получим

(10.14)

Разложим вектор по базису и полученное выражение умножим слева на

Перепишем (10.14) с учетом (10.13)

.

(10.15)

Подсчитаем значение линейной формы в точке :

или

,

где

(10.16)

- оценки векторов относительно базиса .

Теорема 10.1. (необходимое условие оптимальности опорного плана). Для того, чтобы опорный план ЗЛП был оптимальным необходимо, чтобы оценки всех векторов условий относительно базиса этого опорного плана были неотрицательны ().

Д о к а з а т е л ь с т в о. Пусть - оптимальный опорный план с базисом . Выберем вектор , тогда

,

т.е. . Оценка вектора относительно базиса

Таким образом, оценка базисного вектора относительно того же базиса равна нулю.

Теперь рассмотрим вектор () не принадлежащий базису . Допустим, что оценка вектора отрицательна. Перейдем к новому опорному плану так как было проделано выше при рассмотрении процедуры однократного замещения.

Вычислим значение линейной формы в точке :

С учетом того, что и

,

чего быть не может.

Следствие. Если не является оптимальным, то существует оценка , и тогда переход от этого неоптимального плана к новому опорному плану следует выполнять, вводя в базис вектор , так как в этом случае переход выполняется с увеличением значения линейной формы: .

Применение признака оптимальности опорного плана заключается, таким образом, в вычислении оценок всех небазисных векторов . Двум различным способам вычисления соответствует два вычислительных алгоритма симплекс - метода.

Первый способ состоит в вычислении коэффициентов разложения векторов по базису рассматриваемого опорного плана по формулам

и, затем, в вычислении оценок

Второй способ состоит в вычислении вектора-строки

и последующем вычислении оценок , .

В обоих способах приходится обращать матрицу , что весьма трудоемко. Вместе с тем, особенности перехода от одного опорного плана к соседнему позволяют получить простые рекуррентные формулы для пересчета параметров последовательных итераций .

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