Условия оптимальности

Предположим, что задача линейного программирования (1) - (3) обладает планами и каждый ее опорный план невырожден. В этом случае для опорного плана (5) имеем (12) (13), где - это значение линейной формы, соответствующее плану . Разложение любого вектора по векторам базиса - единственно.

(14)

(15)

Теорема (для задачи на min): Если для некоторого вектора выполняются условия , то план не является оптимальным и можно построить такой план X: .

Доказательство:

Умножим равенство (14) на и вычтем из равенства (12), получаем

.

Умножим равенство (15) на и вычтем из равенства (13), получаем

(16).

Следствие: Если для некоторого плана разложение всех векторов в данном базисе, удовлетворяющих условию (17), то план является оптимальным. Неравенство (17) это условие оптимальности задачи на минимум, а величины - оценки плана.

Теорема (для задачи на max): Если для некоторого вектора выполняются условия , то план не является оптимальным и можно построить такой план X: .

Следствие: Если для некоторого плана разложение всех векторов в данном базисе, удовлетворяющих условию (18), то план является оптимальным. Неравенство (18) это условие оптимальности задачи на минимум, а величины - оценки плана.

- формула Жордана-Гаусса.

Поиск по сайту: