Вторая теорема двойственности.

Теорема: Пусть x*, y* - допустимые решения задач (Р) и (D). Необходимым и достаточным условием их оптимальности является одновременное выполнение двух групп условий:

a) y_i* = 0, если ∑ a_ijx_j* < b_i (i=1, …, m)

b) x_j* = 0, если ∑ a_ijy_i* > c_j (j=1, …, n).

Иными словами, k-ая переменная одной задачи = 0, если k-ое ограничение другой задачи не активное.

Доказательство(использует только первую теорему двойственности):

Необходимость условий а) и б). Если x*, y* - оптимальны, то из Первой теоремы двойственности имеем: <с,x*> = <A^Ty*, x*> ≡<Ax*,y *> = <b, y*> ,

что дает два равенства: <A^Ty*-c, x*> =0 и <Ax-b,y*> = 0. Рассмотрим первое.

Так как y* - допустимое решение задачи (D) , то A^Ty* – с ≥ 0. Так как и х* ≥ 0, то все слагаемые в скалярном произведении <A^Ty* – с, x*>=∑ (∑a_ij y_i* - c_i)x_j*

равны нулю. Значит, либо x_j* = 0, либо ∑a_ij y_i* - c_i = 0. Пункт b) доказан.

Аналогично доказывается необходимость условия a). Рассмотрим второе неравенство: <Ax* - b, y*> = 0. Первый сомножитель в этом скалярном произведении – вектор с неположительными координатами (по условию прямой задачи), y* - неотрицательный вектор, так как y* - допустимое решение двойственной задачи. Всё скалярное произведение = 0. Поэтому должны равняться нулю все входящие в него слагаемые:

[Σ a_ij x_j* - b_i] y_i* = 0 (i=1,…,m), что равносильно условию a).

Достаточность условий a) и b). Пусть x*, y* - допустимые решения. Пусть выполняются условия a) и b). Используя их, получим:

∑ (∑a_ij y_i* - c_i) · x_j* = 0 и ∑ (∑a_ij x_j* - b_i) · y_i* = 0.

Это можно записать в виде <A^Ty* - c, x*> = 0 и <Ax* - b, y*> = 0

или <A^Ty*,x*> =< c, x*>, <Ax*,y*> = <b, y*>. Объединяя два последних равенства, имеем:

<c, x*> = <Ax*, y> ≡ <A^Ty*, x> = <b, y*>, то есть <c, x*> = <b, y*> следовательно, x*, y* - оптимальные решения (по 1-й теореме двойственности).

Замечание. Итак, для оптимальности допустимых решений x* и y* необходимо и достаточно выполнения условий т.н. «дополняющей нежесткости»:

для любого k=1,…,n произведение x_k* на левую часть соответствующего k-го неравенства l_k(y) ≥ 0 двойственной задачи равно нулю и для любого k=1,…,m произведение y_k* на левую часть соответствующего k-го неравенства m_k(x)≤ 0 прямой задачи равно нулю.

Вторая теорема дает возможность проверить оптимальность решения прямой задачи, не зная заранее решения двойственной (пример будет дан ниже).

Пример:Проверить оптимальность решения x* = (8, 0) в задаче ЛП

-2x₁ + x₂ ≤ 2

x₁ + 2x₂ ≤ 8

x_1,x₂≥ 0

3x₁ + 2x₂→ max.

Решение: Предположим, что x* = (8, 0) – оптимальное решение. Тогда по первой теореме двойственности должно существовать некоторое оптимальное решение y* двойственной задачи

-2y₁ + y₂ ≥ 3

y₁ + 2y₂≥ 2

y₁, y₂ ≥ 0

2y₁ + 8y₂ → min ,

причем по 2-й теореме двойственности x* и y* должны удовлетворять условиям дополняющей нежесткости (УДН).

Подставив x* в ограничения исходной задачи, видим, что неактивным ограничением в точке (8,0) является первое (-16<2). Поэтому по УДН y*₁=0. Поскольку x*₁ =8>0, первое ограничение двойственной задачи должно выполняться как строгое равенство. Поэтому нетривиальные ограничения двойственной задачи принимают вид: y₂* = 3, 2y₂* ≥ 2, откуда получаем вид оптимального решения двойственной задачи: y* = (0,3).

Итак, допустимое решение прямой задачи x* = (8, 0) вкупе с допустимым решением y* = (0,3) двойственной задачи удовлетворяют УДН. Значит, x* = (8, 0) – оптимальное решение.

Проверим (для контроля) условие оптимальности Z(x*)=F(y*):

3*8+2*0=2*0+3*8= 24.

1 23

Дата добавления: 2016-03-27; просмотров: 1039;