Пример применения признака оптимальности в развернутой форме

Пример применения признака оптимальности в развернутой форме

Признак оптимальности в развернутой форме

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

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

Для оптимальности допустимого вектора х=( х₁,х₂, …х_n,) в задаче 1 достаточно существования допустимого вектора y=(y₁,y₂,…..y_n) в задаче 1*, удовлетворяющего условию

m(х)= n(у)(16)

Тогда допустимый вектор y=(y₁,y₂,…..y_n) также является оптимальным в задаче 1*.

Пусть вектор х допустимый и существует допустимый вектор у такой, что справедливо (16). Покажем, вектор х оптимальный.

Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m(х′)≤ n(у) =m(х)и m(х′)≤m(х). Отсюда следует что х – оптимальный вектор.

Покажем теперь, что вектор у также является оптимальным.

Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′ . Для этой пары допустимых векторов справедливо лемма 1, т. е. n( у′)≥m(х)= n(у) и n(у)≤ n( у′). Отсюда следует что у – оптимальный вектор.▄

Для оптимальности допустимого вектора х=(х₁,х₂…,х_n,) в задаче 1 достаточно существование m-мерного вектора у=(у₁,у₂,у₃,…,у_m), удовлетворяющего условиям:

а) у_i і 0, iОI₂

б) еa_ijy_i + c_j = 0, jОJ_1,

iОI

в) еa_ijy_i + c_j, £ 0, jОJ_2,

iОI

г) еa_ijy_i + c_j, = 0, если х_j >0 для jОJ_2,

iОI

д) у_i = 0, если еa_ijx_j + b_i >0, iОI₂ ,

^jОJ

тогда вектор у является оптимальным в задаче 1*.

Как этим признаком пользоваться?

Предположим, что мы имеем допустимый вектор х, т.е. х_j ≥0 и такие, что , .

Тогда попытаемся найти вектор у из уравнений б), г), д). Эта система совместна и имеет единственное решение, если выполняются следующие условия:

1) Количество уравнений в системе m (совпадает с числом переменных);

2) Матрицы при неизвестных – неособенные

Проверить вектор на оптимальность в следующей задаче ЛП: Максимизировать при условиях:

Решение. Решение задачи необходимо начинать с проверки допустимости данного вектора . Подставляя значения компонент вектора в ограничении I0 и 20, убеждаемся, что все они выполняются. Для проверки остальных условий признака оптимальности составляем двойственную задачу: Требуется найти вектор , удовлетворяющий условиям: