最優(yōu)化理論與方法 課件 6 對偶原理

第四章對偶原理窗含西嶺千秋雪，門泊東吳萬里船對偶是一種普遍現象2線性規(guī)劃的對偶理論1947年提出；支持對偶理論的思想是：每一個線性規(guī)劃問題都存在一個與其對偶的問題。3某公司制造兩種家電產品。假定：已知各制造一件時分別占用的設備A、設備B的臺時、調試時間以及設備A、設備B和調試工序每天的可用能力、產品的單件利潤，如表所示，要確定A、B兩種家電各生產多少件，獲利最大。問題提出產品產品1產品2每天可用能力設備A(h)0515設備B(h)6224調試工序115單件利潤214這是一個典型的最優(yōu)生產計劃制定問題。制定獲得最大利潤生產計劃的線性規(guī)劃問題為：5再從另一個角度看問題。假定：有另一個公司想把該公司的資源收買下來，它至少應付多大的代價才能讓原公司愿意放棄生產活動出讓資源。顯然，原公司出讓自己資源的條件是：出讓價不低于同等資源由自己組織生產時獲取的盈利。設y1,y2,y3分別代表單位時間(h)設備A、B及調試工序的出讓代價，則y1,y2,y3應滿足6又另外一個公司希望用個最小代價把該公司的資源收買過來，有綜上，有7

(LP1)與(LP2)兩個線性規(guī)劃問題的表現形式和系數之間存在許多對應關系，并且maxz=minw前者為原問題，后者是前者的對偶問題。81.對稱形式的對偶9觀察分析上述模型形式，可發(fā)現，按如下規(guī)則，可以從線性規(guī)劃原問題得到其對偶問題：（1）目標函數由max變?yōu)閙in模型；（2）對應原問題，每個約束行有一個對偶變量yi,i

=1,2,…,m;（3）對偶問題約束為>=型，有n行；（4）原問題的價值系數c變換為對偶問題的右端項；（5）原問題的右端項b變換為對偶問題的價值系數。根據上述規(guī)則，可直接寫出規(guī)范形式下LP問題的對偶問題。10例：寫出下列線性規(guī)劃問題的對偶問題11寫對稱形式對偶問題的要點：(1)max變成min(2)價值系數與右端向量互換(3)系數矩陣轉置(4)≤變≥原問題中約束條件的個數=對偶問題中變量的個數原問題中變量的個數=對偶問題中約束條件的個數12寫成等價形式對偶問題為：2.非對稱形式的對偶13例min5x1+4x2+3x3s.t.x1+x2+x3=43x1+2x2+x3=5

x1≥

0,x2≥0,

x3≥0對偶問題為：

max4w1+5w2s.t.w1+3w2≤5

w1+2w2≤

4

w1+w2≤

314mincxs.t.A1x

≥b1，

A1

為m1×n,b1為m1×1

A2x

=b2，A2

為m2×n,b2為m2×1

A3x

≤b3，A3

為m3×n,b3為m3×1

x≥0引入松弛變量：

mincx

s.t.A1x–xs=b1，

xs為m1×1

A2x

=b2，

A3x+xt=

b3，xt為m3×1

x,xs

,xt≥03.一般情形的對偶問題15即：按照非對稱對偶的定義，其對偶問題為：16即：17總結minmax變量>=0<=0無限制<=>==約束方程約束方程>=<==>=0<=0無限制變量18例：19練習：直接寫出線性規(guī)劃問題的對偶問題：20練習：直接寫出線性規(guī)劃問題的對偶問題：21對偶問題的基本性質原問題

對偶問題mincxmaxwbs.t.Ax

≥bs.t.wA≤c

x≥0w≥022定理1：弱對偶定理定理表明，對于對偶中的兩個問題，每一個問題的任何一個可行解處的目標函數