运筹学2024学年期末考试题A卷及答案

运筹学2024年学年其次学期

期末考试题（a卷）

留意事项：

1、答题前，考生务必将自己的姓名、班级填写在答题卡上。

2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。

3、考试结束，将试卷和答题卡一并交回。

一、单项选择题（每小题1分，共10分）

1：在下面的数学模型中，属于线性规划模型的为（

maxS=4X+YminS=3X+YmaxS=X2+Y2minS=2XY

AAs.t.XY<3BAs.t.2X-Y>-1s.t.X-Y<2DJs.t.X+Y>3

X,Y>0X,Y>0X,Y>0X,Y>0

2.线性规划问题若有最优解，则肯定可以在可行域的（）上达到。

A.内点B.顶点C.外点D.几何点

3：在线性规划模型中，没有非负约束的变量称为（）

A.多余变量B.松弛变量C.自由变量D.人工变量

4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优

解为（）

A.两个B.零个C.无穷多个D.有限多个

5：原问题与对偶问题的最优（）相同。

A.解B.目标值C.解结构D.解的重量个数

6：若原问题中看为自由变量，那么对偶问题中的第，个约束肯定为（）

A.等式约束B.''4”型约束C.、'2”约束D.无法确定

7：若运输问题已求得最优解，此时所求出的检验数肯定是全部（）

A.小于或等于零B.大于零C.小于零D.大于或等于零

8：对于m个发点、n个收点的运输问题，叙述错误的是（）

A.该问题的系数矩阵有mXn列B.该问题的系数矩阵有m+n行

C.该问题的系数矩阵的秩必为m+n-lD.该问题的最优解必唯一

9：关于动态规划问题的下列命题中错误的是（）

A、动态规划分阶段依次不同，则结果不同

B、状态对决策有影响

C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性

D、动态规划的求解过程都可以用列表形式实现

10：若P为网络G的一条流量增广链，则P中全部正向弧都为G的（）

A.对边B.饱和边C.邻边D.不饱和边

二、推断题（每小题1分，共10分）

1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一样的。（J）

2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（X）

3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中

删除，而不影响计算结果。（J）

4：若线性规划问题中的如［值同时发生变更，反映到最终单纯形表中，不会出现原问题

与对偶问题均为非可行基的状况。（X）

5：若线性规划的原问题有无穷多最优解，则其对偶问题也肯定具有无穷多最优解。（J）

6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（V）

7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（X）

8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的

决策问题。（J）

9：图论中的图不仅反映了探讨对象之间的关系，而且是真实图形的写照，因而对图中点与

点的相对位置、点与点连线的长短曲直等都要严格留意。（X）

10：网络最短路途问题和最短树问题实质上是一个问题。（X）

三、填空题（每空1分，共15分）

1：线性规划中，满意非负条件的基本解称为—基本可行解,对应的基称为—可行基

2：线性规划的目标函数的系数是其对偶问题的—右端常数；而若线性规划为最大化

问题，则对偶问题为—最小化问题。

3：在运输问题模型中，加+〃-1个变量构成基变量的充要条件是—不含闭回路o

4：动态规划方法的步骤可以总结为：逆序求解—最优目标函数—,依次求—最优策

略、—、―最优路途和—最优目标函数值_。

5：工程路途问题也称为最短路问题，依据问题的不同分为定步数问题和不定步数问题；对

不定步数问题，用迭代法求解，有一函数—迭代法和—策略—迭代法两种方法。

6：在图论方法中，通常用一点—表示人们探讨的对象，用__边表示对象之间的

某种联系。

7：一个____无圈—且一连通—的图称为树。

四、计算题（每小题15分，45分）

1：考虑线性规划问题：

maxz=2玉+4x2+3x3

X

3xl+42+2X3<60

2玉+%+2退<40

s.tA

玉+3X2+2X3<80

%1,%2，%3-0

(a)：写出其对偶问题；

(b)：用单纯形方法求解原问题；

(c)：用对偶单纯形方法求解其对偶问题；

(d)：比较(b)(c)计算结果。

1：解a)：其对偶问题为

minz=60%+40%+80y3

3%+2%+—22

4%+%+3%»4

s.t.5

2%+2y2+2%，3

、%，%,为20

---(3分)

b）：用单纯形方法求解原问题时每步迭代结果:

原问题解

第一步(0,0,0,60,40,80)

其次步(0,15,0,0,25,35)

第三步(0,20/3,50/3,0,0,80/3)

（5分）

c）：用对偶单纯形方法求解对偶问题时每步迭代结果:

对偶问题问题解

第一步(0,0,0,-2,-4,-3)

其次步(1,0,0,1,0,-1)

第三步(5/6,2/3,0,11/6,0,0)

（5分）

d）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因

此（b）、（c）的计算结果完全相同。-----（2分）

2：某公司准备在三个不同的地区设置4个销售点，依据市场预料部门的估计，在不同

的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销

10

216

325

30

32

0

12

17

21

22

0

10

14

16

17

2：解该问题可以作为三段决策问题，对1,2,3地区分别设置销售店形成1,

2,3三个阶段。4表示给地区k设置销售店时拥有安排的数量，曲表示给地区

k设置销售店的数量。

状态转移方程为：4+1=々-以；阶段效应题中表所示；目标函数：

3

maxR=（以）；其中g.（4）表示在k地区设置即个销售店时的收益；

左=1

----（3分）

首先逆序求解条件最有目标函数值集合和条件最有决策集合：

左=3时，0<尤3<4,0<w<x,力（w）=max{g3（为）+力（­）}，其中

33%

%（%）=0

于是有：

力（0）=g3（0）=0,M3（0）=0,

力（l）=g3（l）=10,M'3⑴=1,

力（2）=g3（2）=14,M，3（2）=2,

力⑶=g3⑶=16,*（3）=3,

力（4）=g3（4）=17,M'3（4）=4

-----（3分）

左=2时，0<羽<4,0<w2<x2,力（々）=max{g,（%）+力（X3）},

0<〃2«巧

于是有：

力(0)=max{g2(%)+力(%3)}=°，“2(°)=°，

2Vo

f2(1)=max{g2(“2)+力(X3)}=12,uz(1)=1,

OK”2Vl

力(2)=max{g2(〃2)+力(玛)}=22,w2(2)=1,

0«“2«2

力⑶=max{g2(“2)+)(％)}=27,u2(3)=2,

0<M2<3

力(4)=max{g2(4)+力(玉)}=31,M2(4)=2or3.

0<H2"

---(3分)

左=3时，玉=4,0<%<玉=4,于是有：

<(4)=max{&(%)+人但)}=47,3(4)=2..——(3分)

0V的<4

因此，最优的安排方案所能得到的最大利润位47,安排方案可由计算结果反向查

出得：

<(4)=2,M*2(2)=1,M*3⑴=1。即为地区1设置两个销售店,

地区2设置1各销售店，地区3设置1个销售店。

3：对下图中的网络，分别用破圈法和生长法求最短树。

3：解破圈法

(1):取圈匕#2，匕，匕，去掉边［匕，匕］。(2):取圈”2，丫4，匕#2,去掉边［%，为］。

(3):取圈”2，匕，％，彩，去掉边［%，%］。(4):取圈匕，丫4，%，%，匕，去掉边［匕加41。

在图中已无圈，此时，P=6,而q=p-l=5,因此所得的是最短树。结果如下图，

其树的总长度为12。——(6

分)

V2V4

（3分）

生长法

依据生长法的基本原理，得以下计算表

匕V4%V6

{2}6000000

Si

38900

V2

{3}8900

跖

53GO

5{3}00

S3

001

匕

5{1}

3

丫6

I{3}

据此也得到与破圈法相同的最短树。（6分）

五、简答题（每小题10分，共20分）

1.试述单纯形法的计算步骤，并说明如何在单纯形表上推断问题是具有唯一最优解、无

穷多最优解和无有限最优解。

解：1：单纯形法的计算步骤

第一步：找出初始可行解，建立初始单纯形表。

其次步：推断最优，检验各非基变量句的检验数%4-

若全部的%4°,则基B为最优基，相应的基可行解即为基本最优解，计算停止。

若全部的检验数％4°,又存在某个非基变量的检验数全部的％=°,则线性规划问

题有无穷多最优解。

若有某个非基变量的检验数3>°,并且所对应的列向量的全部重量都非正，则该线

性规划问题的目标函数值无上界，既无界解，停止计算。

第三步：换基迭代

当存在%选%进基来改善目标函数。若检验数大于0的非基变量不止一个，则

可以任选其中之一来作为进基变量。

进基变量/确定后，按最小比值原则选择出基变量与。若比值最小的不止一个，选择

其中之一出基。

做主元变换。

反复进行上述过程就可以找到最优解或推断出没有有限最优解。