《運(yùn)籌學(xué)》課程考試試卷及答案

《運(yùn)籌學(xué)》課程考試試卷

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

1、線性規(guī)劃問(wèn)題的3個(gè)要素是：、和。

2、單純形法最優(yōu)性檢驗(yàn)和解的判別，當(dāng)現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解是最優(yōu)解，

當(dāng)線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)

解，當(dāng)線性規(guī)劃問(wèn)題存在無(wú)界解。

4、連通圖的是指：。

5、樹(shù)圖指,最小樹(shù)是0

6、在產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題中，設(shè)產(chǎn)地為m個(gè)，銷(xiāo)地為n個(gè)，運(yùn)輸問(wèn)題的解中的基變量數(shù)

為.0

二、簡(jiǎn)答題簡(jiǎn)算題（共20分）

1、已知線性規(guī)劃問(wèn)題，如下：

maxZ=7%-24+5%

2巧一巧+3/V6

sH.v43+<8

xj>0,i=1,2,3

請(qǐng)寫(xiě)出其對(duì)偶問(wèn)題。（10分）

2、已知整數(shù)規(guī)劃問(wèn)題：

maxZ=10%]+5%2

3X1+4X2<9

531+2%2<8

ji，X22。,且光i，%為整數(shù)

在解除整數(shù)約束后的非整數(shù)最優(yōu)解為（xl,x2）=（l,1.5）,根據(jù)分支定界法，請(qǐng)選擇一個(gè)變

量進(jìn)行分支并寫(xiě)出對(duì)應(yīng)的2個(gè)子問(wèn)題（不需求解）。（10分）

（3）利用單純形法求解上述問(wèn)題（14分，單純形表格已給出，如若不夠，可自行添加）

三、計(jì)算題（共70分）

1、某廠用Al,A2兩種原料生產(chǎn)Bl,B2,B3三種產(chǎn)品，工廠現(xiàn)有原料，每噸所需原

料數(shù)量以及每噸產(chǎn)品可得利潤(rùn)如下表。

品所需原料（噸）商品現(xiàn)有原料

原料B1B2B3（噸）

A121030

A202450

每噸可得利潤(rùn)（萬(wàn)元）320.5

在現(xiàn)有原料的條件下，應(yīng)如何組織生產(chǎn)才能使該廠獲利最大？（共20分）

（1）寫(xiě)出該線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（4分）

（2）將上面的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式（2分）

（3）利用單純形法求解上述問(wèn)題（14分，單純形表格已給出，如若不夠，可自行添加）

2、考慮下列運(yùn)輸問(wèn)題:

B1B2B3產(chǎn)量

A16424

A28575

銷(xiāo)量333

請(qǐng)用表上作業(yè)法求解此問(wèn)題，要求：使用Vogel法求初始解。若表格不夠可自行添加（15

分）

3、有4臺(tái)機(jī)器都可以做A、B、C、D四種工作，都所需費(fèi)用不同，其費(fèi)用如下表所示。

請(qǐng)用匈牙利法求總費(fèi)用最小的分配方案。（10分）

乍

ABCD

機(jī)器

I41075

II2763

in3344

IV4663

4、某工廠內(nèi)聯(lián)結(jié)6個(gè)車(chē)間的道路如下圖所示，已知每條道路的的距離，求沿部分道路

架設(shè)6個(gè)車(chē)間的電話網(wǎng)，使電話線總距離最短。（10分，提示最小部分樹(shù)問(wèn)題，采用避

圈法或破圈法均可，但必須用圖或文字描述詳細(xì)步驟）

5、用Ford-Fulkerson標(biāo)號(hào)算法求解下圖中VsfVt的最大流量，并標(biāo)出網(wǎng)絡(luò)的最小割集。

（15分）

VI(2,2)V3

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

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

1、決策變量目標(biāo)函數(shù)約束條件

2、所有的5W0所有的5W0,某個(gè)非基變量Xjyzi=0某個(gè)5>0,Pi相量的

所有分量aijWO

4、在一個(gè)圖中，若每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱(chēng)這樣的圖為連通圖

5、無(wú)圈的連通圖樹(shù)枝總長(zhǎng)最小的部分樹(shù)

6、m+n-1

二、簡(jiǎn)答題。簡(jiǎn)算題。（共20分）

1、（10分）

解：minw-6%+8ya（2分）

「2%+缶N7

S.LN~2（8分，每式2分）

3yl+%25

2、（10分）

解：選擇x2進(jìn)行分支，得到以下2個(gè)子問(wèn)題：

maxz=+Sx3maxi=10xt+Sxa

rr

3x1+4xa<q3xt+4xa<9

5Tl+2*aSs5xj+2X3<8

*24。N2

k區(qū)20.*220Lzx20.xx20

評(píng)分標(biāo)準(zhǔn)：以上2個(gè)子問(wèn)題各5分，其中新加入的約束條件各3分。

三、計(jì)算題（共70分）

1、（共20分）

（1）寫(xiě)出該線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（4分）

maxI=3xx+2xa+05x,

12xt+xa<30

s.t2xa+4xai50

IX1-X,

（2）將上面的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式（2分）

maxz=3,1+2xa+05x,+Ox，+Oxa

2&++x4=30

2xa+4x>+x1=50

Xi.x,z,x,zW0

Ias4s

（3）利用單純形法求解上述問(wèn)題（14分，單純形表格已給出，如若不夠，可自行添加）

G320.500

CBXBBXIX2X3X4X5

0X430[2]1010

0X55002401

Cj-Zj320.500

3XI1510.500.50

0X55002[4]01

Cj-2j00.50.5-1.50

3XI1510.500.50

0.5X312.50[0.5]100.25

Cj-Zj00.250-1.5-0.125

3XI2.510-10.5-0.25

2X22501200.5

G-2j00-0.5-1.5-0.25

X=(2.5,25,0,0,0)maxz=57.5（四個(gè)表每個(gè)3分，結(jié)論2分，共14分，按數(shù)字扣完為止）

2、（15分）

（1）使用Vogel法求初始解（7分）

B1B2B3產(chǎn)量①②③

A16/142/34226

A28/25/375238

銷(xiāo)量333

①215

②21

③2

（2）校驗(yàn)數(shù)（7分）

BlB2B3ui

Al16

A238

vj0-3-4

當(dāng)前調(diào)運(yùn)方案：xll=l,xl3=3,x21=2,x22=3,其余為零，為最優(yōu)方案。最優(yōu)值為

6*1+2*3+8*2+5*3=43。(1分)

3、解:

(0631、

Q1075、4'((I)62P

0541

27632(53：

(1)(2)0011(3)

33443『(0)0~:-

33o,

0663/3、132(0),

0010

?0)621]U1=2

(/hTAtuji1

0531“2=2

(0)311

(4)0(0)01=°(5)

(oj90_2_

U32=2

iun

=-20027

KiV2=v3=v4=-

括號(hào)對(duì)應(yīng)的xij=l,最優(yōu)分配方案。最有效率值7+2+3+3=15(以上每步2分)

4、解:

方法1:避圈法

(1)任選一個(gè)點(diǎn)，這里選擇Vi點(diǎn)，令ViGV,其余點(diǎn)屬于V"V與▽間最短邊

為(V1,V2)。邊(V1,V2)是最小樹(shù)內(nèi)的邊。

,,

(2)令VUV2—V,V\V2^V,V與V，間最短邊為(V2,V3)o邊(V2,V3)是最小樹(shù)

內(nèi)的邊。

,,

(3)令VUV33V,V\V3^V,V與V，間最短邊為(V3,V5)o邊(V3,V5)是最小樹(shù)

內(nèi)的邊。

(4)令VUV53V,V'Vs-V5,V與V，間最短邊為(V5,V4)。邊(V5,V4)是最小樹(shù)

內(nèi)的邊。

(5)令VUVTV,V'WHV',V與V，間最短邊為(V4,V6)o邊(V4,V6)是最小樹(shù)

內(nèi)的邊。(或：V與V，間最短邊為(V5,V6)。邊(V5,V6)是最小樹(shù)內(nèi)的邊)

V6

V3V5V5

沿最終圖中紅線標(biāo)識(shí)的邊架設(shè)電話網(wǎng)，電話線總距離最短1+2+3+5+6=17。

上述5個(gè)步驟(文字描述或繪圖均可)各的2分，若最終結(jié)論沒(méi)有給出或給錯(cuò)扣1

分。

方法2：破圈法

(1)從原圖中任取一回