運(yùn)籌學(xué)課件 (2)

1、OR11第一章 緒論w 1.1題解 Operations 漢語翻譯工作、操作、行動、手術(shù)、運(yùn)算Operations Research日本運(yùn)用學(xué) 港臺作業(yè)研究中國大陸運(yùn)籌學(xué)Operational Research原來名稱，意為軍事行動研究歷史淵源OR12緒論w 1.2 運(yùn)籌學(xué)的歷史 早期運(yùn)籌思想：田忌賽馬 丁渭修宮 沈括運(yùn)糧 Erlang 1917 排隊論 Harris 1920 存儲論 Levinson 1930 零售貿(mào)易 康脫洛維奇 1939 LP OR13OR14OR15OR16OR17OR18OR19OR110緒論w 1.2運(yùn)籌學(xué)的歷史 軍事運(yùn)籌學(xué)階段 德軍空襲 防空系統(tǒng) Blacket

2、t 運(yùn)輸船編隊 空襲逃避 深水炸彈 轟炸機(jī)編隊OR111緒論w 1.2運(yùn)籌學(xué)的歷史 管理運(yùn)籌學(xué)階段 戰(zhàn)后人員三分:軍隊、大學(xué)、企業(yè) 大學(xué)：課程、專業(yè)、碩士、博士 企業(yè)：美國鋼鐵聯(lián)合公司 英國國家煤炭局 運(yùn)籌學(xué)在中國：50年代中期引入 華羅庚推廣 優(yōu)選法、統(tǒng)籌法 中國郵遞員問題、運(yùn)輸問題 OR1121.3學(xué)科性質(zhì)應(yīng)用學(xué)科Morse&Kimball定義：運(yùn)籌學(xué)是為決策機(jī)構(gòu)在對其控制的業(yè)務(wù)活動進(jìn)行決策時提供的數(shù)量化為基礎(chǔ)的科學(xué)方法。Churchman定義：運(yùn)籌學(xué)是應(yīng)用科學(xué)的方法、技術(shù)和工具，來處理一個系統(tǒng)運(yùn)行中的問題，使系統(tǒng)控制得到最優(yōu)的解決方法。中國定義：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法

3、，對經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。OR1131.4定性與定量w 例：店主進(jìn)貨w 兩者都是常用的決策方法w 定性是基礎(chǔ)，定量是工具，定量為定性服務(wù)。w 定性有主觀性也有有效性，定量有科學(xué)性也有局限性。管理科學(xué)的發(fā)展，定量越來越多。但定量不可替代定性。OR1141.5運(yùn)籌學(xué)的模型w 模型：真實(shí)事物的模仿，主要因素、相互關(guān)系、系統(tǒng)結(jié)構(gòu)。w 形象模型：如地球儀、沙盤、風(fēng)洞w 模擬模型：建港口，模擬船只到達(dá)。學(xué)生模擬企業(yè)管理系統(tǒng)運(yùn)行。w 數(shù)學(xué)模型：用符號或數(shù)學(xué)工具描述現(xiàn)實(shí)系統(tǒng)。V=F（xi,yj,uk) G(xi,yj,uk)0OR1

4、151.6運(yùn)籌學(xué)的學(xué)科體系w 規(guī)劃論：線性規(guī)劃、非線性規(guī)劃|、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動態(tài)規(guī)劃w 圖論與網(wǎng)絡(luò)w 存儲論w 排隊論w 決策論w 對策論w 計算機(jī)仿真OR1161.7運(yùn)籌學(xué)的工作步驟w 確定問題w 搜集數(shù)據(jù)建立模型w 檢驗(yàn)?zāi)Ｐ蛍 求解模型w 結(jié)果分析w 結(jié)果實(shí)施OR1171.8運(yùn)籌學(xué)與計算機(jī)w 計算機(jī)為運(yùn)籌學(xué)提供解題工具。w 本書有現(xiàn)成的程序可以利用w 要學(xué)會解題的思路與方法，建立模型很重要。OR118第二章 線性規(guī)劃與單純形法w 2.1 LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟(jì)效益的優(yōu)化方法。LP有一組有

5、待決策的變量， 一個線性的目標(biāo)函數(shù)， 一組線性的約束條件。 OR1192.1.1 LP的數(shù)學(xué)模型 例題1生產(chǎn)計劃問題w 某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè) 備原材料9434510360200300利潤元/kg70120OR120例題1建模w 問題：如何安排生產(chǎn)計劃，使得獲利最多？w 步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：人力約束 9X1+4X2360 設(shè)備約束 4X1+5X2 200 原材料約束3X1+10X2 300 非

6、負(fù)性約束X10 X20OR121例題2配方問題w 養(yǎng)海貍鼠 飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：飼料VaVbVc價格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495營養(yǎng)要求70030200OR122例題2建模w 設(shè)抓取飼料I x1kg;飼料II x2kg;飼料III x3kgw 目標(biāo)函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5w 約束條件：3x2+2x2+x3+6x4+18x5 700營養(yǎng)要求： x1+0.5x2+0.2x3+2x4+0.5x5 30

7、 0.5x1+x2+0.2x3+2x4+0.8x5 =200用量要求： x1 50,x2 60,x3 50,x4 70,x5 40非負(fù)性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR123例題3：人員安排問題w 醫(yī)院護(hù)士24小時值班，每次值班8小時。不同時段需要的護(hù)士人數(shù)不等。據(jù)統(tǒng)計： 序號時段最少人數(shù)安排人數(shù)1061060X12101470X23141860X34182250X45220220X56020630 x6OR124例題3建模w 目標(biāo)函數(shù)：min Z=x1+x2+x3+x4+x5+x6w 約束條件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 2

8、0 x5+x6 30 x6+x1 60非負(fù)性約束：xj 0,j=1,2,6OR125歸納：線性規(guī)劃的一般模式w 目標(biāo)函數(shù)：max(min)Z=c1x1+c2x2+c3x3+cnxnw 約束條件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非負(fù)性約束：x1 0,x2 0,xn 0OR1262.1.2線性規(guī)劃圖解法w 由中學(xué)知識可知：y=ax+b是一條直線，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一條直線，以Z為參數(shù)的一族等值

9、線。 9x1+4x2 360 x1 360/9-4/9x2 是直線 x1=360/9-4/9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點(diǎn)，就是滿足所有約束條件的解，稱之為可行解。OR127例1圖示. 90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2OR128概念w 概念：1、可行解：滿足所有約束條件的解。2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。3、基解：

10、約束條件的交點(diǎn)稱為基解（直觀）4、基可行解：基解當(dāng)中的可行解。5、凸集：集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)均屬于這個集合。如：實(shí)心球、三角形OR129結(jié)論w 可行域是個凸集w 可行域有有限個頂點(diǎn)w 最優(yōu)值在可行域的頂點(diǎn)上達(dá)到w 無窮多解的情形w 無界解情形w 無解情形OR1302.1.3線性規(guī)劃的標(biāo)準(zhǔn)型w 代數(shù)式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,nOR131線性規(guī)劃的標(biāo)準(zhǔn)型w 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=

11、1,2,nj=1nnj=1OR132線性規(guī)劃的標(biāo)準(zhǔn)型w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) Tnj=1OR133線性規(guī)劃的標(biāo)準(zhǔn)型w 矩陣式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amnOR134標(biāo)準(zhǔn)型的特征w 目標(biāo)函數(shù)極大化w 約束條件為等式w 決策變量非負(fù)OR135非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型w 目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化： minZ=max(Z) ，一個數(shù)的極小化等價于其相反數(shù)的極大化。w

12、 不等式約束的轉(zhuǎn)化： aijxjbi 加入松弛變量 aijxjbi 減去剩余變量w 非正變量：即xk 0 則令xk = xk 自由變量：即xk無約束，令xk= xkx”kOR136非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5OR137非標(biāo)準(zhǔn)型轉(zhuǎn)化舉例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9

13、 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3無約束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR1382.1.4基可行解w基的概念基的概念：如前所述LP標(biāo)準(zhǔn)型和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩陣式：maxZ=CX AX=b X 0 約束方程的系數(shù)矩陣A的秩為m，且m0 =bL/ aLk 。 這時原基變量XL=0，由基變量變成非基變量，aLk處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱之為樞軸元素j 0O

14、R153單純形法解題舉例單純形表的格式： CjC1 C2 Cn i CBXBbx1 x2 . xn C1 C2 Cmx1x2xmb 1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR154 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5j 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.1

15、30.7620100j3600 34 0 0 0 -12070120X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2OR155單純型法的基本思路單純型法的基本思路確確定定初初試試基基礎(chǔ)礎(chǔ)可可行行解解求求最最優(yōu)優(yōu)解解的的目目標(biāo)標(biāo)函函數(shù)數(shù)值值確確定定改改善善方方向向求求新新的的基基礎(chǔ)礎(chǔ)可可行行解解檢檢查查是是否否為為最最優(yōu)優(yōu)解解？是是否否OR156例二、試列出下面線性規(guī)劃問題的初始單純型表例二、試列出下面線性規(guī)劃問題的初始單純型表0,12023310032.244540)(max3

16、21321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb404524000 x4100231100 x512033201 OBJ = 0 zj00000 cj- -zj40452400OR157關(guān)于檢驗(yàn)數(shù)的數(shù)學(xué)解釋關(guān)于檢驗(yàn)數(shù)的數(shù)學(xué)解釋w 設(shè)設(shè) B 是初始可行基，則是初始可行基，則目標(biāo)函數(shù)可寫為兩部分目標(biāo)函數(shù)可寫為兩部分(1)w 約束條件也寫為兩部分，約束條件也寫為兩部分，經(jīng)整理得經(jīng)整理得 XB 的表達(dá)式的表達(dá)式(2)，注意注意 XB中含有非基變量中含有非基變量作參數(shù)作參數(shù)w 把把 XB 代入目標(biāo)函數(shù)，整代入目標(biāo)函數(shù)，整理得到理得到(3)式式w 第第 j 個非基變量的

17、機(jī)會成個非基變量的機(jī)會成本如本如(4)式式w 若有若有cj zj0, 則未達(dá)到最則未達(dá)到最優(yōu)優(yōu)(5) (4) ) 3 ( )()()(2) )(1) )(1jjmiijijzcaczxfxf檢驗(yàn)數(shù)機(jī)會成本NN1BN1BNN1BNNNN1BNNBBNNBBNNXABCCbBCXAbBCXCXAbBXXAbBXbBXXAXCXCOR158標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法1 找初試基礎(chǔ)可行基找初試基礎(chǔ)可行基n對于對于(max, )，松弛變量對應(yīng)的列構(gòu)成一個單位陣，松弛變量對應(yīng)的列構(gòu)成一個單位陣n若有若有 bi 0 中找最大者，選中者稱為中找最大者，選中者稱為入變量入變量， xj* n第第j*列稱

18、為列稱為主列主列4 確定確定入變量入變量的最大值和的最大值和出變量出變量n最小比例原則最小比例原則 0min*ijijiiaabOR159標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法4 確定確定入變量入變量的最大值和的最大值和出變量出變量n設(shè)第設(shè)第 i* 行使行使 最小，則第最小，則第 i* 行對應(yīng)的基變量稱為行對應(yīng)的基變量稱為出出變量變量，第，第 i* 行稱為行稱為主行主行5 迭代過程迭代過程n主行主行 i* 行與行與主列主列 j* 相交的元素相交的元素ai*j* 稱為稱為主元主元，迭代，迭代以以主元主元為中心進(jìn)行為中心進(jìn)行n迭代的實(shí)質(zhì)是線性變換，即要將迭代的實(shí)質(zhì)是線性變換，即要將主元主元 ai*j

19、*變?yōu)樽優(yōu)?，主主列列上其它元素變?yōu)樯掀渌刈優(yōu)?，變換步驟如下：，變換步驟如下：(1)變換主行變換主行nmjaaajijiji, 2 , 1*OR160標(biāo)準(zhǔn)型的單純型算法5 迭代過程(2)變換主列變換主列除除主元主元保留為保留為1，其余都置，其余都置0(3)變換非主行、主列元素變換非主行、主列元素 aij (包括包括 bi)四角算法公式：四角算法公式：數(shù)據(jù)表示當(dāng)前單純型表中的的數(shù)據(jù)表示上一個單純型表中 , , *ijiijijiijjiijijjiijiiiababaaaaaaabbbOR161標(biāo)準(zhǔn)型的單純型算法標(biāo)準(zhǔn)型的單純型算法5 、迭代過程(4)變換變換CB，XB(5)計算目標(biāo)函數(shù)、機(jī)

20、會成本計算目標(biāo)函數(shù)、機(jī)會成本 zj 和檢驗(yàn)數(shù)和檢驗(yàn)數(shù) cj zj 6、返回步驟 2aijai*jaij*ai*j*主主行行主主列列主主元元四四角角算算法法圖圖示示OR162例二、例二、 單純型表的迭代過程單純型表的迭代過程x1x2x3x4x5序序號號CBXBb4 04 52 400bi/aij*0 x41 0 02(3 )110(3 3 .3 )0 x51 2 0332014 0 O B J = 000000I初初始始解解cj- - zj4 04 52 40045x2100/32/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -z

21、j1009 1504 5x22 001 1 /31 2 /34 0 x12 0101 11 O B J = 1 7 0 04 04 52 551 0III最最優(yōu)優(yōu)解解cj- - zj00 1 5 1 0OR163單純型表中元素的幾點(diǎn)說明單純型表中元素的幾點(diǎn)說明n任何時候，基變量對應(yīng)的列都構(gòu)成一個單位矩陣任何時候，基變量對應(yīng)的列都構(gòu)成一個單位矩陣n當(dāng)前表中的當(dāng)前表中的 b 列表示當(dāng)前基變量的解值，通過變換列表示當(dāng)前基變量的解值，通過變換 B 1 b 得得到到 (資源已變成產(chǎn)品資源已變成產(chǎn)品)n當(dāng)前非基變量對應(yīng)的向量可通過變換當(dāng)前非基變量對應(yīng)的向量可通過變換 B 1 AN 得到，得到， 表示第表示

22、第 j 個變量對第個變量對第 i 行對應(yīng)的基變量的消耗率行對應(yīng)的基變量的消耗率n非基變量的機(jī)會成本由非基變量的機(jī)會成本由 給出給出n注意基變量所對應(yīng)的行注意基變量所對應(yīng)的行x1x2x3x4x5序序號號CBXBb40452400bi/aij*45x2100/32/311/31/30500 x520(1)01 11(20) OBJ = 1500304515150IIcj- -zj1009 150miijijacz1 OR164w 單純型法舉例之三：4321532infxxxxM0,412432642:.432143143214321xxxxxxxxxxxxxxxts4321532xxxxMaxZ0

23、,41232642:.765432174316432154321xxxxxxxxxxxxxxxxxxxxxtsOR165w單純型表如下：w CB XB b 2 1 -3 5 0 0 0w X1 X2 X3 X4 X5 X6 X7 w 0 X5 6 1 2 4 -1 1 0 0w 0 X6 12 2 3 -1 1 0 1 0 w 0 X7 4 1 0 1 1 0 0 1w -z 0 2 1 -3 5 0 0 0 w 0 X5 10 2 2 5 0 1 0 1w 0 X6 8 1 3 -2 0 0 1 -1w 5 X4 4 1 0 1 1 0 0 1w -z -20 -3 1 -8 0 0 0 -

24、5 w 0 X5 14/3 4/3 0 19/3 0 1 -2/3 5/3 w 1 X2 8/3 1/3 1 -2/3 0 0 1/3 -1/3 w 5 X4 4 1 0 1 1 0 0 1w -z -68/3 -10/3 0 -22/3 0 0 -1/3 -14/3OR166用單純型法求解線性規(guī)劃問題用單純型法求解線性規(guī)劃問題w 例一例一：w Max z=3 x1+2 x2 Max z=3 x1+2 x2 0,5332:.0,5332:.4321421321212121xxxxxxxxxxt sxxxxxxt sOR167w CB XB b 3 2 0 0w X1 X2 X3 X4w 0 X

25、3 3 2 -3 1 0 1.5w 0 X4 5 -1 1 0 1 -w Z = 0 3 2 0 0w 3 X1 1.5 1 -3/2 1/2 0 w 0 X4 6.5 0 -1/2 1/2 1w z = 4.5 0 13/2 -3/2 0OR168a21與a22都小于0，原問題沒有最優(yōu)解OR169用單純型法求解線性規(guī)劃問題用單純型法求解線性規(guī)劃問題w 例二：例二：32122xxxMaxz0,936212:.32121321321xxxxxxxxxxxt s0,936212:.65432162153214321xxxxxxxxxxxxxxxxxt s3212xxxMaxzOR170w CB X

26、B b 1 -2 1 0 0 0w X1 X2 X3 X4 X5 X6 w 0 X4 12 1 1 1 1 0 0 12w 0 X5 6 2 1 -1 0 1 0 3w 0 X6 9 -1 3 0 0 0 1 -w z=0 1 -2 1 0 0 0 w 0 X4 9 0 1/2 3/2 1 -1/2 0 6w 1 X1 3 1 1/2 -1/2 0 1/2 0 -w 0 X6 12 0 7/2 -1/2 0 1/2 1 - w z =3 0 -5/2 3/2 0 -1/2 0 w 1 X3 6 0 1/3 1 2/3 -1/3 0 w 1 X1 6 1 2/3 0 1/3 1/3 0 w 0

27、X6 15 0 11/3 0 1/3 1/3 1 w z =12 0 -3 0 -1 0 0 Tx1500606*OR171w X5為非基變量，其檢驗(yàn)數(shù)為為非基變量，其檢驗(yàn)數(shù)為0，可能存在無窮多最優(yōu)解可能存在無窮多最優(yōu)解做進(jìn)一步迭代，令做進(jìn)一步迭代，令X5為進(jìn)基為進(jìn)基,w 得另一最優(yōu)解為：得另一最優(yōu)解為：w 解得無窮多最優(yōu)解在端點(diǎn)為解得無窮多最優(yōu)解在端點(diǎn)為 的線段上，最優(yōu)解為：的線段上，最優(yōu)解為：Tx91801200* TT606,120012*zOR1722.3單純形法的進(jìn)一步討論w 一般線性規(guī)劃問題的處理一般線性規(guī)劃問題的處理 對于一般線性規(guī)劃標(biāo)準(zhǔn)形式問題：對于一般線性規(guī)劃標(biāo)準(zhǔn)形式問題：

28、考慮一般問題：考慮一般問題： bi 0 ， i = 1 , , m 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 主要是討論初始基本可行解不明顯時，常用的方法。主要是討論初始基本可行解不明顯時，常用的方法。OR173w 引入人工變量 xn+i 0 i = 1 , , m ; 得到，s.t. a11 x1 + a12 x2 + + a1n xn +

29、xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0 顯然，顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，對應(yīng)的基是單位矩陣。OR174w 大大M法：法： 引入人工變量 xn+i 0 i = 1 , , m ; 充分大正數(shù) M 。 得到， Max z = c1 x1 + c2 x2 + + cn xn -M xn+1 - - M xn+m s.t. a11 x1 +

30、 a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0顯然，顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，對應(yīng)的基是單位矩陣。w 結(jié)論：若得到的最優(yōu)解滿足結(jié)論：若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的最優(yōu)解；否則，原問題無可行解。OR175w 兩階段法：兩階段法：引入人工變量 xn+i 0，i

31、 = 1 , , m；構(gòu)造， Max z = - xn+1 - xn+2 - - xn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn + xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0w 第一階段求解上述問題：第一階段求解上述問題：顯然，顯然，xj = 0 j=1, , n ; xn+i = bi i =1 , , m 是基本可行解，對應(yīng)的基是單位矩陣。w 結(jié)論：若得到的最優(yōu)解滿足結(jié)論：若

32、得到的最優(yōu)解滿足 xn+i = 0 i = 1 , , m 則是原問題的基本可行解；否則，原問題無可行解。w 得到原問題的基本可行解后，第二階段求解原問題。得到原問題的基本可行解后，第二階段求解原問題。OR176例：（LP） Max z = 5 x1 + 2 x2 + 3 x3 - x4 s.t. x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 0w 大M法問題（LP - M） Max z = 5 x1 + 2 x2 + 3 x3 - x4 - M x5 - M x

33、6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0OR177OR178 得到最優(yōu)解：(25/3，10/3，0，11)T 最優(yōu)目標(biāo)值：112/3OR179w 兩階段法兩階段法 ：第一階段問題（：第一階段問題（LP - 1） Max z = - x5 - x6 s.t. x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x

34、4 = 26 x1 , x2 , x3 , x4 , x5 , x6 0OR180第一階段第一階段 （LP - 1）OR181 得到原問題的基本可行解：得到原問題的基本可行解： (0，15/7，25/7，52/7)T OR182第二階段第二階段 把基本可行解填入表中把基本可行解填入表中OR183w 得到原問題的最優(yōu)解：得到原問題的最優(yōu)解：(25/3，10/3，0，11)T w 最優(yōu)目標(biāo)值：最優(yōu)目標(biāo)值：112/3OR184例例2：（一）（一）大大M法的求解過程法的求解過程0,46 2.7810)(min32132121321xxxxxxxxtsxxxxf0,46 2.7810)(min32132

35、121321xxxxxxxxtsxxxxf0,46 2. .7810)(min32132121321xxxxxxxxtsxxxxfOR185劃為標(biāo)準(zhǔn)型及加入人工變量后劃為標(biāo)準(zhǔn)型及加入人工變量后0,4 6 2. .)7810max()(max654321532164216321xxxxxxxxxxxxxxt sMxxxxxfOR186OR187w 答：最優(yōu)解為答：最優(yōu)解為 x1=2, x2=2, x3=0。OR188（二）二階段法的求解過程（二）二階段法的求解過程w 第一階段的任務(wù)是將人工變量盡快迭代出第一階段的任務(wù)是將人工變量盡快迭代出去，從而找到一個沒有人工變量的基礎(chǔ)可去，從而找到一個沒有人

36、工變量的基礎(chǔ)可行解行解w 第二階段以第一階段得到的基礎(chǔ)可行解為第二階段以第一階段得到的基礎(chǔ)可行解為初始解，采用原單純型法求解初始解，采用原單純型法求解w 若第一階段結(jié)束時，人工變量仍在基變量若第一階段結(jié)束時，人工變量仍在基變量中，則原問題無解中，則原問題無解OR189用二階段法求解例用二階段法求解例2的第一階段的第一階段OR190用二階段法求解例用二階段法求解例2的第二階段的第二階段OR191LP應(yīng)用舉例之一w 例1合理下料問題 料長7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關(guān)鍵：設(shè)變量。OR192方案如下： 方案 1 2 3 4 5 6 7 8 料型 2.9米 1

37、2 0 1 0 1 0 0 2.1米 0 0 2 2 1 1 3 0 1.5米 3 1 2 0 3 1 0 4 合計 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 殘料 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4OR193應(yīng)用舉例之二 w 例2混合配方問題A、B、C、D四種原料配制三種產(chǎn)品，三類約束：技術(shù)要求、原料限量、市場容量。已知產(chǎn)品價格和原料價格，求利潤最大的配方。關(guān)鍵：設(shè)變量。OR194應(yīng)用舉例之三w 例3滾動投資問題茲有100萬元閑錢，投資方向有四： 第四年第一年第二年第三年A項(xiàng)目110%B項(xiàng)目135%C項(xiàng)目125%D項(xiàng)目104%第五年各年投資什么項(xiàng)

38、目，使第五年末資本總額為最大？OR195應(yīng)用舉例之四w 例4動態(tài)生產(chǎn)計劃問題 工廠做n個月的生產(chǎn)計劃，第j月需求量dj、正常生產(chǎn)能力aj、加班生產(chǎn)能力bj、正常生產(chǎn)成本cj、加班生產(chǎn)成本ej、庫存能力為I、庫存費(fèi)用hj，設(shè)期初、期末庫存為零。求費(fèi)用最小的生產(chǎn)計劃。 設(shè)第月正常生產(chǎn)xj件，加班生產(chǎn)件yj，存儲zj件。則： 本期生產(chǎn)+上期庫存-本期庫存=本期需求OR196第三章 對偶問題與靈敏度分析w要求： 了解LP對偶問題的實(shí)際背景 了解對偶問題的建立規(guī)則與基本性質(zhì) 掌握對偶最優(yōu)解的計算及其經(jīng)濟(jì)解釋 掌握LP的靈敏度分析 OR1973.1 對偶問題w3.1.1 對偶問題的提出 回顧例題1： 現(xiàn)在

39、計劃不生產(chǎn)A、B兩產(chǎn)品，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料 9 4 3 4 5 10 360 200 300單位利潤 70 120OR198對偶模型w 設(shè)每個工時收費(fèi)Y1元，設(shè)備臺時費(fèi)用Y2元，原材料附加費(fèi)Y3元。 出租收入不低于生產(chǎn)收入： 9y1+4y2+ 3y3 70 4y1+5y2+10y3 120 目標(biāo)：=360y1+200y2+300y3 出租收入越多越好？至少不低于某數(shù)OR199原問題與對偶問題之比較原問題： 對偶問題：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+ 4X2360 9

40、y1+4y2+ 3y3 70 4X1+ 5X2 200 4y1+5y2+10y3 1203X1+10X2 300 y1 0, y2 0, y3 0X10 X20OR11003.1.2對偶規(guī)則原問題一般模型： 對偶問題一般模型：maxZ=CX min =Yb AX b YA C X 0 Y 0OR1101比較兩形式知：比較兩形式知：TmnmTnbbbbcccCyyyYxxxX),(),(),(),(21212121上上兩兩式式中中mnmmnnaaaaaaaaaA212222111211OR1102對偶規(guī)則w 原問題有m個約束條件，對偶問題有m個變量w 原問題有n個變量，對偶問題有n個約束條件w

41、原問題的價值系數(shù)對應(yīng)對偶問題的右端項(xiàng)w 原問題的右端項(xiàng)對應(yīng)對偶問題的價值系數(shù)w 原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣w 原問題的約束條件與對偶問題方向相反w 原問題與對偶問題優(yōu)化方向相反OR1103標(biāo)準(zhǔn)型的對偶變換0, 15232 25322. .432max4321432143214321xxxxxxxxxxxxtsxxxxZ目目標(biāo)標(biāo)0,4233322212.1525min212121212121yyyyyyyyyytsyyw目標(biāo)函數(shù)為：OR1104非標(biāo)準(zhǔn)型的對偶變換0,510342023.54max .2 1221212121xxxxxxxxtsxxZ不限原線性規(guī)劃問題例 0, 5

42、51033420223.554max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxZ型標(biāo)準(zhǔn)問題化為不限經(jīng)整理得令32132132132132313,0,532443.51020min: yyyyyyyyytsyyywyyy0,532532443. .551020min 323121323121323121323121323121yyyyyyyyyyyyyyyytsyyyyw則應(yīng)用標(biāo)準(zhǔn)型對偶變換規(guī)OR1105對偶規(guī)則. 原問題 對偶問題目標(biāo)函數(shù) max min 目標(biāo)函數(shù)約束條件 = 變量無約束 變量符號 無約束 約束條件=OR1106對偶變換的規(guī)則原原

43、 問問 題題 (max, )對對 偶偶 問問 題題 (min, )技技 術(shù)術(shù) 系系 數(shù)數(shù) 矩矩 陣陣 A技技 術(shù)術(shù) 系系 數(shù)數(shù) 矩矩 陣陣AT價價 值值 系系 數(shù)數(shù) C右右 端端 項(xiàng)項(xiàng) b右右 端端 項(xiàng)項(xiàng) b價價 值值 系系 數(shù)數(shù) C第第i行行 約約 束束 條條 件件 為為 型型對對 偶偶 變變 量量 yi 0第第i行行 約約 束束 條條 件件 為為 型型對對 偶偶 變變 量量 yi 0第第i行行 約約 束束 條條 件件 為為 = 型型對對 偶偶 變變 量量 yi 不不 限限決決 策策 變變 量量 xj 0第第j行行 約約 束束 條條 件件 為為 型型決決 策策 變變 量量 xj 0第第j行行

44、 約約 束束 條條 件件 為為 型型決決 策策 變變 量量 xj 不不 限限第第j行行 約約 束束 條條 件件 為為 = 型型OR1107w 約束條件的類型與非負(fù)條件對偶約束條件的類型與非負(fù)條件對偶w 非標(biāo)準(zhǔn)的約束條件類型對應(yīng)非正常的非負(fù)非標(biāo)準(zhǔn)的約束條件類型對應(yīng)非正常的非負(fù)條件條件w 對偶變換是一一對應(yīng)的對偶變換是一一對應(yīng)的OR1108對偶規(guī)則簡捷記法w原問題標(biāo)準(zhǔn)則對偶問題標(biāo)準(zhǔn)w原問題不標(biāo)準(zhǔn)則對偶問題不標(biāo)準(zhǔn)w例題2 max =7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 3 2x1+x2-4x3+x4+3x5 7 y1 +3y3 2 x1+ 2x3 -x

45、4 4 -4y1+ 2y2 -6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 0 x1，x2，x3 0; 3y1 +y3=1 x4 0;x5無限制 y1 0y2 0y3 無約束 OR1109寫出下列問題的對偶規(guī)劃寫出下列問題的對偶規(guī)劃w 例例1:2153) 1 (xxMaxz0,252:.212121xxxxxxt s2125infyyM0,5232:.212121yyyyyyt sOR1110w 例2：3212xxxMaxz無符號限制， ,63282:.32132121xxxxxxxxt s2168infyyM無符號限制2122121,132212:.yyyyyyytsOR

46、1111w 例3：4321432xxxxMaxz無符號限制4231432143214321, 0,1067912857653:.xxxxxxxxxxxxxxxxtsOR1112w 答案:3211085infyyyM0,4653372971126:.321321321321321yyyyyyyyyyyyyyyts無符號限制OR1113w 例4：5432187523infxxxxxM2551025222332643:.2143143215432xxxxxxxxxxxxxtsOR1114w 變形為：5432187523infxxxxxM2551025222332643:.22114314321543

47、2xxxxxxxxxxxxxxxtsOR1115w 對偶規(guī)劃為：7654321255102526yyyyyyyMaxz0,;847235232332:.754321132132176215432yyyyyyyyyyyyyyyyyyyyyts無符號限制OR1116 3.2 線性規(guī)劃的對偶定理1 弱對偶定理定理 對偶問題(min)的任何可行解Y0，其目標(biāo)函數(shù)值總是不小于原問題(max)任何可行解X0的目標(biāo)函數(shù)值 為了便于討論，下面不妨總是假設(shè)為了便于討論，下面不妨總是假設(shè)0XbAXCX. .max :tsZ原問題0YCYAYb. .min :tsw對偶問題#CXAXYbY0YCAY0XbAXYX

48、., :0000000000容容易易看看出出有有故故有有題題的的可可行行解解分分別別為為原原問問題題和和對對偶偶問問由由于于證證OR1117 弱弱對偶定理推論對偶定理推論w max問題的任何可行解目標(biāo)函數(shù)值是其對偶問題的任何可行解目標(biāo)函數(shù)值是其對偶min問題目問題目標(biāo)函數(shù)值的下限；標(biāo)函數(shù)值的下限； min問題的任何可行解目標(biāo)函數(shù)值問題的任何可行解目標(biāo)函數(shù)值是其對偶是其對偶max問題目標(biāo)函數(shù)值的上限問題目標(biāo)函數(shù)值的上限w 如果原如果原max(min)問題為無界解，則其對偶問題為無界解，則其對偶 min (max)問題無可行解問題無可行解w 如果原如果原max(min)問題有可行解，其對偶問題有可

49、行解，其對偶 min (max)問問題無可行解，則原問題為無界解題無可行解，則原問題為無界解w 注：存在原問題和對偶問題同時無可行解的情況注：存在原問題和對偶問題同時無可行解的情況OR11182 最優(yōu)解判別最優(yōu)解判別定理定理定理定理 若原問題的某個可行解若原問題的某個可行解X0的目標(biāo)函數(shù)值與對偶問題的目標(biāo)函數(shù)值與對偶問題某個可行解某個可行解Y0的目標(biāo)函數(shù)值相等，則的目標(biāo)函數(shù)值相等，則X0, Y0分別是相分別是相應(yīng)問題的最優(yōu)解應(yīng)問題的最優(yōu)解證：由弱對偶定理推論證：由弱對偶定理推論1，結(jié)論是顯然的。，結(jié)論是顯然的。 即即CX0 = Y0b CX, Y0b = CX0 Yb 。 證畢。證畢。3 主對

50、偶主對偶定理定理定理定理 如果原問題和對偶問題都有可行解，則它們都有最如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證：由弱對偶定理推論證：由弱對偶定理推論1可知，原問題和對偶問題的目標(biāo)可知，原問題和對偶問題的目標(biāo)函數(shù)有界，故一定存在最優(yōu)解。函數(shù)有界，故一定存在最優(yōu)解。 現(xiàn)證明定理的后一句話。現(xiàn)證明定理的后一句話。 OR1119 主對偶主對偶定理的證明定理的證明 證：現(xiàn)證明定理的后一句話。證：現(xiàn)證明定理的后一句話。 設(shè)設(shè) X0 為原問題的最優(yōu)解，它所對應(yīng)的基矩陣是為原問題的最優(yōu)解，它所對應(yīng)的基矩陣是 B， X0= B 1

51、 b，則其檢驗(yàn)數(shù)滿足，則其檢驗(yàn)數(shù)滿足 C CBB 1A 0 令令 Y0= CBB 1，則有，則有 Y0 A C。 顯然顯然Y0為對偶問題的可行解。因此有對偶問題目標(biāo)函為對偶問題的可行解。因此有對偶問題目標(biāo)函數(shù)值，數(shù)值， w(Y0)=Y0b= CBB 1 b 而原問題最優(yōu)解的目標(biāo)函數(shù)值為而原問題最優(yōu)解的目標(biāo)函數(shù)值為 z(X0)=CX0= CBB 1 b故由最優(yōu)解判別定理可知故由最優(yōu)解判別定理可知Y0 為對偶問題的最優(yōu)解。證畢。為對偶問題的最優(yōu)解。證畢。n該定理的證明告訴我們一個非常重要的概念：對偶變量的最優(yōu)解對偶變量的最優(yōu)解等于原問題松弛變量的機(jī)會成本等于原問題松弛變量的機(jī)會成本n即對偶變量的最

52、優(yōu)解是原問題資源的影子價格影子價格OR11204 互補(bǔ)松弛互補(bǔ)松弛定理定理定理定理 設(shè)設(shè)X0, , Y0分別是原問題和對偶問題的可行解，分別是原問題和對偶問題的可行解，U0為為原問題的松弛變量的值、原問題的松弛變量的值、V0為對偶問題剩余變量的為對偶問題剩余變量的值。值。X0, , Y0分別是原問題和對偶問題最優(yōu)解的充分分別是原問題和對偶問題最優(yōu)解的充分必要條件是必要條件是 Y0 U0 + V0 X0 = 0證：由定理所設(shè)，可知有證：由定理所設(shè)，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分別以分別以Y0左乘左乘(1)式，以式，

53、以X0右乘右乘(2)式后，兩式相減，得式后，兩式相減，得 Y0 U0 + V0 X0 = Y0 b C X0若若 Y0 U0 + V0 X0 = 0，根據(jù)最優(yōu)解判別定理，根據(jù)最優(yōu)解判別定理， X0, , Y0分別分別是原問題和對偶問題最優(yōu)解。反之亦然。是原問題和對偶問題最優(yōu)解。反之亦然。 證畢。證畢。miuynjxviijj, 2 , 10, 2 , 100000OR11215 原問題檢驗(yàn)數(shù)與對偶問題的解原問題檢驗(yàn)數(shù)與對偶問題的解w 在主對偶定理的證明中我們有：對偶在主對偶定理的證明中我們有：對偶(min型型)變量的最變量的最優(yōu)解等于原問題松弛變量的機(jī)會成本，或者說原問題松優(yōu)解等于原問題松弛變

54、量的機(jī)會成本，或者說原問題松弛變量檢驗(yàn)數(shù)的絕對值弛變量檢驗(yàn)數(shù)的絕對值w 容易證明，對偶問題最優(yōu)解的剩余變量解值等于原問題容易證明，對偶問題最優(yōu)解的剩余變量解值等于原問題對應(yīng)變量的檢驗(yàn)數(shù)的絕對值對應(yīng)變量的檢驗(yàn)數(shù)的絕對值w 由于原問題和對偶問題是相互對偶的，因此對偶問題的由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗(yàn)數(shù)與原問題的解也有類似上述關(guān)系。檢驗(yàn)數(shù)與原問題的解也有類似上述關(guān)系。w 更一般地講，不管原問題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型更一般地講，不管原問題是否標(biāo)準(zhǔn)，在最優(yōu)解的單純型表中，都有原問題表中，都有原問題虛變量虛變量(松弛或剩余松弛或剩余) 的檢驗(yàn)數(shù)對應(yīng)其的檢驗(yàn)數(shù)對應(yīng)其對偶問題對偶問

55、題實(shí)變量實(shí)變量 (對偶變量對偶變量)的最優(yōu)解，原問題的最優(yōu)解，原問題實(shí)變量實(shí)變量(決策變量決策變量) 的檢驗(yàn)數(shù)對應(yīng)其對偶問題的檢驗(yàn)數(shù)對應(yīng)其對偶問題虛變量虛變量 (松弛或剩松弛或剩余變量余變量)的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需求解其中之一就可以了。其中之一就可以了。OR11223.3 3.3 線性規(guī)劃問題的進(jìn)一步研究線性規(guī)劃問題的進(jìn)一步研究1. 對偶單純形法對偶單純形法w 對偶單純形法在什么情況下使用對偶單純形法在什么情況下使用 ： 應(yīng)用前提：應(yīng)用前提： 有一個基，其對應(yīng)的基本解滿足有一個基，其對應(yīng)的基本解滿足 單純形表的檢驗(yàn)數(shù)行全部非正（對偶可單純形

56、表的檢驗(yàn)數(shù)行全部非正（對偶可 行）；行）； 變量取值可有負(fù)數(shù)（非可行解）。變量取值可有負(fù)數(shù)（非可行解）。 *注：通過矩陣行變換運(yùn)算，使所有相應(yīng)變量注：通過矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純性表。取值均為非負(fù)數(shù)即得到最優(yōu)單純性表。OR1123w 對偶單純形法求解線性規(guī)劃問題過程：對偶單純形法求解線性規(guī)劃問題過程： 1、建立初始對偶單純形表，對應(yīng)一個基本解，所建立初始對偶單純形表，對應(yīng)一個基本解，所有檢驗(yàn)數(shù)均非正，轉(zhuǎn)有檢驗(yàn)數(shù)均非正，轉(zhuǎn)2；2、若、若 b 0 ，則得到最優(yōu)解，停止；否則，若有，則得到最優(yōu)解，停止；否則，若有 bk 0 則選則選 k 行的基變量為出基變量，轉(zhuǎn)行的

57、基變量為出基變量，轉(zhuǎn)3；3、若所有、若所有 akj 0 ( j = 1,2,n )，則原問題無可，則原問題無可行解，停止；否則，若有行解，停止；否則，若有 akj 0 則選則選 = min j/ akj akj 0 cs Min j / asj asj 0 br Min-bi / air air 0 OR1141w 例、上例最優(yōu)單純形表如下例、上例最優(yōu)單純形表如下 0 0.25 0 這里這里 B-1 = -2 0.5 1 各列分別對應(yīng)各列分別對應(yīng) b1、b2、b3 的單一的單一w 0.5 -0.125 0 w 變化。因此，設(shè)變化。因此，設(shè) b1 增加增加 4，則，則 x1 , x5 , x2

58、分別變?yōu)椋悍謩e變?yōu)椋簑 4 + 0*4 = 4，4 + (-2)*4 = - 4 0，2 + 0.5*4 = 4w 用對偶單純形法進(jìn)一步求解，可得：用對偶單純形法進(jìn)一步求解，可得：w x* = ( 4, 3, 2, 0, 0 )T f* = 17C i23000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213 X22011/2-1/80j00-1.5-1/80OR1142w 增加一個變量增加一個變量w 增加變量 Xn+1 則有相應(yīng)的 Pn+1 ， Cn+1 。那么，計算出w B-1Pn+1 n+1 =Cn+1 - Cri ari n+1 w 填入最優(yōu)單純形表，

59、若 n+1 0 則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。w 例、前例增加X6，P6 = ( 2, 6, 3 )T ，C6 = 5 。計算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2123 X22011/2-1/800.25j00-1.5-1/801.25用單純形法進(jìn)一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5OR1143w 增加一個約束增加一個約束w 增加約束一個之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個新的非負(fù)變量（原約束若是小于等于形式可

60、引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼?。w 例、前例增加3x1+ 2x215，原最優(yōu)解不滿足這個約束。于是Ci230005CBXBbX1X2X3X4X5X62 X141001/4000 X5400-21/2103 X22011/2-1/8000 X6-100-1-1/201j00-1.5-1/800OR1144w A中元素發(fā)生變化中元素發(fā)生變化 （只討論 N 中某一列變化情況）w 與增加變量 xn+1 的情況類似，假設(shè) pj 變化 。那么，重新計算出 w B-1Pj j = Cj - Cri ari j w 填入最優(yōu)單純形