運籌學(xué) 復(fù)習(xí)資料

1、第 4 章 目標規(guī)劃 某市準備在下一年度預(yù)算中購置一批救護車，已知每輛救護車購某市準備在下一年度預(yù)算中購置一批救護車，已知每輛救護車購 置價為置價為2020萬元。救護車用于所屬的兩個郊區(qū)縣萬元。救護車用于所屬的兩個郊區(qū)縣, ,各分配各分配x xA A和和x xB B臺，臺， A A縣縣 救護站從接到求救電話到救護車出動的響應(yīng)時間為救護站從接到求救電話到救護車出動的響應(yīng)時間為(40(40- x xA A)min)min， B B縣縣 相應(yīng)的響應(yīng)時間為相應(yīng)的響應(yīng)時間為(50- 4 x(50- 4 xB B )min )min，該市確定如下優(yōu)先級目標。，該市確定如下優(yōu)先級目標。 P P1 1：救護車

2、購置費用不超過：救護車購置費用不超過400400萬元。萬元。 要求建立目標規(guī)劃模型。要求建立目標規(guī)劃模型。 P P2 2： A A縣的響應(yīng)時間不超過縣的響應(yīng)時間不超過5min5min。 P P3 3： B B縣的響應(yīng)時間不超過縣的響應(yīng)時間不超過5min5min。 A x 112233 11 22 33 min z 2020400 4035 s.t. 5045 ,0;,0,(1,2,3) AB A B ABii PdP dPd xxdd xdd xdd xxddi 解解 設(shè)設(shè) 為分配給為分配給A A縣的救護車數(shù)量，縣的救護車數(shù)量， 其目標規(guī)劃模型其目標規(guī)劃模型為：為： B x 為分配給為分配給B

3、 B縣的救護車數(shù)量?？h的救護車數(shù)量。 目標規(guī)劃 某工廠計劃生產(chǎn)某工廠計劃生產(chǎn)A A、B B兩種產(chǎn)品，每噸產(chǎn)品的耗電量指兩種產(chǎn)品，每噸產(chǎn)品的耗電量指 標、原材料消耗、單位產(chǎn)品利潤及資源限量如表所示。標、原材料消耗、單位產(chǎn)品利潤及資源限量如表所示。 廠長首先考慮要充分利用供電部門分配的電量限額廠長首先考慮要充分利用供電部門分配的電量限額6666， 然后考慮利潤不低于然后考慮利潤不低于100100元；元； 據(jù)市場調(diào)查結(jié)果，希望據(jù)市場調(diào)查結(jié)果，希望B產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量不低于A產(chǎn)品的產(chǎn)量，產(chǎn)品的產(chǎn)量， 問應(yīng)如何制定產(chǎn)品問應(yīng)如何制定產(chǎn)品A A、B B的產(chǎn)量。建立該目標規(guī)劃的數(shù)學(xué)模型。的產(chǎn)量。建立該

4、目標規(guī)劃的數(shù)學(xué)模型。 產(chǎn)品產(chǎn)品 資源資源 AB資源限量資源限量 電力電力101266 原材料原材料218 單位產(chǎn)品利潤單位產(chǎn)品利潤 1020 目標規(guī)劃 解：解：設(shè)設(shè)x1、x2分別分別表示表示A A、B B兩種產(chǎn)品的產(chǎn)量，則目兩種產(chǎn)品的產(chǎn)量，則目 標規(guī)劃模型如下：標規(guī)劃模型如下： minZ=P1 (d1- + d1+ ) + P2d2- + P3d3- 2x1+x2 8 10 x1+12x2 +d1- - d1+ =66 10 x1+20 x2 +d2- - d2+ =100 -x1+x2 +d3- - d3+ =0 x1,x2 ,d1- ,d1+ ,d2- , d2+ ,d3- , d3+ 0

5、 第 5 章 指派問題 6個人完成個人完成4項工作，由于個人和技術(shù)專長不同，他們項工作，由于個人和技術(shù)專長不同，他們 完成完成4項工作任務(wù)所獲得收益如下表：項工作任務(wù)所獲得收益如下表： 13545 26768 38988 41010911 512111012 613121113 且規(guī)定每人只能做一項工作，一項工作任務(wù)只需一人操且規(guī)定每人只能做一項工作，一項工作任務(wù)只需一人操 作，試求使作，試求使 總收益最大的分派方案?？偸找孀畲蟮姆峙煞桨?。 解解 此問題是一個非標準的指派問題，虛設(shè)兩項任務(wù)此問題是一個非標準的指派問題，虛設(shè)兩項任務(wù)， 并設(shè)任務(wù)的收益為并設(shè)任務(wù)的收益為0， 化為標準的指派問題?；?/p>

6、為標準的指派問題。 標準的指派問題的收益矩陣為：標準的指派問題的收益矩陣為： 354500 676800 8981000 101091100 1211101200 1312111300 ij c 66 11 max 目標函數(shù)： ijij ij zc x 將其化為極小值問題。將其化為極小值問題。 108981313 76751313 54531313 33421313 12311313 01201313 ij c 最優(yōu)解矩陣為：最優(yōu)解矩陣為： 000001 000010 000100 001000 010000 100000 ij c 最優(yōu)分派方案為：第最優(yōu)分派方案為：第3個人做第個人做第項工作

7、，項工作，第第4個人個人 做第做第項工作，第項工作，第5個人做第個人做第項工作，第項工作，第6個人做第個人做第項工作，項工作， 所得最大總收益為：所得最大總收益為： max613(1313342)43 z 第 10 章 圖與網(wǎng)絡(luò)規(guī)劃 用用Ford-Fulkerson標號法求下圖中從標號法求下圖中從s到到t的最大流及其流量，的最大流及其流量， 并求網(wǎng)絡(luò)的最小割。弧旁數(shù)字為（并求網(wǎng)絡(luò)的最小割?；∨詳?shù)字為（cij，fij）。）。 解用解用Ford-Fulkerson標號法求出網(wǎng)絡(luò)的增廣鏈，如下圖中虛線所示。（標號法求出網(wǎng)絡(luò)的增廣鏈，如下圖中虛線所示。（5分）分） 因此，網(wǎng)絡(luò)中的可行流不是最大流，將其

8、調(diào)整后得一新的可行流，如下圖所因此，網(wǎng)絡(luò)中的可行流不是最大流，將其調(diào)整后得一新的可行流，如下圖所 示（示（2分）分） 再用標號法在上圖中找增廣鏈，標號法中斷，表明已找不出增廣鏈，故上圖再用標號法在上圖中找增廣鏈，標號法中斷，表明已找不出增廣鏈，故上圖 中的可行流即為最大流，其流量為中的可行流即為最大流，其流量為5+3+5=13。最小割為：。最小割為： (,)=( ,),( ,),(A,B)V Vs Ds C 3分分 第第11章章 網(wǎng)絡(luò)計劃網(wǎng)絡(luò)計劃 例例(7.1b)(7.1b)：根據(jù)下表給定的條件，繪制：根據(jù)下表給定的條件，繪制PERTPERT網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖。 A B C D E F G H I

9、 J KLM 1 3987 6 5 4 2 10 第 1、2 章 線性規(guī)劃及對偶問題 1 1 (10(10分分) ) 、寫出如下線性規(guī)劃問題的對偶問題，并利、寫出如下線性規(guī)劃問題的對偶問題，并利 用弱對偶性說明用弱對偶性說明z z的最大值不大于的最大值不大于1 1。 123 123 123 123 123 2 2 1 s.t. 22 00 max , zxxx xxx xxx xxx xxx 無限制 解解 原問題的對偶問題為：原問題的對偶問題為： 123 123 123 123 132 22 21 2 s.t. 1 00 m in , wyyy yyy yyy yyy yyy 無 約 束 由于

10、（由于（0，1，0）是上述對偶問題的可行解，對原問題的任一可行解）是上述對偶問題的可行解，對原問題的任一可行解 CXYbX都有。 2 0 1 011 2 , ,Y b 而 所以所以z的最大值不大于的最大值不大于1。 (10(10分分) )設(shè)有某個求極大值線性規(guī)劃問題，它的某一次迭代結(jié)果如下表，試再設(shè)有某個求極大值線性規(guī)劃問題，它的某一次迭代結(jié)果如下表，試再 進行一次迭代，判斷迭代進行一次迭代，判斷迭代的結(jié)果是否已求得最優(yōu)解，寫出解的全部內(nèi)容。的結(jié)果是否已求得最優(yōu)解，寫出解的全部內(nèi)容。 Cj 2 5 0 0 0 基基 b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 6 6 1

11、 0 3 0 1 0 1 0 0 0 1/2 -1 0 0 1 Cj- Z 2 0 0 -5/2 0 解：解：再進行一次迭代結(jié)果如下：再進行一次迭代結(jié)果如下： Cj 25000 基基bx1x2x3x4x5 0 5 0 x3 x2 x5 4 6 6 1 0 3 0 1 0 1 0 0 0 1/2 -1 0 0 1 Cj- Zj200-5/20 0 5 2 x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 -3 1/3 1/2 -1/3 -1/3 0 1/3 Cj- Zj000-11/6-2/3 2 6 2 0 0 T X 最 優(yōu) 解， 2(102(10分分) )、對于線性規(guī)劃問題：、

12、對于線性規(guī)劃問題： 123 13 123 123 123 647 32 324 s.t. 225 0 min , fxxx xx xxx xxx x xx （1）寫出此問題的對偶問題；）寫出此問題的對偶問題； （2）求出此問題和它的對偶問題的最優(yōu)解）求出此問題和它的對偶問題的最優(yōu)解 和最優(yōu)值。和最優(yōu)值。 (1)(1)對偶問題為：對偶問題為： 123 123 23 123 123 245 36 (1) 224 (2) s.t. 327 (3) 0 max , zyyy yyy yy yyy yyy (2)(2)引入松弛變量引入松弛變量y y4 4,y,y5 5,y,y6 6, ,將對偶問題規(guī)范化

13、為：將對偶問題規(guī)范化為： 123 1234 235 1236 456 245 36 22 4 s.t. 32 7 016 max , (,) i zyyy yyyy yyy yyyy yiyyy 為基變量 用單純形表迭代求最優(yōu)解為：用單純形表迭代求最優(yōu)解為： 最優(yōu)解最優(yōu)解Y Y* *=(1,0,2,7,0,0)=(1,0,2,7,0,0)T T，z z* * = max z=12 = max z=12。 13 13 123 1 2 3 23 3 1020 32 225 (1)160 11 32 6 2252 3 11 2 012 63 , , T yy xx xxx x x x xx x Xz

14、 又為，取不等號，即。 ，。 （12分）給出下列分）給出下列線性規(guī)劃的最優(yōu)單純形表，其中線性規(guī)劃的最優(yōu)單純形表，其中s s1 1、s s2 2 分別為第分別為第1 1、第、第2 2約束方程中的松弛變量。約束方程中的松弛變量。 123 123 123 3 max6212 4324 s.t. 26330 , zxxx xxx xxx x xx 12 0 c cj j6 2 12 0 0 6 2 12 0 0 c cB B 基 基 bx x1 1 x x2 2 x x3 3 s s1 1 s s2 2 12 x12 x3 3 8 8 4/3 1/3 1 1/3 0 4/3 1/3 1 1/3 0 0

15、 s 0 s2 2 6 6 -2 5 0 -1 1 -2 5 0 -1 1 c cj j-z-zj j-10 -2 0 -4 0 -10 -2 0 -4 0 (1)求出最優(yōu)基不變的求出最優(yōu)基不變的b2的變化范圍；的變化范圍； (2)求出最優(yōu)解不變的求出最優(yōu)解不變的c3的變化范圍。的變化范圍。 解解 （1）設(shè)）設(shè) b2 b2+ b2，則最終表中的，則最終表中的b變?yōu)椋鹤優(yōu)椋?1 2 8 = 6 bBb b 其中，其中，8 80，要使原最優(yōu)基不變，還應(yīng)滿足：，要使原最優(yōu)基不變，還應(yīng)滿足： 6+ b20，即得到，即得到 b2-6， b b2 224。 （2）設(shè)）設(shè)c3 c c3 3+ + c c3

16、3, ,則最終表中則最終表中x3的檢驗數(shù)變?yōu)椋旱臋z驗數(shù)變?yōu)椋?3333 3 (12)( 4,0)=12 ( 12) 3 cccc 于是原最終表變?yōu)橄卤恚河谑窃罱K表變?yōu)橄卤恚?c cj j6 2 12 0 0 6 2 12 0 0 c cB B 基 基 bx x1 1 x x2 2 x x3 3 s s1 1 s s2 2 12 x12 x3 3 8 84/3 1/3 1 1/3 0 4/3 1/3 1 1/3 0 0 s 0 s2 2 6 6-2 5 0 -1 1 -2 5 0 -1 1 c cj j-z-zj j-10-4-10-4c c3 3/3 -2-/3 -2-c c3 3/3 0

17、-4-/3 0 -4-c c3 3/3 0 /3 0 要使原最優(yōu)解不變，應(yīng)滿足：要使原最優(yōu)解不變，應(yīng)滿足： 3 3 3 4 100 3 20 3 40 3 c c c 解得解得c c3 3-6，故，故 c36。 習(xí)題習(xí)題2.6 2.6 用對偶單純形法求解下述線性規(guī)劃問題：用對偶單純形法求解下述線性規(guī)劃問題： 0 x,x,x 5x2x2 3x3x . t . s x18x12x4zmin 321 32 31 321 123 134 235 12345 max41218 33 s.t.225 ,0 zxxx xxx xxx x x x x x 解解 先將問題改寫為先將問題改寫為 列出單純形表，并用

18、對偶單純形法求解，計算步驟見表列出單純形表，并用對偶單純形法求解，計算步驟見表2-82-8 最優(yōu)解最優(yōu)解X=(0X=(0，3/23/2，1)1)T T，min z=36min z=36 下述線性規(guī)劃問題下述線性規(guī)劃問題習(xí)題習(xí)題 9 . 2 0 x,x 2x 1xx 8xx2 6x2x . t . s x2x3zmax 21 2 21 21 21 21 已知用單純形法求得最優(yōu)解的單純形表如表已知用單純形法求得最優(yōu)解的單純形表如表2-242-24所示。試分所示。試分 析在下列各種條件單獨變化的情況下進行分析。析在下列各種條件單獨變化的情況下進行分析。 (c) (c) 增加一個變量增加一個變量x x

19、7 7, ,其在目標函數(shù)中系數(shù)其在目標函數(shù)中系數(shù)c c7 7=4,P=4,P7 7=(1,2,3,2)=(1,2,3,2)T T (d)(d)增加一個新的約束增加一個新的約束x x1 1 4 4，重新確定最優(yōu)解。，重新確定最優(yōu)解。 解解: : (c c) x7 在最終表中的檢驗數(shù)為在最終表中的檢驗數(shù)為 2 4 1 0 2 3 2 1 103/13/2 0111 003/23/1 003/13/2 PB 1 2 3 2 1 )0 , 0 , 3 4 , 3 1 (4PBC4xc 7 1 7 1 B777 而而 故最終表應(yīng)變?yōu)楣首罱K表應(yīng)變?yōu)?此時題目有無窮多最優(yōu)解，其中之一為此時題目有無窮多最優(yōu)解

20、，其中之一為 x x1 1 = 3, x = 3, x2 2 = 4/3, x = 4/3, x7 7 = 1/3. = 1/3. (d) 原問題的最優(yōu)解滿足新增加的約束條件原問題的最優(yōu)解滿足新增加的約束條件 x1 4, 故最優(yōu)解故最優(yōu)解 不變，仍為不變，仍為X=(10/3, 4/3)T. 習(xí)題習(xí)題2.11 2.11 已知線性規(guī)劃問題：已知線性規(guī)劃問題： )5 , 1j (0 x tbxxaxaxa t3bxxaxaxa . t . s x0 x0 xcxcx)tc (zmax j 225323222121 214313212111 543322111 當當 t t1 1 = t = t2 2

21、 =0 =0 時求解得最終單純形表見表時求解得最終單純形表見表 2-25.2-25. (a)(a)確定確定 a a11 11、 、a a12 12、 、a a13 13、 、a a21 21、 、a a22 22、 、a a23 23、 、 c c1 1、 c c2 2、 c c3 3和和 b b1 1、 b b2 2 的值。的值。 (b)(b)當當 t t2 2= 0 = 0 時，時， t t1 1 值在什么范圍內(nèi)變化，上述最優(yōu)解不變。值在什么范圍內(nèi)變化，上述最優(yōu)解不變。 (c)(c)當當 t t1 1= 0 = 0 時，時， t t2 2 值在什么范圍內(nèi)變化，上述最優(yōu)基不變。值在什么范圍內(nèi)

22、變化，上述最優(yōu)基不變。 02/112/5 12/102/5 3 a 6 a 3 a 6 a 3 a 6 a 3 b 6 b 2 a 2 a 2 a 2 b aaab aaab 3/16/1 02/1 3/16/102/112/5 02/112/102/5 10aaab 01aaab 23132212211121 1312111 2322212 1312111 2322212 1312111 b b1 1 = 5, a = 5, a11 11 = 0, a = 0, a12 12 = 1, = 1, a a13 13 = 2, = 2, b b2 2 = 10, a = 10, a21 21 =

23、 3, a = 3, a22 22 = 1, = 1, a a23 23 = 1. = 1. .10c , 2c , 6c 2)c 3 1 ( 4)c 6 1 c 2 1 ( 4)c 2 1 c 2 1 (c 321 1 13 132 解：解：(b)(b) 0t 3 1 2 0t 6 1 4 1 0t 2 1 4 1 1 1 1 故有故有 即即 6 6 t t1 1 8 8 時，時， 原最優(yōu)解不變。原最優(yōu)解不變。 解：解：(c)(c) 此此時時原原最最優(yōu)優(yōu)基基不不變變。得得 故故 ,15t 3 5 0t 6 1 2 5 0t 2 3 2 5 t 6 1 t 2 3 t t3 3 1 6 1 0

24、 2 1 bB 2 2 2 2 2 2 21 P46.1.6 (a)P46.1.6 (a)將下列線性規(guī)劃問題化為標準形式，并列出初始單純形表將下列線性規(guī)劃問題化為標準形式，并列出初始單純形表 123 123 123 123 123 32 23412 428 336 00無約束， min . . , zxxx xxx xxx s t xxx xxx 12345 1234 1235 123 12345 3200 23412 428 336 000 max . . ,無約束， zxxxxx xxxx xxxx s t xxx xxxxx 33 xx 0 x x 33 令令 ，則 則 令令 222 x

25、 xx 且且x x2 2 , , x x 2 2 0, 0, 問題化為標準形問題化為標準形 122345 12234 12235 1223 122345 3200 233412 428 336 0 m ax . . , , , , zxxxxxx xxxxx xxxxx s t xxxx xxxxxx 再引入人工變量，問題變?yōu)樵僖肴斯ぷ兞?，問題變?yōu)?12234567 12234 122356 12237 max3200 2334 12 42 8 s.t. 33 6 以上變 zxxxxxxMxMx xxxxx xxxxxx xxxxx 量均大于或等于零， 是充分大的正數(shù)M 122345 12234 12235 1223 122345 3200 233412 428 336 0 m ax . . , , , , zxxxxxx xxxxx xxxxx s t xxxx xxxxxx 12234567 12234 122356 12237 max3200 233412 428 . . 336 以上變量均大于或等于零， 是充分大的正數(shù) zxxxxxxMxMx xxxxx xxxxxx st xxxxx M P46.1.6 (b)P46.1.6 (b)將