運籌學課后習題答案-林齊寧版本-北郵出版社

運籌學課后習題答案--林齊寧版本--北郵出版社運籌學課后習題答案--林齊寧版本--北郵出版社

·No.1線性規(guī)劃

1、某織帶廠生產(chǎn)A、B兩種紗線和C、D兩種紗帶，紗帶由特地紗線加工而成。這四種產(chǎn)品的產(chǎn)值、成本、加工工時等資料列表如下：

工廠有供紡紗的總工時7200h，織帶的總工時1200h。

(1)列出線性規(guī)劃模型，以便確定產(chǎn)品的數(shù)量使總利潤最大；

(2)假如組織這次生產(chǎn)具有一次性的投入20萬元，模型有什么變化？對模型的解是否有影響？

解：(1)設A的產(chǎn)量為x1，B的產(chǎn)量為x2，

C的產(chǎn)量為x3，

D的產(chǎn)量為x4，則有線性規(guī)劃模型如下：

maxf(x)=(168-42)x1+(140-28)x2+(1050-350)x3+(406-140)x4

=126x1+112x2+700x3+266x4

s.t.

??

?

??=≥≤+≤+++4,3,2,1,012024.02720241023434321ixxxxxxxi

(2)假如組織這次生產(chǎn)有一次性的投入20

萬元，由于與產(chǎn)品的生產(chǎn)量無關，故上述模型只需要在目標函數(shù)中減去一個常數(shù)20萬，因此可知對模型的解沒有影響。

2、將下列線性規(guī)劃化為極大化的標準形式

解：將約束條件中的第一行

的右端項變?yōu)檎?，并添加松弛變量x4，在其次行添

加人工變量x5，將第三行約束的肯定值號打開，變?yōu)閮蓚€不等式，分別添加松弛變量x6,x7，并令xxx3

3

3

='-''，則有

max={-2x1-3x2-5('-''xx3

3

)+0x4-Mx5+0x6+0x7}

??????

?±≥≤+-=-+--≥-+++=不限

321321321321321,0,13|5719|169765

..532)(minxxxxxxxxxxxxtsxxxxf

s.t.0,,,,,,,13

557191355719

1699765765433217

3321633

215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--??

??

?

????

xxxxxxxxxxxxxxxxxxxxxxxxxxxx

3、用單純形法解下面的線性規(guī)劃

???

???

?≥≤++-≤++-≤-+++=,0,,4205.021*********..352)(max321321321321321xxxxxxxxxxxxtsxxxxf

解：在約束行1,2,3分別添加x4,x5,x6松弛

變量，有初始基礎可行解和單純形法迭代步驟如下：

答：最優(yōu)解為x1=244.375,x2=0,x3

=123.125,剩余變量x6=847.1875；最優(yōu)解的目標函數(shù)值為858.125。

No.2兩階段法和大M法

解：將原問題變?yōu)榈谝浑A段的標準型

???

??≥=+-+=+-+--?+?=0,,,,,75

3802..00)(max6

54321642153216

521xxxxxxxxxxxxxxtsxxxxxf

第一階段單純形表

1、用兩階段法解下面問題：???

??≥≥+≥++=0,75

380

2..64)(min2

1212121xxxxxxtsxxxf

其次階段

cj-zj00-14/5-2/5

答：最優(yōu)解為x1=14，x2=33，目標函數(shù)值為254。

2、用大M法解下面問題，并爭論問題的解

???

???

?≥≥++≤++-≤++++=,0,,52151565935..121510)(max321321321321321xxxxxxxxxxxxtsxxxxf

解：第1、2行約束條件添加x4,x5松弛變量，第3行添加x6剩余變量和x7人工變量，有如下初始單純形表和迭代步驟：

答：最終單純形表中檢驗數(shù)都小于等于0，已滿意最優(yōu)解判定條件，但人工變量x7仍未迭代出去，可知原問題無可行解(無解)。

No.3線性規(guī)劃的對偶問題解：對偶問題為

?????

????±≥≤=+-≥++-≥+≤+++=不限

321313213121321,0,005322..645)(minyyyyyyyyyyyytsyyyyg??

?

???

?????≤≥±-≥-≤≥≤-≥≤0

,0,1284142

6321

332211xxxxxxxxx不限

令改寫后約束條件每行對應的對偶變

量為y1,...,y6，則有對偶規(guī)劃如下：

??????

?≥≤≥+-≤+=+--++-=0

,,,0,,834..12841426)(max642531654321654321yyyyyyyyyyyytsyyyyyyyg

1、寫出下列線性規(guī)劃問題的對偶問題：

(1)

??????

?±≥≤=++≤+≥+-+-+=不限

43214323143213

21,0,,06425

..532)(maxxxxxxxxxxxxxxtsxxxxf

(2)

??

?

??-≤≤-≤≤≤≤-+-=8

1214

46

2..834)(min3213

21xxxtsxxxxf

解：原問題的約束條

件可改寫為右式

2、寫出下問題的對偶問題，解對偶問題，并證明原問題無可行解解：對偶問題為約束條件標準化為???

??≥-≥+--≥-+-=0

,,324

..)(min32132131321yyyyyyyytsyyyyg

??

?

??≥=-+-=++-0,,,,3+2

4543215321431yyyyyyyyyyyy

有對偶問題解的單純形表如下：

??

????

?≥≤+--≤-≤+--=

,0,121

1..34)(max212

12

21

2

1

xxxxxxxtsx

xxf

入變量

答：迭代到第三步，x1為入變量，但主列中技術系數(shù)全為負值，故對偶問題有可行解但解無界，由弱對偶定理推論可知，原問題無可行解。

3、用對偶單純形法求下面問題

???

??≥≥+≥++=0

,75

3802..64)(min21212121xxxxxxtsxxxf

解：

答：最優(yōu)解為x1=14，x2=33，目標函數(shù)值為254。

No.4線性規(guī)劃的靈敏度分析

原問題為max型，x4，x5為松馳變量，x6為剩余變量，回答下列問題：

(1)資源1、2、3的邊際值各是多少？(x4，

x5是資源1、2的松馳變量，x6是資源3的剩余變量)

(2)求C1,C2和C3的靈敏度范圍；(3)求?b1，?b2的靈敏度范圍。解：(1)q1=11,q2=0,q3=-1。(2)x1,x2為基變量，故

max/,/,/max,.,---?????

?≤?---≤?-≤≤+∞?≤≤+∞61311231131816533181111???

CCCC

max/min/,/..-??????≤≤----????

?

??-≤≤?-≤≤61311131231815105222?

?

CCC9

x3為非基變量，故

-∞≤≤?-∞≤≤?

CC33

610

(3)

5.163/123,3/42min3/24max11≤?≤-???

????----≤?≤??????-bb

同理有-≤≤

+∞22?b

No.5運輸問題

1、分別用西北角法、最低費用法和運費差額法，求下面運輸問題(見表)的初始可行解，并計算其目標函數(shù)。(可不寫步驟)

2、以上題中最低費用法所得的解為初始基礎可性解，用表上作業(yè)法（踏石法）求出最優(yōu)解。（要求列出每一步的運費矩陣和基礎可行解矩陣）

OBJ＝955?運費表(檢驗數(shù)zij4

-396

-4-4-3

解：(1)西北角法OBJ＝1415OBJ＝850

運費表(檢驗數(shù)zij

449

6

-4-4-3

答：x13=5,x14=15,x24=30,x32=15,x33=25,x41=25,x43=5,x45=30,OBJ=850。No.6指派問題

1、有4個工人。要指派他們分別完成4項工作。每人做各項工作所消耗的時間(h)如下表，問如何分派工作，使總的消耗時間最少？

解：變換效率矩陣如下：

逐行?標?記每行每列都有兩個以上的0

迭代后的安排表OBJ＝850

未找到最優(yōu)解

∨4

∨8

∨5?

∨1

2637

劃線過程(發(fā)覺有4條直線)找到最優(yōu)解

答：簡單看出，共有四個最優(yōu)解：①甲→B，乙→D，丙→A，丁→C；

②甲→D，乙→B，丙→A，丁→C；③甲→B，乙→D，丙→C，丁→A；④甲→D，乙→B，丙→C，丁→A；OBJ=10。

下面是用匈亞利算法

求解的過程：

S*=1

S*=0.5

*

*

*

其次個最優(yōu)解：OBJ

＝10

2、同學A、B、C、D的各門成果如下表，現(xiàn)將此4名同學派去參與各門課的單項競賽。競賽同時進行，每人只能參與一項。若以他們的成果為選派依據(jù)，應如何指派最有利？

解：變換效率矩陣為適用于min化問題，用96減去上面矩陣中全部元素值，

逐∨3行∨1?變?換

∨2

53124

第一個最優(yōu)解：OBJ＝10

No.7動態(tài)規(guī)劃

1、某公司有9個推銷員在全國三個不同市場里推銷貨物，這三個市場里推銷員人數(shù)與收益的關系如下表，做出各市場推銷人員數(shù)的安排方案，使總收益最大。

解：令安排到各地區(qū)的推銷員人數(shù)為決策變量xk，k=1,2,3代表第1、2、3地區(qū)；令各地區(qū)可供安排的推銷員人數(shù)為狀態(tài)變量sk。最先安排給第1地區(qū)，然后第2、第3地區(qū)，則s1=9。

狀態(tài)轉移公式為：sk+1=sk-xk；目標函數(shù)為：fdx

i

i3

1

3==∑max()第1階段：第3地區(qū)，s3有0～9種可能，由收益表第3行可知d(x3)單調(diào)增，故有x

第2階段：第2地區(qū)，s2仍有0～9種可能，列表如下：

第3階段：第1地區(qū)，由s1=9，列表如下：

答：第1地區(qū)安排2名推銷員，第2地區(qū)不安排人員，第3地區(qū)安排7名推銷員，總收益為218。

2、設某工廠要在一臺機器上生產(chǎn)兩種產(chǎn)品，機器的總運轉時間為5小時。生產(chǎn)這兩種產(chǎn)品的任何一件都需占用機器一小時。設兩種產(chǎn)品的售價與產(chǎn)品產(chǎn)量成線性關系，分別為(12-x1)和(13-2x2)。這里x1和x2分別為兩種產(chǎn)品的產(chǎn)量。假設兩種產(chǎn)品的生產(chǎn)費用分別是4x1和3x2，問如何支配兩種產(chǎn)品的生產(chǎn)量使該機器在5小時內(nèi)獲利最大。(要求用連續(xù)變量的動態(tài)規(guī)劃方法求解)

解：設可用機時為狀態(tài)si，先安排產(chǎn)品1機時，故有狀態(tài)轉移方程

sk+1=sk-xk(i=1,2)

邊界值s1=5,s3=0

目標函數(shù)為：}3)213(4)12max{(2

2

2

1

1

1

2

xxxxxxf--+--=*

)}210()8max{(22

2

21

1

xxxx-+-=

由邊界條件s3=s2-x2=0，得x2=s2，因此有

22

2

22

2

21

210210)(ssxxsf-=-=*

則動態(tài)規(guī)劃總效果的遞推方程為

)}

210()8{(0

max)}

()8{(0

max)(2

222111212

11112ssxxxsfxxxxf-+-

>=+->=**

由狀態(tài)方程s2=s1-x1＝5-x1，代入上

式得

}318{0

max}

)5(2)5(10)8{(0

max)(2

1112112

11112xxxxxxxxxf->=

---+->=*

令

dfxdxx21111860

()/=-=，解得x1=3。因此，

27

933182=?-?=*f

答：最優(yōu)策略為第1種產(chǎn)品生產(chǎn)3件，其次種產(chǎn)品生產(chǎn)2件，5小時內(nèi)最大利潤為27元。

No.8最短路問題

1、求下圖中v1到全部點的最短路徑及其長度。(要求最短路用雙線在圖中標出，保留圖中的標記值)

解：最短路及其長度如圖中粗線和節(jié)點上永久標記所示，

2、將上圖看作

無向圖，寫出邊

權鄰接矩陣，用Prim算法求最大生成樹，并畫出該樹圖。

解：由圖可得鄰接矩陣，由Prim算法的最大生成樹如下圖，

3

7

答：最大生成樹的權值為39。

11

√1√3√2√6√4√5√7√8

No.9網(wǎng)絡流問題

1、求下面網(wǎng)絡s到t的最大流和最小截，從給定的可行流開頭標號法。(要求每得到一個可行流后，即每次增廣之后，重新畫一個圖，標上增廣后的可行流，再進行標號法)

解：

v3

5t

,2)

+

v3

5

t

(s

答：最大流為15，最小割截為VsvVvvvvt==(,),(,,,,)3

1245

v35

(s,9)(3,4))

(s

v3

5

(s(s,5)

vt

習題課1

1、某工廠生產(chǎn)用2單位A和1單位B混合而成的成品出售，市場無限制。A和B可以在該工廠的3個車間中的任何車間生產(chǎn)，生產(chǎn)每單位的A和B在各車間消耗的工時如下表。

試建立使成品數(shù)量最大的線性規(guī)劃模型。

解：設車間1生產(chǎn)x1A單位A、生產(chǎn)x1B單位B；

設車間2生產(chǎn)x2A單位A、生產(chǎn)x2B單位B；

設車間3生產(chǎn)x3A單位A、生產(chǎn)x3B單位B；

則有生產(chǎn)支配最優(yōu)化的模型如下：

????

?

????=≥++≥++≤+≤+≤+++=3,2,1,0,)(2100

5.15.112024002..)(max321321332211321ixxxxxxxxxxxxxxtsxxxxfiBiABBBAAABABABAB

BB

這是一個可分解的線性規(guī)劃，這類問題

就簡單消失退化現(xiàn)象。

2、某飲料工廠根據(jù)肯定的配方將A、B、C三種原料配成三種飲料出售。配方規(guī)定了這三種飲料中A和C的極限成分，詳細見下表，

A、B、C三種原料每月的供應量和每升的價格如下表。

飲料甲、乙、丙分別由不同比例的A、B、C調(diào)兌而成，設調(diào)兌后不同成分的體積不變，求最大收益的生產(chǎn)方案。

解：設x1A為飲料甲中A的總含量(升)，

設x2A為飲料乙中A的總含量(升)

設x1B為飲料甲中B的總含量(升)，設x2B為飲料乙中B的總含量(升)

設x1C為飲料甲中C的總含量(升)，設x2C為飲料乙中C的總含量(升)

設x3A為飲料丙中A的總含量(升)，設x3B為飲料丙中B的總含量(升)

設x3C為飲料丙中C的總含量(升)則有模型如下：

?

??

???

??

????

?????

=≥≤+--≤+--≤++-≤+--≤++-≤++≤++≤++≤++≤+++--++-++-=++-++-++-++++++++=3

,2,1,0,,05.05.05.00

4.06.06.001

5.015.085.008.02.02.00

6.06.04.012024500200030001500..5.05.05.2

7.17.03.1

8.28.12.0)

(0.4)(0.5)(0.7)

(5.4)(7.5)(8.6)(max333222222111111321321321222111333222111321321321333222111ixxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxxxxxxxxxxxxxxxxxfiCiBiACBACBACBACBAC

BA

CCCB

BBAAA

CBACBACBACBACBACCCBBBAAACBACBACBA丙配方約束乙配方約束

甲配方約束資源約束需求約束

3、將下列線性規(guī)劃化為標準形式

??????

?±≤≥≤-+=+--≥-++-=不限

321321321321321,0,019|1210|1573610..235)(minxxxxxxxxxxxxtsxxxxf

??

???

????≥''''≤+''-'+'+-≤+''+'-'-=''-'+'+≤+''-'+'+-''+-'--=-0,,,,,,19

121019121015773610..2'235)](max[654332

16

33215332

133214332

1332

1xxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxf

4、求上題的對偶規(guī)劃。

??????

?≥≤±≥=--+--≥++-≤+++-++-=0

,0,,027312123510106..19191510)(max43214321432143214321yyyyyyyyyyyyyyyytsyyyyyg不限

??????

?≤≤±≥=+-+--≥-+-≤-+++++-=0

,0,,0273121235

10106..19191510)(max43214321432143214

321yyyyyyyyyyyyyyyytsyyyyyg不限

習題課2

1．用連續(xù)型動態(tài)規(guī)劃求解下題

???≥=++=0

,,27..)(min3213

21321xxxxxxtsxxxxf

解：設安排挨次為x1,x2,x3，三階段與安排挨次全都，逆向運算。

由約束條件有狀態(tài)轉移方程：Sk=Sk-1/xk-1

第三階段：邊界條件為S4=1，所以有3

3

Sx=*

，

3

3

3

3

3

3

)(),(SSfxSf==**

其次階段：S3=S2/x2，

2

2

2

3

3

2

2

2

2

/)(),(xSxSfxxSf+=+=*2

22

2

2

22

22

2

2)(,,01SSfSxx

S

dxdf===-=**，第一階段：S2=S1/x1=27/x1，

1

121221111/27