【正文】 XB b x1 x2 x3 x4 x5 x6 0 x5 18 3 2 10 4 1 0 0 x6 3 0 0 2 1/2 0 1 cjzj 9 8 50 19 0 0 。 102 假設(shè)原線性規(guī)劃問(wèn)題變?yōu)? Maxz=9x1+8x2+50x3+19x4 . 3x1+2x2+10x3+4x4≤18 2x3+1/2x4≤3 2x1+ x2+ x3+2x4≤8 xj≥0 (j=1,2,3,4) Maxz=9x1+8x2+50x3+19x4 . 3x1+2x2+10x3+4x4+x5=18 2x3+1/2x4+x6=3 2x1+ x2+ x3+2x4+x7=8 xj≥0 (j=1,2,…,7) 103 cj 9 8 50 19 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 x7 19 x4 2 2 1 0 1 2/3 10/3 0 50 x3 1 1/2 1/3 1 0 1/6 4/3 0 0 x7 8 2 1 1 2 0 0 1 cjzj 4 2/3 0 0 13/3 10/3 0 變?yōu)?0 104 cj 9 8 50 19 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 x7 19 x4 2 2 1 0 1 2/3 10/3 0 50 x3 1 1/2 1/3 1 0 1/6 4/3 0 0 x7 8 2 1 1 2 0 0 1 cjzj 4 2/3 0 0 13/3 10/3 0 19 x4 2 2 1 0 1 2/3 10/3 0 50 x3 1 1/2 1/3 1 0 1/6 4/3 0 0 x7 3 2/3 4/3 0 0 7/6 16/3 1 cjzj 4 2/3 0 0 13/3 10/3 0 不發(fā)生變化 發(fā)生變化 此時(shí) x7的值＝ 3大于 0，所以原問(wèn)題和對(duì)偶問(wèn)題都達(dá)到可行解， 并分別為最優(yōu)解。 99 假設(shè)用甲乙兩種原材料還可以生產(chǎn)新產(chǎn)品為 E，需要甲原料 3個(gè)單位，乙原料 1個(gè)單位，利潤(rùn)為 10，問(wèn)該種新產(chǎn)品是否應(yīng)該生產(chǎn)？ 設(shè)生產(chǎn) E產(chǎn)品 x7個(gè)，則線性規(guī)劃方程為： Maxz=9x1+8x2+50x3+19x4+10x7 . 3x1+2x2+10x3+4x4+3x7≤18 2x3+1/2x4+x7≤3 xj≥0 (j=1,2,3,4,7) Maxz=9x1+8x2+50x3+19x4+10x7 . 3x1+2x2+10x3+4x4+3x7+x5=18 2x3+1/2x4+x7+x6=3 xj≥0 (j=1,2,…,7) 100 P7=(3,1)T P7’=B1P7’= 2/3 10/3 1/6 4/3 (3,1)T =(4/3,5/6)T σ 7’=c 7CBP7’=10 (19,50)(13/4,5/6)T=19/3＜ 0 因?yàn)?x7的檢驗(yàn)數(shù)小于 0，所以原最優(yōu)單純形表即為最優(yōu)單純形表， 最優(yōu)解不變。 ? 用對(duì)偶單純形法求解時(shí)，目標(biāo)函數(shù)必須是求極大化的。已知線性規(guī)劃問(wèn)題 證：首先該問(wè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)。（對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題無(wú)界解或無(wú)可行解。 47 步驟： 一般設(shè)松弛變量為初時(shí)基可行解 若所有的基變量值均 ≥0，則此解為線性規(guī)劃問(wèn)題的最優(yōu)解，若存在基變量的值 ≤0，則問(wèn)題還沒(méi)有達(dá)到最優(yōu)解，需要進(jìn)行改進(jìn)。 19 x4 6 2 1 0 1 2/3 10/3 50 x3 3 1/2 1/3 1 0 1/6 4/3 cjzj 4 2/3 0 0 13/3 10/3 0 x6 9/5 3/5 2/5 0 3/10 1/5 1 50 x3 3/5 3/10 1/15 1 2/5 1/10 0 92 cj 9 8 50 19 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 6 3 2 10 4 1 0 0 x6 3 0 0 2 1/2 0 1 cjzj 9 8 50 19 0 0 。 考慮影子價(jià)格： y1=13/3， y2=10/3 則生產(chǎn)一件 E產(chǎn)品所需要的隱含成本為： 13/3*3+10/3*1=49/3＞ 10(每件 E產(chǎn)品的利潤(rùn)） 所以也不生產(chǎ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 +△ c 2/3 0 0 13/3 10/3 思考：如果 x2的系數(shù)發(fā)生變化，△ c2在什么范圍內(nèi)變化，最優(yōu)解不變？ 97 cj發(fā)生變化 假設(shè) x4的利潤(rùn)由 19變?yōu)?19+△ c4 cj 9 8 50 19 +△ c4 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 18 3 2 10 4 1 0 0 x6 3 0 0 2 1/2 0 1 cjzj 9 8 50 19 0 0 。 89 cj 9 8 50 19 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 6 3 2 10 4 1 0 0 x6 3 0 0 2 1/2 0 1 cjzj 9 8 50 19 0 0 。 35 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 max w=y1y2 . y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1, y2, y3, y4, y5≥0 (y1, y2) =(6,0) (y1,y2,y3,y4,y5) =(6, 0, 0, 2, 3) min z=6x1+8x2+3x3 . x1+ x2 x4 =1 x1+2x2+x3 x5 =1 x1, x2, x3 ,x4, x5≥0 (x1, x2, x3 | x4, x5) (y1, y2 | y3, y4, y5) x2=x3=x4=0 x1=1, x5=2 引進(jìn)剩余變量 求對(duì)偶 引進(jìn)松弛變量 圖解法求解 代入約束 求出松弛變量 互補(bǔ)松弛關(guān)系 代入約束 求解 (x1, x2, x3, x4, x5) =(1, 0, 0, 0, 2) 36 第 5節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋 —— 資源的影子價(jià)格 (Shadow Price) ?影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺 ?影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺 ?如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于 0 yi’=△ w/△ bi=最大利潤(rùn)的增量 /第 i種資源的增量 =第 i種資源的邊際利潤(rùn) w=b1y1+b2y2+… +biyi+… +bmym w+△ w=b1y1+b2y2+… +(bi+△ bi)yi+… +bmym △ w=△ biyi 37 0 1 2 3 4 5 6 7 8 6 5 4 3 2 1 y1 y2 Z*= X=(7/2,3/2) Z*= X=(15/4,5/4) Z=9 X=(3,3) maxZ=2x1+x2 . 2x2≤15 6x1+2x2≤24 x1+x2≤5 x1,x2≥0 25 6 思考 : 如果第一種資源增加 1，也就是把 15變?yōu)?16,目標(biāo)函數(shù)值將怎么變化 ? 為什么 ? 38 ? 資源的影子價(jià)格是一種機(jī)會(huì)成本 ? 根據(jù)互補(bǔ)松弛定理 若 yi’ ＞ 0,則 ∑aijxj=bi， 若 yi’ ＝ 0,則 ∑aijxj＜ bi， ?某種資源 bi未得到充分利用時(shí)，該種資源的影子價(jià)格 為 0； ?當(dāng)資源的影子價(jià)格不為 0，表示該種資源在生產(chǎn)中已 消耗完畢。 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=CBB1b=Z 所以當(dāng)原問(wèn)題為最優(yōu)解時(shí)，對(duì)偶問(wèn)題為可行解且具有相 同的目標(biāo)函數(shù)值。 寫對(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