运筹学2015年学年第二学期

期末考试题（a卷）

注意事项：

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

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

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

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

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

A.等式约束 B .“W ”型约束 C ”约束

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

（ ）

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

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

A.该问题的系数矩阵有 mX n列

C.该问题的系数矩阵的秩必为 m+n-1

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

A、动态规划分阶段顺序不同，则结果不同 B状态对决策有影响

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

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

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

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

3: —旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。 （V ）

4:若线性规划问题中的 bi，Cj值同时发生改变，反映到最终单纯形表中，不会出现原问题

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

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

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

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

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

9:图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。 （X ）

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

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

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

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

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

3：在运输问题模型中， m + n-1个变量构成基变量的充要条件是 __不含闭回路 。

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

略、 、— 最优路线 和—最优目标函数值 。

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

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

6:在图论方法中，通常用 点 表示人们研究的对象，用 —边 表示对象之间的

某种联系。

7: 一个 无圈__且 连通 的图称为树。

四、计算题（每小题 15分，45 分） 1:考虑线性规划问题：

max z = 2x 4x2 3x3

"3X! +4x2 +2x3 兰 60

2音 + x2 +2x3 兰 40 s. t.

捲+ 3冷+ 2x3兰80

为，X2,x3 _0

分）

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

（5

分）

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

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

分）

2:某公司打算在三个不同的地区设置 4个销售点，根据市场预测部门的估计，在不同

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

k =2时，0 辽 x2 <4, Q < u2 乞 x2, f2（x2） = max｛g2（u2） f3（x3）｝,

0虫2纟2

于是有：

f2（0^muax｛ gzU） f3（X3）｝ =0, u 2（0） =0 ,

f2（i）=肿£气｛92（氏）f3（x3）｝ =12, U2（i）=i,

f2（2）二 muax｛g2（u2） f?%）｝ =22, u'2⑵=i,

f2 （3） max｛ g2（U2） f3（X3）｝ = 27, u'2 （3） =2,

0 ^^2 ^3

f2（4） =max｛g2（U2）"3（X3）｝ =31, u'2（4） =2 or 3.

0^2超

（3 分）

k = 3时，为=4, 0_山_为=4, 于是有：

办⑷二max｛gi（5） f2（x2” =47, u\⑷=2. — （3分）

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

得：

口1（4） =2, u 2（2） =1, u 3 （1）=1。即为地区1设置两个销售店,

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

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

3:解破圈法

（1）：取圈 WMWV1，去掉边［vz］。（2）：取圈 V2,V4,V3,V2，去掉边［V2,V4］

（3）：取圈 V2,V3,V5,V2，去掉边［V2,V5］。（ 4）:取圈 V3,V4,V5,V5,V3，去掉边［V3,V4］。

在图中已无圈，此时， p=6，而qnp—1^5，因此所得的是最短树。结果如下图,

其树的总长度为 12。

（6分）

生长法

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

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

分）

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

1 •试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无 穷多最优解和无有限最优解。

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

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

第二步：判断最优，检验各非基变量 Xj的检验数匚j =CBB Pj —c

若所有的Cr~0，则基B为最优基，相应的基可行解即为基本最优解，计算停止。

若所有的检验数- 0，又存在某个非基变量的检验数所有的 二k = 0，则线性规划问

题有无穷多最优解。

若有某个非基变量的检验数 □ 0，并且所对应的列向量的全部分量都非正，则该线

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

第三步：换基迭代

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

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

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

其中之一出基。

做主元变换。

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

（3 分）

2 •简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。

解：2:最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量

最大的问题。如果已知流过弧 （V ,Vj）的单位流量要发生Cij的费用，要求使总费用为最小的

最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标:

种问题称为最小费用最大流问题。模型可以描述为：

min、% c

max f

F 卩

送対—送勺才0

s.tj j j

0 < Xj < bj

采用对偶法求解最大流最小费用问题， 其原理为：用福德一富克逊算法求出网络的最大 流量，然后用Ford算法找出从起点Vs到终点Vt的最短增广链。在该增广链上，找出最大调 整量；，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流 量，则目前的流就是最小费用最大流，否则应继续调整。

对偶法的步骤归纳如下：

第0步：用最大流方法找出网络最大流量 fmax，并以0流作为初始可行流。

第一步：对于当前可行流，绘制其扩展费用网络图。

第二步：用Ford算法求出扩展费用网络图中从 vs到vt的最短路。

第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。

第四步：绘制可行流图。若可行流的流量等于最大流量 fmax，则已找到最小费用最大

流，算法结束；否则从第一步开始重复上述过程

本文来源：https://www.2haoxitong.net/k/doc/bb1e38146729647d27284b73f242336c1eb930e5.html