Критерий оптимальности и критерий допустимости

Пусть наша матрица разделится на столбцы соотв базисным (1,...,m) и свободным переменным.

Умножим на

Если x₂ свободная переменная и в вершине=0, то

6. Метод искусственного базиса для нахождения вершины. Искусственные переменные и недопустимость множества решений злп. Метод искусственного базиса

Для решения задачи

(1)

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

(2)

Переменные – искусственные.

Специальные ограничения можно записать так:

, где единичный вектор-столбец.

Матрица специальных ограничений

уже содержит единичную матрицу порядка m, столбцы которой образуют единичный базис этой матрицы. Исходное базисное решение вспомогательной задачи: За конечное число итераций получается один из ответов: либо min u=0, либо min u>0. Если в последней симплексной таблице задачи минимизации функции u на пересечении строки u и столбцов, соответствующих свободным переменным, отсутствуют положительные числа, то первом случае исходная задача допустима, и из оптимального базисного решения вспомогательной задачи сразу получается исходное допустимое решение основной задачи. Во втором случае основная задача несовместна.

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

От противного. Пусть основная задача ЛП (1) допустима и пусть вектор -ее допустимое решение, тогда вектор есть допустимое решение вспомогательной задачи ЛП (2). На этом допустимом решении значение целевой функции u=0, это противоречит тому, что минимальное значение u строго положительно (min u>0). Значит, основная задача ЛП недопустима.

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

Двойственность в линейном программировании — принцип, заключающийся в том, что для каждой ЗЛП можно сформулировать двойственную задачу. Исходная и двойственная к ней задача образуют пару двойственных задач.

Прямая задача:

Ей соответствует двойственная задача:

В матричном виде пара двойственных задач записывается следующим образом:

Прямая задача:

Двойственная задача:

Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи.

1. Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот.

2. Коэффициенты целевой функции прямой задачи c₁,...,c_n становятся свободными членами ограничений двойственной задачи.

3. Свободные члены ограничений прямой задачи b₁,...,b_m становятся коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи получается путем транспортирования матрицы ограничений прямой задачи.

5. Знаки неравенств в ограничениях изменяются на противоположные.

6. Число ограничений прямой задачи равно числу переменных двойственной задачи, и наоборот.

7. Если дана прямая задача, где некоторые ограничения записаны как равенства, то на соответствующую переменную в двойственной задаче пропадает ограничение

8. Три леммы о двойственных задачах. Первая теорема двойственности

Лемма 1

Если некоторый план исходной задачи, а – произвольный план двойственной задачи, то

Рассмотрим задачу в каноническом виде

Лемма 2.

Если некоторый план исходной задачи, а – произвольный план двойственной задачи и значения целевых функций совпадают, то эти решения оптимальны.

Лемма 3.

Если у 1 из пары двойственных задач ЛФ неогранич., то у другой задачи множество планов пусто.

Докажем, что у II задачи множество допустимых решений пусто при неогранич. ЛФ1.

Предположим обратное: у II задачи есть допустимое решение, но по лемме 1 при этом:

Значит предположение неверно и множество решений пусто. Т.о. наличие планов у обеих задач обеспечивает их разрешимость.