《運籌學(xué)》試題及答案大全(一)

《運籌學(xué)》試題及參考答案

一、填空題（每空2分，共10分）

1、在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負(fù)限制的解為可行解.

2、在線性規(guī)劃問題中，圖解法適合用于處理工為兩個的線性規(guī)劃問題。

3、求解不平衡的運輸問題的基本思想是設(shè)立虛供地或虛需求點，化為供求平衡

的標(biāo)準(zhǔn)形式

4、在圖論中，稱無圈的連通圖為樹。

5、運輸問題中求初始基本可行解的方法通常有最小費用法、西北角法兩

種方法。

二、（每小題5分，共10分）用圖解法求解下列線性規(guī)劃問題：

1)maxz=6xi+4x2

2.x,+x2<10

$+x,<8

x2<7

Xpx220

解：此題在“儂籌約復(fù)習(xí)參考廢科doc”中己有，不再重復(fù)。

2)minz=-3X1+2X2⑴

-2.Y1+4X2<22⑵

-^+4.^<10(3)

<2.v,-x2<7(4)

占一3%2?1(5)

.七戶22°⑹、⑺

解:

可行解域為abcda,最優(yōu)解為b點。

2X]+4X2=22

{$=0解出Xl=ll,X2=0

（\

，X*=xI=（11,0）T

kX2y

minz=—3x11+2X0=—33

三、（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要A、B、C三種資源，

每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲

備如下表所示：

ABC

甲94370

乙1610120

360200300

1）建立使得該廠能獲得最大利潤的生產(chǎn)計劃的線性規(guī)劃模型；（5分）

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

解：1）建立線性規(guī)劃數(shù)學(xué)模型：

設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為Xi、X2,則X】、X220,設(shè)z是產(chǎn)品售后的總利

潤，則

maxz=70X1+120X2

s.t.

’9巧4-4X2<,360

4巧+6X24200

3.Vj4-10x24300

x2^0

2）用單純形法求最優(yōu)解:

加入松弛變量X3,X4,X5,得到等效的標(biāo)準(zhǔn)模型：

maxz=70X1+120x2+0X3+OX4+OX5

s.t.

9巧4-4X2+X3=360

4巧+6x2+x4=200

3巧+10x2+%=300

A?/20,y=1,2,…,5

列表計算如下：

四、（10分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型:

minz=5xi+2x2+4x3

3再4-,x2+2X3>4

<6工]+3.馬+5.0210

石戶2戶320

解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：

maxz/=—5xi—2x2—4x3

s.t.

3再+x,+2X3-x4=4

<6.X]+3x,+5X3-x5=10

>0,j=l,2,...,5

增加人工變量X6、X7,得到：

-

maxZ=—5xi—2x2—4x3—MX6Mx7

s.t

3再+吃+2.r3-x4+x6=4

<6玉+3X2+5玉-x5+x-j=10

>0,j=l,2,...,7

大M法單純形表求解過程如下:

五、（15分）給定下列運輸問題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運費）

BiB2B3B4Si

Ai123410

A2876580

A391011915

dj8221218

1）用最小費用法求初始運輸方案，并寫出相應(yīng)的總運費；（5分）

2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）

解：用“表上作業(yè)法”求解。

1）先用最小費用法（最小元素法）求此問題的初始基本可行解:

費\銷

以

BiB2B3B4Si

1234

Ai10

82XX

8765

Ai20

XX218

910119

As30

X2010X

\60

dj8221218

6o\

???初始方案:

BiB3

A2

B：B4

Z=1X8+2X2+6X2+5X18+10X20+11X10=424

2)①用閉回路法，求檢驗數(shù):

費\銷

7

BiB：B3B4Si

12304-2

Ai10

82XX

8-47-265

A20

XX218

90101191

As30

X2010X

\60

dj8221218

60\

其余%

Vff34=l>0,<0

選0作為入基變量迭代調(diào)整。

②用表上閉回路法進行迭代調(diào)整:

費\銷

NBiB2B3B4Si

123-14-3

Ai10

82XX

8-37—165

A20

XX128

901011-19

A30

X20X10

\60

dj8221218

6C)\

調(diào)整后，從上表可看出，所有檢驗數(shù)％<0,已得最優(yōu)解。

???最優(yōu)方案為:

Bi

B：

最小運費Z=1X8+2><2+6X12+5X8+10X20+9X10=414

六、（8分）有甲、乙、丙、丁四個人，要分別指派他們完成A、B、C、D四項不同的工作，每

人做各項工作所消耗的時間如下表所示：

ABCD

甲21097

乙154148

丙13141611

T415139

問：應(yīng)該如何指派，才能使總的消耗時間為最少？

解：用“匈牙利法”求解。

效率矩陣表示為：

'210971'0875、列約簡

154148””間110104

_____N.|=>

131416111---------，2350標(biāo)號"

415139,1195,

4

r（o）825)[(()825]

it(0)54-41—-——

23(0)0,J——3—-40)-

5I

1。*V

1245J卜),124

6(0)3、

(0)54

30*(0)

1023>

"0010、

0100

至此已得最優(yōu)解:

0001

000)

使總消耗時間為最少的分配任務(wù)方案為

甲~*C,乙一B,丙一D,T-*A

此時總消耗時間W=9+4+l1+4=28

七、（6分）計算下圖所示的網(wǎng)絡(luò)從A點到F點的最短路線及其長度。

此題在“《運籌學(xué)參考綜合習(xí)題》（我站搜集信息自編）doc”中已有。

解：此為動態(tài)規(guī)劃之''最短路問題”，可用逆向追蹤“圖上標(biāo)號法”解決如下:

HHS

最佳策略為：A-*B2-*C】fD】fE?fF

此時的最短距離為5+4+1+2+2=14

《運籌學(xué)》試題及答案

19、簡述線性規(guī)劃模型主要參數(shù)（D11）

（1）、價值系數(shù)：目標(biāo)函數(shù)中決策變量前的系數(shù)為價值系數(shù)

（2）,技術(shù)系數(shù)：約束條件中決策變量前的系數(shù)

（3）、約束條件右邊常數(shù)項

15、簡述線性規(guī)劃解幾種可能的結(jié)果（情形）（ppt第二章39或89頁）

（1）.有唯一最優(yōu)解（單純形法中在求最大目標(biāo)函數(shù)的問題時，對尸某個基本可行解，所

有8jWO）

（2）.無可行解，即可行域為空域，不存在滿足約束條件的解，也就不存在最優(yōu)解了。

（3）.無界解，即可行域的范圍延伸到無窮遠(yuǎn)，目標(biāo)函數(shù)值可以無窮大或無窮小，一般來

說，這說明模型有錯，忽略了一些必要的約束條件

（4）.無窮多個最優(yōu)解，則線段上的所有點都代表了最優(yōu)解

（5）退化問題，基變最有時存在兩個以上相同的最小比值，這樣在下一次迭代中就有一個

或幾個基變最等于零，用圖解法無退化解

1、簡述單純形法的基本思路（p70）

從可行域中某一個頂點開始，判斷此頂點是否是最優(yōu)解，如不是，則再找另一個使得其目標(biāo)

函數(shù)值更優(yōu)的頂點，稱之為迭代，再判斷此點是否是最優(yōu)解。直到找到一個頂點為其最優(yōu)解，

就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。

17、簡述線性規(guī)劃中添加人I：變量的前提（p85）

在系數(shù)矩陣中直接找不到初始可行解，進而通過添加人工變量的方法來構(gòu)造初始可行基，

得出初始基本可行解

10、簡述線性規(guī)劃對儡問題的居外性質(zhì)（D122）

（1）對稱性（2）弱對偶性（3）強對偶性（4）最優(yōu)性（5）互補松弛型

原函數(shù)與對偶問題的關(guān)系

1）求目標(biāo)函數(shù)最大值的線性規(guī)劃問題中有n個變量m個約束條件，它的約束條件都是小于

等于不等式。而其對偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問題，有m個變量n個約束條件，

其約束條件都為大于等于不等式。

2）原問題的目標(biāo)函數(shù)中的價值系數(shù)為對偶問題中的約束條件的右邊常數(shù)項，并且原問題的目

標(biāo)函數(shù)中的第i個價值系數(shù)就等于對偶問題中的第i個約束條件的右邊常數(shù)項。

3）原問題的約束條件的右邊常數(shù)項為對偶問題的目標(biāo)函數(shù)中價值系數(shù)。并且原問題的第i個約

束條件的右邊常數(shù)項就等于零對偶問題的目標(biāo)函數(shù)中的第i個變最的系數(shù)。

4）對偶問題的約束條件的系數(shù)矩陣A是原問題約束矩陣的轉(zhuǎn)置。

5、運輸問題是特殊的線性規(guī)劃問題，但為什么不用單純形法求解

因為這類線性規(guī)劃問題在結(jié)構(gòu)上存在著特殊性,表上作業(yè)法根據(jù)運輸問題的特點來設(shè)計的

特殊的單純形法，可以更加形象直觀簡單的解決運輸問題。

9、簡述表上作業(yè)法的基本步驟

（1）用最小元素法找出初始基可行解，也就是初始調(diào)運方案。對于有m個產(chǎn)地n個銷地的

產(chǎn)銷平衡問題，則有m個關(guān)于產(chǎn)量的約束方程和n個關(guān)于銷量的約束方程。由于產(chǎn)銷平衡，其

模型最多只有m+n-1個獨立的約束方程，即運輸問題有m+n-1個基變量。在mXn的產(chǎn)銷平衡表

上給出m+n-1個數(shù)字格，其相對應(yīng)的調(diào)運量的值即為基變量的值。

（2）求各非基變量的檢驗數(shù)。

（3）用閉回路法來判別問題是否達到最優(yōu)解。如己是最優(yōu)解則停止計免，否則繼續(xù)下一步。

（4）用閉回路法進行基變換，確定入基變量和出基變量，找出新的基本可行解。在表上用

閉回路法調(diào)整。

11、簡述指派問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模生（ppt或書上pl79）

設(shè)A個人被分配去做〃件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。己

知第i個人去做第j件工作的效率（時間或費用）為GJ（f=L2…戶L2…〃）并假設(shè)GJ20。

問應(yīng)如何分配才能使總效率（時間或費用）最高？

12、簡述分枝定界法的基木步驟

分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出整

數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝）,

再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的

最優(yōu)解。

基本思路：

1、先求出線性規(guī)劃的解

2、確定整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值z*初始上界和下界工

3、將一個線性規(guī)劃問題分為兩枝，并求解

4、修改最優(yōu)目標(biāo)函數(shù)上、下界

5、比較與剪枝：各分枝的目標(biāo)函數(shù)值中，若有小于幺者，則剪掉此枝，表明此子問題已

經(jīng)探清，不必再分枝了；否則繼續(xù)分枝。

6、如此反復(fù)進行，直到得到Z=Z為止，即得最優(yōu)解丫-

6、簡述目標(biāo)規(guī)劃的目標(biāo)函數(shù)主要類型及其數(shù)學(xué)表達式。

目標(biāo)規(guī)劃的目標(biāo)函數(shù)只能取極小形式，即minz=f（d+,d-）,共有如下三種形式：（1）,要求

恰好等于目標(biāo)值，即希望決策值超過和不足目標(biāo)值的部分都盡可能小，因此由函數(shù)

minz=f（d++d-）：（2）,要求不超過目標(biāo)值，允許達不到目標(biāo)值，即希望決策值不超過目標(biāo)值，

也希望d+越小越好，因此有minz=f（d+）;（3）要求不低于目標(biāo)值，允許超過目標(biāo)值，即希望決

策值不低于目標(biāo)值，也希望d-越小越好，因此有minz=f（d-）.

2、簡述運籌學(xué)中背包問題的一般提法（p225）

對于N種具有不同重量和不同價值的物品，在攜帶物品總重量限制的情況下，決定這N種

物品中每一種物品多少數(shù)量裝入背包內(nèi)，使得裝入背包物品的總價值最大。

4、建立動態(tài)規(guī)劃模型時，應(yīng)定義狀態(tài)變量，請說明狀態(tài)變量的特點

第一,可知性,即各階段的狀態(tài)變量的取值能直接或間接的確定：第二能夠確切的描述過程

的演變且滿足無后效性.

7、簡述動態(tài)規(guī)劃數(shù)學(xué)模型要點（ppt第十章18論述題增加階段和階段變量）

（1）分析題意，識別問題的多階段特性，按時間或空間的先后順序適當(dāng)劃分為滿足遞推關(guān)

系的若干階段，對分時序的靜態(tài)問題要認(rèn)為賦予“時段”概念;

（2）正確選擇狀態(tài)變量，狀態(tài)變量應(yīng)具備兩個特征：第一，可知性，即各階段的狀態(tài)變量

的取值能直接或間接的確定：第二，能夠確切的描述過程的演變且滿足無后效性：

（3）根據(jù)狀態(tài)變量和決策變量的含義，正確寫出狀態(tài)轉(zhuǎn)移方程；

（4）根據(jù)題意明確過程指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)以及第k階段指標(biāo)函數(shù)的含義，并正確列

出基本方程。

3、簡述著字的哥尼斯堡七橋難題及答案

河上有7座橋，將河中的兩個島和河岸連結(jié)，如圖1所示。一個散步者能否一次走遍7座

橋，而且每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。

歐拉證明了這樣的走法不存在。歐拉是這樣解決問題的：既然陸地是橋梁的連接地點，不

妨把圖中被河隔開的陸地看成A、B、C、D4個點，7座橋表示成7條連接這4個點的線，如圖2

所示。

于是“七橋問題”就等價于圖3中所畫圖形的一筆畫問題了。每個點如果有進去的邊就必

須有出來的邊，從而每個點連接的邊數(shù)必須有偶數(shù)個才能完成一筆畫。圖3的每個點都連接著

奇數(shù)條邊，因此不可能一筆畫出，這就說明不存在一次走遍7座橋，而每座橋只許通過一次的

走法。

8、簡述樹定義及性質(zhì)

樹:連通且不含圈的無向圖稱為樹。

性質(zhì)：（1）裙無圈，m=n-l.（2）相連通，m=n-l.（3）樹無圈，但每加一條新邊，則可得到

惟一一個圈.（4）相連通，但任舍一條邊，圖就不連通.（5）秘中任意兩點之間有惟一一條鏈相

連.

16、簡述求最小生成樹的方法

（1）避圈法：將圖中的邊按權(quán)由小到大排序：按排序由小到大選定n—l條邊為止，選擇

時每選一條邊應(yīng)避免和已選的邊構(gòu)成圈，且所選邊是未選邊中的最小權(quán)邊。

（2）破圈法：在給定的賦權(quán)的連通圖上任選一個圈：在所找的圈中去掉一個權(quán)數(shù)最大的

邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）：如果所余下的圖己

不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。

18、簡述決策按環(huán)境分類（分為哪幾種）（D389）

確定型決策：在決策環(huán)境完全確定的條件下,進行

不確定型決策：在決策環(huán)境不確定的條件下進行，決策者對個自然狀態(tài)發(fā)生的概率一無所

知

風(fēng)險型決策問題：在決策環(huán)境不確定的條件下進行，決策者對各自然狀態(tài)發(fā)生的概率可以

預(yù)先估計或計算出來［非程序化決策：］

13、簡述不確定型決策的決策方法（決策準(zhǔn)則）5389）

（1）最大最小準(zhǔn)則（悲觀準(zhǔn)則），決策者從最不利的角度去考慮問題：

（2）最大最大準(zhǔn)則（樂觀準(zhǔn)則），決策者從最有利的角度去考慮問題：

（3）等可能性準(zhǔn)則，決策者把各自然狀態(tài)發(fā)生的機會看成是等可能的；

（4）樂觀系數(shù)準(zhǔn)則（折衷準(zhǔn)則），決策者取樂觀準(zhǔn)則和悲觀準(zhǔn)則的折衷：

（5）后悔值準(zhǔn)則（沙萬奇準(zhǔn)則），決策者從后悔的角度去考慮問題

14、簡述層次分析法的基本步驟（ppt第16章31）

1.明確問題，提出總目標(biāo)2.繪制層次結(jié)構(gòu)圖3.標(biāo)度及兩兩比較矩陣4.求各因素權(quán)重的過

程5.兩兩比較矩陣一致性檢驗6.利用權(quán)數(shù)或特征向量求出各方案的優(yōu)劣次序.EVPI=EV.PI

-EV^PI

1、結(jié)合我國企業(yè)發(fā)展中面臨的一實際問題，簡要論述運籌學(xué)在我國企業(yè)管理優(yōu)化中的重要應(yīng)用

及作用。

答：運籌學(xué)在企業(yè)管理優(yōu)化領(lǐng)域的主要應(yīng)用有：

①生產(chǎn)計劃。如一家重型制造廠用線性規(guī)劃及整數(shù)規(guī)劃安排生產(chǎn)計劃，節(jié)約了10%的生產(chǎn)費

用。

②市場營銷。在廣告預(yù)算和廣告媒介的選擇、競爭性定價、新產(chǎn)品開發(fā)、銷售計劃、市場

競爭策略的制定等方面，運籌學(xué)也大展身手。美國杜邦公司在五十年代起就非常重視將運籌學(xué)

用于研究如何做好廣告工作、產(chǎn)品定價，通用公司也運用運籌學(xué)方法進行市場模擬研究。

③庫存管理。運籌學(xué)中的存貯論可以應(yīng)用于物資庫存量的管理，以確定倉庫的合理容量，

以及確定適當(dāng)?shù)膸齑娣绞胶蛶齑媪俊?/p>

④運輸問題。運用運籌學(xué)，可以確定最小成本的運輸路線、物資的調(diào)撥、運輸I：具的調(diào)度，

以及新建廠址的選擇等等。

⑤人事管理。對人員的需求和招聘情況的預(yù)測；人力資源的開發(fā)，如對人才的教育和培訓(xùn)I，

人才評價體系、薪酬體系的確定等，都可以運用運籌學(xué)方法。

⑥財務(wù)會計。運籌學(xué)解決企業(yè)如何最有效的利用資金資源的問題。其涉及到投資決策分析、

成本核算分析、證券管理等。在投資決策分析中，企業(yè)如何利用剩余資金，如何投資往往有多

種方案。而運籌學(xué)的作用就是要要對這些不同的投資方案進行決策，以確定最優(yōu)的方案，使得

企業(yè)的收益最大。通常是利用線性規(guī)劃模型、決策論來進行判斷。

滿足乘客需求前提下.以最低成本進行訂票及安排600萬

聯(lián)合航空公司1-2/1986

機場工作班次

控制成品庫存（制定最優(yōu)再訂購點和訂購量，確保

標(biāo)準(zhǔn)品牌公司12/1981380萬

安全庫存）

進行上千個國內(nèi)航線的飛機優(yōu)化配置來,大化制

Delta航空公司1-2/19941億

潤

京新設(shè)計北美生產(chǎn)和分箱系統(tǒng)以降低成本并加快

寶清公司1-2/19972億

了市場進入速度

2、根據(jù)您所學(xué)的《運籌學(xué)》及其它學(xué)科知識，談?wù)勀鷮Α斑\籌帷幄，決勝r里”的理解：

語出〈史記高祖本紀(jì)》，意思是說，張良坐在軍帳中運用計謀，就能決定千里之外戰(zhàn)斗的勝

利，這說明張良心計多，善用腦，善用兵，后來人們就用“運籌帷線”表示善于策劃用兵。

學(xué)習(xí)中，我們應(yīng)當(dāng)努力學(xué)習(xí)運籌學(xué)的理論知識，并將理論知識付諸實踐，在學(xué)習(xí)其他學(xué)科

時，運用運籌學(xué)的知識，比如在寫畢業(yè)論文時，運用運籌學(xué)的知識，豐富論文內(nèi)容，為論文增

加支撐理論。

生活中，我們面對任何問題都要仔細(xì)思考，運用運籌學(xué)的知識，更好地解決問題，而現(xiàn)在

網(wǎng)絡(luò)及通訊工具的不斷發(fā)展，讓我們遠(yuǎn)在廠里之外也可以解決問題，如：越來越多的跨國公司，

不僅僅是局限于面對面的交談，很多網(wǎng)絡(luò)會議或電話會議，讓解決問題更加方便迅速。

在企業(yè)管理中，生產(chǎn)計劃、市場營銷、庫存管理、人事資源、運輸問題等。

3、請論述如何把你所學(xué)的運籌學(xué)的知識應(yīng)用到今后的管理實踐中去：

答：（1）對運籌學(xué)的知識體系了若指掌。（2）處理管理實踐的問題時，有意識的使用運籌

學(xué)的知識體系和方法來解決。（3）需要有很強的歸納總結(jié)能力，把在實踐中遇到的問題，轉(zhuǎn)化

為運籌學(xué)書上的問題來解決，如：背包問題、七橋問題。以上三者缺一不可，遇到問題，首先

想到解決該問題需要哪些資源，從哪里可以獲得這些資源：其次考慮再獲得資源后，如何使這

些資源得到最合理的利用，使其產(chǎn)生最大效益。另外，強化管理，不斷進行管理刨新已成為企

業(yè)在競爭中制勝的根本保證。作為企業(yè)的管理者，把握并運用好運籌學(xué)的理念定會取得“運籌

帷幄之中，決勝千里之外”之功效。

,1、請簡要列舉（至少3）我國古代樸素的運籌學(xué)思想,并論述其間的運籌學(xué)原理。（I個）

答：（1）孫子兵法與運籌學(xué)思想?！秾O子兵法》在表達軍事思想的同時，也蘊藏著豐富的運

籌學(xué)思想-----軍事運籌學(xué)。孫武在《孫子兵法》中靈活運用整體性原則研究軍事問題，采用

定量分析方法謀劃戰(zhàn)爭，運用優(yōu)化原則進行科學(xué)決策。

（2）田忌賽馬。戰(zhàn)國時期的“田忌賽馬”是運籌思想的一次完美應(yīng)用。整個賽馬過程中,

孫臏巧妙地運用了一種科學(xué)合理的方法——博弈論。博弈論是運籌學(xué)的一個分支，是指二人在

平等的對局中各自利用對方的策略變換自己的對抗策略，達到取勝的目的。通過博弈論的思想，

孫臏指出用本方的下馬對齊王的上馬，用本方的上馬對齊王的中馬，用本方的中馬對齊王的下

馬。最終以一負(fù)兩勝取勝。孫臏成功地將本方劣勢轉(zhuǎn)為優(yōu)勢，贏得了比賽。

（3）南魏救趙。魏國攻打趙國，趙國求救于齊。孫臏指出應(yīng)趁魏國國內(nèi)兵力空虛之際，發(fā)

兵直取魏都大梁，迫使偽軍棄趙回救。最終這一戰(zhàn)略取得了勝利。其中的戰(zhàn)略思想，妙在善尸

調(diào)動第二年。調(diào)動敵人的要訣，在于“攻其所必救:這充分體現(xiàn)了如何策劃兵力，選擇最佳時

間、地點，趨利避害，集中優(yōu)勢兵力以弱克強的運籌思想。

（4）沈括運軍糧：沈括曾經(jīng)從行軍中各類人員可以背負(fù)糧食的基本數(shù)據(jù)出發(fā)，分析計

算了后勤人員與作戰(zhàn)兵士在不同行軍天數(shù)中的不同比例關(guān)系，同時也分析計算了用

各種牲畜運糧與人力運糧之間的利弊，最后做出了從敵國就地征糧，保障前方供

應(yīng)的重要決策，從而減少了后勤人員的比例，增強了前方作戰(zhàn)的兵力。這種軍事后勤

問題的分析計算是具有現(xiàn)代意義的運籌思想的范例。

（5）晉國公重建皇城的施工方案，體現(xiàn)了運籌學(xué)的樸素斯思想。要使重建工程的各個

工序，在時間、空間上彼此協(xié)調(diào)，環(huán)環(huán)相扣，就需要運用行列式的相關(guān)知識，進行精確計

算。

1.影子價格:當(dāng)約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標(biāo)函數(shù)值增加的數(shù)量。（影增）

2.對偶價格:當(dāng)約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標(biāo)函數(shù)值改進的數(shù)量。

3.靈敏度分析:對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度分析。

4.0-1規(guī)劃:所有決策變量只能取0或1兩個整數(shù)的整數(shù)線性規(guī)劃。

5.分支定界法:分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，

則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱

為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整

數(shù)規(guī)劃的最優(yōu)解。

6.生成子圖:給定一個無向圖6=（V.E）,保留G的所有點，而刪掉部分G的邊或者說保留一部分

G的邊，所獲得圖G,稱之為G的生成子圖。

7.松弛問題:不考慮整數(shù)約束條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題。

8.歐拉回路:圖G的一個回路，若它恰通過G中每條邊一次,則稱該回路為歐拉回路。

9.樣本信息:研究中實際觀測或調(diào)查的一部分個體的信息。

10.最小生成樹:在一個賦權(quán)的連通的無向圖G找出一個生成樹，并使得這個生成樹的所有邊的

權(quán)數(shù)之和最小。

11.目標(biāo)約束:在引入了目標(biāo)值和正、負(fù)偏差變量后，可以將原目標(biāo)函數(shù)加上負(fù)偏差變量，減去

正偏差變量，并且等于目標(biāo)值，這樣形成一個新的函數(shù)方程，把它作為一個新的約束條件，加

入到原問題中去，稱這種新的約束條件為目標(biāo)約束。

12.偏差變■:指目標(biāo)規(guī)劃中實現(xiàn)值與目標(biāo)值之間的差異。其中實現(xiàn)值超過目標(biāo)值的部分記為d+.

實現(xiàn)值未達到目標(biāo)值的部分記為d-od+,d-這樣的變量稱為偏差變量。

13.狀態(tài)變■:描述各階段狀態(tài)的變量稱為狀態(tài)變量。

14.基本可行解：滿足非負(fù)條件的基本解叫基本可行解。

15.后驗概率：利用樣本情報對先驗概率修正后得到的概率。

16.定性分析：借助決策者的知識,經(jīng)驗,分析和判斷能力等進行決策的方法。

17.定?分析：量化決策問題并建立數(shù)學(xué)模型進行決策的方法。（基于事物的數(shù)據(jù)和數(shù)量關(guān)系,建

模'計算找出解決方案）

18.狀態(tài)與狀態(tài)變置:狀態(tài)是指每個階段開始所處的自然狀況或客觀條件，而描述過程狀態(tài)的變

量就是狀態(tài)變量。能夠完全描述動態(tài)系統(tǒng)時域行為的所含變量個數(shù)最少的變量組稱為系統(tǒng)的狀

態(tài)變量。

《運籌學(xué)》試題及答案（A卷）

一、單項選擇題（從下列各題四個備選答案中選出個正確答案，答案選錯或未選者,該題不得分.每小題1分，

共10分）

1.線性規(guī)劃具有唯一最優(yōu)解是指

A.最優(yōu)表中存在常數(shù)項為零

B.最優(yōu)表中非基變量檢驗數(shù)全部非零

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

D.可行解集合有界

2.設(shè)線性規(guī)劃的約束條件為

=

Kj+五？+Xj3

2々+2X2+&二4

々，…，人＞0

則基本可行解為

A.(0,0,4,3)B.(3.4,0,0)

C.(2.0.1,0)D.(3.0,4,0)

的之°,則

3minZ=3^+4X2,XJ+>4,2XJ+2,XP

A.無可行解B.有唯一最優(yōu)解medn

C.有多重最優(yōu)解D.有無界解

4,互為對偶的兩個線性規(guī)劃m"Z=及min“=丫瓦%

對任意可行解X和

K存在關(guān)系

A.Z>WB.Z=W

C.Z>WD.Z<i

5.有6個產(chǎn)地4個銷地的平衡運輸問題模型具有特征

A.有10個變量24個約束

B,有21個變量10個約束

C.有24個變量9個約束

D.有9個基變量10個非基變量

6.下例錯誤的說法是

A.標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最大值

B.標(biāo)準(zhǔn)型的目標(biāo)函數(shù)是求最小值

C.標(biāo)準(zhǔn)型的常數(shù)項非正

D.標(biāo)準(zhǔn)型的變量一定要非負(fù)

7.m+n—1個變量構(gòu)成一組基變量的充要條件是

A.m+n-l個變量恰好構(gòu)成一個閉回路

B.m-n—l個變量不包含任何閉回路

C.m-n-1個變量中部分變量構(gòu)成一個閉回路

D.m+n-l個變量對應(yīng)的系數(shù)列向量線性相關(guān)

8.互為對偶的兩個線性規(guī)劃問題的解存在關(guān)系

A.原問題無可行解，對偶問題也無可行解

B.時偶問題行可行解，原問題可能無可行解

C.若最優(yōu)解存在，則最優(yōu)解相同

D.一個問題無可行解，則另一個問題具有無界解

9.有m個產(chǎn)地n個銷地的平衡運輸問題模型具有特征

A.有mn個變量m+n個約束-m+n-1個基變量

B.有m+n個變量mn個約束

C.有mn個變量m+n-1約束

D.有m+n—1個基變量，mn—m—n—1個非基變量

10.要求不超過第?目標(biāo)值、恰好完成第二L1標(biāo)值，目標(biāo)函數(shù)是

_minZ=PM：+p?（d[+d；）

B,1而2=夕3：+。式嗎一球）

cminZ=pxd~+p2（d；-dt）

DminZ=pM++d；）

二、判斷題（你認(rèn)為卜列命題是否正確，對正確的打“力；錯誤的打“X”。每小題1分，共15分）

11.若線性規(guī)劃無最優(yōu)解則其可行域無界X基本解為空x

12.凡基本解一定是可行解X同19x

13.線性規(guī)劃的最優(yōu)解一定是基本最優(yōu)解X可能為負(fù)x

14.可行解集非空時，則在極點上至少有一點達到最優(yōu)值X可能無窮x

15.互為對偶問題,或者同時都有最優(yōu)解，或者同時都無最優(yōu)解J

16.運輸問題效率表中某一行元素分別乘以一個常數(shù),則最優(yōu)解不變X

17.要求不超過目標(biāo)值的目標(biāo)函數(shù)是mmZ=d*

18.求最小值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界

19.基本解對應(yīng)的基是可行基XII包時為星本可行解,對應(yīng)的居叫叫】拈

20.對偈問題有可行解,則原問題也有可行解X

21.原問題具有無界解,則對偶問題不可行

22.m+n-l個變量構(gòu)成基變量組的充要條件是它們不包含閉回路

23.目標(biāo)約束含有偏差變量

24.整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然去取整得到X

25.匈牙利法是對指派問題求最小值的一種求解方法

三、填空題（每小題1分，共10分）

26.有5個產(chǎn)地5個銷地的平衡運輸問題，則它的基變量有（9）個

27.已知最優(yōu)基

「12一

B=

L37'C,=（3,6）,則對偶問題的最優(yōu)解是（）

28.已知線性規(guī)劃求極小值，用對偶單純形法求解時，初始表中應(yīng)滿足條件（對偶問題可行）

29.非基變量的系數(shù)c,變化后，最優(yōu)表中（）發(fā)生變化

30.設(shè)運輸問題求最大值，則當(dāng)所有檢驗數(shù)（）時得到最優(yōu)解。

31.線性規(guī)劃maxZ=一丸+入2,246,4IL+x2三8"1，七之0的最優(yōu)解是（0,6）,它的

第1、2個約束中松馳變量（￡,$）=（）

32.在資源優(yōu)化的線性規(guī)劃問題中，某資源有剩余，則該資源影子價格等于（）

33.將目標(biāo)函數(shù)2=與一$勺轉(zhuǎn)化為求極小值是（）

34.來源行*+6X3~6V4=1的高莫雷方程是（）

35.運輸問題的檢驗數(shù)入〃的經(jīng)濟含義是（）

四、求解下列各題（共50分）

36.已知線性規(guī)劃（15分）

maxZ=3Xj+4x2+5x3

Xj+20-x3<10

<2x,一$+3A3<5

弓NO,y=1,2,3

（1）求原問題和對偶問題的最優(yōu)解：（2）求最優(yōu)解不變時0的變化范圍

37.求下列指派問題（min）的最優(yōu)解（10分）

5685

12152018

91097

9656

38.求解下列目標(biāo)規(guī)劃（15分）

niinz=W+d：)+gdj+舄dj

Xj+x2+d；-d：=40

$+x2+dJ-dj=60

<xx+dy~=30

x2+d；-d；=20

演，W，d「，d：>004)

39.求解下列運輸問題（min）（10分）

85440

C=14181390

9210110

8010060

五、應(yīng)用題（15分）

40.某公司要將一批貨從三個產(chǎn)地運到四個銷地,有關(guān)數(shù)據(jù)如下表所示。

供

銷地B：B：B,B,

應(yīng)

產(chǎn)地量

56

A,7379

0

40

A;26511

0

75

As6425

0

32244838

需求量

0000

現(xiàn)要求制定調(diào)運計劃，且依次滿足：

（1）B,的供應(yīng)量不低于需要量：

（2）其余銷地的供應(yīng)量不低于85%：

（3）&給B,的供應(yīng)量不低于200：

（4）A：盡可能少給瓦：

（5）銷地昆、B,的供應(yīng)量盡可能保持平衡。

（6）使總運費最小。

試建立該問題的目標(biāo)規(guī)劃數(shù)學(xué)模型.

運籌學(xué)（B卷）

一、單項選擇題（從下列各題四個備選答案中選出一個正確答案，答案選錯或未選者，該題不得分?每小題1分,

共10分）

1.線性規(guī)劃最優(yōu)解不唯一是指（）

A.可行解集合無界B.存在某個檢驗數(shù)心〉0且％^中=L…普）

C.可行解集合是空集D.最優(yōu)表中存在是變次的檢驗數(shù)卜孝

.maxZ=4.+孫，4毛+3勺匕24町之1°，如々2。，則（）

A.無可行解B.有唯一最優(yōu)解C.有無界解D.有多重解

3.原問題有5個變量3個約束，其對偶問題（）

A.仃3個女用3個約束B.有5個變量3個約束

C.有5個變量5個約束D.有3個變量3個約束

4.有3個產(chǎn)地4個銷地的平衡運輸問題模型具有特征（）

A.有7個變量B.有12個約束

C.有6約束D.仃6個暴變顯

5.線性規(guī)劃可行域的頂點一定是（）

A.居本可行解B.非基本解C.非可行解D.最優(yōu)解

6.X是線性規(guī)劃的基本可行解則有（）

A.X中的基變量非零，非基變量為零B.X?不一定滿足約束條件

C.X中的基變量非負(fù)，非堪變質(zhì)為零D.1是最優(yōu)解

7.互為對偶的兩個問題存在關(guān)系（）

A.原問題無可行解，對偶問題也無可行解

B.對偶問題有可行解，原問題也有可行解

C.原問題有最優(yōu)解解，對偶問題可能沒有最優(yōu)解

D.原問題無界解.對偶問題無可行解

8.線性規(guī)劃的約束條件為

=

2尤］+不3+無35

，2演+2勺+々=6

j卜…NO

則基本解為()

A.(0,2,3,2)B.(3,0,1,0)

C.(0,0,6,5)D.(2,0,1,2)

9.要求不低于目標(biāo)值.其口標(biāo)函數(shù)是()

maxZ=d~mmZ-d~

C.maxZ=&'D.tninZ=d'

10.H是關(guān)于可行流f的一條增廣鏈，則在H上有（）

A,對任意度有4'%B,對任意,力€“，有玲，%

C.對任意也力w-茍X%D..對任意—，，前

二、判斷題（你認(rèn)為下列命題是否正確.對正確的打“寸'；錯誤的打“x”.每小題1分,共15分）

11.線性規(guī)劃的最優(yōu)解是基本解x

12.可行解是基本解“

13.運輸問題不一定存在最優(yōu)解乂

14.一對正負(fù)偏差變量至少一個等于零X

15.人工變量出基后還可能再進基x

16.將指派問題效率表中的每一元素同時減去一個數(shù)后最優(yōu)解不變

17.求極大值的目標(biāo)值是各分校的上界

18.若原問題具有m個約束，則它的對偶問題具有m個變量

19.原問題求最大值，第i個約束是2“約束，則第2.個對偶變量匕4

20.要求不低于目標(biāo)值的目標(biāo)函數(shù)是加11Z=<T

21.原問題無最優(yōu)解，則對偶問題無可行解*

22.正偏差變量大于等于零，負(fù)偏差變量小于等于零x

23.要求不超過目標(biāo)值的目標(biāo)函數(shù)是minZ=d+

24.可行流的流量等于發(fā)點流出的合流

25.割集中弧的容量之和稱為割量.

三、填空題（每小題1分，共10分）

26.將目標(biāo)函數(shù)皿12=3-5.丫2+8/轉(zhuǎn)化為求極大值是（）

110

A=

27.在約束為⑷瓦°的線性規(guī)劃中，設(shè)L20”,它的全部基是（）

28.運輸問題中m+n-l個變量構(gòu)成基變量的充要條件是（）

29.對偶變量的最優(yōu)解就是（）價格

30.來源行“2一亍均二1"的高莫雷方程是（）

31.約束條件的常數(shù)項瓦變化后，最優(yōu)表中（）發(fā)生變化

32.運輸問題的檢驗數(shù)入〃與對偶變量u,、丫,之間存在關(guān)系（）

33.線性規(guī)劃口】初2=_玉+/,2?+.馬<6,4A1+X248,.片/220的最優(yōu)解是（O,6）,它的

對偶問題的最優(yōu)解是（）

34.已知線性規(guī)劃求極大值，用對偶單純形法求解時，初始表中應(yīng)滿足條件（）

35.Dijkstra算法中的點標(biāo)號b（力的含義是（）

四、解答下列各題（共50分）

36.用對偶單純形法求解下列線性規(guī)劃（15分）

minZ=3X[+4必+5為

Xj+2勺+3X3>8

<2/+2與+x3>10

,勺,稱修>0

37.求解下列目標(biāo)規(guī)劃（15分）

minZ=+d?j）+p2（d?j+d；）

為+為+d1一d：=1

2々+2X2+d]-d；=4

2入]一電+d：-d；=2

㈤知行,d：20,”1,2,3

38.求解F列指派問題（min）（10分）

39237