Пример составления двойственной задачи ЛП

Пример составления двойственной задачи ЛП

Пример 1.Записать двойственную задачу к следующей задаче линейного программирования. ЗАДАЧА1. Найти х = (х1, х2, х3, х4), удовлетворяющий условиям:

Решение. Заметим, что т.е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид: ЗАДАЧА 1* Найти удовлетворяющие условиям:

Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , , Зх1 + 2х2 - 5х3 + х5 - 70, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.

Решение. ЗАДАЧА 1* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 + 4y2 + 3y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь между задачами 1 и 1^*

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

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

µ(x) £(у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

Связь между задачами 1 и 1^*

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

х_j ³0 для jÎJ₂

(12)

Суммируя полученные соотношения, получим с учетом того, что (13)

Связь между задачами 1 и 1^*

Доказательство (продолжение). Имеем:

y_i ≥ 0 для iÎI₂

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т.е. выполняется µ(x) £(у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄