Лемма 3

Доказательство (продолжение). Покажем, что выполнено 2). Разобьем сумму в условии 2) на несколько сумм:

Учитывая, что , и

Имеем:

(1) (первая скобка равна 0, т.к. – старый допустимый вектор)

т.к. = , то получим в (1): (0)+ (0)=0

вектор удовлетворяет условию 2).

Покажем, что выполнено условие 1):

Возможны два случая:

а) все коэффициенты g_k≤ 0 в выражении .

б) среди коэффициентов g_k име­ются положительные.

Рассмотрим случай а).

Т.к. g_k≤ 0, то

Если имеет место случай а),то векторы , опреде­ляемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функ­ция на множестве таких векторов не ограничена сверху.

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

Рассмотрим случай б), когда среди коэффициентов g_k име­ются положительные.

Пусть, например, ;

Пусть, например, ;

.

Тогда . Для того, чтобы эти неравенства выполнялись одновременно, находят

Следовательно, , если

причем

, т.е. ограничена сверху и по теореме двойственности вектор х – оптимальный.

Если имеет место случай б),то векторы являются допустимыми в задаче А лишь при , где

,

причем ■

Пример задачи ЛП во 2 канонической форме:

задача ЛП в векторной форме: на множестве векторов х = (х₁,..., х₄), удовлетворяющих условиям: 2)  

					–5 –9
		–3	–5	–1

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