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

習(xí)題1

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

無可行解。

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

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

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

答案：

(a)唯一解X*=(1,1.5)7,z*=17.5),對偶問題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ī)劃問題，并指出屬于哪一類解。

答案：

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

4己知線性規(guī)劃問題的初始單純形表(如表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（-主元檢驗數(shù)/主元）加到檢驗數(shù)行得下一步表的檢

驗數(shù)行。

表1-54第一行系數(shù)X（-a/b）+表1-54檢驗數(shù)行=表1-54檢驗數(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è)施

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

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

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

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

設(shè)施設(shè)施有效臺時

IIIIII（元/小時）

10

A1560000.05

A?7912100000.03

B,6840000.06

411

B270000.11

B3740000.05

原料費（元/件）0.250.350.50

售價（元/件）1.252.002.80

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

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

如下表1-57所示：

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

品牌含量需求每磅售價（美元）

一般腰果仁不超過20%0.89

胡桃仁不低于40%

核桃仁不超過25%

杏仁沒有限制

豪華腰果仁不超過35%1.10

杏仁不低于40%

核桃仁、胡桃仁沒有限制

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

杏仁不低于30%

核桃仁、胡桃仁沒有限制

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

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

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

杏仁0.452000

核桃仁0.554000

腰果仁0.705000

胡桃仁0.503000

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

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

7寫出下列線性規(guī)劃問題的對偶問題。

答案：（a）

（b）

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

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

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

其對偶問題為：

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

為無界。

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

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

對偶問題最優(yōu)解。

答案：

對偶問題

*****

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

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

弛性，y*4=0o

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

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

y；+2y；=2(1)

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

'+y；=1(3)

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

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

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

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

-6]「3一

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

44

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

答案：

最終表

2-1100

Cjb

CBXBX1X2X3X4X5

2XI111106

0X50311110

bj0-3-1-20

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

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

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

重新計算X2的檢驗數(shù)

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

解之，見下表

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

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

對偶問題的最優(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*=2x—+3又一=一

333

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

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

將其添加到最終表得過渡表，然后將第一行乘-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*=。10828

333

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

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ī)劃問題：

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

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

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

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

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

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

航線起點終點每天航班

1ED3

2BC2

3AF1

4DB1

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

點

ABCDEF

起點

A0121477

B1031388

C2301555

/p>

E7851703

F7852030

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

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

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

?口ABCDE

人貝

人員甲127979

人員乙89666

人員丙71712149

人員丁15146610

人員戊4107109

15思索題

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

劃問題有什么不同？

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

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

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

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