運(yùn)籌學(xué)導(dǎo)論第八版 3單純形法及敏感性分析

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

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

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

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

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

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

7、(0，0，4，5)(0，2.5，1.5，0)(2，0，0，3)(5，0，-6，0)(0，4，0，-3)11非基（零）變量基變量基本解相應(yīng)的角點(diǎn)可行否？目標(biāo)值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)點(diǎn)）可以看到，當(dāng)問題的大小增加后（即m與n變大），枚舉所有角點(diǎn)的過程包含巨量的計(jì)算，如m=10和n=20，必須求解184

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

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

10、A處的非基變量x2變成B處的基變量，并且在A處的基變量s2變成在A處的非基變量，稱X2為進(jìn)基變量，s2為離基變量，類似地，在點(diǎn)B，x1進(jìn)基，s1離基，因此到了C點(diǎn)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 單純形算法的計(jì)算細(xì)節(jié)基Zx1x2s1s2s3s4解Z1-5-40

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

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

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

14、法應(yīng)用到上表在基列中，以x1替換s1 新的x1行=當(dāng)前s1行6=(0 6 4 1 0 0 0 24)/6=(0 1 2/3 1/6 0 0 0 4)新的Z行=當(dāng)前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行=當(dāng)前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行=當(dāng)前s3行-(-1)新的x1行=(0 -1 1 0 0 1 0 1)-(-1) (0

15、1 2/3 1/6 0 0 0 4)=(0 0 5/3 1/6 0 1 0 5)新的s4行=當(dāng)前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），因此新的單純形表為進(jìn)基基Zx1x2s1s2s3s4解Z10-2/35/600020s1012/31/60104離基s2004/3-1/61002s3005/31/60105s400100012新的基本解是（x1, s2, s3, s4）=(4 2 5 2)，而Z=20與下面的公式計(jì)算結(jié)果一致新的Z=原來的

16、Z + 新的x1的值 它的目標(biāo)系數(shù)=0+4 5=2022基進(jìn)基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是進(jìn)基變量，由可行性條件可行性條件可得下表因此，s2離開基本解，并且x2的新值是1.5，相應(yīng)增加的Z值是2/3x2=2/31.5=1,它產(chǎn)生新的Z=20+1=21在基列中，用進(jìn)基變量x2替換s2，應(yīng)用高斯-喬丹行運(yùn)算，有：1. 新的樞軸行x2行=當(dāng)前s2行4/3；2. 新的Z行=當(dāng)前Z行-(-2/3)新的x2行；3. 新的x1行=當(dāng)前x1行-

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

18、匱乏市場限制s3=5/2充裕需求限制s4=1/2充裕單純形的計(jì)算結(jié)果還給出了資源的使用情況：如果松弛變量為零，表明資源全部用完，該資源是匱乏的如果松弛變量為正，表明資源尚有余存，該資源是充裕的25練習(xí)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)性條件 在極大化（極小化）問題中，進(jìn)基變量是Z行中具有最負(fù)（最正）系數(shù)的非基變量。如有多個(gè)可任選其一。當(dāng)非基變量的所有Z行系數(shù)是非負(fù)的（非正的）時(shí)，迭代達(dá)到最優(yōu)可行性條件可行性條件 對(duì)于極

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

20、規(guī)劃方便地提供了全部為松弛變量的初始基本可行解。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 需要增加人工變量以扮演松弛變量的角色，然后在迭代中加以適當(dāng)處理。帶有（=）和（）的約束的線性規(guī)劃求解該如何求解？303.4.1 大M方法 大M方法以等式形式

21、的線性規(guī)劃開始。如果第 i 個(gè)約束沒有松弛變量，則將人工變量 Ri 加入到初始解中，類似于所有松弛變量為基本解的情況。然后在目標(biāo)函數(shù)中對(duì)他們指定非常大的懲罰，強(qiáng)迫人工變量在最優(yōu)解中等于零。如果問題有可行解，該種情況總會(huì)發(fā)生。懲罰規(guī)則懲罰規(guī)則已知M為一個(gè)充分大的數(shù)，人工變量的目標(biāo)系數(shù)表示為適當(dāng)?shù)膽土P，如果MM在極大化問題中人工變量的目標(biāo)系數(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

22、0松弛變量剩余變量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ù)運(yùn)算的傳統(tǒng)，并用數(shù)值代替，以簡化表達(dá).M值應(yīng)該多大？依賴于初始線性規(guī)劃的數(shù)據(jù)：u M相對(duì)于初始目標(biāo)系數(shù)必須充分大，使得M能起到懲罰作用，迫使人工變量在最優(yōu)值為零。u 也不希望M太大，否則在計(jì)算機(jī)求解中，非常大的數(shù)與非常小的數(shù)值在一起運(yùn)算時(shí)，可能產(chǎn)生嚴(yán)重的四舍五入。本例似乎取M=10033基x1x2x3R1R2x4解z-

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

24、-4-10-100-10000R13101003R243-10106x41200014基x1x2x3R1R2x4解z696399-100000900R13101003R243-10106x41200014X1為進(jìn)基！最正系數(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/30

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

26、成等式約束形式，并在約束中增加必要的人工變量（如大M方法一樣），以保證找到一個(gè)初始基本解。接下來，求相應(yīng)方程的基本解，無論線性規(guī)劃是求極大化還是極小化，總是使得人工變量之和達(dá)到最小。如果其和的最小值為正，則線性規(guī)劃問題無可行解（正的人工變量約束不滿足）。否則進(jìn)行階段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

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

28、為最小值 r =0，階段 I 產(chǎn)生了基本可行解x1=3/5，x2=6/5，x4=1。此時(shí)人工變量以完成了它的使命，從而我們能夠從表中連同他們所在的列一起去掉，轉(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基變量

29、x1和x2在z行有非零的系數(shù)，使用下列計(jì)算將非零系數(shù)替換出去： 新的z行=舊的z行+（4 x1行+ 1x2行）最優(yōu)解為 x1=2/5 ，x2=9/5，z=17/5； R1=0，R2=0，x3=1，x4=044基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實(shí)際上幾乎所有的商業(yè)軟件包都采用兩階段法來求解線性規(guī)劃。實(shí)際中，大M方法由于潛在的不利的舍入誤差而可能從來不用的。介紹大M方法純粹處于歷史原因，其發(fā)展早于兩階段法。在最后一張表中人工變量及其

30、所在列被去掉，這只有在他們?nèi)渴欠腔兞繒r(shí)才會(huì)發(fā)生。如果在階段I的最后一張表中有一個(gè)或者多個(gè)人工變量是基變量（取零值），則必須采取如下附加步，才能在階段II開始前去掉人工變量。46第一步 選擇一個(gè)零人工變量離開基本解，并指定它所在的行為樞軸行。進(jìn)基變量可以是樞軸行具有系數(shù)非零的任意非基變量，完成相應(yīng)的單純法迭代。第二步 從表中去掉剛剛離基的人工變量的列。如果所有的人工變量已經(jīng)被去掉轉(zhuǎn)入階段II，否則轉(zhuǎn)回第一步。第一步的目的是保持基變量的可行性將不受影響，不論其樞軸元素是正還是負(fù)的總能使得零人工變量變?yōu)榉腔兞俊?7課后作業(yè)： P94，12題； P98，5（a）題、（d）題；1. P102，5題

31、.483.5 單純形法的特殊情況本節(jié)考慮單純形法中的4種情況：n 退化；n 可選擇最優(yōu)解；n 無界解；n 不存在（或者可行解）（1）介紹這些情況的理論解釋（2）提供相應(yīng)的實(shí)際解釋493.5.1 退化在單純形方法可行性條件中，最小比值可能循環(huán)出現(xiàn)，可以隨意打破這種循環(huán)。當(dāng)這樣的情況發(fā)生時(shí)，至少有一個(gè)基變量在下一次迭代中為零，并稱新的解退化。Max z=3x1+9x2St x1+9x28 x1+2x24 x1，x2050迭代基x1x2x3x4解0z-3-9000 x2進(jìn)基x314108x3進(jìn)基x4120141z-3/409/4018x2進(jìn)基x21/411/402x3進(jìn)基x41/20-1/2102z

32、003/23/218(最優(yōu)值)x2011/2-1/22x110-120在迭代中，x3和x4均可以是離基變量，在迭代1構(gòu)成退化，在基變量x4出現(xiàn)零值，再一次迭代后，達(dá)到最優(yōu)值。51x1+9x28（多余約束）x1+2x24超定的到3條直線通過最優(yōu)點(diǎn)，使得某些約束是多余的。目前尚沒有有效的計(jì)算方法能直接從表中識(shí)別多余的約束。退化的含義1，注意迭代1和2，你將注意到目標(biāo)值沒有改進(jìn)（Z=18）。單純形方法有可能進(jìn)入一個(gè)重復(fù)迭代的序列，永遠(yuǎn)不改進(jìn)目標(biāo)值，也永遠(yuǎn)不滿足最優(yōu)性條件。退化的含義2，兩個(gè)迭代盡管對(duì)基變量和非基變量分類不一致，但對(duì)于所有的變量和目標(biāo)值都產(chǎn)生同樣的值。在迭代中（遇到退化的時(shí)候）是否可以

33、停止計(jì)算，答案否定，因?yàn)榭赡艹霈F(xiàn)暫時(shí)退化。523.5.2 可選擇最優(yōu)解當(dāng)目標(biāo)函數(shù)平行于非冗余的緊約束目標(biāo)函數(shù)平行于非冗余的緊約束（binding constraint）（即在最優(yōu)解處作為方程而被滿足的約束）解，目標(biāo)函數(shù)可以在多于一個(gè)解點(diǎn)處相同的最優(yōu)解，因此產(chǎn)生可選擇最優(yōu)解。Max z=2x1+4x2St x1+2x25 x1+x24 x1，x20 x1+x24x1+2x25z=2x1+4x2最優(yōu)基本可行解BCBC上任意一點(diǎn)都表示了具有相同目標(biāo)值Z=10的可選最優(yōu)解53迭代基x1x2x3x4解0z-2-4000X2進(jìn)基x312105X3離基x4110141(最優(yōu)值)z002010X1進(jìn)基x21/

34、211/205/2X4離基x41/20-1/213/22(可選最優(yōu)解)z002010 x2011-11x110-123迭代1給出了最優(yōu)解x1=0，x2=5/2和z=10，它與點(diǎn)B相一致。如何從這個(gè)表格中知道可選擇最優(yōu)解存在呢？看看迭代看看迭代1行方程非基變量的系數(shù)行方程非基變量的系數(shù)。非基變量x1的系數(shù)為零，表明x1可以進(jìn)入基本解而不會(huì)改變Z值，但會(huì)引起變量值的改變。迭代2正是這個(gè)情況：x1進(jìn)基，x4離基，新的解點(diǎn)x1=3,x2=1,z=1054單純形方法僅能確定B點(diǎn)和C點(diǎn)，從數(shù)學(xué)角度來說，BC上的點(diǎn)(x1,x2)作為點(diǎn)B和C的非負(fù)的加權(quán)平均，因此B：x1=0，x2=5/2C：x1=3，x2=

35、1則線段BC上的所有的點(diǎn)如下12(0)(1)(3)33,0153( )(1)(1)122xx 當(dāng)=0，為C點(diǎn)；當(dāng)=0，為B點(diǎn)；否則為B到C之間55在實(shí)踐中，可選擇最優(yōu)解是有用的，因?yàn)槲覀兛梢詮脑S多解中選擇而不會(huì)損害目標(biāo)。例如在前例中，在B處顯示只有第二項(xiàng)活動(dòng)是正值；而在C處，兩項(xiàng)活動(dòng)都為正值。如果例子描述的是一種混合產(chǎn)品情形，生產(chǎn)兩種產(chǎn)品比生產(chǎn)一種產(chǎn)品對(duì)于滿足市場或許更加有優(yōu)勢，在這樣的情況下C處解可能更加吸引人，也就是不要把所有的雞蛋放在一個(gè)籃子里面。563.5.3 無界解在一些線性規(guī)劃中，可以無限地增加變量的值但不破壞任何一個(gè)約束，這個(gè)就意味這解空間中至少又一個(gè)變量是無界的。其結(jié)果是，目標(biāo)

36、值可以無限制的增加（max情形）或減少（min情形），此時(shí)解空間和最優(yōu)目標(biāo)都是無界的。出現(xiàn)無界點(diǎn)可能是由于模型構(gòu)造不合理。此類模型中最大可能的缺陷是一個(gè)或多個(gè)非多余約束沒有考慮在內(nèi)，一些約束參數(shù)估計(jì)錯(cuò)誤57Max z=2x1+x2St x1-2x210 2x1 40 x1，x20通過單純形法迭代會(huì)發(fā)現(xiàn)，x2可以無限制的增加而不破壞任何約束，因?yàn)閤2每增加一個(gè)單位，z將增加1；x2將增加至無窮，使得z無窮大，因此問題無有界解。無界解空間無界目標(biāo)值z=2x1+x2x1-2x210無界變量的下方的系數(shù)將會(huì)產(chǎn)生（也就系數(shù)將會(huì)產(chǎn)生（也就是可行性條件比的分母）是零或者負(fù)的是可行性條件比的分母）是零或者負(fù)的

37、基x1x2x3x4解z-2-1000 x31-11010 x4200140583.5.4 不可行解n 具有不相容約束的線性規(guī)劃模型沒有可行解。假如所有的約束類型都是類型并具有非負(fù)的右端項(xiàng)，則這種情況將永遠(yuǎn)不會(huì)出行，因?yàn)樗沙谧兞刻峁┝艘粋€(gè)可行解。n 對(duì)于混合類型的約束，僅當(dāng)模型有可行空間時(shí)，人工變量在最優(yōu)解處可以取零，否則至少有一個(gè)人工變量在最優(yōu)迭代中取正。n 不可行解空間表明模型的構(gòu)建有可能是不正確的。59Max z=3x1+2x2St 2x1+x22 3x1+ 4x212 x1，x20z=3x1+2x22x1+x223x1+ 4x212偽最優(yōu)解迭代基x1x2x3x4R解0z-303-4021

38、0000-1200X2進(jìn)基x3210105X3離基R1101141(偽最優(yōu))z50101004020-396x2210102R-50-1-414最優(yōu)迭代1顯示人工變量R取值為正，表明問題不可行，上圖也展示了不可行解空間。由于允許人工變量為正，單純形方法實(shí)際上已經(jīng)將不等式的方向顛倒，從3x1+ 4x212變?yōu)?x1+ 4x212，這個(gè)結(jié)果為偽偽最優(yōu)最優(yōu)。M=100課后作業(yè)： P28，第5題； P33，第1題； P36，第2題； P45，第4題； P61，第10題；1. 以上作業(yè)請給出最終的計(jì)算結(jié)果。613.6 靈敏度分析在線性規(guī)劃模型中，參數(shù)通常是不精確的，借助于靈敏度分析，我們能夠探索這種不確

39、定性對(duì)最優(yōu)解質(zhì)量的影響。例如1. 某種產(chǎn)品估計(jì)的單位利潤/成本發(fā)生變動(dòng)，我們是否還能維持原先的產(chǎn)品組合構(gòu)成及產(chǎn)量，以實(shí)現(xiàn)最優(yōu)目標(biāo)？2. 公司準(zhǔn)備添置機(jī)器/雇員/原材料，應(yīng)該以什么依據(jù)來決定優(yōu)先順序？n 線性規(guī)劃中，模型參數(shù)（輸入數(shù)據(jù)）能夠在一定的限度內(nèi)變化而不引起最優(yōu)解的改變。這些內(nèi)容涉及靈敏度的分析n 如果輸入的數(shù)據(jù)中做特定的變化后如何得到新的最優(yōu)解。623.6.1 圖形靈敏度分析考慮兩種情況： 最優(yōu)解對(duì)于資源的可利用性（約束的右端項(xiàng)）變化的靈敏度分析；最優(yōu)解對(duì)于單位利潤或單位費(fèi)用（目標(biāo)函數(shù)系數(shù)）變化的靈敏度分析；maxmin0 z=stCXAX = bX或63例3.6-1 （右端項(xiàng)變化）J

40、OBCO公司在兩臺(tái)機(jī)器上生產(chǎn)兩種產(chǎn)品。1個(gè)單位的產(chǎn)品1需要2小時(shí)機(jī)器1和1小時(shí)機(jī)器2；對(duì)于產(chǎn)品2，一個(gè)單位產(chǎn)品需要1小時(shí)機(jī)器1和3小時(shí)機(jī)器2.每個(gè)單位產(chǎn)品1和產(chǎn)品2的收益分別是30美元和20美元。每臺(tái)機(jī)器的日加工時(shí)間是8小時(shí)。令x1和x2分別表示產(chǎn)品1和產(chǎn)品2的日產(chǎn)量，則線性規(guī)劃模型給出如下：Max z=30 x1+20 x2St 2x1+ x28（機(jī)器1） x1 +3x2 8（機(jī)器2） x1，x20maxmin0 z=stCXAX = bX或64如果日工作能力從8小時(shí)增加到9小時(shí)，則生產(chǎn)能力增加的收益率是多少？2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=

41、128X1=3.8，x2=1.4，z=142Gc11ZZ142 12814.0(/)98CG機(jī)器 增加 小時(shí)工作能力產(chǎn)生美元 小時(shí)工作能力收益的變化率的改變（ 點(diǎn)變化到 ）CD計(jì)算出的變化率提供了模型的輸入（資源）和它的輸入（總收益）的直接聯(lián)系，表示成為資源的單位價(jià)值：即可用資源的單位變化引起目標(biāo)函數(shù)的變化。這意味著機(jī)器1的能力增加（或者減少）1個(gè)單位，將增加（或減少）收益14美元。65盡管目標(biāo)函數(shù)變化率的恰當(dāng)說法是資源的單位價(jià)值，然而在技術(shù)上的名稱是對(duì)偶價(jià)格（dual price）或者影子價(jià)格（shadow price）。2x1+ x292x1+ x28x1 +3x2 8X1=3.2，x2=

42、1.6，z=128X1=3.8，x2=1.4，z=142CGBF當(dāng)機(jī)器1工作能力變化（增加或者減少），即其約束平移到線段BF的任意一點(diǎn)，每小時(shí)14美元的對(duì)偶價(jià)格仍然有效。給定對(duì)偶價(jià)格的適用范圍：機(jī)器1工作能力最小值B點(diǎn)=（0，2.67）=20+12.67=2.67小時(shí)機(jī)器1工作能力最大值F點(diǎn)=（8，0）=28+10=16小時(shí)在2.67機(jī)器1的工作能力16小時(shí)時(shí)，對(duì)偶價(jià)格14美元/小時(shí)將保持不變DE66類似方法可以驗(yàn)證，機(jī)器2工作能力的對(duì)偶價(jià)格是每小時(shí)2美元，它在如下區(qū)域內(nèi)變化時(shí)保持不變，即約束平行移動(dòng)到線段DE的任意一點(diǎn)時(shí)，將產(chǎn)生下面的限制區(qū)域：機(jī)器2工作能力最小值D點(diǎn)=(0，4)=14+30

43、=4小時(shí)機(jī)器2工作能力最大值E點(diǎn)=(0，8)=28+38=24小時(shí)對(duì)于機(jī)器2，在如下區(qū)域?qū)ε純r(jià)格2美元/小時(shí)將保持不變4機(jī)器 2 的工作能力24小時(shí)機(jī)器1和機(jī)器2計(jì)算出的限制稱為可行性區(qū)域（feasibility range）67關(guān)于線性規(guī)劃問題, 對(duì)偶價(jià)格能夠作出相應(yīng)的經(jīng)濟(jì)決策, 比如：問題1 如果JOBCO能夠增加兩種機(jī)器的能力，哪種機(jī)器應(yīng)該有更高的優(yōu)先權(quán)？機(jī)器1和機(jī)器2的對(duì)偶價(jià)格分別為14和2美元/小時(shí)，這時(shí)優(yōu)先權(quán)應(yīng)該是機(jī)器1問題2 一項(xiàng)建議提出，要以10美元/小時(shí)的額外費(fèi)用增加機(jī)器1和機(jī)器2的能力，這項(xiàng)建議可取嗎？對(duì)于機(jī)器1，每小時(shí)附加凈收入為14-10=4美元；而對(duì)于機(jī)器2凈收入為2

44、-10=-8美元，因此只應(yīng)該增加機(jī)器1.68問題3 如果機(jī)器1的工作能力從現(xiàn)在的8小時(shí)增加到13小時(shí)，這個(gè)增加將如何影響最優(yōu)收益？對(duì)于機(jī)器1的對(duì)偶價(jià)格是14美元，在2.67，16小時(shí)的區(qū)域內(nèi)使用，所提出的增加到13小時(shí)落在可行域內(nèi)，因此收入增加量是14(13-8)=70美元，這意味著總收入將增加到（當(dāng)前收益+收益變化）=128+70=198美元。問題4 假定機(jī)器1的工作能力可以增加到20小時(shí)，這個(gè)增加將如何影響最優(yōu)收益？所提出的改變超出2.67，16小時(shí)這個(gè)保持14美元的對(duì)偶價(jià)格區(qū)域，因此我們只能增加到16小時(shí)，超出部分需要進(jìn)一步計(jì)算才能得到答案。落在可行域之外不意味著問題無解，只是我們沒有充

45、分信息立刻作出決策。69問題5 只要資源的改變在可行域內(nèi)，最優(yōu)目標(biāo)值的改變就等于（對(duì)偶價(jià)格資源的改變），相應(yīng)變量的最優(yōu)值是多少？變量的最優(yōu)值一定發(fā)生改變，然而從圖解得到的信息水平并不能充分確定新值。703.6.2 代數(shù)靈敏度分析右端項(xiàng)的變化TOYCO通過3種操作裝配3種玩具玩具火車、卡車和汽車。這個(gè)3種操作可用時(shí)間限制分別為430、460和420分鐘。這3個(gè)產(chǎn)品的單位收入分別為3、2和5美元。每輛火車在3種操作中的裝配時(shí)間分別是1、3和1分鐘，玩具卡車和汽車的時(shí)間分別是(2,0,4)和(1,2,0).令x1，x2，x3分別為每天裝配玩具火車、卡車和汽車的單位數(shù)量，則規(guī)劃模型如下：Max z=3

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

47、=430-x4 (操作1)3x1 +2x3 =460 -x5 (操作2)x1+4x2 = 420-x6 (操作3)或者借助于上式，我們可以是說，松弛變量上減少1分鐘就等價(jià)于操作時(shí)間上增加1分鐘。73可以用上述信息從最優(yōu)表的Z的方程中確定對(duì)偶價(jià)格：Z+4x1+x4+2x5+0 x6=1350可以寫成Z=1350-4x1+x4+2x5+0 x6 =1350-4x1+1(-x4) +2(-x5)+0(-x6)已知松弛變量值的減少等價(jià)于在它的操作時(shí)間上的增加，因此Z=1350-4x1+1增加操作1的時(shí)間 + 2增加操作2的時(shí)間 + 0增加操作3的時(shí)間74這個(gè)方程顯示了：（1）在操作1上時(shí)間增加1分鐘z

48、將增加1美元；（2）在操作2上時(shí)間增加1分鐘z將增加2美元；（3）在操作2上時(shí)間增加1分鐘z將保持不變；概括最優(yōu)表的z行如下：基x1x2x3x4x5x6解z4001201350Z行直接產(chǎn)生的對(duì)偶價(jià)格如下表：資源松弛變量松弛變量的最優(yōu)z方程系數(shù)對(duì)偶價(jià)格（美元/分鐘）操作1x411操作2x522操作3x60075操作3的零對(duì)偶價(jià)格意味著，分配給這個(gè)操作更多的生產(chǎn)時(shí)間沒有經(jīng)濟(jì)效益。這個(gè)結(jié)果有意義，因?yàn)橘Y源已經(jīng)參與了，證據(jù)就是，在最優(yōu)解中與操作3相對(duì)應(yīng)的松弛變量是正值(=20)（即資源過多）. 至于操作1和2每一個(gè)松弛變量，增加1分鐘將分別提高1美元和2美元。對(duì)偶價(jià)格還表明，當(dāng)分配額外資源時(shí)，操作2將

49、得到更高的優(yōu)先權(quán)，因?yàn)樗膶?duì)偶價(jià)格是操作1的2倍。上述計(jì)算說明對(duì)偶價(jià)格是如何從最優(yōu)表的約束中確定的。對(duì)于約束，該方法仍然適用。但是對(duì)偶價(jià)格將于對(duì)應(yīng)的約束符號(hào)相反。等式約束則還需要“相關(guān)的”計(jì)算。76可行性區(qū)域的確定令D1, D2, D3分別是分配給操作1、2和3的每天生產(chǎn)時(shí)間的該變量（正的或者負(fù)的），模型可寫為Max z=3x1+2x2+5x3St x1+2x2+x3430+ D1 （操作1） 3x1 +2x3 460 + D2 （操作2） x1+4x2 420 + D3 （操作3） x1，x2 ，x3 0我們將考慮同時(shí)發(fā)生改變的一般情況，每次只改變一個(gè)變量的特殊情況將從這些結(jié)果中得到。77具

50、體方法是：用所修正的右端項(xiàng)從新計(jì)算最優(yōu)單純形表，然后獲得保持解可行的條件，即最優(yōu)表的右端項(xiàng)保持非負(fù)。為了說明右端項(xiàng)如何重新保持計(jì)算，我們以修正解列開始，即在初始單純形表中使用新的右端項(xiàng)：430+D1、460+D2、420+D3，因此基x1x2x3x4x5x6解右端項(xiàng)D1D2D3z-3-2-50000000 x2121100430100 x3302010460010 x614000142000178基x1x2x3x4x5x6解右端項(xiàng)D1D2D3z4001201350120 x2-1/4101/2-1/401001/2-1/40 x33/20101/2023001/20 x6200-21120-2

51、11在D1，D2，D3下的列與初始基本列x4，x5，x6下的那些列是相同的。這意味著當(dāng)我們像在初始模型那樣完成相同的單純形迭代是，兩組中的列也一定是完全相同。實(shí)際上新的最優(yōu)解變成79新的最優(yōu)表提供了如下的最優(yōu)解：1221232612313502111002412302202zDDxDDxDxDDD只要所有變量非負(fù)，則當(dāng)前解保持可行，這就導(dǎo)出可行性條件可行性條件212326123111000241230022020 xDDxDxDDD任意同步改變D1、D2、D3，只要滿足這些不等式，都將保持解可行。如果所有的條件滿足，則可在上述等式約束中直接替換D1、D2、D3，來找到新的最優(yōu)解。80假設(shè)對(duì)于操

52、作1、2、3的可利用生產(chǎn)時(shí)間分別是480、440和410分鐘，則D1=480-430=50，D2=440-460=-20，D3=410-420=-10，在可行性條件中替換，得到23611100(50)( 20)1300241230( 20)22002202(50)( 20)( 10)1100 xxx （可行）（可行）（不可行）81計(jì)算表明x60，因此當(dāng)前解并沒有保持可行。需要額外的計(jì)算才能得到新的解（本課不介紹）。如果資源的變化使得D1=-30，D2=-12，D3=10，則23611100( 30)( 12)880241230( 12)22402202( 30)( 12)(10)780 xxx

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

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

55、所有單個(gè)可行性區(qū)域。2361000.5( 30)0.25( 12)11802300.5( 12)2240202(30)( 12)(100)480 xxx （可行）（可行）（可行）例如D1=30，D2=-12，D3=100，則85這意味著對(duì)偶價(jià)格仍然可適用，因此能夠從對(duì)偶價(jià)格中計(jì)算出新的最優(yōu)目標(biāo)值z=1350+1(30)+2(-12)+0(100)=1356美元（1）如果約束右端項(xiàng)的該變量Di，i=1,2,3,m，在同步改變時(shí)滿足所有可行性條件，或相應(yīng)的Di在單個(gè)發(fā)生改變時(shí)仍然落在可行性區(qū)域內(nèi)，則對(duì)偶價(jià)格有效。（2）如果同步的可行性條件不滿足，或因?yàn)閱蝹€(gè)的可行性區(qū)域被破壞，對(duì)偶價(jià)格就不再有效。此

56、時(shí)，可以用新的Di 值重新解該問題，或者用后續(xù)方法來解決。86課后作業(yè)P123，第6題P125，第11題87例（目標(biāo)系數(shù)的變化）2x1+ x28x1 +3x2 8X1=3.2，x2=1.6，z=128CGBFDE z=30 x1+20 x2C點(diǎn)為最優(yōu)解點(diǎn)。收入單位數(shù)的變化（目標(biāo)函數(shù)系數(shù)）將改變z的斜率。然而從右圖可以看到，只要目標(biāo)函數(shù)位于直線BF和DE之間，最優(yōu)點(diǎn)將保持在C，這2個(gè)約束確定了最優(yōu)點(diǎn)，這意味著存在一個(gè)關(guān)于目標(biāo)函數(shù)系數(shù)的區(qū)域，在這個(gè)區(qū)域內(nèi)最優(yōu)解在C點(diǎn)將保持不變。maxmin0 z=stCXAX = bX或3.6.3 圖形靈敏度分析目標(biāo)函數(shù)88可以寫出目標(biāo)函數(shù)的一般形式：Max z=

57、c1x1+c2x2可以想象，直線z在C處轉(zhuǎn)動(dòng)，并且它能夠沿著順時(shí)針和逆時(shí)針轉(zhuǎn)動(dòng)，最優(yōu)解始終保持在點(diǎn)C，只要z=c1x1+c2x2介于直線2x1+ x2=8，x1 +3x2 =8之間。這意味著比值c1/c2可以在1/3與2/1之間變化，這產(chǎn)生如下條件：121231cc這個(gè)信息能夠直接提供有關(guān)最優(yōu)解的答案。例如89問題1 假設(shè)產(chǎn)品1和產(chǎn)品2的單位收入分別改變到35美元和25美元，當(dāng)前的最優(yōu)解保持不變嗎？新的目標(biāo)函數(shù)為 Max z=35x1+25x2。解在C處保持最優(yōu)，因?yàn)閏1/c2=35/25=1.4，保持在最優(yōu)區(qū)域1/3, 2之間。盡管變量在最優(yōu)點(diǎn)C的保持不變，z的最優(yōu)值變到35(3.2)+25

58、 (1.6)=152美元。當(dāng)比值落在這個(gè)區(qū)域之外，需要增加額外的計(jì)算來求出新的最優(yōu)解。90問題2 假設(shè)產(chǎn)品2的單位收入固定在當(dāng)前值c2=20美元上，相應(yīng)于c1，即產(chǎn)品1的單位收入保持最優(yōu)值不變的區(qū)域是什么？在條件 中替換c2=20，得到121231cc1/320c1220，即6.67c140這個(gè)區(qū)域稱為c1的最優(yōu)區(qū)域，并隱含的假設(shè)c2固定在20美元。盡管這一節(jié)僅處理了二維變量問題，但是這些結(jié)果奠定了對(duì)一般線性規(guī)劃進(jìn)行靈敏度分析的基礎(chǔ)！913.6.3 代數(shù)靈敏度分析目標(biāo)函數(shù)本節(jié)從之前的圖形法處理的保持線性規(guī)劃最優(yōu)解的條件，拓展到多維的代數(shù)方法。簡約費(fèi)用簡約費(fèi)用在TOYCO模型中，在最優(yōu)表中目標(biāo)Z

59、行系數(shù)是基x1x2x3x4x5x6解z4001201350因此z行方程是 z+4x1+x4+2x5=1350即 z=1350-4x1-x4-2x5 最優(yōu)解建議不生產(chǎn)玩具火車（X1=0）。該建議由z行方程的信息得到證實(shí)，因?yàn)閤1在當(dāng)前零值情況下，每增加一個(gè)單位將降低4美元，即Z=1350-4(1)-1(0)-2(0)=1346美元。92可以把Z行方程中x1的系數(shù)(=4)作為費(fèi)用的單位，因?yàn)樗饅的減少。但是這個(gè)“費(fèi)用”來自哪里？在原來的模型中，x1的單位收入是3美元。我們還知道，每個(gè)玩具火車消耗資源（操作時(shí)間），它本身也導(dǎo)致費(fèi)用。因此，從優(yōu)化的觀點(diǎn)來看，x1的”吸引力”依賴于單位收入與一個(gè)單位

60、資源消耗的費(fèi)用的相對(duì)值。這個(gè)關(guān)系在線性規(guī)劃文獻(xiàn)中被公式化，定義簡約費(fèi)用如下： 應(yīng)該盡量降低單位簡約費(fèi)用，即提高利潤率，以提高運(yùn)營系統(tǒng)的效益！單位利潤=單位收入-單位消耗資源費(fèi)用（成本）單位簡約費(fèi)用=單位消耗資源費(fèi)用（成本）-單位收入93如何理解這個(gè)定義的含義？在TOYCO模型中，玩具卡車的單位收入(=2美元)少于玩具火車的單位收入(=3美元). 然而，最優(yōu)解選擇生產(chǎn)玩具卡車卻不生產(chǎn)玩具火車(x1=0).原因在于用于玩具卡車資源（即操作時(shí)間）的單位成本小于售單位成本小于售價(jià)價(jià)。 而對(duì)于玩具火車，成本大于它的售價(jià)成本大于它的售價(jià)。 借助于簡約費(fèi)用的定義，現(xiàn)在可以看到無利益的變量（如x1）用下面兩種方法使它成為有