运筹学期末考试试题及答案

2011年运筹学期末考试试题及答案

（用疗"公#新）

一、单项选择题（每题3分，共27分）

L使用人工变量法求解极大化的线性规划问题时、当所有的检验数

为40,但在基变量中仍含有非零的人工变量，表明该线性规划问

题（D）

A.有唯一的最优解B.有无穷多最优解

C.为无界解D.无可行解

2.对于线性规划

maxz=一2玉+4x2

s.t.

-3%2+£=4

<xl+5X2+8=1

王，元2，当，工4

如果取基B则对于基B的基解为（B）

A.X=（0,0,4,1）7B.X=（1,0,3,

C.X=（4,0,0,-3/D.X=（23/8,—3/8,0,0了

3.对偶单纯形法解最小化线性规划问题时，每次迭代要求单纯形表

中（C）

A.b列元素不小于零B.检验数都大

于零

C.检验数都不小于零D.检验数都不

大于零

4.在n个产地、m个销地的产销平衡运输问题中，（D）是错误的。

A.运输问题是线性规划问题

B.基变量的个数是数字格的个数

C.非基变量的个数有w〃-加+1个

D.每一格在运输图中均有一闭合回路

5.关于线性规划的原问题和对偶问题，下列说法正确的是（B）

A.若原问题为无界解，则对偶问题也为无界解

B.若原问题无可行解，其对偶问题具有无界解或无可行解

C.若原问题存在可行解，其对偶问题必存在可行解

D.若原问题存在可行解，其对偶问题无可行解

6.已知规范形式原问题（max问题）的最优表中的检验数为

（4,4,…，儿），松弛变量的检验数为（心,加2,…d+,“），则对偶问题的

最优解为（C）

A.（4,4，.“,x“）B.（-4，-4,…4J

C.（一4什］,-4,+2,…D.（2„+1,/1„+2,...,2„+„,）

7.当线性规划的可行解集合非空时一定（D）

A.包含原点B.有界C.无界D.是凸集

8.线性规划具有多重最优解是指(B)

A.目标函数系数与某约束系数对应成比例。

B.最优表中存在非基变量的检验数为零。

C.可行解集合无界。

D.存在基变量等于零。

9.线性规划的约束条件为归+2々+%=4,则基可行解是(D)

xt,x2,x3,x4>0

A.(2,0,0,1)B.(-1,1,2,4)C.(2,2,-2,-4)

D.(0,0,2,4)

二、填空题(每题3分，共15分)

1.线性规划问题中，如果在约束条件中没有单位矩阵作为初始可行

基，我们通常用增加人工变量的方法来产生初始可行

基。

2.当原问题可行，对偶问题不可行时，常用的求解线性规划问题的

方法是单纯形法。

3.原问题的第1个约束方程是型，则对偶问题相应的变量是

无约束变量。

4.运输问题中，当总供应量大于总需求量时，求解时需虚设一个

销地,此地的需求量为总供应量减去总需求量。

5.约束玉+2/W6,4X1+6X2>1及2%+4々420中至少有一个起作用，

引入0-1变量，把它表示成一般线性约束条件为

%+2X2<6+Myx

+6X2>1-My2

2xj+4X2<20+My30

y+%+%w2

%,%，%=。或1

三.考虑线性规划问题

minZ=x,+3x2+4x3

3x}+2X2<13

x+3x<17

<23

2xj+x2+x3=13

XPX320,当无约束

（1）把上面最小化的线性规划问题化为求最大化的标准型；（5

分）

（2）写出上面问题的对偶问题。（5分）

解：

max-Z=一%一3%2+3x；-4x3

3尤［+2芯-2X2+x4=13

<%；~x2+3与+M=17

2%+X；—+“3=13

%,芯,工；,%3，%4,冗520

四.用图解法求解下面的线性规划问题（8分）

maxZ=-2xt+x2

Xj4-x2>1

<%—3/2—1

Xj,x2>0

五.某厂准备生产A、B、C三种产品，它们都消耗劳动

力和材料，如下表：

资、^耗ABC资源量

设备（台时/件）63545

材料（kg/件）34530

利润（元/件）314

建

立能获得最大利润的产品生产计划的线性规划模型，并

利用单纯形法求解问题的最优解。（20分）

解：模型为：

Variable->X1IX2IX3IDirectionIR.H.S.

Maximize314

C1635<=45

C2345<=30

LowerBound000

UpperBoundMMM

VariableTypeContinuousContinuousContinuous

标准化为：

maxZ=3芭++4匕

6%+3X2+5X3+x4=45

v3%+4X2+5X3+/=30

xpx2,x3>0

单纯形为:

X1X2X3Slack_C1Slack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

Slack_C106.00003.00005.00001.0000045.00009.0000

Slack_C203.00004.00005.0：0_0_0___01.000030.00006.0000

3.00001.00004.0000000

X1X2X3SlackedSlack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

Slack_C103.0000-1.000001.0000-1.000015.00005.0000

X34.00000.60000.80001.000000.20006.000010.0000

0.6000-2.200000-0.800024.0000

X1X2X3Slack_C1Slack_C2

Basisc（i）3.00001.00004.000000R.H.S.Ratio

X13.00001.00000.33330.00000.3333-0.33335.0000

X34.00000.00001.00001.0000-0.20000.40003.0000

0-2.00000-0.2000-0.600027.0000

六、已经线性规划

maxZ=X]+2X2+3x3+4x4

x}+2X2+2X3+3X4<20

<2%+9+3%3+2X4<20

内,々，工320,%4无约束

的对偶问题的最优解为y=(120.2),利用对偶性质求原问题的最优

解。(10分)

解；其对偶问题为:

Minimize20y1+20y2

X11y1+2y2>=1

X22y1+1y2>=2

X32y1+3y2>=3

X43y1+2y2>=4

Integer:

Binary:

Unrestricted:

yl>=0,<=M

y2〉=0,<=M

5分

由X，%#0得

x}+2X2+2X3+3X4=20

7

2%+%2+3&+2X4=20分

把丫值代入原问题，知第一、二个约束为严格不等式,

故有玉=々=0......................9分

解得X*=(0,0,4,4)T....................10分

七、有某运费最少的运输问题，其运价表如表:

\销

B?员A产量

地

A67588

A451089

&29737

销量8655

求此运输问题的最优调运方案。（10分）

解:

BTCIJII\T©destinationdestination^destination"destination-SupplyDualP缶

6758

Source180

35

45108

Source29-2

63

2973

Source37-4

25

Demand8655

DualP①6757

ObjectiveValue=104(Minimization)

《运筹学》试题样卷（一）

题号--二三四五七八九十总

分

得分

一、判断题（共计10分，每小题1分，对的打错的打X）

1.无孤立点的图一定是连通图。

2.对于线性规划的原问题和其对偶问题，若其中一个有最优解,

另一个也一定有最优解。

3.如果一个线性规划问题有可行解，那么它必有最优解。

4.对偶问题的对偶问题一定是原问题。

5.用单纯形法求解标准形式（求最小值）的线性规划问题时，与力＞°

对应的变量都可以被选作换入变量。

6.若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷

多个最优解。

7.度为。的点称为悬挂点。

8.表上作业法实质上就是求解运输问题的单纯形法。

9.一个图G是树的充分必要条件是边数最少的无孤立点的图。

10.任何线性规划问题都存在且有唯一的对偶问题。

①②③④⑤⑥⑦⑧⑨

二、建立下面问题的线性规划模型（8分）

某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情

况为秋冬季3500人日；春夏季400（）人日。如劳动力本身用不了时可外

出打工，春秋季收入为25元/人日，秋冬季收入为20元/人日。该农

场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需

要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛

时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春

夏季为50人日，年净收入900元/每头奶牛。养鸡时不占用土地，需

人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元/每

只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三

种作物每年需要的人工及收入情况如下表所示：

大豆玉米麦子

秋冬季需人日数203510

507540

春夏季需人日数300041004600

年净收入（元/公

顷）

试决定该农场的经营方案，使年净收入为最大。

三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表,

表中M，%为松弛变量，问题的约束为形式（共8分）

x\£为4与

为5/201/211/20

司5/21-1/20-1/61/3

5-0—40—4-2

（1）写出原线性规划问题；（4分）

（2）写出原问题的对偶问题；（3分）

（3）直接由上表写出对偶问题的最优解。（1分）

四、用单纯形法解下列线性规划问题（16分）

maxZ=2%）—x2+x-i

s.t.3Xi+xz+X3<60

xi-x2+2x3410

xi+x2-x3<20

X1,X2,X3>0

五、求解下面运输问题。（18分）

某公司从三个产地A】、A2、A3将物品运往四个销地BI、B2、B3、B4,各

产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示:

问：应如何调运，可使得总运输费最小？

销地Bi层B、也

产量

产地

A

1056725

A,827625

4934850

销/p>

六、灵敏度分析（共8分）

线性规划maxz=10xi+6必+4x3

S.t.X1+X2+X3<100

lOxi+4X2+5X3<600

2xi+2X2+6X3<300

X1,X2,X3>0

的最优单纯形表如下：

6X2200/305/615/30

1/6

10XI100/311/60-2/31/60

0X6100040-201

07

0-8/30-10/30

2/3

（1）C1在何范围内变化，最优计划不变？（4分）

（2）bi在什么范围内变化，最优基不变？（4分）

七、试建立一个动态规划模型。（共8分）

某工厂购进100台机器，准备生产pl,p2两种产品。若生产产品pl,每

台机器每年可收入45万元，损坏率为65%；若生产产品p2,每台机器

每年可收入35万元，损坏率为35%；估计三年后将有新的机器出现，旧

的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？

八、求解对策问题。（共10分）

某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500,

1000,1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元,

剩余种子的处理价为每公斤3元。

要求：

（1）建立损益矩阵；（3分）

（2）用悲观法决定该商店应订购的种子数。（2分）

（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（5分）

九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8分）

十、用标号法求V］到V6的最短路。（6分）

运筹学样卷（一）答案

判断题。共计10分，每小题1分

①②③④⑤⑥⑦⑧⑨10

XVXJVVXVXV

二、建线性规划模型。共计8分（酌情扣分）

解：用司，切，％3分别表示大豆、玉米、麦子的种植公顷数；尤4,%分别表示

奶牛和鸡的饲养数；尤6,%7分别表示秋冬季和春夏季的劳动力（人日）数，

则有

maxZ=3000为+4100x2+4600%+900x4+20x5+20x6+25x7

西+句+与+1.5彳4<100（土地限制）

400%4+3为4150（）0（资金限制）

20^+35x2+10x3+l（）0x4+0.6x5+x6<3500（劳动力限制）

50西+175x2+40X3+50X4+0.3x5+x7<4000（劳动力限制）

x4<200（牛栏限制）

4<15（X）（鸡舍限制）

Xj>0（；=1,2,-,7）

三、对偶问题。共计8分

解：（1）原线性规划问题：maxz=6x]-2x2+10x3

x2+2445

<3xt-x2+x3<10

、%i,%2?0•....4分

（2）原问题的对偶规划问题为：

min卬=5凹+10y2

3y2之6

%-乃2-2

2y1+为21°

.凹，为20;……3分

(3)对偶规划问题的最优解为：y*=(4,2)\……1分

四、单纯形表求解线性规划。共计16分

解：引入松弛变量*4、X5,X6,标准化得,

maxZ=2xf-x2+x3

s.t.3xi+X2+X3+X4=60

X1-X2+2x3+Xs=10

X1+X2TX3+X6=0

X1,X2,X3,X4、"5、26,20....................3分

建初始单纯形表，进行迭代运算：....................9分

2-11000

CBXbb，

XlXlX3X4X5X6e

0X46031110020

0X510[1]-1201010*

0X62011-100120

G/02*-11000

0X43004-51-307.5

2Xl101-12010

0X6100[2]-30-115*

62001*-30-20

0X4100011-1-2

2Xi15100.500.50.5

-1X1501-1.50-0.50.5

2500-1.50-1.5-0.5

由最优单纯形表可知，原线性规划的最优解为：（15,5,0）上..2分

最优值为：z*=25o............2分

五、求解运输问题。共计18分

解：

（1）最小元素法：（也可以用其他方法，酌情给分）

设利为由Ai运往Bj的运量（i=l,2,3；j=l,2,3,4）,

列表如下：

销

地用B?%产量

产地

12525

220525

31530550

销/p>

..................3分

所以，基本的初始可行解为：X14=25；X22=20：*24=5：

屋31=15；X33=30；*34=5

其余的Xij=0o..................3分

（2）求最优调运方案：

1会求检验数，检验解的最优性：011=2；012=2；013=3；

<j21=l；CT23=5；O32=-1.3分

2会求调整量进行调整：=5..................2分

销与2%产量

地

产地

12525

2151025

31553050

销/p>

...3分

3再次检验.................2分

4能够写出正确结论

解为：*14=25：X22=15：*24=10%31=15,*32=5*33=30

其余的Xij=0。....1分

最少运费为：535..............1分。

六、灵敏度分析。共计8分

(1)(4分)

-8/3-2/3]-10/3)

max<AC1<min

1/61/6J-2/3J

-4<Ac,<5,6=10-4<c1+Ac1<10+5=15

(2)(4分)

-200/3][-100/3-100]

<AZ?)<min

5/3J[-2/3

—40WA仿=10

七、建动态规划模型。共计8分

解：(1)设阶段变量A表示年度，因此，阶段总数〃=3。

(2)状态变量6表示第A年度初拥有的完好机床台数，同时也是第k-1

年度末时的完好机床数量。

(3)决策变量“左,表示第左年度中分配于生产产品pl的机器台数。于

是SA-NA便为该年度中分配于生产产品pl的机器台数.

(4)状态转移方程为

sk+l=0.35%+0.65(.-%)

(5)允许决策集合，在第k段曲X)={〃&|04%＜与}

(6)目标函数。设或(sA,返)为第左年度的产量，则

gk(sk,uk)=4511k+35(sk-uk),

因此，目标函数为

Rk=£gk(Sk，Uk)

i=k

(7)条件最优目标函数递推方程。

fk(sk)=max(uk(sk))

4叫

令必(W)表示由第k年的状态sk出发,采取最优分配方案到第3年度

结束这段时间的产品产量，根据最优化

原理有以下递推关系：

{[45%+35(s*-〃*)]+加J0.35%+0.65(s*-%)]}

(8).边界条件为

/s+lG+l)=°

八、解决对策问题。共1()分

(1)益损矩阵如下表所示：……3分

Si

销售S2S3S4

500100015002000

订购

5001500150015001500

10000300030003000

1500150045004500

—1500

200003000