規(guī)劃數(shù)學(xué)第三版課后習(xí)題答案

習(xí)題1

1用圖解法求解下列線性規(guī)劃問(wèn)題，并指出問(wèn)題具有唯一最優(yōu)解、無(wú)窮最優(yōu)解、無(wú)界解還是

無(wú)可行解。

答案：(a)唯一解X*=(0.75,0.5)。z*=3);(b)無(wú)可行解；

化)唯一解X*=(10,6)7,z*=16);⑹無(wú)界解)

2用單純形法求解下列線性規(guī)劃問(wèn)題。

答案：

(a)唯一解X*=(1,1.5)7,z*=17.5),對(duì)偶問(wèn)題y*=(0.357,1.786)7,以=17.5;

(b)唯一解X*=(3.5,1.5)。z*=8.5),Y*=(0,0.25,0.5/，以=8.5

3用大M法和兩階段法求解下列線性規(guī)劃問(wèn)題，并指出屬于哪一類解。

答案：

(a)無(wú)界解；(b)唯一解X*=(0.8,1.8,0)r,z*=8),對(duì)偶問(wèn)題y*=(l,0)T,"=8

4己知線性規(guī)劃問(wèn)題的初始單純形表(如表1-54所示)和用單純形法迭代后得到的表(如

表1-55所示)如下，試求括弧中未知數(shù)a?1的值。

表1-54初始單純形表

bXiX2X3X4X5

X46(b)(c)(d)10

X51-13(e)01

Cj-Zj(a)-1200

表1-55單純形法迭代后的表

bX1X2X3X4X5

X1⑴(g)2-11/20

X54(h)(i)11/21

cj-zj0-7(j)(k)(1)

表1-55基變量Xi列向量/7]=,所以g=l,h=0

(2)初始表b,p戶

某步表3-%，B-pj

,(1/20、

有已知表查出B=

11/21J

r-n

B-P3=n⑴=>d=—2,e=2

（3）初始表主元行X（-主元檢驗(yàn)數(shù)/主元）加到檢驗(yàn)數(shù)行得下一步表的檢

驗(yàn)數(shù)行。

表1-54第一行系數(shù)X（-a/b）+表1-54檢驗(yàn)數(shù)行=表1-54檢驗(yàn)數(shù)行

即：-2a—1=-7,6?+2—j,k=—6Z,/—0

3

故：a—3,j—5,k——-,/—?0o

5某廠生產(chǎn)I、II、III三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工?設(shè)A工序可分別在設(shè)施

Ai或A2上完成，有Bi、B2、B3三種設(shè)施可用于完成B工序。已知產(chǎn)品I可在A、B任何

一種設(shè)施上加工；產(chǎn)品H可在任何規(guī)格的A設(shè)施上加工，但完成B工序時(shí)，只能在&設(shè)施

上加工；產(chǎn)品IH只能在A2與B2設(shè)施上加工。加工單位產(chǎn)品所需工序時(shí)間及其他各項(xiàng)數(shù)據(jù)見(jiàn)

下表1-56,試支配最優(yōu)生產(chǎn)方案，使該廠獲利最大。

表1-56產(chǎn)品的有關(guān)數(shù)據(jù)表

產(chǎn)品設(shè)施加工費(fèi)

設(shè)施設(shè)施有效臺(tái)時(shí)

IIIIII（元/小時(shí)）

10

A1560000.05

A?7912100000.03

B,6840000.06

411

B270000.11

B3740000.05

原料費(fèi)（元/件）0.250.350.50

售價(jià)（元/件）1.252.002.80

6一家糖果商店出售三種不同品牌的果仁糖，每個(gè)品牌含有不同比例的杏仁、核桃仁、胡桃

仁。為了維護(hù)商店的質(zhì)量信譽(yù)，每個(gè)品牌中所含有的果仁的最大、最小比例是必需滿意的，

如下表1-57所示：

表1-57每個(gè)品牌中所含有的果仁的比例表

品牌含量需求每磅售價(jià)（美元）

一般腰果仁不超過(guò)20%0.89

胡桃仁不低于40%

核桃仁不超過(guò)25%

杏仁沒(méi)有限制

豪華腰果仁不超過(guò)35%1.10

杏仁不低于40%

核桃仁、胡桃仁沒(méi)有限制

藍(lán)帶腰果仁含量位于30%~50%之間1.80

杏仁不低于30%

核桃仁、胡桃仁沒(méi)有限制

表1-58列出了商店從供應(yīng)商每周能夠得到的每類果仁的最大數(shù)量和每磅的價(jià)格:

表1-58每類果仁的最大數(shù)量和每磅的價(jià)表

果仁類型每磅價(jià)格（美元）每周最大供應(yīng)量（磅）

杏仁0.452000

核桃仁0.554000

腰果仁0.705000

胡桃仁0.503000

商店盼望確定每周購(gòu)進(jìn)杏仁、核桃仁、腰果仁、胡桃仁的數(shù)量:，使周利潤(rùn)最大。建立數(shù)學(xué)模

型，關(guān)心該商店管理人員解決果仁混合的問(wèn)題。

7寫出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。

答案：（a）

（b）

8已知線性規(guī)劃問(wèn)題：

試應(yīng)用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題最優(yōu)解為無(wú)界。

答案：明顯X=（O,O,O）T為該問(wèn)題的可行解，

其對(duì)偶問(wèn)題為：

明顯第一個(gè)約束與變量非負(fù)要求沖突，故對(duì)偶問(wèn)題無(wú)可行解。由無(wú)界性該問(wèn)題最優(yōu)解

為無(wú)界。

9已知線性規(guī)劃問(wèn)題：

要求：（1）寫出其對(duì)偶問(wèn)題；（2）已知原問(wèn)題最優(yōu)解為X*=（2,2,4,0）T,試依據(jù)對(duì)偶理論求出

對(duì)偶問(wèn)題最優(yōu)解。

答案：

對(duì)偶問(wèn)題

*****

設(shè)對(duì)偶問(wèn)題的最優(yōu)解為y=（%，%，％，）4）

將X*=（2,2,4,0）T代入原問(wèn)題,約束（4）為嚴(yán)格不等式（即x*si,x*s2,x*s3）0）,由互補(bǔ)松

弛性，y*4=0o

又由于X*1=2,X*2=2,X*3=4都大于0,由互補(bǔ)松弛性，對(duì)偶問(wèn)題對(duì)應(yīng)（1）-（3）

約束為等式，（即y*s尸y*s2=y*s3=0）

y；+2y；=2(1)

故有3y；+y；+y；=4⑵,

'+y；=1(3)

解得對(duì)偶問(wèn)題的最優(yōu)解為Y*=（4/5,^3/5,1,0）。

io已知線性規(guī)劃問(wèn)題：

先用單純形法求出最優(yōu)解，再分析在下列條件單獨(dú)變化的狀況最優(yōu)解的變化。

(1)目標(biāo)函數(shù)變?yōu)閙axz=2X1+3x2+X3；

-6]「3一

(2)約束右端項(xiàng)由變?yōu)椋?/p>

44

(3)增加一個(gè)新的約束條件：一X1+2X322。

答案：

最終表

2-1100

Cjb

CBXBX1X2X3X4X5

2XI111106

0X50311110

bj0-3-1-20

該問(wèn)題的最優(yōu)解X*=(6,0,0,0,10尸，最優(yōu)值z(mì)*=2x6=12

對(duì)偶問(wèn)題的最優(yōu)解V*=(2,0,3,1,2),最優(yōu)值〃=6x2=12

(1)目標(biāo)函數(shù)中非基變量X2的系數(shù)C2由-1變?yōu)?

重新計(jì)算X2的檢驗(yàn)數(shù)

最優(yōu)解發(fā)生變化，將X2的檢驗(yàn)數(shù)CT2=1，系數(shù)C2=3代入最終表，用單純形法求

解之，見(jiàn)下表

Cj23100

b

CBXBX1X2X3X4X5

2Xi111106

0X50[3]11110?

%0(1)-1-20

2Xi102/32/3-1/38/3

3X2011/31/31/310/3

00-4/3-7/3-1/3

該問(wèn)題的最優(yōu)解X*=(8/3,10/3,0,0,0)7,最優(yōu)值z(mì)*=2x|+3xy=

對(duì)偶問(wèn)題的最優(yōu)解V*=(7/3,1/3,0,0,4/3)，最優(yōu)值①*=6xZ+4xl=—

333

1、

21⑶2、

⑵B"；33>0,故最優(yōu)基不變

5

2725

最優(yōu)解為X*=(2/3,7/3,00,0)7,最優(yōu)值z(mì)*=2x—+3又一=一

333

(3)最優(yōu)解X*=(6,0,0,0,10)7不滿意新加的約束

將約束化為等式，選松弛變量作為基變量得X]—2X3+X6=-2

將其添加到最終表得過(guò)渡表，然后將第一行乘-1加到第三行將基變量X.的系數(shù)列向

量化為單4應(yīng)向量

Cj2-11000

b

CBXBX1X2X3X4X5X6

2xi1111006

0X503111010

0X610-2001-2

2xi1111006

0X503111010

0X60-11-3J-101(-8)

bj0-3-P-200

2xi12/302/301/310/3

0X508/302/311/322/3

1X301/311/30-1/38/3

bj0-8/30-5/30-1/3

新的最優(yōu)解X*=(10/3,0,8/3,0,22/3)7,最優(yōu)值z(mì)*=。10828

333

11用分支定界法求解下列整數(shù)規(guī)劃問(wèn)題：

maxz=2x,+3x2maxz=X]+x2

5x.+7x,<35lx,+5X2<16

(1)-(2)

<4x,+9x2<36<6xj+5X2<30

x,,x2>0,且為整數(shù)X1,X2N0,且為整數(shù)

12用隱枚舉法求解下列0-1規(guī)劃問(wèn)題：

Xj=0或1,j=1，2,3,4,5

13某航運(yùn)公司擔(dān)當(dāng)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)已知

各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)見(jiàn)表1-59。假定各條航線使用相同型號(hào)的船只，

又各城市之間的航程天數(shù)見(jiàn)表1-60。又知每條船只每次裝卸貨物的時(shí)間各需1天，則該航

運(yùn)公司至少應(yīng)配備多少條船，才能滿意全部航線的運(yùn)貨需求?建立模型并用軟件求解。

表1-59各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)表

航線起點(diǎn)終點(diǎn)每天航班

1ED3

2BC2

3AF1

4DB1

表1-60各城市之間的航程天數(shù)表

點(diǎn)

ABCDEF

起點(diǎn)

A0121477

B1031388

C2301555

/p>

E7851703

F7852030

14設(shè)某公司有五個(gè)人可以完成五項(xiàng)工小下，每人做每項(xiàng)工作的用時(shí)如表1-61所示。每人僅做

一項(xiàng)工作，每項(xiàng)工作僅一人做。如何支配是用時(shí)最少？建立數(shù)學(xué)模型并用軟件求解

表1-61每人完成任務(wù)的用時(shí)表單位：天

?口ABCDE

人貝

人員甲127979

人員乙89666

人員丙71712149

人員丁15146610

人員戊4107109

15思索題

(1)線性規(guī)劃問(wèn)題在數(shù)學(xué)模型的形式、可行域的組成和最優(yōu)點(diǎn)的位置等方面與非線性規(guī)

劃問(wèn)題有什么不同？

(2)如何理解線性規(guī)劃問(wèn)題的求解其實(shí)就是可行域頂點(diǎn)的轉(zhuǎn)換方法？

(3)線性規(guī)劃的基解、基可行解和最優(yōu)解之間有什么關(guān)系？

(4)在解得轉(zhuǎn)換中，如何保證從一個(gè)基可行解轉(zhuǎn)換得到的仍舊是一個(gè)基可行解？

(5)在解的轉(zhuǎn)換中，如何保證目標(biāo)函數(shù)的值不僅下降，