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

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

a) yi* = 0, если ∑ aij xj* < bi (i=1, …, m)

b) xj* = 0, если ∑ aij yi* > cj (j=1, …, n).

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

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

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

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

Так как y* - допустимое решение задачи (D) , то ATy* – с ≥ 0. Так как и х* ≥ 0, то все слагаемые в скалярном произведении <ATy* – с, x*>=∑ (∑aij yi* - ci)xj*

равны нулю. Значит, либо xj* = 0, либо ∑aij yi* - ci = 0. Пункт b) доказан.

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

[Σ aij xj* - bi] yi* = 0 (i=1,…,m), что равносильно условию a).

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

∑ (∑aij yi* - ci) · xj* = 0 и ∑ (∑aij xj* - bi) · yi* = 0.

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

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

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

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

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

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

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

-2x1 + x2 ≤ 2

x1 + 2x2 ≤ 8

x1, x2 ≥ 0

3x1 + 2x2 → max.

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

-2y1 + y2 ≥ 3

y1 + 2y2 ≥ 2

y1, y2 ≥ 0

2y1 + 8y2 → min ,

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

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








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


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.