运筹学期末考试试卷(B)卷

福建农林大学考试试卷（B）卷

学年第学期

课程名称：运筹学考试时间120分钟

专业年级班学号姓名

题号—•二三四五六七八九总得分

得分

评卷人签字复核人签字

|得分|一、填空题（每空2分，共10分）

1.目标规划模型中，目标约束办+小一，=女中的女称为H标值。

2.线性规划问题的单纯形法中,有最优解的判别准则是所有检验数非负且最优值为常数。

3.如果流/={4}中所有4=0,则称/•是零流。

4.如果线g为最优基，则引为图

5.无向图中的环是端点重合的边。

।得分।二、单项选择题（选择正确答案的字母填入空格处，每小题2分，共10分）

1.线性规划的非对称形式的原问题和对偶问题数学模型中，互补松弛性的描述式为工。

A.=0，y：x*=0B.yx*=0

C.ysx-0D.y*x*=0

2.若化,K）为最大截集，则c。

A.c化,K）为最小截量B.c化,K）为最大流流量

C.C化,K）为化回）的截量D.c/i,匕）为最小截量

3.最短路求解的主要内容是旦。

A.关键路线B.最短路线

C.最短路长D.最短路线和最短路长

4线性规划问题的价值系数变化后，当最优表中旦不发生变化。

A非基变量检验数B.限定常数、技术系数和基变量检验数

C.检验数D.目标函数值的相反数

5.网络计划中关键工序内的TFy

A.>0B.<0

C.=L「E「TijD.=Lj

|得分|三、判断题（正确打“/；错误打“X”；每小题2分，共io分）

1.在增广链上确定的流量调整量只能是负的。（X）

2.目标规划模型中必须有目标约束。（4）

3.线性规划问题有最优解。（x）

4.网络计划中，非关键路线上工序的施工时间延长可能导致工期延长。（4）

5.树中可能存在环。（x）

।得分।四、问答题（每小题5分，共20分）

1.闭回路的定义及应用。

mXn表可以划分为mXn个格，一个格也可以称为一个点，在不同的

mXn表中，格或点代表不同的含义。取产销平衡表来介绍闭回路定义。

在产销平衡表中取偶数个点/心/,小…，同,"，若这些点满足

厂2=n,ji=ji

i2=z3,j3=74

Li（P-1）=ip,jp=j。

或满足

//=八，H=i2

./2=/3,z3=z4

Y

J(PT)=血ip=，0

则称这些点构成一条闭回路。

闭回路用来进行方案调整，计算检验数，判断可行解是否基本解等等。

2.最大流问题的线性规划模型。

maxv(/)

O&fij&C"%一

,,(/)i=s

S4=<0i=1,2,…,”

①"""[-v(/)i=t

3.线性规划模型的特点。

略。

4.目标规划模型中目标约束的结构。

略。

五、(第一小题5分，第二小题3分，第三小题2分，共10分)

对(P)：要求:

1.c=(c„c)=(l,l),用单纯形法求解；

H2

2.画出可行域；

3.指出c=(q,，2)变动下的最优解。

minz=—+c2x2

X)+x2<10

(P):Xj-x2>5

xpx2>0

解：⑴单纯形法求解如下:

Cj-1-100-M

0

XjX4X

CBXBbX35

@0X3101110010/1

-MX55①-10-115/1

z5M-1+M-1-M0-M0

Cj-1-100-M

0

X4

CBXBhXlX2X3X5

①0X350211-110/1

-1Xl5①-10-115/1

z50-20-11-M

x*=(5,0,5,0,0)r,z*=5。

2.可行域如下：

X2

3.c=（c“C2）变动下的最优解。

序号最优解p

1axA+(1-a)/3/4〃

2xA3/4"</?<3/2zr

3axA+(1-a)xD3/27

4xD—1/2万<夕<1/4万

5ax'+(l-a)x°1/4)

6xB1/4"<p<3/4乃

说明：P=—c.

六、（10分）

H用破圈法或避圈法求图1的最大生成树，并指出其权重和（10分）

解：⑴避圈法：首先确定应选的边数为顶点数减1,即应选7条边。

所选的边染上红色,旁边标明选边序号，结果如下图所示。

最大生成树权为85.

⑵避圈法略。

七、(10分)

对(OP),要求

B1.求解

2.给出一个合理的实际意义。

minz=P《d：+d；)+P/；

“i+"2+4—d；=10

(OP):s.t.<X[+2X2+d：-d；-5

xx,x2,d^,d^,d^,d^>0

解：1.⑴单纯形法

求解过程见下表，据下表得x*=(10,0)、Z*={0,5舄}

a00PiPl0尸2e

CBXBb不X24-d；*d；

PId；1011i-10010

0d；5①2001-15

Pi-10-1-10200

Pi0000001

000

C,PlPip20

CBXBbXid「疗d-d；

Pld；50-11-1-\①5

0X|512001-1一

Pi-501021-1

Pi0000001

；50-11-1-1

P2d(D

0X!10111-100

Pl0001100

尸2-501-1110

⑵图解法

相关图形见图2o

⑴考虑硬约束，可行域为第一限象；

⑵考虑P/,最优解在直线上；

⑶考虑P2,最优解在点〃上。

因此，£=(10,0尸，z*={0,5g}。

2.略。

।得分।八、（10分）

（教材P155例7）有某种机床,可以在高低两种不同的负荷下进行生产,在高负

荷下生产时,产品的年产量为g,与年初投入生产的机床数量W1的关系为

疔g（%）=8%,这时，年终机床完好台数将为a%,（a为机床完好率，0〈水1,设所0.7）.

在低负荷下生产时，产品的年产量为h,和投入生产的机床数量均的关系为

/F/?（W2）=5M2,相应的机床完好率为从0。＜1,设b=0.9）,--般情况下水上假设某厂

开始有x=1000台完好的机床，现要制定一个五年生产计划，问每年开始时如何重

新分配完好的机床在两种不同的负荷下生产的数量，以使在5年内产品的总产量为

最高。

解：首先构造这个问题的动态规划模型。

⑴变量设置

①设阶段变量人表示年度，因此，阶段总数〃=5。

②状态变量“表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时

的完好机床数量。

③决策变量依，表示第4年度中分配于高负荷下生产的机床台数。于是必-以

便为该年度中分配于低负荷下生产的机床台数。

这里也与以均取连续变量，当它们有非整数数值时.可以这样理解：如sk=

0.6,就表示一台机器在左年度中正常工作时间只占6/10；以=0.4时，就表示一台

机床在k年度只有4/10的时间于高负荷下工作。

⑵状态转移方程为

%+i=auk+久力-%）=0.7%+0.9区-4）

（3）允许决策集合，Dk（s*）={MJO<uk<sJ

（4）目标函数。设4）为第k年度的产量，则以（品,a）=8/当（&-%）,因此，

目标函数为

匕（S*）=%（S*,2"）+Vi+1（S*+|,"八1）+,,•+丹,孙）

⑸递推方程。

令£（8）表示由第A年的状态国出发，采取最优分配方案到第5年度结束这

段时间的产品产量，根据最优化原理有以下递推关系：

r/（•%）=吗ax»*（s*,"*）+/+|（s*+|）}k=5,4,3,2,1

1/6日）=0

⑹边界条件：S/=1000,.’20。

分阶段求解见下表。

k匕（S*,%）+/+1（5八|）/G)

5

8%+5(55-〃5)+°=3〃5+5s5558s5

4

8〃4+5(§4—〃4)+8[0.7〃4+0.9(巴—〃4)]=1.4〃4+12.2%§413.6.

38%+5(%—〃3)+13,6[0.7〃3+0.9(53-w)]=0.28w+17.24.17.52s3

33*

2=,0

8〃2+5(52一〃2)+17.52[0,7〃2+0・9($2-w2)]-0.504w2+20.7685220.768$2

18%+5(S]—%)+20.768[0.7〃]+0,9(邑一场)]=-1.1536%+23.6912sl023.6912sl

由表5可得最优策略：/?,（1000）={0,0,810,567,397}0目标函数最优值:

工(1000)=23691.2个。

九、（10分）

对表1,用表上作业法求解。

B表1

地产量

IIIIIIIV

产地（万吨）

A631275

B43956

C91013—5

需求（万吨）455不限

'解：根据产销平衡可知表1中不限应取为2,一应取为M,因此问题的基础数据表等价与表2：

表2

也产量

iIIIIIIV

产地（万吨）

A631275

B43956

C91013M5

需求（万吨）4552

⑴关于的计算

用伏格尔法确定x°

差额表1

行差额

IIIIIIIV

产地

A6③1273

B43951

C91013M1

列差额203