В этом случае y* - оптимальное решение двойственной задачи.

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

Достаточность. Пусть x*, y* - допустимые решения прямой и двойственной задач и <с, x*> = <b, y*>. Тогда для любого допустимого решения х по основной лемме имеем:

<с, x> ≤ <b, y*> = <с, x*>,

то есть <с, x> ≤ <с, x*> при любом допустимом x. Это и означает оптимальность решения x*.

С другой стороны, для любого допустимого решения y из основной леммы имеем:

<b,y> ≥ <c, x*>=<b, y*>, т. е. <b,y> ≥ <b, y*>,что и означает оптимальность y*.

Необходимость(без доказательства). Если х* - оптимальное решение задачи (Р), то в двойственной задаче обязательно найдется допустимый вектор y* такой, что значения целевых функций будут равны: <c, x*> = <b, y*>.

Эквивалентная формулировка первой теоремы (симметричная): Если одна из пары двойственных задач имеет оптимальное решение, то и другая задача также имеет оптимальное решение, причем оптимальные значения целевых функций (на оптимальных решениях) совпадают.

Лемма: Если целевая функция ∑bi yi в двойственной задаче (D) не ограничена снизу на множестве допустимых решений y, то прямая задача (Р) не имеет ни одного допустимого решения, то есть несовместна.

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

Если бы задача (Р) имела допустимое решение х˚, то по основной лемме для любого допустимого решения y F(y) = bi yi ≥ ∑ сj xj˚ = const, то есть F(y) ограничена снизу, что противоречит условию леммы. Противоречие доказывает лемму.

Замечание: Эту лемму можно использовать для установления факта несовместности задачи ЛП (то есть как достаточное условие несовместности).

Логически возможны три случая:

1) Обе задачи (Р) и (D) совместны;

2) Обе задачи несовместны;

3) Одна из задач совместна, а другая несовместна.

В последнем случае совместная задача не имеет решения, что может быть вызвано только неограниченностью целевoй функции. Действительно, если бы совместная задача была ограничена по целевой фунции, то она имела бы оптимальное решение. Но тогда по первой теореме двойственности имела бы решение и другая задача, что противоречит предположению пункта 3).

Следующие три примера показывают, что все три возможности осуществляются.

Примеры:

1) 1 + х2 ≤ 4 2y1 + y2 ≥ 1

x1 + 2x2 ≤ 4 y1 + 2y2 ≥ 1

x1, х2 ≥ 0 y1, y2 ≥ 0

Z(x)= x1 + х2 → max F(y)= 4y1 + 4y2 → min

Решите задачи геометрическим способом и убедитесь, что оптимальные решения

x* =( 4/3, 4/3 ), y* = ( ⅓, ⅓ ) и Z(x*) = F(y*)= 8/3 .

Вывод: В этом примере обе задачи совместны и имеют оптимальное решение.

2)х1 - х2 ≤ 3 y1 - y2 ≥ 1

-x1 + x2 ≤ -4 -y1 + y2 ≥3

x1, х2 ≥ 0 y1, y2 ≥ 0

Z(x)= x1 + 3х2 → max F(y)= 3y1 -4y2 → min

Легко видеть, что здесь обе задачи несовместны. Складывая неравенства, в первой из них получим 0 ≥-1, во второй 0 ≥4, что указывает на несовместность ограничений.

3) х1 - х2 ≤ 1 y1 ≥ 1

-y1 ≥ 0

x1, х2 ≥ 0 y1 ≥ 0

Z(x)= x1 → max F(y)= y1 → min

Здесь первая задача совместна, а вторая – несовместна. Сложив два неравенства, получим 0 ≥1. В соответствии с леммой первая задача должна не иметь оптимального решения. Действительно, она оказывается неограниченной сверху.









Дата добавления: 2016-03-27; просмотров: 552; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


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

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

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

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2020 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.