с = Ар,(4.16)
d>{b,p).(4.17)
Легко видеть, что если неравенство {c,x)<d является неотрицательной линейной комбинацией неравенств системы (4.12), то
Ax<b{c,x)<d .
В дальнейшем нам понадобится результат, являющийся одной из формулировок леммы Фаркаша, который мы сформулируем без доказательства [6].
Теорема 4.1. Имеет место следующая альтернатива: либо система уравнений Ау = с имеет неотрицательное решение, либо имеет решение
система неравенств < О, (с,х) > О.
Рассмотрим несколько очевидных соотношений. Пусть Р = (А»Р2»-Рт) неотрицательный вектор, /?,>0, / = 1,...,т.
Умножив/-е равенство системы (4.12) на число р получим:
Pi ( /11 + /22 + - +) Ргг •(4-18)
Просуммируем полученные неравенства по / = l,...,/w :
т пт
(4.19)
;=/ 7=1/=1
Так как число X ijXj представляет собой компоненту вектора Ах, то
формулу (4.19) можно записать в более компактной форме:
{р,Ах)<{р,Ь).(4.20)
Поскольку
{р,Ах) = {Ах,р),(4.21)
то при р>0 т неравенства Ах<Ь вытекает:
{Ар,х)<{р,Ь).(4.22)
Обозначим через Y множество планов двойственной задачи (4.4)-(4.6).
Лемма 4.1. Пусть хеХ, уеУ - произвольные допустимые решения прямой (4.1)-(4.3) и двойственной (4.4)-(4.6) задачи. Тогда
{с,х)<{Ь,у).(4.23)
Доказательство. Поскольку хеХ ,то Ах<Ь. Умножив это неравенство на вектор >>0 из (4.20) и (4.22), получим
{с,х) = {Ау,х) = {у,Ах)<{у,Ь).
Лемма 4.2. Пусть х* еХ, у* е¥ - допустимые решения задач (4.1)-(4.3); (4.4)-(4.6) соответственно. Если (с,х* = (ь,у*, то х* - оптимальное решение задачи (4.1)-(4.3); у* - оптимальное решение задачи (4.4.)-(4.6).
Доказательство. Пусть хеХ - допустимое решение задачи (4.1)-(4.3).Тогда по лемме 4.1 (с,х)<(ь,у* = (с,х*, т.е. х* - оптимальное решение задачи (4.1)-(4.3). Если yeY - допустимое решение задачи (4.4)-(4.6), то также учитывается утверждение леммы 4.1 (b,y)>(c,x* = (b,y* и следовательно, у* - оптимальное решение задачи (4.4)-(4.6).
Легко видеть, что лемма 4.2 дает достаточное условие оптимальности решение прямой двойственной задачи.
Основу теорем двойственности составляют две теоремы. Одна из них называется первой теоремой двойственности, вторая - теоремой равновесия.
Кроме достаточного признака оптимальности взаимодвойственных задач, существуют и другие важные соотношения между их решениями. Ответ на вопрос о взаимной разрешимости двойственных задач дает следующая теорема [47].
Первая теорема двойственности. Если взаимодвойственные задачи (4.1)-(4.3) (4.4)-(4.6) имеют непустое множество допустимых решений, то они имеют оптимальные решения, значения которых совпадают.
Доказательство. Пусть каждая из задач (4.1)-(4.3) и (4.4)-(4.6) имеет непустое множество допустимых решений и у eY - произвольное допустимое решение (план) задачи (4.4)-(4.6).
Тогда по лемме 4.1 целевая функция (с,х) ограничена на множестве X
числом (fe, у). Отсюда учитывая, что множество решений задачи 92
(4.1)-(4.3) йе пусто и ограничено, следует, что она имеет оптимальное ре-
шение X*.
Рассмотрим в пространстве R" систему линейных уравнений
Ау = с(4.24)
(й,>;) = (с,/).(4.25)
Если вектор у* неотрицателен и является решением системы (4.24)-(4.25), то
1)- допустимое решение задачи (4.4)-(4.6), так как у >0, Ау*=с;
2)у* - оптимальное решение задачи (4.4)-(4.6), так как (ь,У* = (с,х*,аэто согласно лемме 4.2 является достаточным условием оптимальности
3)оптимальные значения (с,х* 6,>* задач (4.1)-(4.3) и (4.4)-(4.6)
совпадают.
Таким образом, для доказательства теоремы двойственности остается показать, что система (4.24)-(4.25) имеет неотрицательное решение.
Запишем эту систему в матричном виде. Пусть А =
с
, тогда
Ау = с(4.26)
- запись системы уравнений (4.24), (4.25) в новых обозначениях.
Допустим, что система (4.26) не имеет неотрицательных решений. В этом случае, согласно теореме 4.1, имеет решение система неравенств
Ах<0, (с,х)>0.(4.27)
Здесь вектор х имеет размерность « +1 (в соответствии с тем, что у матрицы А = [А,Ь) имеется « +1 столбец)*.