Замечание 1. Если условие 1 не выполнено (т. е. все коэффициенты при переменной xj, входящей в целевую функцию с положительным коэффициентом, неположительны), то задача ЛП неограничена, решения нет.
Замечание 2. Если минимальное из отношений bi/ aij равно нулю, новая базисная переменная в очередном базисном решении равна 0, улучшения функции на данном шаге не происходит.
В последнем случае совместная задача не имеет решения, что может быть вызвано только неограниченностью целевoй функции. Действительно, если бы совместная задача была ограничена по целевой фунции, то она имела бы оптимальное решение. Но тогда по первой теореме двойственности имела бы решение и другая задача, что противоречит предположению пункта 3).
Следующие три примера показывают, что все три возможности осуществляются.
Примеры:
1)2х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
Решите задачи геометрическим способом и убедитесь, что оптимальные решения
Вывод: В этом примере обе задачи совместны и имеют оптимальное решение.
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. В соответствии с леммой первая задача должна не иметь оптимального решения. Действительно, она оказывается неограниченной сверху.
Теорема существования. Прямая и двойственная задачи имеют оптимальное решение тогда и только тогда, когда обе задачи имеют допустимые решения.
Доказательство необходимости очевидно. Достаточность следует из того, что по основной лемме целевые функции в обеих задачах будут ограничены (соответственно сверху и снизу) и потому будут иметь (по теореме Вейерштрасса) оптимальные решения.
Определение: Назовем ограничение активным (существенным, эффективным), если оно выполняется в данной точке как равенство и неактивным (несущественным, неэффективным), если оно выполняется как строгое неравенство.
Вторая теорема двойственности.
Теорема: Пусть 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. Поэтому должны равняться нулю все входящие в него слагаемые:
Это можно записать в виде <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*):
x1 x2 x3 x4 x5 x6 b
2 ½ x6 0 0 1/6 1/3 -5/6 1 5/6
2х1 + х2 ≤ 4 2y1 + y2 ≥ 1
2)х1 - х2 ≤ 3 y1 - y2 ≥ 1 
