【正文】 值系數(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)。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)表。 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。 寫對(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’。另一個(gè)就是它的對(duì)偶問(wèn)題。 推論： ? 若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解時(shí)，原問(wèn)題目標(biāo)函數(shù)無(wú)界 ? 若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解時(shí)，對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界。 31 （ 4）最優(yōu)性 ? 若 X為原問(wèn)題的可行解， Y為對(duì)偶問(wèn)題的可行解，且 CX＝Y(jié)’b則 X， Y分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。x j=0 33 maxZ=+5x2 . 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0 y1 y2 minw=24y1+40y2 . 3y1+4y2y3= 2y1+5x2y4=5 y1,y2,y3,y4≥0 x1 x2 X3=0, 3x1+2x2=24,y1=14/5 X4=0,4x1+5x2=40,y2=6/7 y3=0, 3y1+4y2=5,x1=40/7 y4=0, 2y1+5y2=5,x2=24/7 34 利用互補(bǔ)松弛關(guān)系求解線性規(guī)劃 min z=6x1+8x2+3x3 . x1+ x2 ≥1 x1+2x2+x3 ≥1 x1, x2, x3 ≥0 max w=y1y2 . y1+ y2 ≤6 y1+2y2 ≤8 y2 ≤3 y1,y2≥0 原始問(wèn)題 對(duì)偶問(wèn)題 0 1 2 3 4 5 6 7 8 6 5 4 3 2 1 w1 w2 y=1 y=1 y=3 y=6 最優(yōu)解為 (y1, y2)=(6, 0) max y=6 先用圖解法求解對(duì)偶問(wèn)題。一個(gè)從對(duì)偶不可行的解，經(jīng)過(guò)幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原始可行的，又是對(duì)偶可行的，這個(gè)解就分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。 選擇換出變量 min{ bi’/ bi≤0}假設(shè)選取 xk為換出變量 選擇換入變量 θ＝ min{(cjzj)arj|arj＜ 0,cjzj＜ 0}則假設(shè)選取 xl為換出變量 。 85 某廠準(zhǔn)備用甲乙兩種原料生產(chǎn) A， B， C， D四種產(chǎn)品，相關(guān)參數(shù)見(jiàn)表。 19 x4 2 2 4/3 0 1 2/3 10/3 50 x3 1 1/2 1/3 1 0 1/6 4/3 cjzj 4 2/3 0 0 13/3 10/3 Z*=88 B= (P4,P3)= 4 10 189。 95 cj發(fā)生變化的分析 cj發(fā)生變化 x1的利潤(rùn)值由 9變?yōu)?9+△ c1 則： σ 1= 9+△ c12 19+25=4+ △ c1 如果 σ 1=4+ △ c1≤0，最優(yōu)解不發(fā)生變化； σ 1=4+ △ c1＞ 0，最優(yōu)解將發(fā)生變化。 98 當(dāng)目標(biāo)函數(shù)中 cj發(fā)生變化，將影響最終單純形表非基變量的檢驗(yàn)數(shù)。 101 ? 增加一個(gè)變量也就是多生產(chǎn)一種產(chǎn)品，只須考慮該種產(chǎn)品的檢驗(yàn)數(shù)是否大于 0，如果大于 0則表示應(yīng)該生產(chǎn)，用單純形表進(jìn)行求解；如果小于 0則該種產(chǎn)品不用生產(chǎn)，最優(yōu)解不發(fā)生變化。 106 aij發(fā)生變化 Maxz=9x1+8x2+50x3+19x4 . 3x1+2x2+10x3+4x4≤18 2x3+1/2x4≤3 xj≥0 (j=1,2,3,4) 3x1+x2+10x3+4x4≤18 變?yōu)? 則 P2=(2,0)T P2’=(1,0)T P2’’=B1P2’= 2/3 10/3 1/6 4/3 (1,0)T =(2/3,1/6)T σ 2’= c2CBP2’’=8(19,50)(2/3,1/6)T=11/3＞ 0 107 cj 9 8 50 19 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 18 3 1 10 4 1 0 0 x6 3 0 0 2 1/2 0 1 cjzj 9 8 50 19 0 0