北外奧鵬作業(yè)運(yùn)籌學(xué)

1、運(yùn)籌學(xué)作業(yè)精講運(yùn)籌學(xué)作業(yè)精講第一單元某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，其單位利潤分別為20元和30元。每生產(chǎn)一件甲產(chǎn)品需勞動(dòng)力3個(gè)，原材料2千克，設(shè)備4小時(shí)；每生產(chǎn)一件乙產(chǎn)品需勞動(dòng)力7個(gè)，原材料4千克，設(shè)備3小時(shí)。企業(yè)現(xiàn)有勞動(dòng)力240個(gè)，原材料150千克，設(shè)備可用時(shí)間為250小時(shí)。問：如何安排生產(chǎn)計(jì)劃，才能使所獲總利潤最大？寫出線性規(guī)劃模型；化成問：如何安排生產(chǎn)計(jì)劃，才能使所獲總利潤最大？寫出線性規(guī)劃模型；化成標(biāo)準(zhǔn)形式；用圖解法進(jìn)行求解。標(biāo)準(zhǔn)形式；用圖解法進(jìn)行求解。解：設(shè)解：設(shè) x x1 1和和x x2 2分別表示產(chǎn)品甲和乙的產(chǎn)量，分別表示產(chǎn)品甲和乙的產(chǎn)量，這樣可以建立如下的數(shù)學(xué)模型。這樣可以建立如下

2、的數(shù)學(xué)模型。目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max20Max20 x x1 1 +30 +30 x x2 2約束條件：約束條件：s.ts.t.3 .3 x x1 1 +7 +7 x x2 2 240 240（勞動(dòng)力限制）（勞動(dòng)力限制） 2 2 x x1 1 + 4 + 4 x x2 2 150 150（原材料限制）（原材料限制） 4 4 x x1 1 + 3 + 3 x x2 2 250 250（設(shè)備限制）（設(shè)備限制） x x1 1，x x2 2 0 0（非負(fù)約束）（非負(fù)約束）化為標(biāo)準(zhǔn)型：化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max20Max20 x x1 1 +30 +30 x x2 2約束條件：約束條件：s

3、.ts.t.3 .3 x x1 1 + 7 + 7 x x2 2 + +x x3 3= 240= 240 2 2 x x1 1 + 4 + 4x x2 2+x x4 4=150=150 4 4 x x1 1 + 3 + 3 x x2 2 + +x x5 5= 250= 250 x x1 1，x x2 2，x x3 3，x x4 4，x x5 5 0 0陰影部分為可行域，陰影部分為可行域，虛線為目標(biāo)函數(shù)線。虛線為目標(biāo)函數(shù)線。由圖可知最優(yōu)解為由圖可知最優(yōu)解為約束約束2 2和約束和約束3 3的的交點(diǎn)，解得坐標(biāo)為交點(diǎn)，解得坐標(biāo)為（55,1055,10），故最），故最優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)優(yōu)生產(chǎn)計(jì)劃為生產(chǎn)甲產(chǎn)

4、品甲產(chǎn)品5555件，乙件，乙產(chǎn)品產(chǎn)品1010件，最大件，最大利潤為利潤為202055+3055+301010 =1400 =1400元。元。第二單元產(chǎn)品資源大號中號小號可用資源量鋁板(張)624400勞力(小時(shí))486360機(jī)器(臺(tái))8410420售價(jià)(元/個(gè))504030某廠生產(chǎn)三種型號的鋁鍋，已知單耗數(shù)據(jù)如下。試制定最優(yōu)生產(chǎn)計(jì)劃使總收入最大。 解：設(shè)解：設(shè) x x1 1、x x2 2、x x3 3分別表示大號、中號、小號鋁鍋的產(chǎn)量，分別表示大號、中號、小號鋁鍋的產(chǎn)量， 這樣可以建立如下的數(shù)學(xué)模型。這樣可以建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max50Max50 x x1 1 +40 +

5、40 x x2 2+30 +30 x x3 3約束條件：約束條件：s.ts.t.6.6x x1 1 +2 +2 x x2 2+ 4 + 4 x x3 3 400 400（鋁板限制）（鋁板限制） 4 4x x1 1 +8 +8 x x2 2+ 6 + 6 x x3 3 360 360（勞力限制）（勞力限制） 8 8x x1 1 +4 +4 x x2 2+10 +10 x x3 3 420 420 （機(jī)器限制）（機(jī)器限制） x x1 1，x x2 2，x x3 3 0 0（非負(fù)約束）（非負(fù)約束） 化為標(biāo)準(zhǔn)型：化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max50Max50 x x1 1 +40 +40 x x

6、2 2+30 +30 x x3 3約束條件：約束條件：s.ts.t.6.6x x1 1 + 2+ 2x x2 2+4 +4 x x3 3 + + x x4 4= 400= 400 4 4x x1 1 +8 +8 x x2 2+6 +6 x x3 3 + + x x5 5 =360 =360 8 8x x1 1 +4 +4 x x2 2+ 10 + 10 x x3 3 + + x x6 6= 420= 420 x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6 0 0 使用單純形法求解：使用單純形法求解：504030000CBXBbx1x2x3x4x5x60 x4

7、400624100200/30 x5360486010900 x6420(8)410001105/2-z050*40300000 x4850-1-7/210-3/4-0 x51500(6)101-1/22550 x1105/211/25/4001/8105-z-2625015*-65/200-25/40 x411000-10/311/6-5/640 x225011/601/6-1/1250 x140107/60-1/121/6-z-300000-350-5/2-5得到最優(yōu)解（得到最優(yōu)解（40,25,0,110,0,040,25,0,110,0,0），最優(yōu)值），最優(yōu)值30003000。即應(yīng)該生產(chǎn)

8、大號鋁鍋。即應(yīng)該生產(chǎn)大號鋁鍋4040個(gè)，中號鋁鍋個(gè)，中號鋁鍋2525個(gè)單位，小號鋁鍋產(chǎn)量為個(gè)單位，小號鋁鍋產(chǎn)量為0 0（不生產(chǎn)），最（不生產(chǎn)），最大利潤為大利潤為30003000元。元。 . 第三單元cj-551300iCBXBbx1x2x3x4x55x220-113100 x510160-2-41-z-10000-2-50線性規(guī)劃Maxz=5x1+5x2+13x3s.t.x1+x2+3x32012x1+4x2+10 x390 x1,x2,x30的最優(yōu)表為：分析在下列條件下，最優(yōu)解分別有什么變化（1）b2由90變?yōu)?0。（2）c1由-5變?yōu)?10。（3）增加一個(gè)約束條件 4 x1 + 3 x2

9、 + 6 x3 50。 解：解：（1 1）由最優(yōu)基不變的條件）由最優(yōu)基不變的條件 Max - Max -bibi/ /iriririr00D DbrbrMinMin- -bibi/ /iriririr00 得得-10 = -10/1D-10 = -10/1Db b2 2 b b2 2由由9090變?yōu)樽優(yōu)?070，超出了允許變化范圍，繼續(xù)計(jì)算，超出了允許變化范圍，繼續(xù)計(jì)算或者由或者由B B-1-1( (b b +D +Db b)=(20,-10)=(20,-10)T T可以知道最優(yōu)基發(fā)生變化，繼可以知道最優(yōu)基發(fā)生變化，繼續(xù)迭代。續(xù)迭代。最優(yōu)解變?yōu)樽顑?yōu)解變?yōu)閤 x1 1 =0 =0，x x2 2

10、= 5 = 5，x x3 3 = 5 = 5，x x4 4 = 0 = 0，x x5 5 = 0 = 0，最優(yōu)值，最優(yōu)值 z z* * = 90 = 90。2 2）c c1 1是非基變量的系數(shù)，最優(yōu)解不變的條件是：是非基變量的系數(shù)，最優(yōu)解不變的條件是：D Dc c1 1 - - s s1 1， c c1 1由由-5-10-5-10，D Dc c1 1 = -5 0 = - = -5 0 = - s s1 1，不影響最優(yōu)，不影響最優(yōu)解。解。 cj-551300CBXBbx1x2x3x4x55x220-113100 x5-10160(-2)-41-z-10000-2-505x252310-53/2

11、13x35-8012-1/2-z-90-1600-1-1（3 3）增加一個(gè)約束條件）增加一個(gè)約束條件4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 50 50，原最優(yōu)解不滿足這個(gè)約束。，原最優(yōu)解不滿足這個(gè)約束。引入松弛變量，得到引入松弛變量，得到4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 + + x x6 6 = 50 = 50填入最優(yōu)單純形表，進(jìn)一步求解，得到最優(yōu)解為填入最優(yōu)單純形表，進(jìn)一步求解，得到最優(yōu)解為X=(0X=(0，1010，10/3)T10/3)T，最優(yōu)值，最優(yōu)值為為280/3280/3。 Ci-551300

12、0CBXBbx1x2x3x4x5x65x220-1131000 x510160-2-4100 x650436001-z-10000-2-5005x220-1131000 x510160-2-4100 x6-1070(-3)-301-z-10000-2-5005x210610-2010 x550/334/300-21-2/313x310/3-7/30110-1/3-z-280/3-14/300-30-2/3第四單元對于以下的運(yùn)輸問題，若各個(gè)銷地少得到對于以下的運(yùn)輸問題，若各個(gè)銷地少得到1 1個(gè)單位的產(chǎn)品，將要求得到賠償，個(gè)單位的產(chǎn)品，將要求得到賠償，金額分別為金額分別為9 9、1212、6 6、

13、1212，問如何組織運(yùn)輸，才能使總費(fèi)用最低。（建立運(yùn)，問如何組織運(yùn)輸，才能使總費(fèi)用最低。（建立運(yùn)輸模型，用最小元素法求初始解，并求出最優(yōu)解）輸模型，用最小元素法求初始解，并求出最優(yōu)解）解：總產(chǎn)量為解：總產(chǎn)量為99+55+110=26499+55+110=264，總銷量，總銷量44+88+88+77=29744+88+88+77=297，產(chǎn)，產(chǎn)銷不平衡且供不應(yīng)求，增加一個(gè)虛擬產(chǎn)地銷不平衡且供不應(yīng)求，增加一個(gè)虛擬產(chǎn)地A4A4，其產(chǎn)量為，其產(chǎn)量為297-297-264=33264=33。由虛擬產(chǎn)地運(yùn)往銷地的費(fèi)用即為賠償金額。因此可以。由虛擬產(chǎn)地運(yùn)往銷地的費(fèi)用即為賠償金額。因此可以建立運(yùn)輸模型如下：建

14、立運(yùn)輸模型如下：使用最小元素法求初始解：使用最小元素法求初始解：說明：每次選擇最小元素，因此依次選擇說明：每次選擇最小元素，因此依次選擇3 3（x x3333）、）、6 6（x x2222）、）、9 9（x x4141）、）、1212（x x1111）、）、1515（x x1414）、）、2121（x x3232）、）、3333（x x1212）。）。）得到初始解得到初始解x x1111=11=11，x x1212=11=11，x x1414=77=77，x x2222=55=55，x x3232=22=22，x x3333=88=88，x x4141=33=33，其余運(yùn)量為，其余運(yùn)量為0 0

15、，總運(yùn)費(fèi)為，總運(yùn)費(fèi)為30033003。 B1B2B3B4產(chǎn)量余額A11211 3311 9()1577 9988, 11A230()655 18()27()550/A324()2122 388 30()11022, 0/A4933 12()6()12()330/銷量44888877297余額11, 033, 110/0/使用位勢法計(jì)算各非基變量檢驗(yàn)數(shù)，填入括號中：使用位勢法計(jì)算各非基變量檢驗(yàn)數(shù)，填入括號中： B1B2B3B4產(chǎn)量位勢uiA1121133119(-6)1577990A230(45)65518(30)27(39)55-27A324(24)212238830(27)110-12A49

16、3312(-18)6(-6)12(0)33-3銷量44888877297位勢vj12331515令令u u1 1=0=0，由基變量滿足，由基變量滿足u ui i+ +v vj j= =c cij ij，依次得到各位勢，依次得到各位勢v v1 1=12=12，v v2 2=33=33，v v4 4=15=15，u u4 4=-3=-3，u u2 2=-27=-27，u u3 3=-12=-12，v v3 3=15=15，再根據(jù)公式，再根據(jù)公式s sij ij = = c cij ij - - u ui i - - v vj j計(jì)算各非基變量檢驗(yàn)數(shù)。計(jì)算各非基變量檢驗(yàn)數(shù)。進(jìn)行調(diào)整：選負(fù)檢驗(yàn)數(shù)中最小

17、的進(jìn)行調(diào)整：選負(fù)檢驗(yàn)數(shù)中最小的s s4242，那么，那么x x4242為主元，作為進(jìn)基為主元，作為進(jìn)基變量。以變量。以x x4242為起點(diǎn)找一條閉回路為起點(diǎn)找一條閉回路x x4242、x x4141、x x1111、x x1212，取偶數(shù)標(biāo)，取偶數(shù)標(biāo)號格的最小運(yùn)量號格的最小運(yùn)量1111作為調(diào)整量，調(diào)整后運(yùn)量為作為調(diào)整量，調(diào)整后運(yùn)量為x x4242=11=11，x x4141=22=22，x x1111=22=22，x x1212=0=0（調(diào)整為非基變量），得到新的基本解，并重新（調(diào)整為非基變量），得到新的基本解，并重新用位勢法計(jì)算檢驗(yàn)數(shù)（令用位勢法計(jì)算檢驗(yàn)數(shù)（令v v2 2=0=0），如下表所

18、示。），如下表所示。 所有非基變量檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解為所有非基變量檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解為x x1111=22=22，x x1414=77=77，x x2222=55=55，x x3232=22=22，x x3333=88=88， x x4141=22=22，x x4242=11=11，其余運(yùn)量為，其余運(yùn)量為0 0，最，最小的總運(yùn)費(fèi)為小的總運(yùn)費(fèi)為28052805。 B1B2B3B4產(chǎn)量位勢uiA1122233(18)9(12)15779915A230(27)65518(30)27(21)556A324(6)212238830(9)11021A492212116(12)12(0)3312

19、銷量44888877297位勢vj-30-180第五單元有一個(gè)工廠要確定明年各季度的生產(chǎn)計(jì)劃，通過訂貨了解到各季度對產(chǎn)品的需求量dk分別為4000件、3000件、4000件和4000件。又知，工廠生產(chǎn)該產(chǎn)品的季度固定成本為10萬元（但如果在某季度中，該種產(chǎn)品1件也不生產(chǎn)，則不需支付固定成本費(fèi)），單位產(chǎn)品的可變成本為50元，由于設(shè)備的能力所限，每季度最多只能生產(chǎn)5000件。若產(chǎn)品銷售不出，則每件每季度的存貯費(fèi)為8元。假設(shè)本年底無存貨轉(zhuǎn)入下年，明年末也不需要留有存貨，問每季度的生產(chǎn)計(jì)劃應(yīng)如何安排（假設(shè)生產(chǎn)產(chǎn)量以千件為單位），才能使生產(chǎn)的總費(fèi)用最??？解：首先建立動(dòng)態(tài)規(guī)劃模型解：首先建立動(dòng)態(tài)規(guī)劃模型（

20、1 1）階段）階段k k：每個(gè)季度作為一個(gè)階段，：每個(gè)季度作為一個(gè)階段，k k=1,2,3,4=1,2,3,4（2 2）狀態(tài)變量）狀態(tài)變量s sk k：第：第k k個(gè)季度初的庫存量（千件）個(gè)季度初的庫存量（千件）（3 3）決策變量）決策變量u uk k：第：第k k個(gè)季度的生產(chǎn)量（千件）個(gè)季度的生產(chǎn)量（千件）（4 4）狀態(tài)轉(zhuǎn)移方程：）狀態(tài)轉(zhuǎn)移方程： s sk k+1+1= = s sk k+ + u uk k - - d dk k ( (需求，千件需求，千件) )（即季（即季度末庫存量度末庫存量= =季度初庫存量季度初庫存量+ +季度生產(chǎn)量季度生產(chǎn)量 - - 季度銷售量或需季度銷售量或需求量）

21、求量）（5 5）階段指標(biāo)：）階段指標(biāo)： g gk k ( (s sk k, , u uk k) =) =生產(chǎn)成本生產(chǎn)成本C(C(u uk k) + ) + 庫存成本庫存成本E(E(s sk k) )（6 6）最優(yōu)指標(biāo)函數(shù)）最優(yōu)指標(biāo)函數(shù)f fk k ( (s sk k) )：第：第k k個(gè)季度的狀態(tài)為個(gè)季度的狀態(tài)為s sk k時(shí)從該季時(shí)從該季度至計(jì)劃結(jié)束的最低總費(fèi)用（萬元）度至計(jì)劃結(jié)束的最低總費(fèi)用（萬元）（7 7）遞推方程：）遞推方程： f fk k ( (s sk k)=min)=ming gk k ( (s sk k, , u uk k)+ )+ f fk k+1+1( (s sk k+1+

22、1) )（8 8）終端條件：）終端條件：f f5 5( (s s5 5)=0)=0下面進(jìn)行求解，采用逆序解法。下面進(jìn)行求解，采用逆序解法。（1 1）k k=5=5，f f5 5( (s s5 5)=0 )=0 （2 2）k k=4=4，00s s4 444，u u4 4=4-=4-s s4 4，s s5 5= =s s4 4+ +u u4 4- -d d4 4（說明：第（說明：第4 4季度的需求為季度的需求為4 4千件，因此庫存量不應(yīng)超過千件，因此庫存量不應(yīng)超過4 4且顯然非負(fù)，且顯然非負(fù)，所以有所以有00s s4 444；年底不需要有庫存，所以生產(chǎn)量；年底不需要有庫存，所以生產(chǎn)量u u4 4

23、 = 4 - = 4 - s s4 4）s4u4(s4)s5g4(s4,u4)g4(s4,u4)+f5(s5)f4(s4)u4*040303030413025.825.825.8322021.621.621.6231017.417.417.414003.23.23.20（3 3）k k=3=3，00s s3 35+5-4-3=35+5-4-3=3，s s4 4= =s s3 3+ +u u3 3- -d d3 3= =s s3 3+ +u u3 3-4-4，Max(0, 4-Max(0, 4-s s3 3)u u3 3Min(5, 8-Min(5, 8-s s3 3) )（說明：前兩季度總產(chǎn)量

24、為（說明：前兩季度總產(chǎn)量為5+5=105+5=10千件，需求量為千件，需求量為3+4=73+4=7千件，所以第千件，所以第3 3季度初最大庫存量季度初最大庫存量=10-7=3=10-7=3千件；千件；在產(chǎn)量需求方面，為了滿足需求，至少生產(chǎn)在產(chǎn)量需求方面，為了滿足需求，至少生產(chǎn)d d3 3- -u u3 3=4 -=4 - u u3 3，且最大產(chǎn)量為且最大產(chǎn)量為5 5千件，后兩個(gè)季度總需求為千件，后兩個(gè)季度總需求為4+4=84+4=8千件，千件，產(chǎn)量不應(yīng)該超過產(chǎn)量不應(yīng)該超過8-8-s s3 3。因此有。因此有00s s3 333，Max(0, 4 - Max(0, 4 - s s3 3)u u3

25、 3Min(5, 8-Min(5, 8-s s3 3) )）（4 4）k k=2=2，00s s2 25-4=15-4=1，s s3 3= =s s2 2+ +u u2 2- -d d2 2= =s s2 2+ +u u2 2-3-3，Max(0, 3-Max(0, 3-s s2 2)u u2 2Min(5, Min(5, 11-11-s s2 2)（5 5）k k=1=1，s s1 1=0=0，s s2 2= =s s1 1+ +u u1 1- -d d1 1= =u u1 1-4-4，44u u1 155最優(yōu)解為最優(yōu)解為s s1 1=0, =0, u u1 1* *=5, =5, s s2

26、 2=1, =1, u u2 2* *=5, s=5, s3 3=3, =3, u u3 3* *=5, =5, s s4 4=4=4，u u4 4* *=0=0即前即前3 3個(gè)季度均生產(chǎn)個(gè)季度均生產(chǎn)50005000件，第件，第4 4個(gè)季度不生產(chǎn)，最低總個(gè)季度不生產(chǎn)，最低總費(fèi)用為費(fèi)用為111.4111.4萬元。萬元。 第六單元某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品。生產(chǎn)一件甲產(chǎn)品需要使用勞動(dòng)力4小時(shí)，能源2個(gè)單位，銷售利潤為16萬元；生產(chǎn)一件乙產(chǎn)品需要使用勞動(dòng)力2小時(shí)，能源4個(gè)單位，銷售利潤為20萬元。企業(yè)目前擁有勞動(dòng)力可用時(shí)間22小時(shí)，能源20個(gè)單位。在制定生產(chǎn)計(jì)劃時(shí)，決策者考慮下述4項(xiàng)目標(biāo)：首先，乙產(chǎn)品

27、的產(chǎn)量不低于甲產(chǎn)品的產(chǎn)量；其次加班費(fèi)用比較高，盡量不要加班；第三，盡可能充分利用能源，但是又不希望再購買；最后，利潤盡量不少于112萬元。求決策方案。（建立目標(biāo)規(guī)劃模型并用單純形法求解）解：設(shè) X1、X2分別表示甲產(chǎn)品和乙產(chǎn)品的產(chǎn)，以建立如下的目標(biāo)規(guī)劃模型：目標(biāo)函數(shù)：MINF = P1 D1+ + P2 D2+ + P3(D3- + D3+) + P4 D4-約束條件： X1 X2 + D1- - D1+ = 0 4 X1 + 2X2 +D2- D2+ = 22 2 X1 + 4X2 +D3- D3+ = 20 16X1 + 20 X2 + D4-D4+ =112 X1，X2，DI-， DI+

28、 0，I = 1, 2, 3, 4（說明：目標(biāo)1和2是不超過目標(biāo)值，因此正偏差變量盡量?。荒繕?biāo)3是恰好達(dá)到目標(biāo)值，因此要求正、負(fù)偏差變量都盡量小；目標(biāo)4要求不少于目標(biāo)值，因此是負(fù)偏差變量盡量小） 下面用單純形法進(jìn)行求解。列出單純形表，取d1-、d2-、d3-、d4-為初始基變量。把最小化問題轉(zhuǎn)為為最大化問題，所以目標(biāo)函數(shù)系數(shù)均乘以-1；基變量的檢驗(yàn)數(shù)應(yīng)該為0，處理初始基本可行解對應(yīng)的各級檢驗(yàn)數(shù)。由于P1、P2優(yōu)先級對應(yīng)目標(biāo)函數(shù)中不含di-，其檢驗(yàn)數(shù)只需取系數(shù)負(fù)值，分別為(0，0，0，-1，0，0，0，0，0，0；0)和(0，0，0，0，0，-1，0，0，0，0；0)。x1x2d1-d1+d2-

29、d2+d3-d3+d4-d4+RHSP1000-10000000P200000-100000P3000000-1-1000P400000000-100d1-1-11-10000000d2-42001-1000022d3-2400001-10020d4-16200000001-1112 P3優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含d3-，所以其檢驗(yàn)數(shù)需要把第3個(gè)約束行加到取負(fù)值的這一行上，得到(2，4，0，0，0，0，0，-2，0，0；20 )。P4優(yōu)先級對應(yīng)的目標(biāo)函數(shù)中含d4-，所以其檢驗(yàn)數(shù)需要把第4個(gè)約束行加到取負(fù)值的這一行上，得到(16，20，0，0，0，0，0，0，0，-1；112 )。列目標(biāo)規(guī)劃的初始

30、單純形表如下：x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10000000P200000-100000P32400000-20020P416200000000-1112d1-1-11-10000000-d2-42001-100002211d3-24*00001-100205d4-16200000001-111228/5下面進(jìn)行計(jì)算。（1）k = 1，在初始單純形表中基變量為（d1-，d2-，d3-，d4-) =（0，22，20，112)； （2）因?yàn)镻1與P2優(yōu)先級的檢驗(yàn)數(shù)均已經(jīng)為非正，所以這個(gè)單純形表對P1與P2優(yōu)先級是最優(yōu)單純形表；（3）下面考慮P3優(yōu)先級，第

31、二列的檢驗(yàn)數(shù)為4最大，此為進(jìn)基變量，計(jì)算相應(yīng)的比值 bi/aij 寫在q列。通過比較，得到d3-對應(yīng)的比值最小，于是取a32（標(biāo)*號）為轉(zhuǎn)軸元進(jìn)行矩陣行變換得到新的單純形表如下。x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10000000P200000-100000P3000000-1-1000P4600000-550-112d1-3/201-1001/4-1/400510/3d2-30001-1-1/21/200124x21/2100001/4-1/400510d4-6*00000-551-1122 （4）下面考慮P4優(yōu)先級，第一列的檢驗(yàn)數(shù)為6最大，此為進(jìn)基變量

32、，計(jì)算相應(yīng)的比值 bi/aij 寫在q列。通過比較，得到d4-對應(yīng)的比值最小，于是取a41（標(biāo)*號）為轉(zhuǎn)軸元進(jìn)行矩陣行變換得到新的單純形表如下。 x1x2d1-d1+d2-d2+d3-d3+d4-d4+RHSP1000-10000000P200000-100000P3000000-1-1000P400000000-100d1-001-1003/2-3/2-1/41/42d2-00001-12-2-1/21/26x20100002/3-2/3-1/121/124x1100000-5/65/61/6-1/62 5 5）當(dāng)前的單純形表各優(yōu)先級的檢驗(yàn)數(shù)均滿足了最優(yōu)條件，故為當(dāng)前的單純形表各優(yōu)先級的檢驗(yàn)

33、數(shù)均滿足了最優(yōu)條件，故為最優(yōu)單純形表。于是得到最優(yōu)解最優(yōu)單純形表。于是得到最優(yōu)解x x1 1=2=2，x x2 2=4=4。 第七單元下圖為一個(gè)交通運(yùn)輸網(wǎng)絡(luò)圖，道路（即?。┡缘臋?quán)數(shù)表示該道路的容量和目前的運(yùn)輸量(cij, fij)，求出該交通運(yùn)輸網(wǎng)絡(luò)的最大運(yùn)輸能力（即網(wǎng)絡(luò)最大流）。解：解：第一次標(biāo)號。第一次標(biāo)號。（1 1）首先給）首先給v vs s標(biāo)號標(biāo)號(0, +)(0, +)； （2 2）看）看v vs s：在?。涸诨? (v vs s, , v v2 2) )上，上，f fs s2 2= =c cs s2 2=2=2，不具備標(biāo)號條件。在弧，不具備標(biāo)號條件。在弧( (v vs s, , v

34、 v1 1) )上，上，f fs s1 1=5=5c cs s1 1=8=8，故給，故給v v1 1標(biāo)號標(biāo)號( (v vs s, , l l( (v v1 1) )，其中，其中l(wèi) l( (v v1 1) = min) = minl l( (v vs s), (), (c cs s1 1- -f fs s1 1) = ) = min+, 8-5 = 3min+, 8-5 = 3。 （3 3）看）看v v1 1：在弧：在弧( (v v1 1, , v v2 2) )上，上，f f1212 =5 =5c c1212=6=6，給，給v v2 2標(biāo)號標(biāo)號( (v v1 1, , l l( (v v2 2

35、) )，其中，其中l(wèi) l( (v v2 2) ) = min= minl l( (v v1 1), (), (c c1212- -f f1212) = min3, 6-5 = 1) = min3, 6-5 = 1；在?。辉诨? (v v1 1, , v v3 3) )上，上，f f1313 =2 =20=20，故給，故給v v4 4標(biāo)號標(biāo)號(- (-v v1 1, , l l( (v v4 4) )，其中，其中l(wèi) l( (v v4 4) = ) = minminl l( (v v1 1),),f f4141 = min3, 2 = 2 = min3, 2 = 2。 （4 4）看）看v v3 3：在弧：在弧( (v v3 3, , v vt t) )上，上，f f3t3t =5 =5c c