В15Связь между решениями прямой и двойственной задач

Теорема двойственности:1)Если одна из пары двойственных задач имеет оптимальный план, то и др. задача имеет оптимальный план и значение целевых ф-ции задач при оптимальных планах равны между собой:Fmax(X*)=F*min(Y*)

Если целевая ф-ция одной из задач не ограничена, то др. задача не имеет оптимальных планов, те несовместная система ограничений.2)(на примере симметрич. Пары взаимодвойственных задач)

F(X)=-X1+3X2-X3→MAX X*=(4,5,0,0,0,11) Fmax(X*)=11

3X1-X2+2Х3+Х4≤7

-2Х1+4Х2+Х5≤12

-4Х1+3Х2+8Х3+Х6≤10

Х1,Х2,Х3≥0

F*(Y)=7y1+12Y2+10y3→MIN

3y1-2y2-4y3-y4≥-1

-1y1+4y2+3y3-y5≥3

2y1+8y3-y6≥-1

План Х*=(Х*1,Х*2,Х*3,Х*4,Х*5,Х6)прямой задачи и план У*=(у*1,у*2,у*3,у*4,у*5,у*6)двойственной задачи являются оптимальными планами этих задач,тогда и только тогда, когда выполняются условия:х1*у4=0; х2*у5=0; х3*у6=0; у1*х4=0; у2*х5=0; у3*х6=0.

Алгоритм нахождения решения двойственной задачи по оптимальному решению двойственной задачи. 1. Приводят систему ограничений прямой и двойственной задач к канонич. Форме. 2. Составляют условия (смотри теорему 2) 3. Определяют переменные двойственной задачи принимающие в оптимальном плане нулевые значения у3;у4;у5=0 в двойственной задаче в оптимальном плане. 4. Удаляют из системы уравнений двойственной задачи переменные принимающие в оптимальном плане нулевые значения. 5 Решают полученную систему уравнений. 6. Проверяют выполнение равенства(смотри теорему 1)