運籌學(xué)期末考試試題及答案

2011年運籌學(xué)期末考試試題及答案

（用療"公#新）

一、單項選擇題（每題3分，共27分）

L使用人工變量法求解極大化的線性規(guī)劃問題時、當(dāng)所有的檢驗數(shù)

為40,但在基變量中仍含有非零的人工變量，表明該線性規(guī)劃問

題（D）

A.有唯一的最優(yōu)解B.有無窮多最優(yōu)解

C.為無界解D.無可行解

2.對于線性規(guī)劃

maxz=一2玉+4x2

s.t.

-3%2+￡=4

<xl+5X2+8=1

王，元2，當(dāng)，工4

如果取基B則對于基B的基解為（B）

A.X=（0,0,4,1）7B.X=（1,0,3,

C.X=（4,0,0,-3/D.X=（23/8,—3/8,0,0了

3.對偶單純形法解最小化線性規(guī)劃問題時，每次迭代要求單純形表

中（C）

A.b列元素不小于零B.檢驗數(shù)都大

于零

C.檢驗數(shù)都不小于零D.檢驗數(shù)都不

大于零

4.在n個產(chǎn)地、m個銷地的產(chǎn)銷平衡運輸問題中，（D）是錯誤的。

A.運輸問題是線性規(guī)劃問題

B.基變量的個數(shù)是數(shù)字格的個數(shù)

C.非基變量的個數(shù)有w〃-加+1個

D.每一格在運輸圖中均有一閉合回路

5.關(guān)于線性規(guī)劃的原問題和對偶問題，下列說法正確的是（B）

A.若原問題為無界解，則對偶問題也為無界解

B.若原問題無可行解，其對偶問題具有無界解或無可行解

C.若原問題存在可行解，其對偶問題必存在可行解

D.若原問題存在可行解，其對偶問題無可行解

6.已知規(guī)范形式原問題（max問題）的最優(yōu)表中的檢驗數(shù)為

（4,4,…，兒），松弛變量的檢驗數(shù)為（心,加2,…d+,“），則對偶問題的

最優(yōu)解為（C）

A.（4,4，.“,x“）B.（-4，-4,…4J

C.（一4什］,-4,+2,…D.（2?+1,/1?+2,...,2?+?,）

7.當(dāng)線性規(guī)劃的可行解集合非空時一定（D）

A.包含原點B.有界C.無界D.是凸集

8.線性規(guī)劃具有多重最優(yōu)解是指(B)

A.目標(biāo)函數(shù)系數(shù)與某約束系數(shù)對應(yīng)成比例。

B.最優(yōu)表中存在非基變量的檢驗數(shù)為零。

C.可行解集合無界。

D.存在基變量等于零。

9.線性規(guī)劃的約束條件為歸+2々+%=4,則基可行解是(D)

xt,x2,x3,x4>0

A.(2,0,0,1)B.(-1,1,2,4)C.(2,2,-2,-4)

D.(0,0,2,4)

二、填空題(每題3分，共15分)

1.線性規(guī)劃問題中，如果在約束條件中沒有單位矩陣作為初始可行

基，我們通常用增加人工變量的方法來產(chǎn)生初始可行

基。

2.當(dāng)原問題可行，對偶問題不可行時，常用的求解線性規(guī)劃問題的

方法是單純形法。

3.原問題的第1個約束方程是型，則對偶問題相應(yīng)的變量是

無約束變量。

4.運輸問題中，當(dāng)總供應(yīng)量大于總需求量時，求解時需虛設(shè)一個

銷地,此地的需求量為總供應(yīng)量減去總需求量。

5.約束玉+2/W6,4X1+6X2>1及2%+4々420中至少有一個起作用，

引入0-1變量，把它表示成一般線性約束條件為

%+2X2<6+Myx

+6X2>1-My2

2xj+4X2<20+My30

y+%+%w2

%,%，%=?；?

三.考慮線性規(guī)劃問題

minZ=x,+3x2+4x3

3x}+2X2<13

x+3x<17

<23

2xj+x2+x3=13

XPX320,當(dāng)無約束

（1）把上面最小化的線性規(guī)劃問題化為求最大化的標(biāo)準(zhǔn)型；（5

分）

（2）寫出上面問題的對偶問題。（5分）

解：

max-Z=一%一3%2+3x；-4x3

3尤［+2芯-2X2+x4=13

<%；~x2+3與+M=17

2%+X；—+“3=13

%,芯,工；,%3，%4,冗520

四.用圖解法求解下面的線性規(guī)劃問題（8分）

maxZ=-2xt+x2

Xj4-x2>1

<%—3/2—1

Xj,x2>0

五.某廠準(zhǔn)備生產(chǎn)A、B、C三種產(chǎn)品，它們都消耗勞動

力和材料，如下表：

資、^耗ABC資源量

設(shè)備（臺時/件）63545

材料（kg/件）34530

利潤（元/件）314

建

立能獲得最大利潤的產(chǎn)品生產(chǎn)計劃的線性規(guī)劃模型，并

利用單純形法求解問題的最優(yōu)解。（20分）

解：模型為：

Variable->X1IX2IX3IDirectionIR.H.S.

Maximize314

C1635<=45

C2345<=30

LowerBound000

UpperBoundMMM

VariableTypeContinuousContinuousContinuous

標(biāo)準(zhǔn)化為：

maxZ=3芭++4匕

6%+3X2+5X3+x4=45

v3%+4X2+5X3+/=30

xpx2,x3>0

單純形為:

X1X2X3Slack_C1Slack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

Slack_C106.00003.00005.00001.0000045.00009.0000

Slack_C203.00004.00005.0：0_0_0___01.000030.00006.0000

3.00001.00004.0000000

X1X2X3SlackedSlack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

Slack_C103.0000-1.000001.0000-1.000015.00005.0000

X34.00000.60000.80001.000000.20006.000010.0000

0.6000-2.200000-0.800024.0000

X1X2X3Slack_C1Slack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

X13.00001.00000.33330.00000.3333-0.33335.0000

X34.00000.00001.00001.0000-0.20000.40003.0000

0-2.00000-0.2000-0.600027.0000

六、已經(jīng)線性規(guī)劃

maxZ=X]+2X2+3x3+4x4

x}+2X2+2X3+3X4<20

<2%+9+3%3+2X4<20

內(nèi),々，工320,%4無約束

的對偶問題的最優(yōu)解為y=(120.2),利用對偶性質(zhì)求原問題的最優(yōu)

解。(10分)

解；其對偶問題為:

Minimize20y1+20y2

X11y1+2y2>=1

X22y1+1y2>=2

X32y1+3y2>=3

X43y1+2y2>=4

Integer:

Binary:

Unrestricted:

yl>=0,<=M

y2〉=0,<=M

5分

由X，%#0得

x}+2X2+2X3+3X4=20

7

2%+%2+3&+2X4=20分

把丫值代入原問題，知第一、二個約束為嚴(yán)格不等式,

故有玉=々=0......................9分

解得X*=(0,0,4,4)T....................10分

七、有某運費最少的運輸問題，其運價表如表:

\銷

B?員A產(chǎn)量

地

A67588

A451089

&29737

銷量8655

求此運輸問題的最優(yōu)調(diào)運方案。（10分）

解:

BTCIJII\T?destinationdestination^destination"destination-SupplyDualP缶

6758

Source180

35

45108

Source29-2

63

2973

Source37-4

25

Demand8655

DualP①6757

ObjectiveValue=104(Minimization)

《運籌學(xué)》試題樣卷（一）

題號--二三四五七八九十總

分

得分

一、判斷題（共計10分，每小題1分，對的打錯的打X）

1.無孤立點的圖一定是連通圖。

2.對于線性規(guī)劃的原問題和其對偶問題，若其中一個有最優(yōu)解,

另一個也一定有最優(yōu)解。

3.如果一個線性規(guī)劃問題有可行解，那么它必有最優(yōu)解。

4.對偶問題的對偶問題一定是原問題。

5.用單純形法求解標(biāo)準(zhǔn)形式（求最小值）的線性規(guī)劃問題時，與力＞°

對應(yīng)的變量都可以被選作換入變量。

6.若線性規(guī)劃的原問題有無窮多個最優(yōu)解時，其對偶問題也有無窮

多個最優(yōu)解。

7.度為。的點稱為懸掛點。

8.表上作業(yè)法實質(zhì)上就是求解運輸問題的單純形法。

9.一個圖G是樹的充分必要條件是邊數(shù)最少的無孤立點的圖。

10.任何線性規(guī)劃問題都存在且有唯一的對偶問題。

①②③④⑤⑥⑦⑧⑨

二、建立下面問題的線性規(guī)劃模型（8分）

某農(nóng)場有100公頃土地及15000元資金可用于發(fā)展生產(chǎn)。農(nóng)場勞動力情

況為秋冬季3500人日；春夏季400（）人日。如勞動力本身用不了時可外

出打工，春秋季收入為25元/人日，秋冬季收入為20元/人日。該農(nóng)

場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時不需

要專門投資，而飼養(yǎng)每頭奶牛需投資800元，每只雞投資3元。養(yǎng)奶牛

時每頭需撥出1.5公頃土地種飼料，并占用人工秋冬季為100人日，春

夏季為50人日，年凈收入900元/每頭奶牛。養(yǎng)雞時不占用土地，需

人工為每只雞秋冬季0.6人日，春夏季為0.3人日，年凈收入2元/每

只雞。農(nóng)場現(xiàn)有雞舍允許最多養(yǎng)1500只雞，牛欄允許最多養(yǎng)200頭。三

種作物每年需要的人工及收入情況如下表所示：

大豆玉米麥子

秋冬季需人日數(shù)203510

507540

春夏季需人日數(shù)300041004600

年凈收入（元/公

頃）

試決定該農(nóng)場的經(jīng)營方案，使年凈收入為最大。

三、已知下表為求解某目標(biāo)函數(shù)為極大化線性規(guī)劃問題的最終單純形表,

表中M，%為松弛變量，問題的約束為形式（共8分）

x\￡為4與

為5/201/211/20

司5/21-1/20-1/61/3

5-0—40—4-2

（1）寫出原線性規(guī)劃問題；（4分）

（2）寫出原問題的對偶問題；（3分）

（3）直接由上表寫出對偶問題的最優(yōu)解。（1分）

四、用單純形法解下列線性規(guī)劃問題（16分）

maxZ=2%）—x2+x-i

s.t.3Xi+xz+X3<60

xi-x2+2x3410

xi+x2-x3<20

X1,X2,X3>0

五、求解下面運輸問題。（18分）

某公司從三個產(chǎn)地A】、A2、A3將物品運往四個銷地BI、B2、B3、B4,各

產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示:

問：應(yīng)如何調(diào)運，可使得總運輸費最小？

銷地Bi層B、也

產(chǎn)量

產(chǎn)地

A

1056725

A,827625

4934850

銷/p>

六、靈敏度分析（共8分）

線性規(guī)劃maxz=10xi+6必+4x3

S.t.X1+X2+X3<100

lOxi+4X2+5X3<600

2xi+2X2+6X3<300

X1,X2,X3>0

的最優(yōu)單純形表如下：

6X2200/305/615/30

1/6

10XI100/311/60-2/31/60

0X6100040-201

07

0-8/30-10/30

2/3

（1）C1在何范圍內(nèi)變化，最優(yōu)計劃不變？（4分）

（2）bi在什么范圍內(nèi)變化，最優(yōu)基不變？（4分）

七、試建立一個動態(tài)規(guī)劃模型。（共8分）

某工廠購進100臺機器，準(zhǔn)備生產(chǎn)pl,p2兩種產(chǎn)品。若生產(chǎn)產(chǎn)品pl,每

臺機器每年可收入45萬元，損壞率為65%；若生產(chǎn)產(chǎn)品p2,每臺機器

每年可收入35萬元，損壞率為35%；估計三年后將有新的機器出現(xiàn)，舊

的機器將全部淘汰。試問每年應(yīng)如何安排生產(chǎn)，使在三年內(nèi)收入最多？

八、求解對策問題。（共10分）

某種子商店希望訂購一批種子。據(jù)已往經(jīng)驗，種子的銷售量可能為500,

1000,1500或2000公斤。假定每公斤種子的訂購價為6元，銷售價為9元,

剩余種子的處理價為每公斤3元。

要求：

（1）建立損益矩陣；（3分）

（2）用悲觀法決定該商店應(yīng)訂購的種子數(shù)。（2分）

（3）建立后悔矩陣，并用后悔值法決定商店應(yīng)訂購的種子數(shù)。（5分）

九、求下列網(wǎng)絡(luò)計劃圖的各時間參數(shù)并找出關(guān)鍵問題和關(guān)鍵路徑。（8分）

十、用標(biāo)號法求V］到V6的最短路。（6分）

運籌學(xué)樣卷（一）答案

判斷題。共計10分，每小題1分

①②③④⑤⑥⑦⑧⑨10

XVXJVVXVXV

二、建線性規(guī)劃模型。共計8分（酌情扣分）

解：用司，切，％3分別表示大豆、玉米、麥子的種植公頃數(shù)；尤4,%分別表示

奶牛和雞的飼養(yǎng)數(shù)；尤6,%7分別表示秋冬季和春夏季的勞動力（人日）數(shù)，

則有

maxZ=3000為+4100x2+4600%+900x4+20x5+20x6+25x7

西+句+與+1.5彳4<100（土地限制）

400%4+3為4150（）0（資金限制）

20^+35x2+10x3+l（）0x4+0.6x5+x6<3500（勞動力限制）

50西+175x2+40X3+50X4+0.3x5+x7<4000（勞動力限制）

x4<200（牛欄限制）

4<15（X）（雞舍限制）

Xj>0（；=1,2,-,7）

三、對偶問題。共計8分

解：（1）原線性規(guī)劃問題：maxz=6x]-2x2+10x3

x2+2445

<3xt-x2+x3<10

、%i,%2?0?....4分

（2）原問題的對偶規(guī)劃問題為：

min卬=5凹+10y2

3y2之6

%-乃2-2

2y1+為21°

.凹，為20;……3分

(3)對偶規(guī)劃問題的最優(yōu)解為：y*=(4,2)\……1分

四、單純形表求解線性規(guī)劃。共計16分

解：引入松弛變量*4、X5,X6,標(biāo)準(zhǔn)化得,

maxZ=2xf-x2+x3

s.t.3xi+X2+X3+X4=60

X1-X2+2x3+Xs=10

X1+X2TX3+X6=0

X1,X2,X3,X4、"5、26,20....................3分

建初始單純形表，進行迭代運算：....................9分

2-11000

CBXbb，

XlXlX3X4X5X6e

0X46031110020

0X510[1]-1201010*

0X62011-100120

G/02*-11000

0X43004-51-307.5

2Xl101-12010

0X6100[2]-30-115*

62001*-30-20

0X4100011-1-2

2Xi15100.500.50.5

-1X1501-1.50-0.50.5

2500-1.50-1.5-0.5

由最優(yōu)單純形表可知，原線性規(guī)劃的最優(yōu)解為：（15,5,0）上..2分

最優(yōu)值為：z*=25o............2分

五、求解運輸問題。共計18分

解：

（1）最小元素法：（也可以用其他方法，酌情給分）

設(shè)利為由Ai運往Bj的運量（i=l,2,3；j=l,2,3,4）,

列表如下：

銷

地用B?%產(chǎn)量

產(chǎn)地

12525

220525

31530550

銷/p>

..................3分

所以，基本的初始可行解為：X14=25；X22=20：*24=5：

屋31=15；X33=30；*34=5

其余的Xij=0o..................3分

（2）求最優(yōu)調(diào)運方案：

1會求檢驗數(shù)，檢驗解的最優(yōu)性：011=2；012=2；013=3；

<j21=l；CT23=5；O32=-1.3分

2會求調(diào)整量進行調(diào)整：=5..................2分

銷與2%產(chǎn)量

地

產(chǎn)地

12525

2151025

31553050

銷/p>

...3分

3再次檢驗.................2分

4能夠?qū)懗稣_結(jié)論

解為：*14=25：X22=15：*24=10%31=15,*32=5*33=30

其余的Xij=0。....1分

最少運費為：535..............1分。

六、靈敏度分析。共計8分

(1)(4分)

-8/3-2/3]-10/3)

max<AC1<min

1/61/6J-2/3J

-4<Ac,<5,6=10-4<c1+Ac1<10+5=15

(2)(4分)

-200/3][-100/3-100]

<AZ?)<min

5/3J[-2/3

—40WA仿=10

七、建動態(tài)規(guī)劃模型。共計8分

解：(1)設(shè)階段變量A表示年度，因此，階段總數(shù)〃=3。

(2)狀態(tài)變量6表示第A年度初擁有的完好機床臺數(shù)，同時也是第k-1

年度末時的完好機床數(shù)量。

(3)決策變量“左,表示第左年度中分配于生產(chǎn)產(chǎn)品pl的機器臺數(shù)。于

是SA-NA便為該年度中分配于生產(chǎn)產(chǎn)品pl的機器臺數(shù).

(4)狀態(tài)轉(zhuǎn)移方程為

sk+l=0.35%+0.65(.-%)

(5)允許決策集合，在第k段曲X)={〃&|04%＜與}

(6)目標(biāo)函數(shù)。設(shè)或(sA,返)為第左年度的產(chǎn)量，則

gk(sk,uk)=4511k+35(sk-uk),

因此，目標(biāo)函數(shù)為

Rk=￡gk(Sk，Uk)

i=k

(7)條件最優(yōu)目標(biāo)函數(shù)遞推方程。

fk(sk)=max(uk(sk))

4叫

令必(W)表示由第k年的狀態(tài)sk出發(fā),采取最優(yōu)分配方案到第3年度

結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化

原理有以下遞推關(guān)系：

{[45%+35(s*-〃*)]+加J0.35%+0.65(s*-%)]}

(8).邊界條件為

/s+lG+l)=°

八、解決對策問題。共1()分

(1)益損矩陣如下表所示：……3分

Si

銷售S2S3S4

500100015002000

訂購

5001500150015001500

10000300030003000

1500150045004500

—1500

200003000