4. Сформулируем двойственную задачу
Z = -y,+14 +3, -15 -min
при Офаничениях:
-У1-У2+Уз-У4 -1
3>,+4>2->3->4>3
у,>0, у,>0,у,>0, у,>0.
В рассмотренном примере в качестве исходной задачи линейного программирования рассматривадась стандартная задача линейного программирования.
Выясним, в каком виде может быть представлена двойственная задача для канонической задачи линейного программирования.
F = сх + С2Х2 +... + с„х„ -> max.
«тЛ + «т22 + - + «m»n = *m Х,>0, Х2>0,..., Х„>0.
(4.7)
Заменим каждое равенство Y*ijXj=b на два ajXj<b. и
-у , тогда задача (4.7) эквивалентна следующей задаче, ко-торую мы зададим в матричном виде.
maxXc,JCj /=1
АхйЬ -Ах<-Ь
(4.8)
Обозначив А =
вую запись задачи (4.8): 88
jc>0.
получаем в других обозначениях но-
Ax<b(4.9)
x>0.
Ясно, что (4.9) представляет собой стандартную задачу линейного профаммирования. Воспользовавшись правилом формирования двойственной задачи для стандартной задачи линейного профаммирования получим:
AV>c V>0,
где F = (, Г2,..., , , ,...5) - вектор 2т-мерного просфанства. Возвращаясь к прежним обозначениям имеем:
mm{{b,r)-{b,S))
Ar-AS>c(4.10)
г >0, 5>0,
где г = (г1,Г2,...,г), 5 = (5i,52,...5). Обозначим p = r-S.
Очевидно, что задача (4.10) эквивалентна следующей:
mintbiPi /=1
Ар>с,(4.11)
где на р уже не накладьгоается никаких дополнительных офаничений (типа неофицательности), поскольку р есть разница двух неотрицательных векторовРи8иэто никакой информации не несет.
Задача (4.11) называется двойственной канонической задачей (4.7).
4.2. Основные теоремы двойственности
Рассмофим некоторые свойства систем линейных неравенств вида Ах<Ь или в векторном виде:
{а,х)<Ь,, (а2)<Й2,..., М<Ь.(4.12)
II Если взаимно-двойственные 11 Пусть неравенство т системы ли-
задачи имеют непустое множество решений, то они имеют оптимальные решения, значения которых совпадают.
нейных неравенств (4.12) является неотрицательной линейной комбинацией остальных т -1 линейных неравенств, т.е. существуют неотрицательные:
Д,Д,такие,
что а = 1А , b>J:/ify. /=1/=1
Тогда ясно, что m-OQ неравенство «лишнее» в системе (4.12).
Действительно, если точка х удовлетворяет только первым т-\ неравенствам, то она автоматически удовлетворяет неравенству с отношением т :
/=1/=1
Будем говорить, что неравенство
{c,x)<d(4.13)
является следствием системы неравенств (ai,x)<bi / = l,...,w, если для
любого X, удовлетворяющего всем неравенствам этой системы выполняется неравенство (4.13).Для сокращения записи это будет выражаться следующим образом:
Ax<b{c,x)<d.
Будем говорить, что неравенство (4.13) является неотрицательной линейной комбинацией неравенств (4.12), если существуют такие неотрицательные числа Pi,P2,-,Pm»что
c = lLPiai j = \,...,n,(4.14)
dtPih-(4.15)
С использованием транспонированной матрицы А и обозначения p = (pj,p2-Pm) формулы (4.14) и (4.15) могут быть записаны в форме 90