第三章單純形法及敏感性分析12

1、1第3章 單純形方法&靈敏度分析23.1 等式形式的線性規(guī)劃模型為了方便單純形法的計算，對模型的約束有如下兩個要求：(1) 所有的約束都是等式(變量的非負限制除外)，并且具有非負的右端項；(2) 所有變量是非負的。 這兩項要求目的在于使得單純形方法標準化和簡單化。這也就是現(xiàn)在的所有商業(yè)軟件都直接運行不等式約束、非負的右端項和無限制變量。在進行單純形法求解前，模型的任何必要處理都在軟件內(nèi)部完成。33.1.1 將不等式轉(zhuǎn)化為帶有非負右端項的等式約束在()約束中，右端項可被視為資源可利用性限制的描述，在這種情況下，左端項表示模型的活動(變量)對這些有限資源的用量。因此， ()約束的右端項與左

2、端項之間的差構(gòu)成未用的或松弛的資源量。為了把()不等式約束轉(zhuǎn)為等式約束，在約束左端增加非負的松弛變量(Slack Variable). 例如在Reddy Mikks模型中，相當于原料M1的約束給出如下：6x1+4x224定義s1作為M1的松弛的或未用的量，約束可以轉(zhuǎn)化為如下等式約束：6x1+4x2+s1=24, s104在()約束設置了模型的活動(變量)對的下限。因此， 可以將()約束的左端項超出最下限制的量表示為剩余。為了把()不等式約束轉(zhuǎn)為等式約束，在約束左端減去非負的剩余變量(Surplus Variable). 例如在營養(yǎng)配方模型（例2.2-2）中，表示最小飼料需求的約束是：x1+x2

3、800定義S1作為剩余變量，約束可以轉(zhuǎn)化為如下等式約束：x1+x2-S1=800, S105對于讓等式約束的右端項是非負的，這個條件總是可以滿足的，必要時可以在得到的方程兩端乘以(-1). 例如，約束-x1+x2-3則等價方程為-x1+x2+s1=-3，s10對上式兩邊乘以(-1), 轉(zhuǎn)化為非負的右端項，便得到我們需要的約束等式，即x1-x2-s1=363.1.2 無限制變量處理方法在單純形方法中，要求所有的決策變量是非負的。然而很多現(xiàn)實問題中往往很多的決策變量恰恰是不要求非負的。例如多周期生產(chǎn)平滑模型，其中要求每個周期在開始時要根據(jù)周期需求上下調(diào)整。如果xi是周期 i 的勞動力數(shù)量，則xi+

4、1是周期 i+1的勞動力數(shù)量，可以表示為xi+1= xi+ yi+1變量yi+1必須無符號限制，它運行xi+1相對于xi增加或減少，即雇傭或解雇工人?？梢圆捎萌缦绿鎿Q方法來滿足這個要求11111,00iiiiiyyyyy其中，這樣的替換原理是什么？7假定在周期1中，勞動力是x1=20名工人，在周期2中，勞動力將增加5名，達到25名。依據(jù)變量 和變量 ，這等價于 ，或者y2=5-0=5. 類似地，如果在周期2中勞動力減少到16名，則我們有 或者y2=0-4=-4. 替換還運行勞動力不作改變的可能性，此時兩個變量均為0來實現(xiàn)。2y2y2250yy和2204yy和那么 和 能否同時取正值？這種情況是

5、不會發(fā)生的，否則這意味著相同的時間內(nèi)既雇傭工人又解雇工人。通過數(shù)學的證明也發(fā)現(xiàn)，在任意的單純形中，這兩個值同時取正值是不可能的。2y2y83.2 從圖形解到代數(shù)解的轉(zhuǎn)換在2.2節(jié)介紹的二元決策變量的線性規(guī)劃模型的圖形求解思想奠定了代數(shù)單純形法發(fā)展的基礎。在圖解方法中，解空間由表示約束的半空間描述，而在單純形法中，解空間由m個同時成立的線性方程和n個非負變量表示。9根據(jù)圖形，容易看出解空間有無窮個解點的原因，那么如何能從解空間的代數(shù)表示中得出類似的結(jié)論？在代數(shù)表示上，方程的個數(shù)m小于決策變量個數(shù)n 。如果m=n，方程是相容的，則方程組只有唯一解；如果mn，假定方程組是相容的，則方程組有無窮多的解

6、。在代數(shù)中如何定義角點：在mn (mn)階方程組中，如果令(n-m)個變量等于0，然后求解其余的含m個變量的m個方程，如果有唯一解，則稱相應的解為基本解，它一定對應解空間的一個(可行或不可行)角點，這意味著角點的最大數(shù)目為!()!mnnCm nm1012121212max232425,0zxxstxxxxxx方程組有m=2個方程和n=4個變量。因此最大數(shù)目的角點為4!/(2!2!)6mnC到底令哪些點為零才能對應一個特定的角點？21122121212425,0 xxsxxsx x s s解空間(x1，x2，s1，s2)最優(yōu)點(1,2,0,0)2x1xABCDEF10s 20s (0，0，4，5

7、)(0，2.5，1.5，0)(2，0，0，3)(5，0，-6，0)(0，4，0，-3)11非基（零）變量基變量基本解相應的角點可行否？目標值Z（x1, x2）（s1, s2）(4, 5)A是0（x1, s1）（x2, s2）(4, -3)F否-（x1, s2）（x2, s1）(2.5, 1.5)B是7.5（x2, s1）（x1, s2）(2, 3)D是4（x2, s2）（x1, s1）(5, -6)E否-（s1, s2）（x1, x2）(1, 2)C是8（最優(yōu)點）可以看到，當問題的大小增加后（即m與n變大），枚舉所有角點的過程包含巨量的計算，如m=10和n=20，必須求解184756個1010

8、階的方程。而在很多實際的問題中，很多是有成百上千的變量和約束的問題。123.2 單純形方法3.3.1 單純形方法的迭代本質(zhì)2x1xABCDEF10s 最優(yōu)點（x1=1，x2=2）20s 12max23zxx正常情況下，單純形從原點（A點）開始，此時Z=0，能否在當前零值的基礎上，通過增加非基變量x1和x2來增加Z值？圖形顯示，增加x1和x2將增加Z。單純形方法每次要求增加一個變量，且選擇使得Z有最大改善率的那個變量。因此選擇增加x2具有最大改善率，因此增加x2直到角點B，在點B，再增加x1的值，達到改進的角點C，他是最優(yōu)點。因此單純形方法的路徑是沿著ABC。沿著路徑的每個角點與一步迭代是對應的

9、，單純形方法是沿著解空間的邊緣移動，不能抄近路，直接AC132x1xABCDEF10s 最優(yōu)點(1,2,0,0)20s (0，2.5，1.5，0)(2，0，0，3)x1x2s1s2A0045B02.51.50C1200D2003(0，0，4，5)單純形方法的本質(zhì)就是換基！角點基變量零變量As1 ，s2x1， x2Bs1 ，x2x1 ，s2Cx1 ，x2s1 ，s214相應的角點基變量非基（零）變量A（s1, s2）（x1, x2）B（x2, s1）（x1, s2）C（x1, x2）（s1, s2）可以看到，在基變量和非基變量中的變化模式隨著解沿著路徑ABC的移動而改變。AB，在A處的非基變量x

10、2變成B處的基變量，并且在A處的基變量s2變成在B處的非基變量，稱X2為進基變量，s2為離基變量，類似地，在點B，x1進基，s1離基，因此到了C點15Reddy Mikks模型是Max Z=5x1+4x2St 6x1+4x224 （原料M1） x1+2x26 （原料M1） -x1+x21 （市場限制） x2 2 （需求限制） x1, x2012123412112212324121234max54000064242612,0zxxssssstxxsxxsxxsxsx x s s s s12540zxx163.3.2 單純形算法的計算細節(jié)基Zx1x2s1s2s3s4解Z1-5-400000Z 行s

11、1064100024s1 行s201201006s2 行s30-1100101s3 行s400100012s4 行初始解是最優(yōu)解嗎？目標函數(shù)表明可以增加x1或x2來改進這個解，選擇具有最正的系數(shù)的變量選擇具有最正的系數(shù)的變量x1為進基變量為進基變量，這個等價于將目標函數(shù)中最負系數(shù)的變量作為進基變量。最優(yōu)性條件最優(yōu)性條件，該條件確定進基變量單純形迭代開始于原點（x1, x2）=(0, 0)，因此, 在初始點處的非基（零）變量：（x1, x2），在初始點處的基變量： （s1, s2, s3, s4）即 Z=0， s1=24, s2=6, s3=1, s4=217基進基x1解比值（或截距）s1624

12、x1=24/6=4 最小值s216x1=6/1=6s3-11x1=1/-1=-1 （不考慮）s402x1=2/0= （不考慮）結(jié)論：x1進基，s1離基 從單純形表中確定離基變量的方法是，計算方程的右端項（解列）與相應的在進基變量x1下方的約束系數(shù)的非負比可行性規(guī)則可行性規(guī)則最小非負比自動識別當前基變量s1作為離基變量，并指定進基變量x1的新值為4181212112212324121234max54:6424:26:1:2,0zxxaxxsbxxscxxsdxsx x s s s sabcd-1461234561235s1=0s2=0s3=0s4=01/-1=-124/6=46/1=6ABC在點

13、B處的非基（零）變量： （s1, x2）在點B處的基變量： （x1, s2, s3, s4）19進基變量和離基變量如何進基變量和離基變量如何“交換交換”？進基基Zx1x2s1s2s3s4解Z1-5-400000離基s1064100024樞軸行s201201006s30-1100101s400100012樞軸列一些概念一些概念20基于高斯基于高斯-喬丹行操作來計算新的基本解喬丹行操作來計算新的基本解1. 樞軸行 a. 在基列中，以進基變量替換離基變量 b. 新的樞軸行=當前樞軸行樞軸元素2. 其他所有行，包括Z行 新的行=當前行-當前樞軸列的系數(shù)新的樞軸行將該方法應用到上表將該方法應用到上表在基

14、列中，以x1替換s1 新的x1行=當前s1行6=(0 6 4 1 0 0 0 24)/6=(0 1 2/3 1/6 0 0 0 4)新的Z行=當前Z行-(-5)新的x1行=(1 -5 -4 0 0 0 0 0)-(-5) (0 1 2/3 1/6 0 0 0 4)=(1 0 -2/3 5/6 0 0 0 20)新的s2行=當前s2行-(1)新的x1行=(0 1 2 0 1 0 0 6)-(1) (0 1 2/3 1/6 0 0 0 4)=(0 0 4/3 -1/6 1 0 0 2)新的s3行=當前s3行-(-1)新的x1行=(0 -1 1 0 0 1 0 1)-(-1) (0 1 2/3 1/

15、6 0 0 0 4)=(0 0 5/3 1/6 0 1 0 5)新的s4行=當前s4行-(0)新的x1行=(0 0 1 0 0 0 1 2)-(0) (0 1 2/3 1/6 0 0 0 4)=(0 0 1 0 0 0 1 2)21新的基本解是（x1, s2, s3, s4），因此新的單純形表為進基基Zx1x2s1s2s3s4解Z10-2/35/600020 x1012/31/60104離基s2004/3-1/61002s3005/31/60105s400100012新的基本解是（x1, s2, s3, s4）=(4 2 5 2)，而Z=20與下面的公式計算結(jié)果一致新的Z=原來的Z + 新的x

16、1的值 它的目標系數(shù)=0+4 5=2022基進基x2解比值x12/34X2=4/(2/3)=6s24/32X2=2/(4/3)=1.5 最小值s35/35X2=5/(5/3)=3s412X2=2/1=2在前表中，最優(yōu)性條件最優(yōu)性條件表明，x2是進基變量，由可行性條件可行性條件可得下表因此，s2離開基本解，并且x2的新值是1.5，相應增加的Z值是2/3x2=2/31.5=1,它產(chǎn)生新的Z=20+1=21在基列中，用進基變量x2替換s2，應用高斯行運算，有：1. 新的樞軸行x2行=當前s2行4/3；2. 新的Z行=當前Z行-(-2/3)新的x2行；3. 新的x1行=當前x1行-(2/3)新的x2行

17、；4. 新的s3行=當前s3行-(5/3)新的x2行；5. 新的s4行=當前s4行-(1)新的x2行；23這些計算產(chǎn)生新的單純形表為基Zx1x2s1s2s3s4解Z1003/41/20021x10101/4-1/2003x2001-1/83/4003/2s30003/8-5/4105/2s40001/8-3/4011/2基于最優(yōu)性條件，Z行中相應于非基變量s1和s2的系數(shù)沒有一個是負的，因此最后的單純形表是最優(yōu)的決策變量最優(yōu)值建議x13日生產(chǎn) 3 噸外墻涂料x23/2日生產(chǎn) 1.5 噸內(nèi)墻涂料Z21利潤2.1萬美元24資源松弛變量的值狀況原料M1s1=0匱乏原料M2s2=0匱乏市場限制s3=5

18、/2充裕需求限制s4=1/2充裕單純形的計算結(jié)果還給出了資源的使用情況：如果松弛變量為零，表明資源全部用完，該資源是匱乏的如果松弛變量為正，表明資源尚有余存，該資源是充裕的25練習Max z=2x1+x2St 5x215 6x1+2x224 x1+ x25 x1，x2 0 結(jié)果：x1=7/2x2=3/2s1=15/2s2=0s3=0z=17/2263.3.3 單純形方法的總結(jié)最優(yōu)性條件最優(yōu)性條件 在極大化（極小化）問題中，進基變量是Z行中具有最負（最正）系數(shù)的非基變量。如有多個可任選其一。當非基變量的所有Z行系數(shù)是非負的（非正的）時，迭代達到最優(yōu)可行性條件可行性條件 對于極大化（極小化）問題，

19、離基變量都是具有最小非負比（帶有嚴格的正分母）的基變量，如有多個可任選其一高斯高斯-若爾當行運算若爾當行運算 （1）樞軸行 a. 在基列中，用進基變量替換離基變量 b. 新的樞軸行=當前樞軸行樞軸元素 （2）包括 Z 的所有其他行 新行=當前行樞軸列系數(shù)新的樞軸行決定進基變量！決定離基變量！27單純形方法總結(jié)第1步 確定初始基本可行解第2步 用最優(yōu)性條件選擇一個進基變量，如果沒有進基變量，停止計算；上一個解就是最優(yōu)的，否則轉(zhuǎn)第3步。第3步 用可行性條件選擇離基變量。第4步 用適當?shù)母咚?若爾當行運算確定新的基本解。轉(zhuǎn)到第2步283.4 人工初始解所有約束是（）并且有非負右端的線性規(guī)劃方便地提供

20、了全部為松弛變量的初始基本可行解。Max & Min Z=5x1+4x2St 6x1+4x224 x1+2x26 -x1+x21 x2 2 x1, x2029Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min z=4x1+x2s.t. 3x1+x2 =3 4x1+3x2-x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4 0松弛變量剩余變量u需要增加人工變量以扮演松弛變量的角色，然后在迭代中加以適當處理。帶有（=）和（）的約束的線性規(guī)劃求解該如何求解？303.4.1 大M方法 大M方法以等式形式的線性規(guī)劃開始。

21、如果第 i 個約束沒有松弛變量，則將人工變量 Ri 加入到初始解中，類似于所有松弛變量為基本解的情況。然后在目標函數(shù)中對他們指定非常大的懲罰，強迫人工變量在最優(yōu)解中等于零。如果問題有可行解，該種情況總會發(fā)生。懲罰規(guī)則懲罰規(guī)則已知M為一個充分大的數(shù)，人工變量的目標系數(shù)表示為適當?shù)膽土P，如果MM在極大化問題中人工變量的目標系數(shù)在極小化問題中31Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min z=4x1+x2s.t. 3x1+x2 =3 4x1+3x2-x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4 0松弛變量剩余變

22、量Min z=4x1+x2+MR1+MR2s.t. 3x1+x2 +R1 =3 4x1+3x2-x3 + R2 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4， R1， R2 0初始解(R1, R2, x4)=(3,6,4)32M可以不采用代數(shù)運算的傳統(tǒng)，并用數(shù)值代替，以簡化表達.M值應該多大？依賴于初始線性規(guī)劃的數(shù)據(jù)：uM相對于初始目標系數(shù)必須充分大，使得M能起到懲罰作用，迫使人工變量在最優(yōu)值為零。u也不希望M太大，否則在計算機求解中，非常大的數(shù)與非常小的數(shù)值在一起運算時，可能產(chǎn)生嚴重的四舍五入。本例似乎取M=10033基x1x2x3R1R2x4解z-4-10-100 -

23、10000R13101003R243-10106x41200014在進行單純形方法之前，需要將z 行與表的其余部分保持一致！在表中，x1=x2=x3=0，初始基本解(R1, R2, x4)=(3,6,4)，z=100*3+100*6=900（而不是z行右端當前顯示的0?。?，這種不一致是由于R1, R2在目標函數(shù)中有非零系數(shù)（-100, -100）造成的?。ㄔ谒兴沙谧兞繛槌跏冀庵校琙行的松弛變量系數(shù)為0）34為此，在z行選用適當?shù)募s束方程替換出R1和R2，注意到橙色部分，用100乘以R1和R2行的每一行，求和之后加到z行，替換出R1和R2, 即基x1x2x3R1R2x4解z-4-10-100-

24、10000R13101003R243-10106x41200014基x1x2x3R1R2x4解z696399-100000900R13101003R243-10106x41200014X1為進基！最正系數(shù)！新的Z行=舊的z行+(100R1+100R2行)35基x1x2x3R1R2x4解z696399-100000900R13101003R243-10106x41200014基x1解最小比R1333/3=1（最小值）R2466/4=1.5x4144/1=4可行性條件，選擇R1為離基變量！36基x1x2x3R1R2x4解z0167-100-23200204x111/301/3001R205/3-1

25、-4/3102x405/30-1/3013采用高斯-喬丹運算可以計算出如下最后的單純形顯示x2和R2分別是進基變量與離基變量。連續(xù)采用單純形計算，再經(jīng)過兩步的迭代即可達到最優(yōu)最優(yōu)解為 x1=2/5 ，x2=9/5，z=17/5； R1=0，R2=0，x3=1，x4=0如果線性規(guī)劃沒有可行解，在最終的單純形迭代中，使用懲罰項將不能迫使人工變量取值為零，此時至少有一個人工變量取正值。373.4.2 兩階段法大M方法中懲罰值的使用，可能會導致大的求解誤差。兩階段法分兩個階段來求解線性規(guī)劃：階段一試圖求一個初始基本可行解，找到一個解以后，調(diào)用階段二求解原問題。38階段 I 將問題變成等式約束形式，并在

26、約束中增加必要的人工變量（如大M方法一樣），以保證找到一個初始基本解。接下來，求相應方程的基本解，無論線性規(guī)劃是求極大化還是極小化，總是使得人工變量之和達到最小。如果其和的最小值為正，則線性規(guī)劃問題無可行解（正的人工變量約束不滿足）。否則進行階段II。階段II 使用階段I得到的可行解作為原始問題的初始基本可行解。兩階段法的概況39Min z=4x1+x2s.t. 3x1+x2=3 4x1+3x26 x1+2x24 x1，x20Min r =R1+R2s.t. 3x1+x2+ R1 =3 4x1+3x2-x3 +R2 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4,R1,R2

27、 0基x1x2x3R1R2x4解r000-1-100R13101003R243-10106x41200014階段I40基x1x2x3R1R2x4解r74-10009R13101003R243-10106x41200014類似于大M方法中一樣，在r行中的R1和R2用以下計算來替換： 新的 r 行=舊的r行+（1R1行+ 1R2行）利用上面的單純形表格為基礎，利用標準的單純形方法，計算第一階段的最優(yōu)解。41基x1x2x3R1R2x4解r000-1-100 x1101/53/5-1/503/5x201-3/5-4/53/506/5x40011-111采用單純形法迭代得到如下表格因為最小值 r =0，

28、階段 I 產(chǎn)生了基本可行解x1=3/5，x2=6/5，x4=1。此時人工變量以完成了它的使命，從而我們能夠從表中連同他們所在的列一起去掉，轉(zhuǎn)入階段 II42階段IIMin z=4x1+x2s.t. x1+x3/5=3/5 x2-3x3/5=6/5 x3+x4=1 x1，x20基x1x2x3x4解r00000 x1101/503/5x201-3/506/5x400111基x1x2x3x4解z-4-1000 x1101/503/5x201-3/506/5x40011143基x1x2x3x4解z001/5018/5x1101/503/5x201-3/506/5x400111基變量x1和x2在z行有非

29、零的系數(shù)，使用下列計算將非零系數(shù)替換出去： 新的z行=舊的z行+（4 x1行+ 1x2行）44基x1x2x3x4解z000-1/517/5x1100-1/52/5x20103/59/5x300111最優(yōu)解為 x1=2/5 ，x2=9/5，z=17/5； x3=1，x4=0采用單純形方法得到：45實際上幾乎所有的商業(yè)軟件包都采用兩階段法來求解線性規(guī)劃。實際中，大M方法由于潛在的不利的舍入誤差而可能從來不用的。介紹大M方法純粹處于歷史原因，其發(fā)展早于兩階段法。在最后一張表中人工變量及其所在列被去掉，這只有在他們?nèi)渴欠腔兞繒r才會發(fā)生。如果在階段I的最后一張表中有一個或者多個人工變量是基變量（取零

30、值），則必須采取如下附加步，才能在階段II開始前去掉人工變量。46第一步 選擇一個零人工變量離開基本解，并指定它所在的行為樞軸行。進基變量可以是樞軸行具有系數(shù)非零的任意非基變量，完成相應的單純法迭代。第二步 從表中去掉剛剛離基的人工變量的列。如果所有的人工變量已經(jīng)被去掉轉(zhuǎn)入階段II，否則轉(zhuǎn)回第一步。第一步的目的是保持基變量的可行性將不受影響，不論其樞軸元素是正還是負的總能使得零人工變量變?yōu)榉腔兞俊?7課后作業(yè)： P94，12題； P98，5（a）題、（d）題；1. P102，5題.483.5 單純形法的特殊情況本節(jié)考慮單純形法中的4種情況：n退化；n可選擇最優(yōu)解；n無界解；n不存在（或者可行

31、解）（1）介紹這些情況的理論解釋（2）提供相應的實際解釋493.5.1 退化在單純形方法可行性條件中，最小比值可能循環(huán)出現(xiàn)，可以隨意打破這種循環(huán)。當這樣的情況發(fā)生時，至少有一個基變量在下一次迭代中為零，并稱新的解退化。Max z=3x1+9x2St x1+9x28 x1+2x24 x1，x2050迭代基x1x2x3x4解0z-3-9000 x2進基x314108X3離基x4120141z-3/409/4018x1進基x21/411/402X4離基x41/20-1/2102z003/23/218(最優(yōu)值)x2011/2-1/22x110-120在迭代中，x3和x4均可以是離基變量，在迭代1構(gòu)成退

32、化，在基變量x4出現(xiàn)零值，再一次迭代后，達到最優(yōu)值。51x1+9x28（多余約束）x1+2x24超定的到3條直線通過最優(yōu)點，使得某些約束是多余的。目前尚沒有有效的計算方法能直接從表中識別多余的約束。退化的含義1，注意迭代1和2，你將注意到目標值沒有改進（Z=18）。單純形方法有可能進入一個重復迭代的序列，永遠不改進目標值，也永遠不滿足最優(yōu)性條件。退化的含義2，兩個迭代盡管對基變量和非基變量分類不一致，但對于所有的變量和目標值都產(chǎn)生同樣的值。在迭代中（遇到退化的時候）是否可以停止計算，答案否定，因為可能出現(xiàn)暫時退化。523.5.2 可選擇最優(yōu)解當目標函數(shù)平行于非冗余的緊約束目標函數(shù)平行于非冗余的

33、緊約束（binding constraint）（即在最優(yōu)解處作為方程而被滿足的約束）解，目標函數(shù)可以在多于一個解點處相同的最優(yōu)解，因此產(chǎn)生可選擇最優(yōu)解。Max z=2x1+4x2St x1+2x25 x1+x24 x1，x20 x1+x24x1+2x25z=2x1+4x2最優(yōu)基本可行解BCBC上任意一點都表示了具有相同目標值Z=10的可選最優(yōu)解53迭代基x1x2x3x4解0z-2-4000X2進基x312105X3離基x4110141(最優(yōu)值)z002010X1進基x21/211/205/2X4離基x41/20-1/213/22(可選最優(yōu)解)z002010 x2011-11x110-123迭代

34、1給出了最優(yōu)解x1=0，x2=5/2和z=10，它與點B相一致。如何從這個表格中知道可選擇最優(yōu)解存在呢？看看迭代看看迭代1行方程非基變量的系數(shù)行方程非基變量的系數(shù)。非基變量x1的系數(shù)為零，表明x1可以進入基本解而不會改變Z值，但會引起變量值的改變。迭代2正是這個情況：x1進基，x4離基，新的解點x1=3,x2=1,z=1054單純形方法僅能確定B點和C點，從數(shù)學角度來說，BC上的點(x1,x2)作為點B和C的非負的加權(quán)平均，因此B：x1=0，x2=5/2C：x1=3，x2=1則線段BC上的所有的點如下12(0)(1)(3)33,0153( )(1)(1)122xx 當=0，為C點；當=0，為B

35、點；否則為B到C之間55在實踐中，可選擇最優(yōu)解是有用的，因為我們可以從許多解中選擇而不會損害目標。例如在前例中，在B處顯示只有第二項活動是正值；而在C處，兩項活動都為正值。如果例子描述的是一種混合產(chǎn)品情形，生產(chǎn)兩種產(chǎn)品比生產(chǎn)一種產(chǎn)品對于滿足市場或許更加有優(yōu)勢，在這樣的情況下C處解可能更加吸引人，也就是不要把所有的雞蛋放在一個籃子里面。563.5.3 無界解在一些線性規(guī)劃中，可以無限地增加變量的值但不破壞任何一個約束，這個就意味這解空間中至少又一個變量是無界的。其結(jié)果是，目標值可以無限制的增加（max情形）或減少（min情形），此時解空間和最優(yōu)目標都是無界的。出現(xiàn)無界點可能是由于模型構(gòu)造不合理。

36、此類模型中最大可能的缺陷是一個或多個非多余約束沒有考慮在內(nèi)，一些約束參數(shù)估計錯誤57Max z=2x1+x2St x1-2x210 2x1 40 x1，x20通過單純形法迭代會發(fā)現(xiàn)，x2可以無限制的增加而不破壞任何約束，因為x2每增加一個單位，z將增加1；x2將增加至無窮，使得z無窮大，因此問題無有界解。無界解空間無界目標值z=2x1+x2x1-2x210無界變量的下方的系數(shù)將會產(chǎn)生（也就系數(shù)將會產(chǎn)生（也就是可行性條件比的分母）是零或者負的是可行性條件比的分母）是零或者負的基x1x2x3x4解z-2-1000 x31-11010 x4200140583.5.4 不可行解n 具有不相容約束的線性

37、規(guī)劃模型沒有可行解。假如所有的約束類型都是類型并具有非負的右端項，則這種情況將永遠不會出行，因為松弛變量提供了一個可行解。n 對于混合類型的約束，僅當模型有可行空間時，人工變量在最優(yōu)解處可以取零，否則至少有一個人工變量在最優(yōu)迭代中取正。n 不可行解空間表明模型的構(gòu)建有可能是不正確的。59Max z=3x1+2x2St 2x1+x22 3x1+ 4x212 x1，x20z=3x1+2x22x1+x223x1+ 4x212偽最優(yōu)解迭代基x1x2x3x4R解0z-303-40210000-1200X2進基x3210105X3離基R1101141(偽最優(yōu))z50101004020-396x221010

38、2R-50-1-414最優(yōu)迭代1顯示人工變量R取值為正，表明問題不可行，上圖也展示了不可行解空間。由于允許人工變量為正，單純形方法實際上已經(jīng)將不等式的方向顛倒，從3x1+ 4x212變?yōu)?x1+ 4x212，這個結(jié)果為偽偽最優(yōu)最優(yōu)。M=100課后作業(yè)： P28，第5題； P33，第1題； P36，第2題； P45，第4題； P61，第10題；以上作業(yè)請給出最終的計算結(jié)果。613.6 靈敏度分析在線性規(guī)劃模型中，參數(shù)通常是不精確的，借助于靈敏度分析，我們能夠探索這種不確定性對最優(yōu)解質(zhì)量的影響。例如1. 某種產(chǎn)品估計的單位利潤/成本發(fā)生變動，我們是否還能維持原先的產(chǎn)品組合構(gòu)成及產(chǎn)量，以實現(xiàn)最優(yōu)目標

39、？2. 公司準備添置機器/雇員/原材料，應該以什么依據(jù)來決定優(yōu)先順序？n線性規(guī)劃中，模型參數(shù)（輸入數(shù)據(jù)）能夠在一定的限度內(nèi)變化而不引起最優(yōu)解的改變。這些內(nèi)容涉及靈敏度的分析n如果輸入的數(shù)據(jù)中做特定的變化后如何得到新的最優(yōu)解。623.6.1 圖形靈敏度分析考慮兩種情況： 最優(yōu)解對于資源的可利用性（約束的右端項）變化的靈敏度分析；最優(yōu)解對于單位利潤或單位費用（目標函數(shù)系數(shù)）變化的靈敏度分析；maxmin0 z=stCXAX = bX或63例3.6-1 （右端項變化）JOBCO公司在兩臺機器上生產(chǎn)兩種產(chǎn)品。1個單位的產(chǎn)品1需要2小時機器1和1小時機器2；對于產(chǎn)品2，一個單位產(chǎn)品需要1小時機器1和3小

40、時機器2.每個單位產(chǎn)品1和產(chǎn)品2的收益分別是30美元和20美元。每臺機器的日加工時間是8小時。令x1和x2分別表示產(chǎn)品1和產(chǎn)品2的日產(chǎn)量，則線性規(guī)劃模型給出如下：Max z=30 x1+20 x2St 2x1+ x28（機器1） x1 +3x2 8（機器2） x1，x20maxmin0 z=stCXAX = bX或64如果日工作能力從8小時增加到9小時，則生產(chǎn)能力增加的收益率是多少？2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=128X1=3.8，x2=1.4，z=142Gc11ZZ142 12814.0(/)98CG機器 增加 小時工作能力產(chǎn)生美元 小時工

41、作能力收益的變化率的改變（ 點變化到 ）CG計算出的變化率提供了模型的輸入（資源）和它的輸入（總收益）的直接聯(lián)系，表示成為資源的單位價值：即可用資源的單位變化引起目標函數(shù)的變化。這意味著機器1的能力增加（或者減少）1個單位，將增加（或減少）收益14美元。65盡管目標函數(shù)變化率的恰當說法是資源的單位價值，然而在技術(shù)上的名稱是對偶價格（dual price）或者影子價格（shadow price）。2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=128X1=3.8，x2=1.4，z=142CGBF當機器1工作能力變化（增加或者減少），即其約束平移到線段BF的任意一

42、點，每小時14美元的對偶價格仍然有效。給定對偶價格的適用范圍：機器1工作能力最小值B點=（0，2.67）=20+12.67=2.67小時機器1工作能力最大值F點=（8，0）=28+10=16小時在2.67機器1的工作能力16小時時，對偶價格14美元/小時將保持不變DE66類似方法可以驗證，機器2工作能力的對偶價格是每小時2美元，它在如下區(qū)域內(nèi)變化時保持不變，即約束平行移動到線段DE的任意一點時，將產(chǎn)生下面的限制區(qū)域：機器2工作能力最小值D點=(0，4)=14+30=4小時機器2工作能力最大值E點=(0，8)=28+38=24小時對于機器2，在如下區(qū)域?qū)ε純r格2美元/小時將保持不變4機器 2 的

43、工作能力24小時機器1和機器2計算出的限制稱為可行性區(qū)域（feasibility range）67關于線性規(guī)劃問題, 對偶價格能夠作出相應的經(jīng)濟決策, 比如：問題1 如果JOBCO能夠增加兩種機器的能力，哪種機器應該有更高的優(yōu)先權(quán)？機器1和機器2的對偶價格分別為14和2美元/小時，這時優(yōu)先權(quán)應該是機器1問題2 一項建議提出，要以10美元/小時的額外費用增加機器1和機器2的能力，這項建議可取嗎？對于機器1，每小時附加凈收入為14-10=4美元；而對于機器2凈收入為2-10=-8美元，因此只應該增加機器1.68問題3 如果機器1的工作能力從現(xiàn)在的8小時增加到13小時，這個增加將如何影響最優(yōu)收益？對

44、于機器1的對偶價格是14美元，在2.67，16小時的區(qū)域內(nèi)使用，所提出的增加到13小時落在可行域內(nèi)，因此收入增加量是14(13-8)=70美元，這意味著總收入將增加到（當前收益+收益變化）=128+70=198美元。問題4 假定機器1的工作能力可以增加到20小時，這個增加將如何影響最優(yōu)收益？所提出的改變超出2.67，16小時這個保持14美元的對偶價格區(qū)域，因此我們只能增加到16小時，超出部分需要進一步計算才能得到答案。落在可行域之外不意味著問題無解，只是我們沒有充分信息立刻作出決策。69問題5 只要資源的改變在可行域內(nèi)，最優(yōu)目標值的改變就等于（對偶價格資源的改變），相應變量的最優(yōu)值是多少？變量

45、的最優(yōu)值一定發(fā)生改變，然而從圖解得到的信息水平并不能充分確定新值。703.6.2 代數(shù)靈敏度分析右端項的變化TOYCO通過3種操作裝配3種玩具玩具火車、卡車和汽車。這個3種操作可用時間限制分別為430、460和420分鐘。這3個產(chǎn)品的單位收入分別為3、2和5美元。每輛火車在3種操作中的裝配時間分別是1、3和1分鐘，玩具卡車和汽車的時間分別是(2,0,4)和(1,2,0).令x1，x2，x3分別為每天裝配玩具火車、卡車和汽車的單位數(shù)量，則規(guī)劃模型如下：Max z=3x1+2x2+5x3St x1+2x2+x3430（操作1） 3x1 +2x3 460（操作2） x1+4x2 420（操作3） x

46、1，x2 ，x3 071基x1x2x3x4x5x6解z4001201350 x2-1/4101/2-1/40100 x33/20101/20230 x6200-21120這個結(jié)果表明生產(chǎn)玩具卡車100，汽車230，但不生產(chǎn)玩具火車，收入為1350美元。72對偶價格的確定在增加松弛變量x4，x5，x6后，模型的約束可以寫為：x1+2x2+x3+x4=430(操作1)3x1 +2x3+x5 =460 (操作2)x1+4x2 +x6=420 (操作3)x1+2x2+x3=430-x4 (操作1)3x1 +2x3 =460 -x5 (操作2)x1+4x2 = 420-x6 (操作3)或者借助于上式，我

47、們可以是說，松弛變量上減少1分鐘就等價于操作時間上增加1分鐘。73可以用上述信息從最優(yōu)表的Z的方程中確定對偶價格：Z+4x1+x4+2x5+0 x6=1350可以寫成Z=1350-4x1+x4+2x5+0 x6 =1350-4x1+1(-x4) +2(-x5)+0(-x6)已知松弛變量值的減少等價于在它的操作時間上的增加，因此Z=1350-4x1+1增加操作1的時間 + 2增加操作2的時間 + 0增加操作3的時間74這個方程顯示了：（1）在操作1上時間增加1分鐘z將增加1美元；（2）在操作2上時間增加1分鐘z將增加2美元；（3）在操作2上時間增加1分鐘z將保持不變；概括最優(yōu)表的z行如下：基x1

48、x2x3x4x5x6解z4001201350Z行直接產(chǎn)生的對偶價格如下表：資源松弛變量松弛變量的最優(yōu)z方程系數(shù)對偶價格（美元/分鐘）操作1x411操作2x522操作3x60075操作3的零對偶價格意味著，分配給這個操作更多的生產(chǎn)時間沒有經(jīng)濟效益。這個結(jié)果有意義，因為資源已經(jīng)參與了，證據(jù)就是，在最優(yōu)解中與操作3相對應的松弛變量是正值(=20)（即資源過多）. 至于操作1和2每一個松弛變量，增加1分鐘將分別提高1美元和2美元。對偶價格還表明，當分配額外資源時，操作2將得到更高的優(yōu)先權(quán)，因為它的對偶價格是操作1的2倍。上述計算說明對偶價格是如何從最優(yōu)表的約束中確定的。對于約束，該方法仍然適用。但是對

49、偶價格將于對應的約束符號相反。等式約束則還需要“相關的”計算。76可行性區(qū)域的確定令D1, D2, D3分別是分配給操作1、2和3的每天生產(chǎn)時間的該變量（正的或者負的），模型可寫為Max z=3x1+2x2+5x3St x1+2x2+x3430+ D1 （操作1） 3x1 +2x3 460 + D2 （操作2） x1+4x2 420 + D3 （操作3） x1，x2 ，x3 0我們將考慮同時發(fā)生改變的一般情況，每次只改變一個變量的特殊情況將從這些結(jié)果中得到。77具體方法是：用所修正的右端項從新計算最優(yōu)單純形表，然后獲得保持解可行的條件，即最優(yōu)表的右端項保持非負。為了說明右端項如何重新保持計算，

50、我們以修正解列開始，即在初始單純形表中使用新的右端項：430+D1、460+D2、420+D3，因此基x1x2x3x4x5x6解右端項D1D2D3z-3-2-50000000 x2121100430100 x3302010460010 x614000142000178基x1x2x3x4x5x6解右端項D1D2D3z4001201350120 x2-1/4101/2-1/401001/2-1/40 x33/20101/2023001/20 x6200-21120-211在D1，D2，D3下的列與初始基本列x4，x5，x6下的那些列是相同的。這意味著當我們像在初始模型那樣完成相同的單純形迭代是，兩

51、組中的列也一定是完全相同。實際上新的最優(yōu)解變成79新的最優(yōu)表提供了如下的最優(yōu)解：1221232612313502111002412302202zDDxDDxDxDDD只要所有變量非負，則當前解保持可行，這就導出可行性條件可行性條件212326123111000241230022020 xDDxDxDDD任意同步改變D1、D2、D3，只要滿足這些不等式，都將保持解可行。如果所有的條件滿足，則可在上述等式約束中直接替換D1、D2、D3，來找到新的最優(yōu)解。80假設對于操作1、2、3的可利用生產(chǎn)時間分別是480、440和410分鐘，則D1=480-430=50，D2=440-460=-20，D3=41

52、0-420=-10，在可行性條件中替換，得到23611100(50)( 20)1300241230( 20)22002202(50)( 20)( 10)1100 xxx （可行）（可行）（不可行）81計算表明x60，因此當前解并沒有保持可行。需要額外的計算才能得到新的解（本課不介紹）。如果資源的變化使得D1=-30，D2=-12，D3=10，則23611100( 30)( 12)880241230( 12)22402202( 30)( 12)(10)780 xxx （可行）（可行）（可行）新的可行解是x2=88，x3=224，x6=78，且 z=3(0)+2(88)+5(224)=1296美元

53、，或z=1350+1(-30)+2(-12)=1296美元。82給出的條件可以專門用于產(chǎn)生各自的可行性區(qū)域，這就是一次只改變一種資源的變化結(jié)果。情況1 把操作1的時間從460分鐘改變到(460+D1)分鐘，這一變化等價于在同步條件中置D2=D3=0，得到21131611110002002230020010202010 xDDxDxDD 以上考慮的是同時發(fā)生改變的一般情況，而每次只改變一個變量的特殊情況將從一般結(jié)果中得到。83情況2 把操作2的時間從430分鐘改變到(430+D2)分鐘，這一變化等價于在同步條件中置D1=D3=0，得到2223222612110004004123004002040

54、0220020 xDDxDDDxDD 情況3 把操作3的時間從430分鐘改變到(430+D3)分鐘，這一變化等價于在同步條件中置D1=D2=0，得到232631000230020200 xxDxD 84對TOYCO模型，總結(jié)對偶價格和可行性區(qū)域如下資源對偶價格可行性區(qū)域資源數(shù)量（分鐘）最小值當前值最大值操作11-200D110230430440操作22-20D2400440440860操作30-20D3400420注意：對偶價格有效的同步可行性條件，不一定要求滿足所有單個可行性區(qū)域。2361000.5( 30)0.25( 12)11802300.5( 12)2240202(30)( 12)(1

55、00)480 xxx （可行）（可行）（可行）例如D1=30，D2=-12，D3=100，則85這意味著對偶價格仍然可適用，因此能夠從對偶價格中計算出新的最優(yōu)目標值z=1350+1(30)+2(-12)+0(100)=1356美元（1）如果約束右端項的該變量Di，i=1,2,3,m，在同步改變時滿足所有可行性條件，或相應的Di在單個發(fā)生改變時仍然落在可行性區(qū)域內(nèi)，則對偶價格有效。（2）如果同步的可行性條件不滿足，或因為單個的可行性區(qū)域被破壞，對偶價格就不再有效。此時，可以用新的Di 值重新解該問題，或者用后續(xù)方法來解決。86課后作業(yè)P123，第6題P125，第11題87例（目標系數(shù)的變化）2x

56、1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=128CGBFDE z=30 x1+20 x2C點為最優(yōu)解點。收入單位數(shù)的變化（目標函數(shù)系數(shù)）將改變z的斜率。然而從右圖可以看到，只要目標函數(shù)位于直線BF和DE之間，最優(yōu)點將保持在C，這2個約束確定了最優(yōu)點，這意味著存在一個關于目標函數(shù)系數(shù)的區(qū)域，在這個區(qū)域內(nèi)最優(yōu)解在C點將保持不變。maxmin0 z=stCXAX = bX或3.6.3 圖形靈敏度分析目標函數(shù)88可以寫出目標函數(shù)的一般形式：Max z=c1x1+c2x2可以想象，直線z在C處轉(zhuǎn)動，并且它能夠沿著順時針和逆時針轉(zhuǎn)動，最優(yōu)解始終保持在點C，只要z=c1x1+c2x2介于

57、直線2x1+ x2=8，x1 +3x2 =8之間。這意味著比值c1/c2可以在1/3與2/1之間變化，這產(chǎn)生如下條件：121231cc這個信息能夠直接提供有關最優(yōu)解的答案。例如89問題1 假設產(chǎn)品1和產(chǎn)品2的單位收入分別改變到35美元和25美元，當前的最優(yōu)解保持不變嗎？新的目標函數(shù)為 Max z=35x1+25x2。解在C處保持最優(yōu)，因為c1/c2=35/25=1.4，保持在最優(yōu)區(qū)域1/3, 2之間。盡管變量在最優(yōu)點C的保持不變，z的最優(yōu)值變到35(3.2)+25 (1.6)=152美元。當比值落在這個區(qū)域之外，需要增加額外的計算來求出新的最優(yōu)解。90問題2 假設產(chǎn)品2的單位收入固定在當前值c

58、2=20美元上，相應于c1，即產(chǎn)品1的單位收入保持最優(yōu)值不變的區(qū)域是什么？在條件 中替換c2=20，得到121231cc1/320c1220，即6.67c140這個區(qū)域稱為c1的最優(yōu)區(qū)域，并隱含的假設c2固定在20美元。盡管這一節(jié)僅處理了二維變量問題，但是這些結(jié)果奠定了對一般線性規(guī)劃進行靈敏度分析的基礎！913.6.3 代數(shù)靈敏度分析目標函數(shù)本節(jié)從之前的圖形法處理的保持線性規(guī)劃最優(yōu)解的條件，拓展到多維的代數(shù)方法。簡約費用簡約費用在TOYCO模型中，在最優(yōu)表中目標Z行系數(shù)是基x1x2x3x4x5x6解z4001201350因此z行方程是 z+4x1+x4+2x5=1350即 z=1350-4x1

59、-x4-2x5 最優(yōu)解建議不生產(chǎn)玩具火車（X1=0）。該建議由z行方程的信息得到證實，因為x1在當前零值情況下，每增加一個單位將降低4美元，即Z=1350-4(1)-1(0)-2(0)=1346美元。92可以把Z行方程中x1的系數(shù)(=4)作為費用的單位，因為它引起z的減少。但是這個“費用”來自哪里？在原來的模型中，x1的單位收入是3美元。我們還知道，每個玩具火車消耗資源（操作時間），它本身也導致費用。因此，從優(yōu)化的觀點來看，x1的”吸引力”依賴于單位收入與一個單位資源消耗的費用的相對值。這個關系在線性規(guī)劃文獻中被公式化，定義簡約費用如下： 應該盡量降低單位簡約費用，即提高利潤率，以提高運營系統(tǒng)

60、的效益！單位利潤=單位收入-單位消耗資源費用（成本）單位簡約費用=單位消耗資源費用（成本）-單位收入93如何理解這個定義的含義？在TOYCO模型中，玩具卡車的單位收入(=2美元)少于玩具火車的單位收入(=3美元). 然而，最優(yōu)解選擇生產(chǎn)玩具卡車卻不生產(chǎn)玩具火車(x1=0).原因在于用于玩具卡車資源（即操作時間）的單位成本小于售單位成本小于售價價。 而對于玩具火車，成本大于它的售價成本大于它的售價。 借助于簡約費用的定義，現(xiàn)在可以看到無利益的變量（如x1）用下面兩種方法使它成為有利可圖： （1）增加單位收入； （2）減少單位成本 n 一般情況下，產(chǎn)品銷售價格難以提高，因為這由市場決定。n 現(xiàn)實的選擇是減少資源消