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

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

一、判斷題（在下列各題中，你認(rèn)為題中描述的內(nèi)容為正確者，在題尾括號

內(nèi)寫“J”，錯誤者寫“義”。）

1.圖解法提供了求解線性規(guī)劃問題的通用方法。（）

2.用單純形法求解一般線性規(guī)劃時，當(dāng)目標(biāo)函數(shù)求最小值時，若所有的檢驗數(shù)C-Z.

》0,則問題達(dá)到最優(yōu)。（）

3.在單純形表中，基變量對應(yīng)的系數(shù)矩陣往往為單位矩陣。（）

4.滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。（）

5.在線性規(guī)劃問題的求解過程中，基變量和非基變量的個數(shù)是固定的。（）

6.對偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。（）

7.原問題與對偶問題是一一對應(yīng)的。（）

8.運輸問題的可行解中基變量的個數(shù)一定遵循m+n-l的規(guī)則。（）

9.指派問題的解中基變量的個數(shù)為m+n。（）

10.網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點至終點的一條權(quán)和最小的路線。（）

11.網(wǎng)絡(luò)最大流量是網(wǎng)絡(luò)起點至終點的一條增流鏈上的最大流量。（）

12.工程計劃網(wǎng)絡(luò)中的關(guān)鍵路線上事項的最早時間和最遲時間往往不相等。（）

13.在確定性存貯模型中不許缺貨的條件下，當(dāng)費用項目相同時，生產(chǎn)模型的間隔

時間比訂購模型的間隔時間長。（）

14.單目標(biāo)決策時，用不同方法確定的最佳方案往往是一致的。（）

15.動態(tài)規(guī)劃中運用圖解法的順推方法和網(wǎng)絡(luò)最短路徑的標(biāo)號法上是一致的。

（）

二、簡述題

1.用圖解法說明線性規(guī)劃問題單純形法的解題思想。

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

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

三、填空題

1.圖的組成要素；“

2.求最小樹的方法有、。

3.線性規(guī)劃解的情形有、、、

4.求解指派問題的方法是o

5.按決策環(huán)境分類，將決策問題分為、、

6.樹連通，但不存在。

四、下列表是線性規(guī)劃單純形表（求ZmaJ，請根據(jù)單純形法原理和算法。

1.計算該規(guī)劃的檢驗數(shù)

C—A32000

J

CiXBbxxxX

lX,34、

1

3X,310-10

12

2X340111/20

z.33.52-20

C.—Z.

JJ

2.計算對偶問題的目標(biāo)函數(shù)值

3.確定上表中輸入，輸出變量

五、已知一個線性規(guī)劃原問題如下,請寫出對應(yīng)的對偶模型

S=6x+x

max12

x+x<7

12

2x+3犬>16

12

x,x>0

112

六、下圖為動態(tài)規(guī)劃的一個圖示模型，邊上的數(shù)字為兩點間的距離，請用逆推

法求出S至F點的最短路徑及最短路長。

七、自己選用適當(dāng)?shù)姆椒?，對下圖求最?。ㄉ桑?。

八、用標(biāo)號法求下列網(wǎng)絡(luò)Vi-V7的最短路徑及路長。

九、下圖是某一工程施工網(wǎng)絡(luò)圖（統(tǒng)籌圖），圖中邊上的數(shù)字為工序時間（天）,

請求出各事項的最早時間和最遲時間，求出關(guān)鍵路線，確定計劃工期。

十、某企業(yè)生產(chǎn)三種產(chǎn)品A1、ArA3O每種產(chǎn)品在銷售時可能出現(xiàn)銷路

好（SJ,銷路一般（SJ和銷路差（SJ三種狀態(tài)，每種產(chǎn)品在不同銷售狀態(tài)的獲利情

況（效益值）如表1所示，請按樂觀法則進(jìn)行決策，選取生產(chǎn)哪種產(chǎn)品最為合適。

M態(tài)

-―或益值\sS

,2S3

Ai3010-6

2012

A29

A3151312

俵1)

十一、已知運輸問題的運價表和發(fā)量和收量如表2所示，請用最小元素法求出

運輸問題的一組可解釋。

B3

B2Bq

A\291279

13524

A2

A3104265

3546

（表2）

十二下列表3是一個指派問題的效率表（工作時間表），其中A.為工作人員（i=l,

2,3,4）、Bj為工作項目（j=l,2,3,4）,請作工作安排，使總的工作時間最小。

B3B4

B2

A\4174

2235

A2

A35643

A46324

參考答案

一、判斷題

⑴X⑵J⑶J(4)X(5)V(6)X(7)V(8)V(9)X(10)V

(11)X(12)X(13)7(14)X(15)X

二、簡述題

1、在可行域內(nèi)先確定一個基本可行解，然后通過迭代計算，逐步使目標(biāo)函數(shù)增大(求2,皿)，

求出新解，計算出方案機(jī)會成本后，得出相應(yīng)檢驗數(shù)，當(dāng)所有的CjZjWO時即得最優(yōu)解。

2、運輸問題可以用單純形求解，但由于虛設(shè)的變量多，運算復(fù)雜，十分不合算，所以不用

單純形法求解，而用簡單的表上作業(yè)法求解。

3、由于動態(tài)規(guī)劃的求解過程是一個多段決定過程，其狀態(tài)變量必須滿足無后效性和可知性

的特征要求。

三、填空題

1.樹

2.破圈法和避圈法

3.可行解、退化解、無界解、多重解

4.匈牙利法

5.確定性決策，不確定性決策，風(fēng)險性決策。

6.圈。

四.

c.-320000

CXbX,X,X*XX.X

1n0123445A6

M一I一x］a一-1--------?------------uo---------1------------u------------ux

⑵X240111/2-10

Z327/2-2-23/2

C-Z00(-7/2)(2)2-3/2

3.X〈輸入，玉輸出。

五、Zm—x+l6y2

'-兀+2y24

'一片+3y24I

六、吊？

(16)

s—A—B—c—F32

七、

s,

S2S3

A\3010-6

20129

A2

A3151312

選方案A1

十一、

.12...

2...(§)..?

(1)???3?,,(5…&3

3

10-④,,?②…6

b.3746

J

B1B,B,%B；

,,????6???

A14①74N

A3

2②235一??6

A3564③J??3

63②士=8??i…?！?

俵3）

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

??

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

1、在線性規(guī)劃問題中，若存在兩個最優(yōu)解時，必有相鄰的頂點是最優(yōu)解。

2、樹圖中，任意兩個頂點間有且僅有一條鏈。

3、線性規(guī)劃的圖解法適用于決策變量為兩個線性規(guī)劃模型。

4、在線性規(guī)劃問題中，將約束條件不等式變?yōu)榈仁剿氲淖兞勘环Q為松弛變

量。

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

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

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

種方法。

7、稱無圈的連通圖為樹，若圖的頂點數(shù)為p,則其邊數(shù)為p—l。

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

1)maxz=6X]+4x,⑴

2x+x<10(2)

12

x+x<8(3)

*12

〈2

x<7(4)

2

⑸、⑹

2)minz=2x,+x、⑴

12

-%+4%<24(2)

I2

(3)

5<x<10⑷、

X0

2-(6)

解：

從上圖分析，可行解域為abcde,最優(yōu)解為e點。

由方程組

[%+x—8

解出X]=5,X=3

[x=52

(x)

.?.X*=1=(5,3)T

1%

minz=Z*=2x5+3=13

三、（15分）一家工廠制造甲、乙、丙三種產(chǎn)品，需要三種資源一一技術(shù)服務(wù)、勞

動力和行政管理。每種產(chǎn)品的資源消耗量、單位產(chǎn)品銷售后所能獲得的利潤值以

及這三種資源的儲備量如下表所示：

技術(shù)服務(wù)勞動力行政管理單位利潤

甲110210

乙1426

丙1564

資源儲備量100600300

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

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

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

設(shè)甲、乙、丙三種產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為％、x2>x3,則％、x2>x3^0,設(shè)z

是產(chǎn)品售后的總利潤，則

maxz=10x,+6Xc+4x.

123

s.t.

%+x+x<100

123

10%+4x+5%<600

《123

2x+2x+6x<300

123

x,x,x>0

l123

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

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

456

maxz=10x,+6x^+4x+0x+0x+0x,

123456

X+x+%+x=10()

1234

10%+4x+5%+x-600

1235

2x+2x+6%+x=300

1236

%20,j=1,2,…6

i/

列表計算如下:

1064000

CXbe

BBXXXXXXL

123456

X

04100111100100

0X60045010

5(10)60

0X300226001

6150

000000

10f64000

X1/2

04400(3/5)1-1/100200/3

10X

16012/51/201/100150

0X18006/5501

6-1/5150

1045010

02t-10-10

6X015/65/3-1/60

2200/3

10X100/3101/6-2/31/60

1

X

06100004-201

220010620/310/32/30

3

00-8/3-10/3-2/30

?V(100200c\(\(\i(\r\\

..X*=(__，___,0,0,0,100)T

33

...maxz=10X122+6X92200

333

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

minz=540X]+450x2+720x3

3x+5x+9x>70

123

<9x+5x+3x>30

123

x,x,x>0

1123

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

maxz/=-540X|-450x^—720x3

s.t.

3%+5%+9%-%=70

1234

49%+5%+3%-x=30

I235

y>0,j=1,2,...,5

ij

增加人工變量相、x7,得到：

maxz/=-540x,—450x、-720x「Mx「Mx〃

12367

3x+5x+9x-x+x=70

12346

49%+5%+3%-％++x=30

I2357

%>0,j=1,2,...,5

ij

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

-540-450-72000-M-M

Xb0

cBBL

XXXXXXX

1234567

-MX70359-1010

670/3

-MX30(9)530-101

730/9=10/3

-12M—10M-12MMM-M-M

12M-540t10M-45012M-720-M-M00

-MX60010/3(8)-11/31-1/3

6

10/3/1/3

-540X10/315/91/30-1/901/9

1=10

-300+10/3M-8M-180-M-M/3+60-MM/3-60

0-150+10/3M8M-540tMM/3-600-M/3+60

15/2/5/12

-720X15/205/121-1/81/241/8-1/24

3=18

5/6/5/12

-540X5/61(5/12)01/24-1/8-1/241/8

1=2

-540-572-720-135/2475/12-135/2-75/2

0125t0135/2-475/12135/2-M75/2-M

-720X20/3-1011/61/61/6-1/6

3

—450X

2212/5101/10-3/10-1/103/10

-360-450-7207515-75-15

-5700

-18000-75-1575-M15-M

20

，該對偶問題的最優(yōu)解是x*=(0,2,3’0,0)T

最優(yōu)目標(biāo)函數(shù)值minz=—(-5700)=5700

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

B2B3B4s.

1

AI2011865

A]5910210

1874115

d.331212

j

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

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

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

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

...初始方案:

Z=2OX3+11X2+2X10+7X1+4X12+1X2=159

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

②用表上閉回路法進(jìn)行迭代調(diào)整：

費\銷

BB3B

1B24Si

20-121186-1

A

15

X32X

59-110-52

A

210

3XX7

18-147041

A15

3

XX105

\30

331212

430\

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

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

最小運費Z=11X3+8X2+5X3+2X7+4X10+1X5=123

六、（8分）一個公司經(jīng)理要分派4個推銷員去4個地區(qū)推銷某種商品。4個推銷員各有不同的

經(jīng)驗和能力，因而他們在每一地區(qū)能獲得的利潤不同，其估計值如下表所示：

7D2D3D4

甲35272837

乙28342940

丙35243233

T24322528

問：公司經(jīng)理應(yīng)怎樣分派4個推銷員才使總利潤最大？

解：用求極大值的“匈牙利法”求解。

效率矩陣表示為:

<35272837、’513123、

M—C行約簡

283429402126110

〉N

35243233516871

M=40

(24322528JJ681512,

c2106(0)、

(21090、

126110二12680*

0)110*2所畫()0元素少于n(n=4),

°1132

18074j18(0)44,

未得到最優(yōu)解,需要繼續(xù)變換矩陣(求能覆蓋所有0元素的最少數(shù)直線集合):

(2106J(0)>

1268J0*

11

w；11T2

\一\一44

未被直線覆蓋的最小元素為Cij=2,在未被直線覆蓋處減去2,在直線交叉處加上2。

"(0)840*、

0840]標(biāo)號

1046(0)

10460]>

011040*11(0)4

8046,<8(0)46>

J00o'

得最優(yōu)解：0001

0010

、0100,

...使總利潤為最大的分配任務(wù)方案為:

甲一Dj乙一D小丙一D3，丁—D,

此時總利潤W=35+40+32+32=139

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

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

最佳策略為：A-C-FfG-M

此時的最短距離為8+8+5+5=26

八、（8分）用P-T標(biāo)號法求下圖從至的最短路。（需寫出最短路線）

VV

2

5V

8

13

解：此為網(wǎng)絡(luò)分析之“最短路問題”，可用順向追蹤“TP標(biāo)號法”解決如下:

□□E

%到V］的最短路線是：叫一v°fv〈fv°fv&fV”，最短距圖2+1+1+7+9=20。

1/1ZDyo11

九、（10分）用找增廣鏈的方法求如下網(wǎng)絡(luò)的最大流。（需寫出相應(yīng)的增廣鏈）（弧

旁的數(shù)字為該弧容量）

解：此為網(wǎng)絡(luò)分析之“尋求網(wǎng)絡(luò)最大流問題”，可用“尋求網(wǎng)絡(luò)最大流的標(biāo)號法（福

特-富克爾遜算法)”解決如下：

㈠標(biāo)號過程：

1、給VS標(biāo)上(0,8)；

2、檢查v,在弧(v,v,)上，f>0,C=4,f<C,給匕標(biāo)號(s,B(v)),其

ss1sisisisi11

中P(v)=min(v),(C-f)}=min{t-oo,4-o}=4>

Issisi

(s,4)

(s,10)

R］理,給V標(biāo)號(S,B(v)),其中p(u)=min{|3(u),(C-f)}=minVoo,10-0)=10>

222ss2s2

3、檢查v,在弧(v,v)上，f=0,C=3,fvC,給v標(biāo)號(LB(v)),其

1131313131333

中B(u)=min{p(v),(C-f)}=minU,3-o)=3,

311313

(s,4)(3,3)

檢查v,同理，給v標(biāo)號(3,B(v)),其中)=min4e),(C-f)}=min&4-。}=3，

344433434

檢查v，同理，給V標(biāo)號(2,B(V)),其中p(v)=min{p(v),(C-f)}=min{10,4-oL4，

255522525

4、檢查v,,在弧(v,v)上，f=0,C=7,f<C,給v標(biāo)號(4,B(v)),其中

3(v)=min{p(v),(C-f)}=min6,7-()}=3/V得到標(biāo)號,標(biāo)號過程結(jié)束。

t44t4fI

(s,4)(3,3)

㈡調(diào)整過程：從