1、第六節 線性規劃應用舉例 例1：某工廠生產A,B兩種產品，均需經過兩道工序， 每種產品需各工序加工的時間及各工序可提供的時間如下表。生產產品B同時生產出副產品C，每生產一噸產品B可同時得到2噸產品C，無需費用。出售一頓A盈利400元，B盈利1000元，C盈利300元，而生產要報廢的C每噸損失200元，經預測C最大銷量為5噸，列模型決定A,B產量，使工廠總盈利最大。 A B C工時限量一工序二工序 2 3 3 4 12 24盈利損失400 1000 300 -200可控變量：設X1為A產量，X2為B產量，X3為C銷售量，X4為C報廢量目標為總盈利，約束為資源限制等 maxZ=4X1+10X2+3

2、X3-2X4 2X1+3X212 3X1+4X224 X3+X4=2X2 X35 X1,X2,X3,X40 例2：某工廠生產的一種產品由四個零件一和三個零件二組成，這兩種零件好用兩種原材料，由于三個車間擁有的設備和工藝不同，每個工班原材料耗用量和零件產量不同，問三個車間應各開多少工班，才能使該產品的配套數達到最大。 分析：可控變量是什么，目標和約束是什么每班用料數（公斤）每班產量（件數）A材料B材料零件一零件二一車間二車間三車間853698768594資源限量300500可控變量：三個車間工班數，目標：產品配套數，約束資源約束 目標為兩目標取小，要轉化為一個目標時的方法。Z=min( (7x1

3、+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)可令y= min( (7x1+6x2+8x3)/4 ,(5x1+9x2+4x3)/3)則上目標轉化為maxZ=y (7x1+6x2+8x3)/4y(5x1+9x2+4x3)/3y maxZ=y (7x1+6x2+8x3)/4y (5x1+9x2+4x3)/3y 8x1+5x2+3x3300 6x1+9x2+8x3500 x1,x2,x3,y0 解 先看有多少種裁料方案，再進行組合和選擇。方案： 例3 合理利用線材問題 現要做一百套鋼管, 每套要長為2.9m、2.1m和1.5m的鋼管各一根。已知原料長7.4m，問應如何下料，使用的原料最省

4、。 2 .9 m 2 .1 m 1 .5 m 2 0 1 1 2 0 1 1 1 1 0 3 0 3 0 0 2 2 0 1 3 0 0 4 料料 頭頭 0 .1 0 .3 0 .9 0 1 .1 0 .2 0 .8 1 .4 設用方案設用方案,分別裁原料分別裁原料鋼管鋼管x1,x2, ,x8根根, 則：則：Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8 2x1+ x2+x3 + x4 100 2x2+x3+ 3x5 +2x6+ x7 100 x1+ x3 +3x4 +2x6+3x7+4x8 100 x1, x2, x3, x4, x5 ,x6, x7, x8 0 例例4

5、4 某工廠要用三種原材料某工廠要用三種原材料C,P,HC,P,H混合調配出混合調配出三種不同規格的產品三種不同規格的產品A,B,DA,B,D。已知產品的規格要。已知產品的規格要求、單價和原料的供應量、單價如下表。該廠應求、單價和原料的供應量、單價如下表。該廠應如何安排生產，能使利潤最大？如何安排生產，能使利潤最大？ 產產品品名名規規格格要要求求單單價價A原原料料 C 不不少少于于 50%原原料料 P 不不超超過過 25%50 元/KGB原原料料 C 不不少少于于 25%原原料料 P 不不超超過過 50%35 元/KGD不不限限25 元/KG原原料料名名每每天天最最多多供供應應量量單單價價CPH

6、100KG100KG60KG65 元/KG25 元/KG35 元/KG根據產品要求有：根據產品要求有： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH=A BC+BP+BH=B根據原料供應量有：根據原料供應量有： AC+BC+DC100 AP+BP+DP100 AH+BH+DH60設設AC,AP,DH分別為分別為x1,x2,x9，有，有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2

7、0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+ x7100 x2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9解：記產品解：記產品A,B,DA,B,D中中C,P,HC,P,H的含量分的含量分別為別為AC,AP,AH,BC,BP,BH,DC,DP,DH。 例例5 連續投資問題。某單位有資金連續投資問題。某單位有資金10萬元，在萬元，在今后今后5年內可考慮下列投資項目，已知：年內可考慮下列投資項目，已知： 項目項目A：從第：從第1到第到第4年每年初可投資，并于次年每年

8、初可投資，并于次年末回收本利年末回收本利115%； 項目項目B：第：第3年初需要投資，到第年初需要投資，到第5年末回收本年末回收本利利125%，但最大投資額不超過，但最大投資額不超過4萬元；萬元； 項目項目C：第：第2年初需要投資，到第年初需要投資，到第5年末能回收年末能回收本利本利140%，但最大投資額不超過，但最大投資額不超過3萬元；萬元； 項目項目D：5年內每年初可購買公債，當年末回年內每年初可購買公債，當年末回收本利收本利106%。 問它應該如何安排每年的投資，使到問它應該如何安排每年的投資，使到5年末年末擁有的資金最多？擁有的資金最多？ 年份年份項目項目 一一 二二 三三 四四 五五

9、 A X1AX2AX3AX4A B X3B CX2C D X1DX2DX3DX4DX5D x2A+x2C+x2D=1.06x1D解：每年的投資額解：每年的投資額應不超過手中的資應不超過手中的資金。由于項目金。由于項目D每每年都可投資，且當年都可投資，且當年末就可收回。所年末就可收回。所以該單位每年必然以該單位每年必然把資金全部投出去，把資金全部投出去，即投資額等于手中即投資額等于手中的資金數。的資金數。 設第設第i年投資各項目的資金年投資各項目的資金為為xiA,xib,xiC,xiD 。數學模型為：。數學模型為： x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4

10、A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D第二章第二章 線性規劃的對偶理論線性規劃的對偶理論與靈敏度分析與靈敏度分析改進單純型法對偶問題 對偶理論 目標函數值之間的關系 最優解之間的互補松弛關系 對偶單純形法對偶的經濟解釋靈敏度分析DUAL第一節 改進單純型法 需要求的幾個重要指標需要求的幾個重要指標 ，不需要完全的矩陣，不需要完全的矩陣變換就可求得。變換就可求得。需要求的：基可行解，需要求的：基可行解，非基變量，非基變量，XBB-1b B-1B-1P

11、k初始表為單位陣（初始基）確定主元素 -Y=-CBB-1 k 求求，確定換入變確定換入變量量xk ,計算計算B-1Pk ,計計算算，確定主元素確定主元素，對簡化單純型表作對簡化單純型表作旋轉變換旋轉變換簡化單純形表簡化單純形表Cj CCB XB B-1b X b A B-1b B-1ACCB B-1A Cj CB CS CN1CB XB B-1b XB XS XN1 CS XS b B E N1 CB XB B-1b E B-1 B-1N1 0 CSCB B-1 CN1CB B-1N1初始表初始表以以B為基的為基的單純形表單純形表當XS為松弛變量時CS=0,松弛變量檢驗數為Cj CB CNCB

12、 XB B-1b XB XN b B N B-1b E B-1N 0 CNCB B-1N 第二節 對偶問題 產品產品資源資源 I II 總總量量原料原料工時工時 2 3 4 6 100 120利潤利潤 6 4原問題：確定獲利最大的生產方案原問題：確定獲利最大的生產方案對偶問題：確定資源最低可接受對偶問題：確定資源最低可接受 出讓價格出讓價格建立兩問題的模型，對比其最優解，最優目標函數建立兩問題的模型，對比其最優解，最優目標函數值的關系。值的關系。 兩規劃最優目標函數值相等 為Z=CB B-1b 此時最優解XB= B-1b， Y= CB B-1(為原規劃松弛變量在最終表 中的檢驗數,即單純形乘子

13、）原始問題max z=C Xs.t.AXbX 0對偶問題min =Ybs.t. YACY 0maxbAC CTATbTminmnmn 第三節 對偶理論 一、對偶問題的性質1、對偶的對偶就是原始問題對偶的定義min=Ybs.t. YACY 0對偶的定義max =-Ybs.t. -YA-CY 02、其他形式問題的對偶原始問題約束條件的性質，影響對偶問題變量的性質。原始問題變量的性質，影響對偶問題約束條件的性質。min =Ybs.t. YAC Y 0min =Ybs.t. YAC Y :unrmin =Ybs.t. YAC Y 0原問題（或對偶問題）原問題（或對偶問題）對偶問題（或原問題）對偶問題（

14、或原問題）目標目標maxZ目標目標min變量變量（n個）個）00無約束無約束約束約束（n個）個）=約束約束（m個）個）=變量變量（m個）個）00無約束無約束min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max =6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unrq原始問題變量的個數(3)等于對偶問題約束條件的個

15、數(3)； 原始問題約束條件的個數(4)等于對偶問題變量的個數(4)。q原始問題變量的性質影響對偶問題約束條件的性質。 原始問題約束條件的性質影響對偶問題變量的性質。二、原始對偶關系1、可行解的目標函數值之間的關系 設XF、YF分別是原始問題和對偶問題的可行解z=C XF YF AXF YF b=2、最優解的目標函數值之間的關系 設Xo、Yo分別是原始問題和對偶問題的最優解 z=C Xo=Yo AXo=Yo b=Ymax z=CXs.t.AX+XS=bX, XS 0min =Ybs.t. YA-YS=CY, YS 0 YSX=0Y XS=0ATY-EYsCmn=nXA EXsb=nmm3、基解

16、與檢驗數之間的關系 單純形表和對偶 max z=C Xs.t. AX+XS=b X, XS0min =Yb s.t. YA -YS=C Y, YS0min =Yb s.t. YA C Y0對偶問題max z=C Xs.t. AX b X 0原始問題引進松弛變量引進松弛變量 X XS B-1b B-1A B-1 -YS -Y z X XS C 0 b A E max z=C Xs.t. AX+XS=b X, XS0min Y=Yb s.t. YA -YS= C Y, YS0 X XS B-1b B-1A B-1 C-CB B-1A -CB B-1 Y =CB B-1YS = YA Cy1. yi

17、 . ym ym+1 . ym+j . yn+m x1 . xj . xn xn+1 xn+i xn+m 對偶問題的變量 對偶問題的松弛變量 原始問題的變量 原始問題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于0，另一個一定等于0第四節 對偶單純形法 把對其對偶問題運用單純型算法的計算步驟反應在對原問題的求解步驟上面。在原問題初始表檢驗數0,B-1b為非可行解的時候可用。通常不單獨使用，運用與靈敏度分析時候較多。如何從最優單純形表中讀出對偶問題的解（1） x1x2x3x4x5x6x7x5 * 100 x6 *0 10 x7 *00 1

18、 x1x2x3x4x5x6x7初始單純形表最優單純形表 *000 -y4-y5-y6-y7-y1-y2-y3-ATY EYs -Cmn=nXA EXsb=nmmMin Z = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 標準化：標準化： Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0CI - 2 - 3 - 4 0 0 CB

19、XB b X1 X2 X3 X4 X5 0 X4 - 3 - 1 - 2 - 1 1 0 0 X5 - 4 - 2 1 - 3 0 1 j - 2 - 3 - 4 0 0 0 X4 - 1 0 - 5 / 2 1 / 2 1 - 1 / 2 - 2 X1 2 1 - 1 / 2 3 / 2 0 - 1 / 2 j 0 - 4 - 1 0 - 1 - 3 X2 2 / 5 0 1 - 1 / 5 - 2 / 5 1 / 5 - 2 X1 1 1 / 5 1 0 7 / 5 - 1 / 5 - 2 / 5 j 0 0 - 9 / 5 - 8 / 5 - 1 / 5 對偶單純形法對偶單純形法 cj3

20、 4 0 0 0CB XB by1 y2 y3 y4 y50 y3 20 y4 30 y5 41 2 1 0 01 - 1 0 1 01 3 0 0 13 4 0 0 04 y2 1 0 y4 40 y5 1 1 0 05/25/2 0 1 0- 0 3/2 3/2 0 11 0 -2 0 0和單純形法的比較和單純形法的比較0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa. t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn12121112222111、原始問題是利潤最大化的生產計劃問題單位產品的利潤（元/件）產品產量（件

21、）總利潤（元）資源限量（噸）單位產品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）2、對偶問題0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayat sybybybw資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優解y1、y2、.、ym稱為m種資源的影子價格（Shadow Price）原始和對偶問題都取得最優解時，最大利潤 max z=min y對偶問題是資源定價問題，對偶問題的最優解y1、y2、.、ym稱為m種資源的影子價格（Sh

22、adow Price）影子價格為當bi有單位增量，若原最終優基不變，總收益Z的變化，也可以說yi是對第i種資源的一種價格估計，由于影子價格是指資源增加時對最優收益的貢獻，所以又稱它為資源的機會成本或者邊際產出當市場價格低于影子價格時，企業應該買進資源用于擴大生產，高于影子價格時，企業應該將已有資源賣掉。影子價格的計算 一個不起作用約束的影響價格總為0,一個起作用約束的影子價格在資源在一定范圍內變化時是不變的。這個變化范圍就是關于資源限量bi的靈敏度不起作用的約束是對最優解而言，該約束的松弛變量 的值不為0起作用的約束是是對最優解而言，該約束的松弛變量 的值為0 x2=0 x1=0 x3=0 x

23、4=0OABC不起作用約束不起作用約束,影子價格為影子價格為0起作用約束，起作用約束，影子價格不為影子價格不為0 進一步理解最優單純形表中各元素的含義進一步理解最優單純形表中各元素的含義 考慮問題考慮問題 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0 引入引入 m 個松弛變量后，通過計算得到最優單純形表。應個松弛變量后，通過計算得到最優單純形表。應 -1 -1

24、能夠找到最優基能夠找到最優基 B的逆矩陣的逆矩陣 B ，以及，以及 B N，檢驗數等。，檢驗數等。 c1cn00CBXBx1xnxn+1xn+mi0 xn+1b1a11a1n1010 xn+2b2a21a2n0020 xn+mbmam1amn01m-zfc1cn00c1 cn cn+1 cn+m CB XB x1 xn xn+1 xn+m i ci1 xi1 b1 a11 a1n a1n+1 a1n+m 1 ci2 xi2 b2 a21 a2n a2n+1 a2n+m 2 Cim xim bm am1 amn amn+1 amn+m m -z f 1 n n+1 n+m 最優單純形表最優單純形

25、表B-1cB B -1EO A,b,C變化時對最優解的影響，最優解（最優基）不變，A,b,C的變化范圍以下作圖看看C,b變化對最優解的影響 x2=0 x1=0 x3=0 x4=0OABCC的變化等值線斜率發生變化，旋轉 x2=0 x1=0 x3=0 x4=0OABCb的變化約束對應直線的截距變化，平移 思考，A的變化將如何影響最優解。 例子：兩種產品由三種原料混合而成，A包括原料一60%，原料二40%，B包括原料一50%，原料二10%，原料三40%，原料一、二、三限量為11250,4000,6000（噸）.試建立模型，求解。A每噸25美元，B每噸10美元maxZ=25x1+10 x20.6x1

26、+0.5x2120000.4x1+0.1x240000.4x26000 x1,x20原料原料2的約束的約束原料原料1的約束的約束原料原料3的約束的約束 當市場價格低于影子價格時，企業應該買進資源用于擴大生產，高于影子價格時，企業應該將已有資源賣掉。 兩類問題：一、已知變化，求新最優解1、增廣陣( b, A )的變化。包括改變約束、增減變量，增減約束。主要充分利用原最終表信息得到一新表，在新表基礎上選擇適當方法變化得新最優解。 比較 原最終表 B-1( b , A ) 新表 B-1( b+b , A+A ) = B-1 ( b+b , P1+P1 ， P2+P2 Pn+Pn）=原最終表(B-1b

27、 , B-1P1 , B-1P2 B-1 Pn） 2、C的變化 僅對產生影響產生的新表 可以分為四種情況： 1）已是最優解 2）單純形法繼續求解 3）對偶單純形法繼續求解 4）人工變量法或保持原有最有基方法繼續求解二、未知變化，保持原最優基，求變化范圍 CjCCB XB B-1b X bA B-1b B-1ACCB B-1A CjCCB XB B-1b X bA B-1b B-1ACCB B-1A 原最終表原最終表新表新表原問題新問題CjCCB XB B-1b X b+bA+A B-1b+ B-1b B-1 A+ B-1 A CCB B-1A CjCCB XB B-1b X b+bP1+P1

28、. Pn+Pn B-1b+ B-1bB-1P1 + B-1 P1 . B-1Pn + B-1 PnCCB B-1A 價值系數價值系數C發生變化：發生變化： m考慮檢驗數考慮檢驗數 j = cj - cri arij j = 1,2,n i = 1 1、若、若 ck 是非基變量的系數：是非基變量的系數： 設設 ck 變化為變化為 ck + ck k= ck + ck - cri arik = k+ ck 只要只要 k 0 ，即，即 ck - k ，則最優解不變；否則，將最則最優解不變；否則，將最優單純形表中的檢驗數優單純形表中的檢驗數 k 用用 k取代，繼續單純形法的表取代，繼續單純形法的表格計

29、算格計算。 例例: Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0 例：最優單純形表例：最優單純形表從表中看到從表中看到 3 = C3 +CC3 - （C2 * a13 + C1* a23 ） 可得到可得到 CC3 9/5 時，原最優解不變。時，原最優解不變。CI-2-3-400CBXBbX1X2X3X4X5-3 X22 /501-1 /5-2 /51 /5-2 X11 1 /5107 /5-1 /5-2 /5j00-9

30、/5-8 /5-1 /5CI-2-3-4+c300CBXBbX1X2X3X4X5-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5 2、若、若 cs 是基變量的系數：是基變量的系數： 設設 cs 變化為變化為 cs + cs ，那么，那么 j= cj - cri arij - ( cs + cs ) asj = j - cs asj ，對所有非基變，對所有非基變量量 i s 只要對所有非基變量只要對所有非基變量 j 0 ，即，即 j cs asj ，則最則最優解不變；否則，將最優單純形表中的檢驗數優解不變；否則，將最優單純

31、形表中的檢驗數 j 用用 j取代，取代，繼續單純形法的表格計算繼續單純形法的表格計算。 Max j / asj asj 0 cs Min j / asj asj 0 br Min-bi / air air 0 例、上例最優單純形表如下例、上例最優單純形表如下 0 0.25 0 這里這里 B-1 = -2 0.5 1 各列分別對應各列分別對應 b1、b2、b3 的的單一單一 0.5 -0.125 0 變化。因此，設變化。因此，設 b1 增加增加 4，則，則 x1 , x5 , x2 分別變為：分別變為： 4 + 0*4 = 4，4 + (-2)*4 = - 4 0，2 + 0.5*4 = 4用對

32、偶單純形法進一步求解，可得：用對偶單純形法進一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17C i 2 3 0 0 0 CB XB B X1 X2 X3 X4 X5 2 X1 4 1 0 0 1/4 0 0 X5 4 0 0 -2 1/2 1 3 X2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8 0 增加一個變量增加一個變量 增加變量增加變量 xn+1 則有相應的則有相應的 pn+1 ， cn+1 。那么，計算。那么，計算出出 B-1pn+1 n+1 = cn+1 - cri ari n+1 填入最優單純形表，若填入最優單純形表，若 n+1 0 則最優解不變；否則，則最優解不變；否則，進一步用單純形法求解。進一步用單純形法求解。例、前例增加例、前例增加 x6，p6 = ( 2, 6, 3 )T ，c6 = 5 。計算得到。計算得到Ci 2 3 0 0 0 5 CB XB b X1 X2 X3 X4 X5 X6 2 X1 4 1