一、填空題（每題4分，共20分）

minZ=5x1—2x2

s.t-Xi+2X2=-2

1、設(shè)原LP問題為那么它的標(biāo)準(zhǔn)形和對(duì)偶規(guī)劃問題分別為:

-+3X2<4

2a—x2>2

X］無約束，*240

和

minZ=-x1-5x2

%—X）2—2

2、用分枝定界法求整數(shù)規(guī)劃5%+6々<30的解時(shí)，求得放松問題的解為X/=18/U,X2

x,<4

X1,x220且/為整數(shù)

=40/11,那么可將原問題分成如下兩個(gè)子問題

與求解。

3、右邊的圖的最小支撐樹是

4、以下圖是某網(wǎng)絡(luò)圖中的關(guān)于一可行流的增廣路，其中每巢弧上的數(shù)表示其容量和流量。

在其上增流的方法可用圖示為:

5、某線性規(guī)劃問題的最優(yōu)單純形表如下:

CBXBV工230000i

XjX1X2X3X4X5

1七4I001/40

0Z400-21/2I

2三20I1/2-1/80

-Z00-3/2-1/8-1/2

那么其最優(yōu)解為:最優(yōu)值Zz=

二、單項(xiàng)選擇題(每題2分，共1()分)

1、線性規(guī)劃的可行域的頂點(diǎn)是()

A、可行解B、正那么解C、根本可行解D、最優(yōu)解

2、在保持最優(yōu)解不變的前提下，基變量的系數(shù)q的改變量Aq可由不等式()解得。

A、B-1b>0B、『C/'NWO

C、CLGQ'NWOD、

3、在運(yùn)輸問題中如果總需求量小于總供給量，那么求解時(shí)應(yīng)()

A.虛設(shè)一些供給量；B.虛設(shè)一個(gè)供給點(diǎn)；

C.根據(jù)需求短缺量，虛設(shè)多個(gè)需求點(diǎn)；D.虛設(shè)一個(gè)需求點(diǎn)。

4.以下規(guī)劃問題用動(dòng)態(tài)規(guī)劃方法求解簡(jiǎn)便的是(

maxZ=+cx+cx

2233minf(x,y)=(x+2)2+3(y-l)2

X1+4X+3.V=10

A、23B、[x+4v=6

2j]-x+5I=6SJ.'

23j>0,y>0

x>0,y>0

minf(x,y)=4x+3(y-l)2

min/(A;y)=Cv+2)2+3(y-l)2

2x-y<3

D、s.t,4y<6

s.t.-x+4y=6

x>0,y>0

x>0,.y>0

5、以下關(guān)于樹的論述錯(cuò)誤地是()

A、任何一個(gè)圖，都有支撐樹；

B、圖G是樹的充分必要條件是其任意兩點(diǎn)之間恰有一條鏈；

C、連通圖G是樹的充分必要條件是G的邊數(shù)二G的頂點(diǎn)數(shù)?1；

D、假設(shè)連通圖G是的是無圈的，那么連通圖G是一個(gè)樹圖。

三、判斷題(每題2分，共10分)

()1、對(duì)偶單純形法與一般單純形法的解題思路的區(qū)別是：它是從根本正那么解出發(fā)

通過逐步迭代尋找既是根本正那么解又是根本可行解的解二最優(yōu)解：而單純形法是從根本可

行解出發(fā)通過逐步迭代尋找3死是根本可行解又是根本正那么解的解二最優(yōu)解。

）2、對(duì)LP問題的標(biāo)準(zhǔn)形，血:一1"用兩階段法求解時(shí)，假設(shè)其的輔助LP問題假

'AX=b

X>O

設(shè)其的輔助LP問題目標(biāo)函數(shù)最優(yōu)值等于零，那么原問題無可行解，停止計(jì)算。

（）3、分枝定界法中的分枝起到有效縮減求最優(yōu)解的范圍作用；而定界那么起到“巧

妙”地刪去不必要的一些點(diǎn)的分枝，使計(jì)算量大大減少作用。

（）4、一個(gè)可行流必需滿足平衡條件，即所有的結(jié)點(diǎn)處流出量與流入量相等。

1）5、左圖中可行流是最大流。

minZ=3.V1-x3

四、求解線性規(guī)劃：（方法不限）（15分）

s.t.i2x}-X2+X3<2

再,%2，％3NO

五、設(shè)有某救災(zāi)物資要從A八2調(diào)往三個(gè)災(zāi)區(qū)，供需情況及運(yùn)價(jià)表如下:

運(yùn)諭飛

BB2B3產(chǎn)量

AI31028

A21836

q

銷量65

（運(yùn)價(jià)單位：千元/噸，產(chǎn)銷量單位：噸）

求：（1）用最小元素法建立用最小元素法求一個(gè)初始可行調(diào)運(yùn)方案；

（2）用位勢(shì)法檢驗(yàn)該初始調(diào)運(yùn)方案是否是總運(yùn)輸費(fèi)最少的最優(yōu)方案；假設(shè)是求最少總運(yùn)

輸費(fèi)，假設(shè)不是，求一次調(diào)整新方案。（15分）

六、用Dijkstra法求右圖片到V?點(diǎn)的最短路

線及最短路程。（10分）

七、某紡織廠生產(chǎn)兩種布料，一種用來做服裝，另一種用來做窗簾。該廠實(shí)行兩班生產(chǎn)，

每周生產(chǎn)時(shí)間定為80小時(shí)。這兩種布料每小時(shí)都生產(chǎn)1000米。假定每周窗簾布可銷售70000

米，每米的利潤(rùn)為2.5元；衣料布可銷售45000米，每米的利潤(rùn)為1.5元。該廠在制定生

產(chǎn)方案時(shí)有以下各級(jí)目標(biāo)：

P：每周必須用足80小時(shí)的生產(chǎn)時(shí)間；

P：：每周加班時(shí)數(shù)不超過10小時(shí)；

P，：每周銷售窗簾布70000米,衣料布45000米;

P,：每周利潤(rùn)不低于是190000元

試建立這個(gè)問題的目標(biāo)規(guī)劃模型。

八、某工程工序明細(xì)表如下:

工序工時(shí)緊前工序工序工時(shí)案前工序

A15—F5D,E

B12—G20C,F

C10A,BH1