【正文】 1 對(duì)偶理論和靈敏度分析 ?對(duì)偶的定義 ?原始對(duì)偶關(guān)系 ?目標(biāo)函數(shù)值之間的關(guān)系 ?最優(yōu)解之間的互補(bǔ)松弛關(guān) 系 ?對(duì)偶問(wèn)題的性質(zhì) ?對(duì)偶的經(jīng)濟(jì)解釋 ?對(duì)偶單純形法 ?靈敏度分析 DUAL 2 第 3節(jié) 線性規(guī)劃對(duì)偶問(wèn)題的提出 現(xiàn)有甲乙兩種原材料生產(chǎn) A1， A2兩種產(chǎn)品，所需的原料，甲乙兩種原料的可供量，以及生產(chǎn)A1,A2兩種產(chǎn)品可得的單位利潤(rùn)見(jiàn)表。問(wèn)如何安排生產(chǎn)資源使得總利潤(rùn)為最大？ A1 A2 可供量 甲 3 2 24 已 4 5 40 利潤(rùn) 5 3 解：設(shè)生產(chǎn) A1為 x1件，生產(chǎn) A2為 x2件，則線性規(guī)劃問(wèn)題為： maxZ=+5x2 . 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0 假設(shè)現(xiàn)在不考慮生產(chǎn)產(chǎn)品，而是把甲乙兩種原材料賣掉，則 問(wèn)題變成對(duì)于甲乙兩種原材料企業(yè)以多少最低價(jià)愿意出讓？ 解：設(shè)甲資源的出讓價(jià)格為 y1,乙資源的出讓價(jià)格為 y2 minw=24y1+40y2 . 3y1+4y2≥ 2y1+5y2≥5 y1,y2≥0 3 2 4 5 3 4 2 5 4 第 4節(jié) 線性規(guī)劃的對(duì)偶理論 —— 對(duì)偶問(wèn)題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取極大值時(shí)均取 “ ≤” 號(hào)；當(dāng)目標(biāo)函數(shù)求極小值時(shí)均取“ ≥“ 號(hào)。則稱這些線性規(guī)劃問(wèn)題具有對(duì)稱性。 max z=c1x1+c2x2+…… +xn . a11x1+a12x2+…… +a1nxn ≤b1 a21x1+a22x2+…… +a2nxn ≤b2 …… am1x1+am2x2+…… +amnxn ≤bm x1, x2, …… , xn ≥0 min w=b1y1+b2y2+…… +bmym . a11y1+a21y2+…… +am1ym ≥c1 a12y1+a22y2+…… +am2ym ≥ c2 …… a1ny1+a2ny2+…… +amnym ≥ y1, y2, …… , ym ≥0 Max Z=CX . AX≤b X≥0 Minw=Y’b . A’Y≥C’ Y≥0 5 原始問(wèn)題 max z=CX . AX≤b X ≥0 對(duì)偶問(wèn)題 min w=Y’b . A’Y≥C’ Y ≥0 ≥ max b A C C AT b ≤ min m n m n 6 舉例： maxZ=3x1+2x2 . x1+2x2≤4 3x1+2x2≤14 x1x2 ≤3 x1,x2≥0 minw=4y1+14y2+y3 . y1+3y2+y3≥3 2y1+2x2y3≥2 y1,y2,y3≥0 y1 y2 y3 第一種資源 第二種資源 第三種資源 第一種產(chǎn)品 第二種產(chǎn)品 x1 x2 7 原始問(wèn)題為 min z=2x1+3x2x3 . x1+2x2+x3≥6 2x13x2+2x3≥9 x1, x2, x3≥0 根據(jù)定義，對(duì)偶問(wèn)題為 max y=6y1+9y2 . y1+2y2≤2 2y1 3y2≤3 y1+2y2≤1 y1, y2≥0 原始問(wèn)題是極小化問(wèn)題 原始問(wèn)題的約束全為 ≥ 原始問(wèn)題有 3個(gè)變量， 2個(gè)約束 原始問(wèn)題的變量全部為非負(fù) 對(duì)偶問(wèn)題是極大化問(wèn)題 對(duì)偶問(wèn)題的約束全為 ≤ 對(duì)偶問(wèn)題有 2個(gè)變量， 3個(gè)約束 原始問(wèn)題的變量全部為非負(fù) 原始問(wèn)題變量的個(gè)數(shù) (3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù) (3) 原始問(wèn)題約束條件的個(gè)數(shù) (2)等于對(duì)偶問(wèn)題變量的個(gè)數(shù) (2) 8 非對(duì)稱形式的原 — 對(duì)偶問(wèn)題 minz=2x1+3x25x3+x4 . x1+x23x3+x4≥5 2x1 +2x3x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0 x2+x3+x4≥6 x2+x3+x4≤6 x1=x1’ ， x1’≥0。x4’x4”=x4,x4’ ≥0,x4” ≥0 minz=2x1’+3x25x3+(x4’x4”) ’+x23x3+(x4’x4”)≥5 2x1’ 2x3+(x4’x4”)≥4 x2+x3 +(x4’x4”) ≥6 x2x3(x4’x4”) ≥6 x1’,x2,x3 ,x4’,x4” ≥0 變?yōu)橐话阈问? y1 y2’ y3’ y3” maxw=5y14y2’+6(y3’y3”) +2y2’ ≤2 y1 +(y3’y3”) ≤3 3y12y2’ +(y3’y3”) ≤ 5 y1+y2’+(y3’y3”) ≤ 1 y1y2’(y3’y3”) ≤1 y1,y2’ ,y3’,y3”≥0 寫出對(duì)偶問(wèn)題 9 maxw=5y14y2’+6(y3’y3”) +2y2’ ≤2 y1 +(y3’y3”) ≤3 3y12y2’ +(y3’y3”) ≤ 5 y1+y2’+(y3’y3”) ≤ 1 y1y2’(y3’y3”) ≤1 y1,y2’ ,y3’,y3”≥0 設(shè) y2=y2’,y3=y3’y3”,則 y2≤0,y3無(wú)約束 此時(shí)對(duì)偶問(wèn)題變?yōu)? maxw=5y1+4y2+6y3 . y1+2y2 ≥2 y1 +y3 ≤3 3y1+2y2+y3 ≤ 5 y1 y2 +y3 = 1 y1≥0 ,y2≤0,y3無(wú)約束 minz=2x1+3x25x3+x4 . x1+x23x3+x4≥5 2x1 +2x3x4≤ 4 x2+x3+x4 = 6 x1≤0,x2,x3≥0 比較原問(wèn)題 和對(duì)偶問(wèn)題 10 原 始 對(duì) 偶 表 11 對(duì)偶關(guān)系 極大與極小的對(duì)偶 價(jià)值系數(shù)與資源系數(shù)的對(duì)偶 約束條件系數(shù)矩陣的對(duì)偶是矩陣的轉(zhuǎn)置 反向不等式與非正的決策變量的對(duì)偶 等式與非負(fù)限制的決策變量的對(duì)偶 最優(yōu)解與檢驗(yàn)數(shù)的對(duì)偶 12 min z= 2x1+4x2x3 . 3x1 x2+2x3 6 x1+2x23x3 12 2x1+x2+2x3 8 x1+3x2x3 15 max y=6w1+12w2+8w3+15w4 . 3w1 w2+2w3+ w4 2 w1+2w2+ w3+3w4 4 2w1 3w2+2w3 w4 1 w1 0,w2 ,w3 0,w4 0 ≤ ≥ = ≥ Free ≤ ≥ ≥ = ≤ ≥ x1≥0 x2≤0 x3: Free ?原始問(wèn)題變量的個(gè)數(shù) (3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù) (3)； ?原始問(wèn)題約束條件的個(gè)數(shù) (4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù) (4)。 ?原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)。 ?原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)。 寫對(duì)偶問(wèn)題的練習(xí)（ 1） 13 寫對(duì)偶問(wèn)題的練習(xí)（ 2） 原始問(wèn)題 max z=2x1x2+3x32x4 . x1 +3x2 2x3 + x4≤12 2x1 + x2 3x4≥8 3x1 4x2 +5x3 x4 = 15 x1≥0, x2:Free, x3≤0, x4≥0 min y=12w1+8w2+15w3 . w1 2w2 + 3w3≥2 3w1 + w2 4w3=1 2w1 +5w3≤3 w1 3w2 w3≥2 w1≥0,w2≤0, w3:Free 對(duì)偶問(wèn)題 14 maxZ=x12x2+3x3 . 2x1+4x2+3x3≥100 3x12x2+6x3≤200 5x1+3x2+4x3=150 x1, x3≥0 練習(xí) minw=100y1+200y2+150y3 . 2y1+3y2+5y3≥1 4y12y2+3y3= 2 3y1+6y2+4y3≥3 y1≤0,y2≥0 minZ=2x1+2x2+4x3 . x1+3x2+4x3≥2 2x1+ x2+3x3≤3 x1+4x2+3x3=5 x1 ≥0, x2≤0 maxw=2y1+3y2+5y3 . y1+2y2+ y3≤2 3y1+ y2+4y3≥ 2 4y1+3y2+3y3≥4 y1≥0,y2≤0 15 原始和對(duì)偶問(wèn)題可行解目標(biāo)函數(shù)值比較 min z=2x1+3x2 . x1+3x2≥3 2x1+x2 ≥4 x1, x2 ≥0 max w=3y1+4y2 . y1+2y2≤2 3y1+y2 ≤3 y1, y2 ≥0 0 1 2 3 4 3 2 1 A(3,0) B(,) C(0,4) D(2,2) 可行解 z 最優(yōu)解 A 6 B 是 C 12 D 10 3 2 1 0 1 2 A(1,0) B(,) C(0,1) O(0,0) 可行解 w 最優(yōu)解 O 0 A 3 B 是 C 4 16 單純形法計(jì)算的矩陣描述 Max Z=CX AX≤b X≥0 其中 X＝ (x1,x2……x n)T Max Z=CX+0Xs AX+IXs=b X,Xs≥0 其中 Xs＝ (xn+1,xn+2……x n+m)T I 為 m m的單位矩陣 17 非基變量 基變量 XB XN Xs 0 Xs b B N I cjzj CB CN 0 …… 基變量 非基變量 XB XN Xs CB XB B1 b I B1N B1 cjzj 0 CNCBB1N CBB1 ?對(duì)應(yīng)初始單純形表中的單位矩陣 I，迭代后的單純形表中為 B1； ?初始單純形表中基變量 Xs=b，迭代后的表中為 XB=B1b； ?約束矩陣（ A， I）＝（ B， N， I），迭代后為 （ B1B， B1N， B1I）＝（ I， B1N， B1)； ?初始單純形表中 xj的系數(shù)向量為 Pj，迭代后為 Pj’，且 Pj’=B1Pj’。 18 當(dāng) B為最優(yōu)基時(shí)， XB為最優(yōu)解時(shí)，則有： CNCBB1N≤0 CBB1≤0 ∵ CBCBI=0 代入得： CN－ CBB1N+CBCBI≤0 C－ CBB1(B+N)≤0 整理得： C－ CBB1 A≤0 CBB1≤0 令 CBB1為單純形乘子， Y‘＝ CBB1 則： C－ Y’ A≤0 Y’≤0 Y’ A≥C’ Y’ ≥0 W＝ Y’b=CB