Правило построения двойственных задач к общей з.Л.П.

1. Количество переменных в двойственной задаче равно количеству ограничений в прямой задаче.

2. Количество ограничений двойственной задачи равно числу переменных в прямой задачи.

3. Вектор свободных элементов прямой задачи b является вектором коэффициентов двойственной задачи.

4. Вектор коэффициентов функции цели C=(C1…Cn) прямой задачи служит вектором свободных членов системы ограничений двойственной задачи.

5. Если прямой Z->max то в Д.З. W->min/

6. Каждому ограничению – неравенству ai1x1+a12x2+..+ainxm , i=1,m Соответствует неотрицательная переменная yi>=0 ; i=1,m Д.З.

7. Каждой неотрицательной переменной (xj>=0) j=1,n прямой задачи соответствует ограничения неравенства Д.З. a1jy1+a2jy2+…+amjym>=Cj (j=1,n)

8. Матрица системы ограничений Д.З. служит транспонированная матрица прямой задачи.

9. Каждом ограничению равенству прямой задачи ai1x1+ai2x2+…+ainxn=bi (i=1,m) соответствует свободная переменная yi><0

10. Каждой свободной переменной xj><0 (j=1,n) соответствует ограничение равенства a1j+a2j+…+amjym=Cj

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

1. Если прямая и двойственная задача имеют допустимые решения Х и У , то они имеют оптимальное решение Х^* и У^* и причем значение функции в этих точках совпадают. Zmax=Wmin CX^*=Y^*b

Лемма №1

Для любых двух допустимых решений Х и У пары Д.З. справедливо СХ<=Уb

Док-во:

Z=CX->max W=yb->min

Ax<=b YA>=C

x>=0 y>=0

Допустим что X¹ – любое допустимое решение П.З. , а Y¹ – для Д.З.

Тогда Х¹ удовлетворяет системе ограничений , т.е. АХ¹<=b ¦ y¹>=0 Y¹A>=C¦x¹>=0

Первое ограничение умножим на y¹

Y¹Ax¹<=y¹b

Y¹Ax¹>=Cx¹

Cx¹<=T<=y¹b => Cx¹<=y¹b

Лемма № 2

Если для допустимых решений X^* и У ^* , выполняется условие равенства СХ^* =У^*b , то Х^* и У^* являются оптимальными решениями пары двойственных задач.

Док-во : Дана пара Д.З. Х^* и У^* допустимые решения. СХ^*=У^*b , док-ть Х^* и У^* оптим. решение

Предположим что Х- ОДР (любое) , тогда по первой лемме СХ<=У^*b , но У^*b=Cx^* => Cx=Cx^* отсюда следует , что Х^* т. максимума => у^* т. минимума.

На основании графического анализа Д.З. исследовать разрешимость данной задачи в случаи разрешимости – найти экстремальные значение целевой функции.

2. Часть теоремы.

Если одна из задач не разрешима из-за не ограниченности функции , то и вторая задача не имеет решения по причине не совместимости систем ограничений.

Док-во :

Согласно первой лемме СХ<=уb , если прямая задача не имеет решения zmax->бесконечности , то, очевидно, что нет такого допустимого решения (у) в котором значение функции было бы больше бесконечности.

Вторая теорема двойственности и свойства двойственных оценок.

Z=CX->max W=yb->min

Ax>=b ¦ y1 A- матрица коэффициентов

x>=0 ¦ y>=0 y1>=c

теорема : Для того что бы допустимое решение Х^* и У^* пары двойственных задач были оптимальными , необходимо и достаточно , что бы для них выполнялись условия «дополнительное не жесткости»

Z=Cx->max W=yb->min

Ax<=b ¦y YA>=C ¦x

x>=0 y>=0

1. Y*(Ax*-b)=0 (тогда оптимальное решение)

2. (У*А-С)Х*=0

необходимость :

Х* У* - оптимальное решение.

Док-ть: 1 и 2

Док-во: т.к. Х* является оптимальным решением , то и я является допустимым решением => Ах*<=b¦y*>=0 Y*Ax*<=y*b; y* в ходит ОДР => Y*A>=C¦x*>=0 y*Ax*>=Cx* =>

Cx*<=Y*Ax*<=y*b, т.к. х* и у* - оптимальное решение , то Сх*=уb* , по первой теореме => Сх*=у*Ах*=у*b. Ч.т.д

(С-у*А)х*=0

2) (у*А-С)х*=0

1) у*(Ах*-b)=0

достаточность

Дано

1) 2)

Док-ть

Х* и У* - оптим. решение.

Док-во: у*Ах*-у*b=0

Y*Ax*=y*b

y*Ax*-Cx=0

yAx*=Cx*

Cx*=T=y*b=> Cx*=y*b

Вывод для практики : Если в оптимальном решении исходной задачи х*j ><0 , то соответствующее ограничение Д.З. превращается в оптимальное решение равенства. Если какое либо из ограничений исходной задачи в оптимальном решении превращается в строгое не равенство , то соответствующая переменная Д.З=0