運(yùn)籌學(xué)例題及答案

1、運(yùn)運(yùn) 籌 籌 帷 帷 幄 幄 之 之 中 中 決決 勝 勝 千 千 里 里 之 之 外 外 作業(yè)及答案作業(yè)及答案 1。用單純形法解。用單純形法解lp問題問題 0, 44 222 . 326max 321 31 321 321 xxx xx xxx ts xxxz 線性規(guī)劃線性規(guī)劃 cj6-2300 cbxbbx1x2x3x4x5 0 x422-1210 0 x5410401 cj - zj6-2300 6x111-1/211/20 0 x5301/23-1/21 cj - zj01-3-30 6x1410401 -2x26016-12 cj - zj00-9-2-2 cj6-2300 cbxb

2、bx1x2x3x4x5 達(dá)到最優(yōu)解，且最優(yōu)解唯一達(dá)到最優(yōu)解，且最優(yōu)解唯一 2。用大。用大m或兩階段法解或兩階段法解lp問題問題 0, 02 22 6 . 22max 321 32 31 321 321 xxx xx xx xxx ts xxxz cj2-12000-m-m-m cbxbbx1x2x3x4x5x6x7x8x9 -mx76111-100100 -mx82-2010-10010 -mx9002-100-1001 cj-zj 2-m3m-1m+2 -m-m-m000 -mx76103/2-101/210 -1/2 -mx82-2010-10010 -1x2001 -1/2 00 -1/

3、2 001/2 cj-zj 2-m05/2m +3/2 -m-m 1/2m- 1/2 00 - 3/2m +1/2 cj2-12000-m-m-m cbxbbx1x2x3x4x5x6x7x8x9 -mx73400-13/21/21 -3/2-1/2 2x32-201000010 -1x21-1100 -1/2-1/2 01/21 cj-zj 5+4m00 -m 3/2m +3/2 1/2m- 1/2 0 -5/2m- 3/2 - 3/2m+ 1/2 2x13/4100 -1/4 3/81/81/4 -3/8-1/8 2x37/2001 -1/2-1/4 1/41/21/4 -1/4 -1x27

4、/401 0 -1/4-1/8-3/8 1/81/83/8 cj-zj 000 5/4 - 無(wú)界解無(wú)界解 3，某廠在今后四個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資。已知各月份需某廠在今后四個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資。已知各月份需 租用倉(cāng)庫(kù)面積見表，倉(cāng)庫(kù)租借費(fèi)用隨合同期不同而不同，期租用倉(cāng)庫(kù)面積見表，倉(cāng)庫(kù)租借費(fèi)用隨合同期不同而不同，期 限越長(zhǎng)折扣越大，具體數(shù)字見表。租借合同每個(gè)月月初都可限越長(zhǎng)折扣越大，具體數(shù)字見表。租借合同每個(gè)月月初都可 辦理，合同規(guī)定具體的租借面積和月數(shù)，因此該廠可根據(jù)需辦理，合同規(guī)定具體的租借面積和月數(shù)，因此該廠可根據(jù)需 要，在任何一個(gè)月月初辦理合同，每次辦理可簽一份或多份，要，在任何一個(gè)月

5、月初辦理合同，每次辦理可簽一份或多份， 總目標(biāo)是總的租借費(fèi)用最低，請(qǐng)建立數(shù)學(xué)模型并用軟件給出總目標(biāo)是總的租借費(fèi)用最低，請(qǐng)建立數(shù)學(xué)模型并用軟件給出 結(jié)果。結(jié)果。 月份1234 所需倉(cāng)庫(kù)面 積（100m2） 15102012 合同租借 期限 1個(gè)月2個(gè)月3個(gè)月4個(gè)月 租借費(fèi)用 2800450060007300 解解:設(shè)一月初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè)設(shè)一月初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè) 月，四個(gè)月的倉(cāng)庫(kù)面積分別為月，四個(gè)月的倉(cāng)庫(kù)面積分別為 ， ， ， ，二月，二月 初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè)月的倉(cāng)庫(kù)初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè)月的倉(cāng)庫(kù) 面積分別為面積分別為 ，三月初

6、簽訂合同期限為一，三月初簽訂合同期限為一 個(gè)月，兩個(gè)月的倉(cāng)庫(kù)面積分別為個(gè)月，兩個(gè)月的倉(cāng)庫(kù)面積分別為 ，四月初簽，四月初簽 訂合同期限為一個(gè)月的倉(cāng)庫(kù)面積為訂合同期限為一個(gè)月的倉(cāng)庫(kù)面積為 。 則則 11 x 12 x 13 x 14 x 232221 ,xxx 3231, x x 41 x 142313 32221241312111 7300)(6000 )(4500)(2800min xxx xxxxxxxz 0 12 20 10 15 41322314 323123221413 232221141312 14131211 ij x xxxx xxxxxx xxxxxx xxxx 計(jì)算結(jié)果如下計(jì)

7、算結(jié)果如下 4，某廠生產(chǎn)，某廠生產(chǎn)i,ii,iii三種產(chǎn)品，都分別經(jīng)過三種產(chǎn)品，都分別經(jīng)過a,b兩道工兩道工 序加工。設(shè)序加工。設(shè)a工序可分別在設(shè)備工序可分別在設(shè)備a1或或a2上完成，有上完成，有 b1，b2，b3三種設(shè)備可用于完成三種設(shè)備可用于完成b工序。已知產(chǎn)品工序。已知產(chǎn)品 i可在可在a,b任何一種設(shè)備上加工；產(chǎn)品任何一種設(shè)備上加工；產(chǎn)品ii可在任何規(guī)可在任何規(guī) 格的格的a設(shè)備上加工，但完成設(shè)備上加工，但完成b工序時(shí)，只能在工序時(shí)，只能在b1設(shè)設(shè) 備上加工；產(chǎn)品備上加工；產(chǎn)品iii只能在只能在a2和和b2設(shè)備上加工。加設(shè)備上加工。加 工單位產(chǎn)品所需的工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見表，工單位產(chǎn)品

8、所需的工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見表， 試安排最優(yōu)生成計(jì)劃，使該廠獲利最大。試安排最優(yōu)生成計(jì)劃，使該廠獲利最大。 設(shè)備 產(chǎn)品 i ii iii 設(shè)備有效設(shè)備有效 臺(tái)時(shí)臺(tái)時(shí) 設(shè)備加工費(fèi)設(shè)備加工費(fèi) （元（元/h） a15 10 60000.05 a27 9 12100000.03 b16 840000.06 b24 1170000.11 b3740000.05 原料費(fèi)（元原料費(fèi)（元/ 件）件） 售價(jià)（元售價(jià)（元/件）件） 0.25 0.35 0.50 1.25 2.00 2.80 解：設(shè)第解：設(shè)第種產(chǎn)品中，分別在種產(chǎn)品中，分別在 上加工的數(shù)量依次為上加工的數(shù)量依次為 ，第，第種種 產(chǎn)品中分別在產(chǎn)品中分

9、別在a1,b1和和a2,b1 上加工的數(shù)量為上加工的數(shù)量為 生產(chǎn)生產(chǎn)種產(chǎn)品數(shù)量為種產(chǎn)品數(shù)量為 。 3 , 2 , 1),(),( 21 jbaba jj 654321 ,;,xxxxxx 87,x x 9 x 0 4000)(7 700011)(4 4000)(8)(6 10000129)(7 600010)(5 )(705. 011)(411. 0)(8 )(606. 0129)(703. 010)(505. 0 )5 . 08 . 2()(35. 02()(25. 025. 1(max 63 952 8741 98654 7321 6395287 41986547321 987654321

10、 j x xx xxx xxxx xxxxx xxxx xxxxxxx xxxxxxxxxxx xxxxxxxxxz 對(duì)偶理論對(duì)偶理論 1. 已知線性規(guī)劃問題：已知線性規(guī)劃問題： 0, 9 6 6 2 83 . 42max 4321 321 432 21 421 4321 xxxx xxx xxx xx xxx ts xxxxz 要求要求：a)寫出對(duì)偶問題，寫出對(duì)偶問題，b)已知原問題最有解已知原問題最有解 x*=(2,2,4,0),用互補(bǔ)松弛性求出對(duì)偶問題的用互補(bǔ)松弛性求出對(duì)偶問題的 最優(yōu)解。最優(yōu)解。 解：對(duì)偶問題：解：對(duì)偶問題： 0, 1 1 4 3 22 . 9668min 4321 3

11、1 43 4321 421 4321 yyyy yy yy yyyy yyy ts yyyyw 將原問題的最優(yōu)解帶入約束，發(fā)現(xiàn)第將原問題的最優(yōu)解帶入約束，發(fā)現(xiàn)第4個(gè)約束為嚴(yán)格個(gè)約束為嚴(yán)格 不等式，所以，得不等式，所以，得y4*=0 又因?yàn)?，原問題最優(yōu)解的前三個(gè)分量都大于又因?yàn)椋瓎栴}最優(yōu)解的前三個(gè)分量都大于0，所以，所以， 有如下三個(gè)等式成立。有如下三個(gè)等式成立。 1 4 3 22 3 321 21 y yyy yy 解方程組得對(duì)偶問題的最優(yōu)解為解方程組得對(duì)偶問題的最優(yōu)解為y*=(4/5,3/5,1,0) 2。已知線性規(guī)劃問題。已知線性規(guī)劃問題 0, 2 1 8 2 62 . 23max 21

12、 2 21 21 21 21 xx x xx xx xx ts xxz 及最終單純形表及最終單純形表 cj320000 cbxbbx1x2x3x4x5x6 2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 表表1 分析下列各種條件單獨(dú)變化時(shí)，最優(yōu)解將如何變化。分析下列各種條件單獨(dú)變化時(shí)，最優(yōu)解將如何變化。 （a）第）第1，2個(gè)約束條件的后端項(xiàng)分別由個(gè)約束條件的后端項(xiàng)分別由6變變7，8變變4； （b）目標(biāo)函數(shù)變?yōu)椋┠繕?biāo)函數(shù)變?yōu)?; （c） 增加一個(gè)變量增加一個(gè)變

13、量 ，系數(shù)為，系數(shù)為 （d）問題中變量）問題中變量 的系數(shù)變?yōu)榈南禂?shù)變?yōu)?（e）增加一個(gè)新的約束）增加一個(gè)新的約束 21 52maxxxz 3 x t pc)2 , 3 , 2 , 1(, 4 33 2 x t )2 , 1 , 2 , 3 , 4( 4 1 x 解：解：a） 0 0 4 1 b 2 5 3 2 0 0 4 1 103/13/2 0111 003/23/1 003/13/2 b 將其加到表（將其加到表（1）的最終單純形表的基變量）的最終單純形表的基變量b這一列數(shù)這一列數(shù) 字上得表（字上得表（2） （表（表2） 表（表（2）中原問題為非可行解，故用對(duì)偶單純形法繼續(xù)）中原問題為非可

14、行解，故用對(duì)偶單純形法繼續(xù) 計(jì)算得表（計(jì)算得表（3） cj320000 cbxbbx1x2x3x4x5x6 2x210/3 012/3-1/3 00 3x11/310-1/3 2/300 0 x5-200-1110 0 x6-4/3 00-2/3 1/301 cjzj 00-1/3 -4/3 00 （表（表3） cj320000 cbxbbx1x2x3x4x5x6 2x220101/32/30 3x111001/3-1/3 0 0 x32001-1-10 0 x60000-1/3 -2/3 1 cjzj 000-5/3 -1/3 0 即新解為即新解為 t x)0 , 0 , 0 , 2 , 2

15、 , 1( 第第25頁(yè)頁(yè) b) 將將cj的改變反應(yīng)到最終單純形表上的改變反應(yīng)到最終單純形表上,得表（得表（4） cj250000 cbxbbx1x2x3x4x5x6 5x24/3012/3-1/3 00 2x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-8/3 1/300 繼續(xù)迭代繼續(xù)迭代,得表（得表（5） cj250000 cbxbbx1x2x3x4x5x6 5x22010001 2x1210100-2 0 x5100101-3 0 x4200-2103 cjzj 00-200-1 表表5 即新解為即新解為 t x)2

16、 , 2( c） 將其加到最終單純形表上得表（將其加到最終單純形表上得表（6） 01 2 3 2 1 003/43/14 7 2 4 1 0 2 3 2 1 103/13/2 0111 003/23/1 003/13/2 7 1 / 7 pbp cj320000 cbxbbx1x2x3x4x5x6 2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 4 x7 0 1 4 2 1 繼續(xù)迭代繼續(xù)迭代,得表（得表（7） 表表6 cj320000 cbxbbx1x2x3

17、x4x5x6 2x24/3012/3-1/3 00 3x131001/20-1/2 0 x55/3001/31/21-2 4x71/300-1/3 1/601/2 cjzj 000-3/2 0-1/2 4 x7 0 0 0 1 0 即新解為即新解為 t x)3/1 , 3/4 , 3( 表表7 d） 將其加到最終單純形表上得表（將其加到最終單純形表上得表（8） 03/1 2 1 2 3 003/43/14 2 3/2 0 3/1 3/4 2 1 2 3 103/13/2 0111 003/23/1 003/13/2 2 1 / 2 pbp cj320000 cbxbbx1x2x3x4x5x6

18、2x24/3012/3-1/3 00 3x110/3 10-1/3 2/300 0 x5300-1110 0 x62/300-2/3 1/301 cjzj 00-1/3 -4/3 00 4 x2 4/3 1/3 0 2/3 1/3 表表8 因因x2已變化為已變化為x/2，故用單純形法算法將，故用單純形法算法將x/2替換出基變替換出基變 量中的量中的x2，并在下一個(gè)表中不再保留，并在下一個(gè)表中不再保留x2，得表（，得表（9） cj320000 cbxbbx1x2x3x4x5x6 4x21011/2-1/4 00 3x1310-1/2 3/400 0 x5300-1110 0 x6000-11/2

19、01 cjzj 00-1/2 -5/4 00 表表9 此時(shí)已經(jīng)達(dá)到最優(yōu)，新解為此時(shí)已經(jīng)達(dá)到最優(yōu)，新解為 t x)1 , 3( e) 此時(shí)將原來(lái)的最優(yōu)解帶入約束，發(fā)現(xiàn)滿足，所以此時(shí)將原來(lái)的最優(yōu)解帶入約束，發(fā)現(xiàn)滿足，所以 最優(yōu)解不變。最優(yōu)解不變。 運(yùn)輸問題運(yùn)輸問題 1，試求下表給出的產(chǎn)銷不平衡問題的最優(yōu)解。，試求下表給出的產(chǎn)銷不平衡問題的最優(yōu)解。 b1b2b3b4產(chǎn)量 a137645 a224322 a343856 銷量3322 產(chǎn)地 銷地 解：用最小元素法求得初始方案如下解：用最小元素法求得初始方案如下 b1b2b3b4b5 a123 a220 a3132 產(chǎn)地 銷地 用位勢(shì)法求檢驗(yàn)數(shù)知用位勢(shì)法

20、求檢驗(yàn)數(shù)知 01 35 找到閉回路，調(diào)整得找到閉回路，調(diào)整得 b1b2b3b4b5 a132 a220 a3321 又用位勢(shì)法求檢驗(yàn)數(shù)知又用位勢(shì)法求檢驗(yàn)數(shù)知01 14 找到閉回路，調(diào)整得找到閉回路，調(diào)整得 b1b2b3b4b5 a1320 a220 a333 又用位勢(shì)法求檢驗(yàn)數(shù)知所有的檢驗(yàn)數(shù)都非負(fù)，達(dá)又用位勢(shì)法求檢驗(yàn)數(shù)知所有的檢驗(yàn)數(shù)都非負(fù)，達(dá) 到最優(yōu)到最優(yōu)z=32。 2，某市有三個(gè)面粉廠，他們供給三個(gè)面食加工廠所，某市有三個(gè)面粉廠，他們供給三個(gè)面食加工廠所 需的面粉。各面粉廠的產(chǎn)量、面食加工廠加工面粉需的面粉。各面粉廠的產(chǎn)量、面食加工廠加工面粉 的能力、各面食加工廠和各面粉廠之間的單位運(yùn)價(jià)的能

21、力、各面食加工廠和各面粉廠之間的單位運(yùn)價(jià) 見下表。假定在第見下表。假定在第1，2，3面食加工廠制作單位面粉面食加工廠制作單位面粉 食品的利潤(rùn)分別為食品的利潤(rùn)分別為12元，元，16元，元，11元，試確定使總元，試確定使總 效益最大的面粉分配計(jì)劃（假定面粉廠和面食加工效益最大的面粉分配計(jì)劃（假定面粉廠和面食加工 廠都屬于同一個(gè)主管單位）廠都屬于同一個(gè)主管單位） 123 面粉廠產(chǎn)量 a310220 c411830 b811420 食品廠需要量 152520 食品廠食品廠 面粉廠面粉廠 解：解：從題意很容易知道，總效益最大實(shí)際上是食品利潤(rùn)減去單從題意很容易知道，總效益最大實(shí)際上是食品利潤(rùn)減去單 位運(yùn)價(jià)

22、之后再求的總效益。再因?yàn)槊娣鄣目偖a(chǎn)量為位運(yùn)價(jià)之后再求的總效益。再因?yàn)槊娣鄣目偖a(chǎn)量為70，比食，比食 品廠的總需求量品廠的總需求量60多了多了10個(gè)單位，可以認(rèn)為，多的個(gè)單位，可以認(rèn)為，多的10個(gè)單位個(gè)單位 最后還是會(huì)分配給最后還是會(huì)分配給13個(gè)食品廠，所以就需要增加一個(gè)虛擬個(gè)食品廠，所以就需要增加一個(gè)虛擬 的食品廠的食品廠4。 設(shè)設(shè)xij第第i個(gè)面粉廠運(yùn)到第個(gè)面粉廠運(yùn)到第j個(gè)食品廠的運(yùn)量，個(gè)食品廠的運(yùn)量，i=1,2,3;j=1,2,3,4 得下表：得下表： 1234 面粉廠產(chǎn)量 a969920 c853830 b457720 食品廠需要量 15252010 為使用求解運(yùn)輸問題的表上作業(yè)法，用上

23、表中的最大為使用求解運(yùn)輸問題的表上作業(yè)法，用上表中的最大 數(shù)減去其他各數(shù)，得下表數(shù)減去其他各數(shù)，得下表 1234 面粉廠產(chǎn)量 a030020 c146130 b542220 食品廠需要量 15252010 使用表上作業(yè)法，得最優(yōu)解使用表上作業(yè)法，得最優(yōu)解. 整數(shù)規(guī)劃整數(shù)規(guī)劃 1，分配甲、乙、丙、丁四個(gè)人完成，分配甲、乙、丙、丁四個(gè)人完成abcde五項(xiàng)五項(xiàng) 任務(wù)，每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示：任務(wù)，每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示： abcde 甲2529314237 乙乙3938262 033 丙丙3427284 032 丁丁2442362345 由于任務(wù)多于人數(shù)，故考慮由于任務(wù)多于人數(shù)，

24、故考慮： （a）任務(wù)）任務(wù)e必須完成，其他各項(xiàng)可任意選必須完成，其他各項(xiàng)可任意選3項(xiàng)完成；項(xiàng)完成； （b）其中有一人完成）其中有一人完成2項(xiàng)，其他每人完成一項(xiàng)。項(xiàng)，其他每人完成一項(xiàng)。 分別確定最優(yōu)方案，使完成任務(wù)總時(shí)間最少分別確定最優(yōu)方案，使完成任務(wù)總時(shí)間最少 解解（a）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng)）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng) 的效率如下的效率如下 m0000 4523364224 3240282734 3320263839 3742312925 m0000 22013191 513107 13061819 1217640 m0000 16013191 013107 7061

25、819 717640 m1000 15012180 014107 6051718 718640 m5004 1508100 0191013 2011318 318200 z=105 解解（b）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng)）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng) 的效率如下的效率如下 3220262724 4523364224 3240282734 3320263839 3742312925 70574 17012191 013007 8051819 717540 60463 16011180 014007 7041718 718540 20023 1207140 0180011 3001

26、318 318100 最優(yōu)方案：甲最優(yōu)方案：甲b，乙，乙c， d，丙，丙e，丁，丁a， z=131 2，用割平面法求解，用割平面法求解 取整, 0, 2054 62 max 21 21 21 21 xx xx xx xxz cj1100 cbxbbx1x2x3x4 1x15/3105/6-1/3 1x28/301-2/31/3 cj - zj00-1/6-1/6 單純形迭代得最終單純形表單純形迭代得最終單純形表 寫出第一行的約束寫出第一行的約束 3 2 1 3 1 6 5 431 xxx 將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和 3 2 1) 3 2 1

27、( 6 5 431 xxx 分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊 4341 3 2 6 5 3 2 1xxxx 由于左邊為整數(shù)，所以右邊也為整數(shù)，所以由于左邊為整數(shù)，所以右邊也為整數(shù)，所以 0, 0 43 xx所以所以由于由于 加入松弛變量加入松弛變量 放入單純形表放入單純形表 3 2 3 2 6 5 3 2 43 xx 0 3 2 6 5 3 2 43 xx 0 3 2 6 5 3 2 543 xxx cj1100 cbxbbx1x2x3x4 1x15/3105/6-1/6 1x28/301-2/31/3 0 x5-2/300-5/61/6 cj - zj00-1/6

28、-1/60 0 x5 0 0 1 對(duì)偶單純形法繼續(xù)迭代，得對(duì)偶單純形法繼續(xù)迭代，得 cj1100 cbxbbx1x2x3x4 1x111000 1x216/50101/5 0 x34/5001-1/5 cj - zj000-1/5-1/5 0 x5 1 -4/5 -6/5 寫出第二行的約束寫出第二行的約束 5 1 3 5 4 5 1 542 xxx 將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和 分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊 5 1 3) 5 1 1( 5 1 542 xxx 5452 5 1 5 1 5 1 3xxxx 由于左

29、邊為整數(shù)，所以右邊也為整數(shù)，所以由于左邊為整數(shù)，所以右邊也為整數(shù)，所以 0, 0 54 xx所以所以由于由于 加入松弛變量加入松弛變量 放入單純形表放入單純形表 5 1 5 1 5 1 5 1 54 xx 0 5 1 5 1 5 1 54 xx 0 5 1 5 1 5 1 654 xxx cj1100 cbxbbx1x2x3x4 1x111000 1x216/50101/5 0 x34/5001-1/5 cj - zj000-1/5-1/50 0 x5 1 -4/5 -6/5 0 x6 0 0 0 0 x6-1/5000-1/5-1/51 cj1100 cbxbbx1x2x3x4 1x1110

30、00 1x230100 0 x310010 cj - zj00000-1 0 x5 1 -1 -1 0 x6 0 1 -1 0 x4100011-5 達(dá)到最優(yōu)，達(dá)到最優(yōu)， t x)3 , 1( 還可以得到另一個(gè)最優(yōu)解：。還可以得到另一個(gè)最優(yōu)解：。 t x)4 , 0( 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 1，已知目標(biāo)規(guī)劃問題，已知目標(biāo)規(guī)劃問題 0, 2 42 92 62 )35(min 21 442 3321 21 21 443321 22 11 121 ii ddxx ddx ddxx ddxx ddxx dpddpdpdpz 用圖解法求解最優(yōu)解。用圖解法求解最優(yōu)解。 62 21 xx 92 21 xx 42

31、 21 xx 2 2 x 最優(yōu)解最優(yōu)解 2，某工廠生產(chǎn)，某工廠生產(chǎn)a,s兩種型號(hào)的微型計(jì)算機(jī)，他們兩種型號(hào)的微型計(jì)算機(jī)，他們 都需要經(jīng)過兩道工序，每臺(tái)計(jì)算機(jī)所需的加工都需要經(jīng)過兩道工序，每臺(tái)計(jì)算機(jī)所需的加工 時(shí)間、銷售利潤(rùn)及該廠每周最大的加工能力如時(shí)間、銷售利潤(rùn)及該廠每周最大的加工能力如 下表：下表： as周最大加 工能力 工序1（h/臺(tái)） 46150h 工序2（h/臺(tái)） 3275h 利潤(rùn)（元/臺(tái)） 300450 工廠經(jīng)營(yíng)目標(biāo)的各優(yōu)先級(jí)如下：工廠經(jīng)營(yíng)目標(biāo)的各優(yōu)先級(jí)如下： p1：每周總利潤(rùn)不低于：每周總利潤(rùn)不低于10000元；元； p2：合同要求：合同要求a型機(jī)每周至少生產(chǎn)型機(jī)每周至少生產(chǎn)10臺(tái)

32、，臺(tái)，s型機(jī)至型機(jī)至 少少15臺(tái)；臺(tái)； p3：工序：工序1每周生成時(shí)間最好恰為每周生成時(shí)間最好恰為150h,工序工序2生成生成 時(shí)間可適當(dāng)超過其能力；時(shí)間可適當(dāng)超過其能力； 試寫出目標(biāo)規(guī)劃的模型。試寫出目標(biāo)規(guī)劃的模型。 0, 7566 15064 15 10 10000450300 )()(min 21 5521 4421 2 1 21 5443321 33 22 11 21 ii ddxx ddxx ddxx ddx ddx ddxx dddpddpdpz 解：設(shè)生產(chǎn)解：設(shè)生產(chǎn)a，s機(jī)器分別為機(jī)器分別為x1,x2臺(tái)，則有臺(tái)，則有 3，查找參考書，參閱較復(fù)雜問題的模型，查找參考書，參閱較復(fù)雜問

33、題的模型 圖論圖論 1，用避圈法或破圈法求下圖的最小樹，用避圈法或破圈法求下圖的最小樹 1 v 2 v 5 v 7 v 8 v 6 v 3 v 4 v 9 v 6 4 5 5 4 4 7 7 6 2 9 3 813 1 v 2 v 5 v 7 v 8 v 6 v 3 v 4 v 9 v 6 4 5 5 4 4 7 7 6 2 9 3 813 或選取或選取 去掉去掉),( 51 vv ),( 71 vv 解答：解答： 2，下圖中，下圖中 是倉(cāng)庫(kù)，是倉(cāng)庫(kù)， 是商店，求一條是商店，求一條 到到 的最短路的最短路 0 v 1 v 3 v 5 v 7 v 8 v 6 v 9 v 4 v 2 v 2 2

34、2 11 11 11 7 7 4 4 43 3 36 6 6 5 5 9 9 0 v 9 v 0 v 9 v 0 v 1 v 3 v 5 v 7 v 8 v 6 v 9 v 4 v 2 v 2 2 2 11 11 11 7 7 4 4 43 3 36 6 6 5 5 9 9 )0( )2( )4( )7( )11( )11( )13( )13( )16()19( 最優(yōu)方案可以有幾種：最優(yōu)方案可以有幾種： 9210 , 1vvvv 94210 , 2vvvvv 9230 , 3vvvv 94230 , 4vvvvv 9430 , 5vvvv 9870 , 6vvvv 3，用標(biāo)號(hào)算法求下圖的最大流

35、，用標(biāo)號(hào)算法求下圖的最大流 s v 2 v 4 v 1 v 5 v t v 3 v )5(5 )3(3 )2(3 )4(6 )0(2 )4(5 )2(2 )4(4 )6(6 )6(8)3(3 )0(2 s v 2 v 4 v 1 v 5 v t v 3 v ) 5 ( 5 ) 3( 3 ) 2( 3 ) 4 ( 6 ) 0 ( 2 ) 4 ( 5 ) 2( 2 ) 4 ( 4 ) 6 ( 6 ) 6 ( 8) 3( 3 ) 0 ( 2 ),(, 1 ss vv )2 ,(, 2 2s vv )1 ,(, 3 23 vv )1 ,(, 4 34 vv )1 ,(, 5 41 vv )1 ,(,

36、6 15 vv )1 ,(, 7 5 vvt s v 2 v 4 v 1 v 5 v t v 3 v ) 5( 5 ) 3( 3 ) 2( 3 ) 4( 6 ) 0( 2 ) 4( 5 ) 2( 2 ) 4( 4 ) 6( 6 ) 6( 8) 3( 3 ) 0( 2 得增廣鏈如右圖中紅色部得增廣鏈如右圖中紅色部 分，調(diào)整后得新圖如下：分，調(diào)整后得新圖如下： s v 2 v 4 v 1 v 5 v t v 3 v ) 5( 5 )3( 3 )3( 3 ) 5( 6 )0( 2 )5( 5 ) 1 ( 2 )4( 4 )6( 6 )7( 8) 2( 3 )0( 2 再次標(biāo)號(hào)知：沒有增廣鏈存在，故達(dá)

37、到最大流。最再次標(biāo)號(hào)知：沒有增廣鏈存在，故達(dá)到最大流。最 大流量為大流量為13 4，求下圖中流值為，求下圖中流值為6的最小費(fèi)用流，其中弧旁邊的最小費(fèi)用流，其中弧旁邊 的數(shù)字為的數(shù)字為 , 表示容量，表示容量， 表示單位流表示單位流 量費(fèi)用。量費(fèi)用。 s vt v 2 v 1 v 3 v 4 v )2 , 3( )3 , 3( )1 , 3( )3 , 4( )1 , 4( )1 , 7( )5 , 6( )4 , 5( ),( ijij dcij c ij d s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3( )1( )1( )5( )4( 解：以解：以0作為初始流

38、量，得長(zhǎng)度網(wǎng)絡(luò)作為初始流量，得長(zhǎng)度網(wǎng)絡(luò) 最短路：最短路： ts vvvv 43 調(diào)整流量，得新的流量網(wǎng)絡(luò)調(diào)整流量，得新的流量網(wǎng)絡(luò) s vt v 2 v 1 v 3 v 4 v 0 3 3 0 3 0 0 0 對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò)對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò) s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3( )1( )1( )5( )4( )1( 最短路：最短路： ts vvvv 23 調(diào)整流量，得新的流量網(wǎng)絡(luò)調(diào)整流量，得新的流量網(wǎng)絡(luò) s vt v 2 v 1 v 3 v 4 v 0 3 3 0 4 1 0 1 對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò)對(duì)新的流量網(wǎng)絡(luò)，得到

39、長(zhǎng)度網(wǎng)絡(luò) s vt v 2 v 1 v 3 v 4 v )2( )3( )1( )3()1( )5( )4( )1( )4( )1( 最短路：最短路： ts vvvvvv 2341 調(diào)整流量，得新的流量網(wǎng)絡(luò)調(diào)整流量，得新的流量網(wǎng)絡(luò) s vt v 2 v 1 v 3 v 4 v 2 1 3 2 4 3 0 3 pert圖圖 與與 關(guān)鍵路線法關(guān)鍵路線法 1，下表給出一個(gè)汽車庫(kù)及引道的施工計(jì)劃：，下表給出一個(gè)汽車庫(kù)及引道的施工計(jì)劃： 作業(yè)編號(hào)作業(yè)內(nèi)容作業(yè)時(shí)間（天）緊前作業(yè) 1清理場(chǎng)地準(zhǔn)備施工10無(wú) 2備料8無(wú) 3車庫(kù)地面施工61，2 4墻及房頂 架預(yù)制162 5車庫(kù)混凝土地面保養(yǎng)243 6豎立墻架4

40、4，5 7豎立房頂 架46 8裝窗及邊墻106 9裝門46 10裝天花板127 11油漆168，9，10 12引道混凝土施工83 13引道混凝土保養(yǎng)2412 14清理場(chǎng)地交工驗(yàn)收411，13 請(qǐng)解答請(qǐng)解答（1）該工程從施工開始道工程結(jié)束的最）該工程從施工開始道工程結(jié)束的最 短周期；（短周期；（2）如果引道混凝土施工工期拖延）如果引道混凝土施工工期拖延 10天，對(duì)整個(gè)工程進(jìn)度有何影響？（天，對(duì)整個(gè)工程進(jìn)度有何影響？（3）若裝）若裝 天花板的施工時(shí)間從天花板的施工時(shí)間從12天縮短為天縮短為8天，對(duì)整個(gè)天，對(duì)整個(gè) 工程進(jìn)度有何影響？（工程進(jìn)度有何影響？（4）為保證工期不拖延，）為保證工期不拖延， 裝

41、門這項(xiàng)作業(yè)最晚應(yīng)從哪一天開工？（裝門這項(xiàng)作業(yè)最晚應(yīng)從哪一天開工？（5）如）如 果要求該工程必須在果要求該工程必須在75天內(nèi)完工，是否應(yīng)采取天內(nèi)完工，是否應(yīng)采取 措施，應(yīng)采取什么措施？措施，應(yīng)采取什么措施？ 0 40 10 0 4 10 24 0 0 4 16 24 1 2 3 4 5 87 10 11 9 4 6 44 a 16 0 6 168 4 1213 b 16 c e l i g fh j n m dk 8 24 12 0 0 10 0 2 8 44 44 48 60 24 7680 807660 52 50 56 48 44 40 16 44 10 解：作業(yè)編號(hào)分別對(duì)應(yīng)a,b,c,d

42、,e,f,g,h,i,j,k,l,m,n，pert 圖如下 第第80頁(yè)頁(yè) （1）該工程從施工開始道工程結(jié)束的最短周期為）該工程從施工開始道工程結(jié)束的最短周期為80天天 可計(jì)算出自由時(shí)差和總時(shí)差可計(jì)算出自由時(shí)差和總時(shí)差 若使用公式：若使用公式： ),(),(),(jitjitjir esls ),(),(),(min),(jitjitkjtjif eses k 0 40 10 0 4 10 24 0 0 4 16 24 1 2 3 4 5 87 10 11 9 4 6 44 a 16 0 6 168 4 1213 b 16 c e l i g fh j n m dk 8 24 12 0 0 10

43、 0 2 8 44 44 48 60 24 7680 807660 52 50 56 48 44 40 16 44 10 00 2 16 0 28 0 12 6 0 0 0 28 0 )0( )0( )0( )16( )0( )0( )0( )12( )0( )0( )6( )0( )28( )0( *表示總時(shí)差表示總時(shí)差(*) 表示自由時(shí)差表示自由時(shí)差 如此可找到關(guān)鍵路線：如此可找到關(guān)鍵路線：a-c-e-f-g-j-k-n （2）如果引道混凝土施工）如果引道混凝土施工(l)工期拖延工期拖延10天，由于此工序天，由于此工序 有總時(shí)差有總時(shí)差28，所以它的工期拖延，所以它的工期拖延10天，對(duì)整個(gè)

44、工程進(jìn)度天，對(duì)整個(gè)工程進(jìn)度 無(wú)影響。無(wú)影響。 （3）若裝天花板（）若裝天花板（j）的施工時(shí)間從）的施工時(shí)間從12天縮短為天縮短為8天，天， 觀察它的平行工序觀察它的平行工序h，i，發(fā)現(xiàn)關(guān)鍵路線不會(huì)改變，所，發(fā)現(xiàn)關(guān)鍵路線不會(huì)改變，所 以整個(gè)工程進(jìn)度也縮短以整個(gè)工程進(jìn)度也縮短4天。天。 （4）為保證工期不拖延，裝門（）為保證工期不拖延，裝門（i）這項(xiàng)作業(yè)最）這項(xiàng)作業(yè)最 晚應(yīng)從第晚應(yīng)從第56天開工天開工 （5）如果要求該工程必須在）如果要求該工程必須在75天內(nèi)完工，在合適的關(guān)天內(nèi)完工，在合適的關(guān) 鍵工序上壓縮鍵工序上壓縮5天工期。天工期。 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 1. 設(shè)有設(shè)有6萬(wàn)元資金用于四個(gè)工廠的擴(kuò)建

45、。已知每個(gè)工廠萬(wàn)元資金用于四個(gè)工廠的擴(kuò)建。已知每個(gè)工廠 的利潤(rùn)增長(zhǎng)額同投資數(shù)的大小有關(guān)，數(shù)據(jù)見表。如何的利潤(rùn)增長(zhǎng)額同投資數(shù)的大小有關(guān)，數(shù)據(jù)見表。如何 確定對(duì)四個(gè)工廠的投資數(shù)，使得總利潤(rùn)增長(zhǎng)額最大。確定對(duì)四個(gè)工廠的投資數(shù)，使得總利潤(rùn)增長(zhǎng)額最大。 0100200300400500600 10204260758590 20254557657073 30183961789095 40284765748085 利潤(rùn)增長(zhǎng)額利潤(rùn)增長(zhǎng)額 工廠工廠 投資投資 1.解：解： 設(shè)設(shè)sk表示第表示第k個(gè)工廠到第個(gè)工廠到第4個(gè)工廠的投資數(shù)。個(gè)工廠的投資數(shù)。xk 表示第表示第k個(gè)工廠的投資數(shù)個(gè)工廠的投資數(shù),則第則第4個(gè)階

46、段如下：個(gè)階段如下： fx* 0100200300400500600 0000 1002828100 2004747200 3006565300 4007474400 5008080500 6008585600 fx* 0100200300400500600 0000 1002818280 200474639470 3006565676167200 400748386897889300 500809210410810690108300 600859811312612511895126300 第第3個(gè)階段：個(gè)階段： fx* 0100 200 300400 500 600 0000 100 282

47、5280 200 47534553100 300 6772735773200 400 899292856592 100，200 500 108 114 112 1049370114 100 600 126 133 134 124112 9873134 200 第第2個(gè)階段：個(gè)階段： fx* 0100 200 300400 500 600 600 134 134 134 133128 113 90134 0，100，200 第第1個(gè)階段：個(gè)階段： 最優(yōu)方案：最優(yōu)方案： 1，0，200，300，100 2，100，100，300，100 3，200，100，200，100 4，200，200，0，

48、200 2. 用動(dòng)態(tài)規(guī)劃解以下靜態(tài)問題：用動(dòng)態(tài)規(guī)劃解以下靜態(tài)問題： 0, 93 102 567max 21 21 21 2 21 2 1 xx xx xx xxxz 解：令解：令k=2, 狀態(tài)變量：狀態(tài)變量：k階段初各約束條件右端項(xiàng)的剩余值階段初各約束條件右端項(xiàng)的剩余值r1k,r2k 決策變量：決策變量：x1,x2 ， ，狀態(tài)轉(zhuǎn)移方程為： 狀態(tài)轉(zhuǎn)移方程為： 112122 111112 9 10 xxrr xxrr 212 2 2 2 3 ,0max 22122 ) 2 (55max),( 12 2 22 r xrrf r x r 令令k=1,由于由于 k=2時(shí)時(shí), 2 10 2 112 2 x

49、r x 而由第而由第2個(gè)約束知，個(gè)約束知， 5 48 2 10 3939 1 1 11 x x xx 所以所以 92.70212519 4 33 12519 4 33 max ) 2 10 (567max ) 2 (567max)( 5 481 2 1 1 2 1 5 48 0 21 1 2 1 5 48 0 212 1 2 1 5 48 ,10min0 11 1 1 1 1 x x x x xx xx x xx r xxsf 此時(shí)此時(shí),x2=0.5 決策分析決策分析 1,某鐘表公司計(jì)劃通過它的銷售網(wǎng)銷售一種低價(jià)鐘某鐘表公司計(jì)劃通過它的銷售網(wǎng)銷售一種低價(jià)鐘 表，計(jì)劃每塊售價(jià)表，計(jì)劃每塊售價(jià)10

50、元。生產(chǎn)這種鐘表有元。生產(chǎn)這種鐘表有3個(gè)設(shè)個(gè)設(shè) 計(jì)方案：方案計(jì)方案：方案1需一次投資需一次投資10萬(wàn)元，以后生產(chǎn)一萬(wàn)元，以后生產(chǎn)一 個(gè)的費(fèi)用為個(gè)的費(fèi)用為5元，方案元，方案2需一次投資需一次投資16萬(wàn)元，以萬(wàn)元，以 后生產(chǎn)一個(gè)的費(fèi)用為后生產(chǎn)一個(gè)的費(fèi)用為4元；方案元；方案3需一次投資需一次投資25 萬(wàn)元，以后生產(chǎn)一個(gè)的費(fèi)用為萬(wàn)元，以后生產(chǎn)一個(gè)的費(fèi)用為3元。對(duì)該種鐘表元。對(duì)該種鐘表 的需求量為未知，但估計(jì)有三種可能：的需求量為未知，但估計(jì)有三種可能： e130000；e2120000；e3200000 a)建立這個(gè)問題的收益矩陣；建立這個(gè)問題的收益矩陣；b)分別用悲觀主義、分別用悲觀主義、 樂觀主義和等可能性決策準(zhǔn)則決定該公司應(yīng)采樂觀主義和等可能性決策準(zhǔn)則決定該公司應(yīng)采 用哪一個(gè)設(shè)計(jì)方案；用哪一個(gè)設(shè)計(jì)方案；c)建立機(jī)會(huì)損失矩陣，并用建立機(jī)會(huì)損失矩陣，并用 最小機(jī)會(huì)損失決策準(zhǔn)則決定采取哪一個(gè)設(shè)計(jì)方最小機(jī)會(huì)損失決策準(zhǔn)則決定采取哪一個(gè)設(shè)計(jì)方 案。案。 e1e2e3 a155090 a2256104 a3-459115 收益矩陣（單位：萬(wàn)）：收益矩陣（單位：萬(wàn)）： e1e2e3 a1550909 a2256104104 a3-459115115 樂觀準(zhǔn)則：樂觀準(zhǔn)則： 選選a3 e1e2e3 a1550909 a2256104104 a3-459115115 悲觀準(zhǔn)則：悲觀準(zhǔn)則： 選選a1 e