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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時(shí)間比訂購(gòu)模型的間隔時(shí)間長(zhǎng)。（）

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

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

（）

二、簡(jiǎn)述題

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

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

3.建立動(dòng)態(tài)規(guī)劃模型時(shí)，應(yīng)定義狀態(tài)變量，請(qǐng)說明狀態(tài)變量的特點(diǎn)。

三、填空題

1.圖的組成要素；“

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

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

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

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

6.樹連通，但不存在。

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

1.計(jì)算該規(guī)劃的檢驗(yàn)數(shù)

C—A32000

J

CiXBbxxxX

lX,34、

1

3X,310-10

12

2X340111/20

z.33.52-20

C.—Z.

JJ

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

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

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

S=6x+x

max12

x+x<7

12

2x+3犬>16

12

x,x>0

112

六、下圖為動(dòng)態(tài)規(guī)劃的一個(gè)圖示模型，邊上的數(shù)字為兩點(diǎn)間的距離，請(qǐng)用逆推

法求出S至F點(diǎn)的最短路徑及最短路長(zhǎng)。

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

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

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

請(qǐng)求出各事項(xiàng)的最早時(shí)間和最遲時(shí)間，求出關(guān)鍵路線，確定計(jì)劃工期。

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

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

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

M態(tài)

-―或益值\sS

,2S3

Ai3010-6

2012

A29

A3151312

俵1)

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

運(yùn)輸問題的一組可解釋。

B3

B2Bq

A\291279

13524

A2

A3104265

3546

（表2）

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

2,3,4）、Bj為工作項(xiàng)目（j=l,2,3,4）,請(qǐng)作工作安排，使總的工作時(shí)間最小。

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

二、簡(jiǎn)述題

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

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

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

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

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

的特征要求。

三、填空題

1.樹

2.破圈法和避圈法

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

4.匈牙利法

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

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）

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

??

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

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

2、樹圖中，任意兩個(gè)頂點(diǎn)間有且僅有一條鏈。

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

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

量。

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

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

6、運(yùn)輸問題中求初始基本可行解的方法通常有最小費(fèi)用法與西北角法兩

種方法。

7、稱無圈的連通圖為樹，若圖的頂點(diǎn)數(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)

解：

從上圖分析，可行解域?yàn)閍bcde,最優(yōu)解為e點(diǎn)。

由方程組

[%+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ù)、勞

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

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

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

甲110210

乙1426

丙1564

資源儲(chǔ)備量100600300

1）建立使得該廠能獲得最大利潤(rùn)的生產(chǎn)計(jì)劃的線性規(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)品售后的總利潤(rù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/

列表計(jì)算如下:

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

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

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

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

B2B3B4s.

1

AI2011865

A]5910210

1874115

d.331212

j

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

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

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

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

...初始方案:

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

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

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

費(fèi)\銷

BB3B

1B24Si

20-121186-1

A

15

X32X

59-110-52

A

210

3XX7

18-147041

A15

3

XX105

\30

331212

430\

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

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

最小運(yùn)費(fèi)Z=11X3+8X2+5X3+2X7+4X10+1X5=123

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

經(jīng)驗(yàn)和能力，因而他們?cè)诿恳坏貐^(qū)能獲得的利潤(rùn)不同，其估計(jì)值如下表所示：

7D2D3D4

甲35272837

乙28342940

丙35243233

T24322528

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

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

效率矩陣表示為:

<35272837、’513123、

M—C行約簡(jiǎn)

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)號(hào)

1046(0)

10460]>

011040*11(0)4

8046,<8(0)46>

J00o'

得最優(yōu)解：0001

0010

、0100,

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

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

此時(shí)總利潤(rùn)W=35+40+32+32=139

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

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

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

此時(shí)的最短距離為8+8+5+5=26

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

VV

2

5V

8

13

解：此為網(wǎng)絡(luò)分析之“最短路問題”，可用順向追蹤“TP標(biāo)號(hà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)號(hào)法（福

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

㈠標(biāo)號(hào)過程：

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

2、檢查v,在弧(v,v,)上，f>0,C=4,f<C,給匕標(biāo)號(hà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)號(hà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)號(hào)(LB(v)),其

1131313131333

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

311313

(s,4)(3,3)

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

344433434

檢查v，同理，給V標(biāo)號(hà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)號(hào)(4,B(v)),其中

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

t44t4fI

(s,4)(3,3)

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