運(yùn)籌學(xué)課后習(xí)題答案__林齊寧版本__北郵出版社

1、No.1 線性規(guī)劃1、某織帶廠生產(chǎn)A、B兩種紗線和C、D兩種紗帶，紗帶由專門紗線加工而成。這四種產(chǎn)品的產(chǎn)值、成本、加工工時(shí)等資料列表如下： 產(chǎn)品 項(xiàng)目ABCD單位產(chǎn)值 (元)1681401050406單位成本 (元)4228350140單位紡紗用時(shí) (h)32104單位織帶用時(shí) (h)0020.5工廠有供紡紗的總工時(shí)7200h，織帶的總工時(shí)1200h。(1) 列出線性規(guī)劃模型，以便確定產(chǎn)品的數(shù)量使總利潤最大；(2) 如果組織這次生產(chǎn)具有一次性的投入20萬元，模型有什么變化？對(duì)模型的解是否有影響？解：(1)設(shè)A的產(chǎn)量為x1，B的產(chǎn)量為x2，C的產(chǎn)量為x3，D的產(chǎn)量為x4，則有線性規(guī)劃模型如下：m

2、ax f(x)=(168-42)x1 +(140-28)x2 +(1050-350)x3 +(406-140)x4=126 x1 +112 x2 +700 x3 +266 x4s.t. (2)如果組織這次生產(chǎn)有一次性的投入20萬元，由于與產(chǎn)品的生產(chǎn)量無關(guān)，故上述模型只需要在目標(biāo)函數(shù)中減去一個(gè)常數(shù)20萬，因此可知對(duì)模型的解沒有影響。2、將下列線性規(guī)劃化為極大化的標(biāo)準(zhǔn)形式解：將約束條件中的第一行的右端項(xiàng)變?yōu)檎?，并添加松弛變量x4，在第二行添加人工變量x5，將第三行約束的絕對(duì)值號(hào)打開，變?yōu)閮蓚€(gè)不等式，分別添加松弛變量x6, x7，并令，則有max-f(x)= -2 x1 -3 x2 -5()+0

3、x4 -M x5+0 x6 +0 x7s.t. 3、用單純形法解下面的線性規(guī)劃解：在約束行1,2,3分別添加x4, x5, x6松弛變量，有初始基礎(chǔ)可行解和單純形法迭代步驟如下：Cj 253000CBXBbx1x2x3x4x5x6bi/aij*0x461032-1100610/20x5125-1(6)3010125/6*0x6420-211/2001420/1OBJ=0zj 000000cj - zj253000Cj 253000CBXBbx1x2x3x4x5x6bi/aij*0x41705/3(10/3)0-21-1/30170.55x2125/6-1/611/201/600x62395/6

4、-11/6000-1/61OBJ=625/6zj -5/655/205/60cj - zj17/601/20-5/60Cj 253000CBXBbx1x2x3x4x5x6bi/aij*2x1341/210-3/53/10-1/1005x5197/401(2/5)1/203/200125.1250x62847/400-11/1011/20-7/201OBJ=2349/4zj 254/517/2011/200cj - zj0011/50-11/200Cj 253000CBXBbx1x2x3x4x5x6bi/aij*2x11955/813/203/81/803x3985/805/211/83/800

5、x613555/16011/4011/161/161OBJ=6865/8zj 221/239/811/80cj - zj0-11/20-9/8-11/80答：最優(yōu)解為x1 =244.375, x2 =0, x3 =123.125, 剩余變量x6 =847.1875；最優(yōu)解的目標(biāo)函數(shù)值為858.125。No.2 兩階段法和大M法1、用兩階段法解下面問題：解：將原問題變?yōu)榈谝浑A段的標(biāo)準(zhǔn)型第一階段單純形表Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*-1x58012-101080-1x675(3)10-10175/3*OBJ=-155zj -4-311-1-1cj - zj4

6、3-1-100Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*-1x5550(5/3)-11/31-1/3553/5*0x12511/30-1/301/3253OBJ=-55zj 0-5/31-1/3-11/3cj - zj05/3-11/30-4/3Cj 0000-1-1CBXBbx1x2x3x4x5x6bi/aij*0x23301-3/51/53/5-1/50x114101/5-2/5-1/52/5OBJ=0zj 000000cj - zj0000-1-1第二階段Cj -4-600CBXBbx1x2x3x4bi/aij*-6x23301-3/51/5-4x114101

7、/5-2/5OBJ=-254zj -4-614/52/5cj - zj00-14/5-2/5答：最優(yōu)解為x1 =14，x2 =33，目標(biāo)函數(shù)值為254。2、用大M法解下面問題，并討論問題的解解：第1、2行約束條件添加x4, x5松弛變量，第3行添加x6剩余變量和x7人工變量，有如下初始單純形表和迭代步驟：Cj 101512000-MCBXBbx1x2x3x4x5x6x70x49(5)3110000x515-56150100-Mx7521100-11OBJ=-5Mzj -2M-M-M00M-Mcj - zj10+2M15+M12+M00-M0Cj 101512000-MCBXBbx1x2x3x4

8、x5x6x710x19/513/51/51/50000x52409(16)1100-Mx77/50-1/53/5-2/50-11OBJ=18-7M/5zj 106+M/52-3M/52+2M/50M-Mcj - zj09-M/510+3M/5-2-2M/50-M0Cj 101512000-MCBXBbx1x2x3x4x5x6x710x13/2139/8003/10-1/100012x33/209/1611/203/2000-Mx71/20-43/80011/20-7/20-11OBJ=33-M/2zj 1093/8+43M/801221/8+7M/165/8+3M/80M-Mcj - zj02

9、7/8-43M/800-21/8-7M/16-5/8-3M/80-M0答：最后單純形表中檢驗(yàn)數(shù)都小于等于0，已滿足最優(yōu)解判定條件，但人工變量x7仍未迭代出去，可知原問題無可行解(無解)。No.3 線性規(guī)劃的對(duì)偶問題1、寫出下列線性規(guī)劃問題的對(duì)偶問題：(1) 解：對(duì)偶問題為 (2) 解：原問題的約束條件可改寫為右式令改寫后約束條件每行對(duì)應(yīng)的對(duì)偶變量為y1,.,y6，則有對(duì)偶規(guī)劃如下：2、寫出下問題的對(duì)偶問題，解對(duì)偶問題，并證明原問題無可行解 解：對(duì)偶問題為 約束條件標(biāo)準(zhǔn)化為 有對(duì)偶問題解的單純形表如下：Cj 1-1100CBYBby1y2y3y4y50y44-101100y53-1(1)-201

10、OBJ=0zj 00000zj - cj-11-100Cj 1-1100CBYBby1y2y3yy50y44-10(1)10-1y23-11-201OBJ=-3zj 1-120-1zj - cj0010-1Cj 1-1100CBYBby1y2y3y4y51y34-10110-1y211-31021OBJ=-7zj 2-11-1-1zj - cj100-1-1 入變量答：迭代到第三步，x1為入變量，但主列中技術(shù)系數(shù)全為負(fù)值，故對(duì)偶問題有可行解但解無界，由弱對(duì)偶定理推論可知，原問題無可行解。3、用對(duì)偶單純形法求下面問題解：Cj 4600min( zj - cj)/ai*jCBXBbx1x2x3x4

11、ai*j00x3-80-1(-2)104,3*0x4-75-3-101OBJ=0zj 0000zj - cj-4-600Cj 4600CBXBbx1x2x3x46x2401/21-1/200x4-35(-5/2)0-1/212/5*,6OBJ=240zj 36-30zj - cj-10-30Cj 4600CBXBbx1x2x3x46x23301-3/51/54x114101/5-2/5OBJ=254zj 46-14/5-2/5zj - cj00-14/5-2/5答：最優(yōu)解為x1 =14，x2 =33，目標(biāo)函數(shù)值為254。No.4 線性規(guī)劃的靈敏度分析1、下表是一線性規(guī)劃最優(yōu)解的單純形表Cj 2

12、194000CBXBbx1x2x3x4x5x621x14101/32/301/30x5200-2/3-4/311/39x223011/3-1/30-2/3zj219101101cj - zj00-6-110-1原問題為max型，x4，x5為松馳變量，x6為剩余變量，回答下列問題：(1)資源1、2、3的邊際值各是多少？(x4，x5是資源1、2的松馳變量，x6是資源3的剩余變量)(2)求C1, C2 和C3的靈敏度范圍；(3)求Db1，Db2的靈敏度范圍。解：(1) q1 =11, q2 =0, q3 = -1。(2) x1 , x2 為基變量，故x3 為非基變量，故(3) 同理有 No.5 運(yùn)輸

13、問題1、分別用西北角法、最低費(fèi)用法和運(yùn)費(fèi)差額法，求下面運(yùn)輸問題(見表)的初始可行解，并計(jì)算其目標(biāo)函數(shù)。(可不寫步驟)2、以上題中最低費(fèi)用法所得的解為初始基礎(chǔ)可性解，用表上作業(yè)法（踏石法）求出最優(yōu)解。（要求列出每一步的運(yùn)費(fèi)矩陣和基礎(chǔ)可行解矩陣）銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A16948520A2106128730A365920940A4213614360銷量2515354530解：(1) 西北角法205151025153030OBJ1415(2) 最低費(fèi)用法20x143015101525530(2) 差額法51530152525530OBJ850OBJ955 運(yùn)費(fèi)表 (檢驗(yàn)數(shù)zij |wij

14、)06094(15)8154-710-76-3128-67-356592069922136171436-4-4011-3迭代后的分配表xij 51530152525530OBJ850運(yùn)費(fèi)表 (檢驗(yàn)數(shù)zij |wij )0609481540100641281745659132069922136101436-4-404-3答：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, OBJ=850。No.6 指派問題1、有4個(gè)工人。要指派他們分別完成4項(xiàng)工作。每人做各項(xiàng)工作所消耗的時(shí)間(h) 如下表，問如何分派工作，使總的消耗時(shí)間最

15、少？消耗 工作工人ABCD甲3353乙3252丙1516丁46410解：變換效率矩陣如下：3353逐(0)0*20*逐(0)0*20*3252行1030列1(0)30*1516標(biāo)0*4(0)5標(biāo)0*4(0)546410記0*20*6記0*20*6每行每列都有兩個(gè)以上的0 未找到最優(yōu)解4(0) 0*2 0*重0*(0)20*81(0)3 0*新10*3(0)5 0*4(0)5標(biāo)0*4(0)51 0*2 0*6記(0)20*62637劃線過程(發(fā)現(xiàn)有4條直線) 找到最優(yōu)解答：容易看出，共有四個(gè)最優(yōu)解：甲B，乙D，丙A，丁C；甲D，乙B，丙A，丁C；甲B，乙D，丙C，丁A；甲D，乙B，丙C，丁A；O

16、BJ=10。 b a 1.52.51.52.5 0.5 335(3) -0.53(2)52 -0.5(1)516* 0.546410slack2327nbour4444S*=1下面是用匈亞利算法求解的過程： b a 1212 * 03353 03(2)52 0(1)516* * 046410slack2131nbour1141S*=0.5 b a 2.53.52.53.5 -0.5335(3) -1.53(2)52 -1.5(1)516 1.546(4)10slacknbour第一個(gè)最優(yōu)解：OBJ10 b a 2.53.52.53.5 -0.5335(3) -1.53(2)52 -1.515(

17、1)6 1.5(4)6410slacknbour第二個(gè)最優(yōu)解：OBJ102、學(xué)生A、B、C、D的各門成績?nèi)缦卤?，現(xiàn)將此4名學(xué)生派去參加各門課的單項(xiàng)競賽。競賽同時(shí)舉行，每人只能參加一項(xiàng)。若以他們的成績?yōu)檫x派依據(jù)，應(yīng)如何指派最有利？得分 課程學(xué)生數(shù)學(xué)物理化學(xué)外語A89926881B87886578C95908572D75788996解：變換效率矩陣為適用于min化問題，用96減去上面矩陣中所有元素值，742815逐302411逐3(0102310列1 0*16101161124變051023變(0)5323211870換211870換2118(0) 0*22(0)1610

18、52(0)137答：A物理(0) 0*1593(0)0*126B數(shù)學(xué)OBJ= 0*63231 0*6(0)20C化學(xué)3602119(0) 0*2422 0*(0)D外語24No.7 動(dòng)態(tài)規(guī)劃1、某公司有9個(gè)推銷員在全國三個(gè)不同市場里推銷貨物，這三個(gè)市場里推銷員人數(shù)與收益的關(guān)系如下表，做出各市場推銷人員數(shù)的分配方案，使總收益最大。推銷員市場012345678912032475766718290100110240506071829310411512513535061728497109120131140150解：令分配到各地區(qū)的推銷員人數(shù)為決策變量xk ，k=1,2,3代表第1、2、3地區(qū)；令各地區(qū)

19、可供分配的推銷員人數(shù)為狀態(tài)變量sk 。最先分配給第1地區(qū)，然后第2、第3地區(qū)，則 s1=9。狀態(tài)轉(zhuǎn)移公式為：sk+1 = sk -xk ；目標(biāo)函數(shù)為：第1階段：第3地區(qū)， s3 有09種可能，由收益表第3行可知d(x3)單調(diào)增，故有x3 *= s3；列表如下：x3*=s30123456789f1*5061728497109120131140150第2階段：第2地區(qū)，s2 仍有09種可能，列表如下： x20123456789x2*f2* s2090*0901101*10001012112*11111001123124*12212112101244137*13413213213201375149*

20、14714414314314301496160*15915715515415415401607171*17016916816616516516501718180181*18018017917717617617511819190190191*191*191*1901881871861852,3,4191s39876543210第3階段：第1地區(qū)，由s1 =9， 列表如下： x1 s10123456789x1*f3*9211213218*2172152082062022012002218s29876543210答：第1地區(qū)分配2名推銷員，第2 地區(qū)不分配人員，第3地區(qū)分配7名推銷員，總收益為218

21、。2、設(shè)某工廠要在一臺(tái)機(jī)器上生產(chǎn)兩種產(chǎn)品，機(jī)器的總運(yùn)轉(zhuǎn)時(shí)間為5小時(shí)。生產(chǎn)這兩種產(chǎn)品的任何一件都需占用機(jī)器一小時(shí)。設(shè)兩種產(chǎn)品的售價(jià)與產(chǎn)品產(chǎn)量成線性關(guān)系，分別為(12-x1)和(13-2x2)。這里x1和x2分別為兩種產(chǎn)品的產(chǎn)量。假設(shè)兩種產(chǎn)品的生產(chǎn)費(fèi)用分別是4x1和3x2，問如何安排兩種產(chǎn)品的生產(chǎn)量使該機(jī)器在5小時(shí)內(nèi)獲利最大。(要求用連續(xù)變量的動(dòng)態(tài)規(guī)劃方法求解)解：設(shè)可用機(jī)時(shí)為狀態(tài)si，先分配產(chǎn)品1機(jī)時(shí)，故有狀態(tài)轉(zhuǎn)移方程sk+1 = sk -xk (i =1,2)邊界值s1 =5, s3=0目標(biāo)函數(shù)為：由邊界條件s3 = s2 -x2 =0，得 x2 = s2，因此有則動(dòng)態(tài)規(guī)劃總效果的遞推方程為由

22、狀態(tài)方程 s2 = s1 -x1 5-x1，代入上式得令 ，解得 x1 =3。因此，答：最優(yōu)策略為第1種產(chǎn)品生產(chǎn)3件，第二種產(chǎn)品生產(chǎn)2件，5小時(shí)內(nèi)最大利潤為27元。No.8 最短路問題1、求下圖中v1到所有點(diǎn)的最短路徑及其長度。(要求最短路用雙線在圖中標(biāo)出，保留圖中的標(biāo)記值)解：最短路及其長度如圖中粗線和節(jié)點(diǎn)上永久標(biāo)記所示，2、將上圖看作無向圖，寫出邊權(quán)鄰接矩陣，用Prim算法求最大生成樹，并畫出該樹圖。解：由圖可得鄰接矩陣，由Prim 算法的最大生成樹如下圖，123456781 11(4)3 2153(5)2 34(5)126 43163(7)4 55(6)(7)5 637217 7272(

23、5)8 815答：最大生成樹的權(quán)值為39。No.9 網(wǎng)絡(luò)流問題1、求下面網(wǎng)絡(luò)s到t的最大流和最小截，從給定的可行流開始標(biāo)號(hào)法。(要求每得到一個(gè)可行流后，即每次增廣之后，重新畫一個(gè)圖，標(biāo)上增廣后的可行流，再進(jìn)行標(biāo)號(hào)法)解：答：最大流為15，最小割截為習(xí)題課11、某工廠生產(chǎn)用2單位A和1單位B混合而成的成品出售，市場無限制。A和B可以在該工廠的3個(gè)車間中的任何車間生產(chǎn)，生產(chǎn)每單位的A和B在各車間消耗的工時(shí)如下表。工時(shí)消耗車間1車間2車間3A211.5B121.5可用工時(shí)100120100試建立使成品數(shù)量最大的線性規(guī)劃模型。解：設(shè)車間1生產(chǎn)x1A單位A、生產(chǎn)x1B單位B；設(shè)車間2生產(chǎn)x2A單位A、生

24、產(chǎn)x2B單位B；設(shè)車間3生產(chǎn)x3A單位A、生產(chǎn)x3B單位B；則有生產(chǎn)安排最優(yōu)化的模型如下：這是一個(gè)可分解的線性規(guī)劃，這類問題就容易出現(xiàn)退化現(xiàn)象。2、某飲料工廠按照一定的配方將A、B、C三種原料配成三種飲料出售。配方規(guī)定了這三種飲料中A和C的極限成分，具體見下表，飲料品種規(guī) 格每升售價(jià)(元)需求量甲 (1)A60，C206.801500乙 (2)A15，C605.703000丙 (3)C504.50無限制A、B、C三種原料每月的供應(yīng)量和每升的價(jià)格如下表。供應(yīng)量(升/月)價(jià)格(元/升)A20007.00B25005.00C12004.00飲料甲、乙、丙分別由不同比例的A、B、C調(diào)兌而成，設(shè)調(diào)兌后不同成分的體積不變，求最大收益的生產(chǎn)方案。解：設(shè)x1A為飲料甲中A的總含量 (升)，設(shè)x2A為飲料乙中A的總含量 (升)設(shè)x1B為飲料甲中B的總含量 (升)，設(shè)x2B為飲料乙中B的總含量 (升)設(shè)x1C為飲料甲中C的總含量 (升)，設(shè)x2C為飲料乙中C的總含量 (升)設(shè)x3A為飲料丙中A的總含量 (升)， 設(shè)x3B為飲料丙中B的總含量 (升)設(shè)x3C為飲料丙中C的總含量 (升)則有模型如下：3、將下列線性規(guī)劃化為標(biāo)準(zhǔn)形式 4、求上題的對(duì)偶規(guī)劃。 習(xí)題課21用連續(xù)型動(dòng)態(tài)規(guī)劃求解下題解：設(shè)分配順序?yàn)閤1, x2, x3，三階段與分配順序