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

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

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

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

m (х) = n (у)(1)

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

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

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

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

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

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

а) у_i і 0, iI₂

б) еa_ijy_i + c_j = 0, jJ_1,

iI

в) еa_ijy_i + c_j, £ 0, jJ_2,

iI

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

iI

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

^jJ

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

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