2
原问题解
第一步 第二步 第三步
（0，0，0，60，40，80） （0，15，0，0，25，35） （0，20/3，50/3，0，0，80/3）
c）：用对偶单纯形方法求解对偶问题时每步迭代结果：
------（5 分）
对偶问题问题解
第一步 第二步 第三步
（0，0，0，-2，-4，-3） （1，0，0，1，0，-1） （5/6，2/3，0，11/6，0，0）
B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性
D、动态规划的求解过程都可以用列表形式实现
10：若 P 为网络 G 的一条流量增广链，则 P 中所有正向弧都为 G 的（ ）
A．对边
B．饱和边
C．邻边
D．不饱和边
二、 判断题（每小题 1 分，共 10 分） 1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（√） 2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（× ） 3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中 删除，而不影响计算结果。（√ ）
因此，最优的分配方案所能得到的最大利润位 47，分配方案可由计算结果反向查出
得：
u*1 (4) 2, u*2 (2) 1, u*3 (1) 1 。即为地区 1 设置两个销售店，地
4
区 2 设置 1 各销售店，地区 3 设置 1 个销售店。 3：对下图中的网络，分别用破圈法和生长法求最短树。
3：解 破圈法
运筹学 2015 年学年第二学期 期末考试题（a 卷）
一、 单项选择题(每小题 1 分，共 10 分)
1：在下面的数学模型中，属于线性规划模型的为（ ）
max A. s.t.
S 4X Y XY 3 X, Y 0
min B. s.t.
S 3X Y 2X Y 1
X, Y 0
max C. s.t.
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对 不定步数问题，用迭代法求解，有____函数____迭代法和____策略____迭代法两种方法。 6：在图论方法中，通常用____点____表示人们研究的对象，用___边_____表示对象之间的
某种联系。 7：一个_____无圈___且____连通____的图称为树。
量，则目前的流就是最小费用最大流，否则应继续调整。 对偶法的步骤归纳如下：
第 0 步：用最大流方法找出网络最大流量 fmax ，并以 0 流作为初始可行流。
第一步：对于当前可行流，绘制其扩展费用网络图。
第二步：用 Ford 算法求出扩展费用网络图中从 vs 到 vt 的最短路。
第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。
第二步：判断最优，检验各非基变量 x j 的检验数 j CB B1Pj C j 。
若所有的 j 0 ，则基 B 为最优基，相应的基可行解即为基本最优解，计算停止。
若所有的检验数
j
0 ，又存在某个非基变量的检验数所有的 k
0 ，则线性规划问
题有无穷多最优解。
若有某个非基变量的检验数 j 0 ，并且所对应的列向量的全部分量都非正，则该线
S X2 Y2 XY2 X, Y 0
min D. s.t.
S 2XY XY3 X, Y 0
2．线性规划问题若有最优解，则一定可以在可行域的 （ ）上达到。
A．内点
B．顶点
C．外点
D．几何点
3：在线性规划模型中，没有非负约束的变量称为 （ ）
A．多余变量
B．松弛变量
C.自由变量
D．人工变量
4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优
解为（ ）
A.两个
B.零个
C.无穷多个
D.有限多个
5：原问题与对偶问题的最优（ ）相同。
A．解
B．目标值
C． 解结构
D．解的分量个数
6：若原问题中 xi 为自由变量，那么对偶问题中的第 i 个约束一定为 （ ）
A．等式约束
B．“≤”型约束 C．“≥”约束
D．无法确定
7：若运输问题已求得最优解，此时所求出的检验数一定是全部（ ）
（d）：比较（b）（c）计算结果。
1：解 a）：其对偶问题为
minz 60 y1 40 y2 80 y3
3y1 2 y2 y3 2
s.
t.
4 2
y1 y1
y2 2 y2
y3 2 y3
4 3
y1, y2 , y3 0
------（3 分）
b）：用单纯形方法求解原问题时每步迭代结果：
在图中已无圈，此时， p 6 ，而 q p 1 5 ，因此所得的是最短树。结果如下图，
其树的总长度为 12。 分）
.------（6
生长法 根据生长法的基本原理，得以下计算表
v2
v3
v4
S1
{2}
6
v2
3
8
S2
{3}
8
v3
5
S3
5
v5
5
.------（3 分）
v5
v6
9
93{3}源自1S45v6
3
S5
{3}
据此也得到与破圈法相同的最短树。
{1} .------（6 分）
五、简答题(每小题 10 分，共 20 分) 1．试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无 穷多最优解和无有限最优解。 解：1：单纯形法的计算步骤 第一步：找出初始可行解，建立初始单纯形表。
------（5 分）
d）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因
此（b）、（c）的计算结果完全相同。
--------(2 分)
2：某公司打算在三个不同的地区设置 4 个销售点，根据市场预测部门的估计，在不同 的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销
（1）：取圈 v1 , v2 , v3 , v1 ，去掉边[v1, v3 ] 。（2）：取圈 v2 , v4 , v3 , v2 ，去掉边[v2 , v4 ] 。
（3）：取圈 v2 , v3 , v5 , v2 ，去掉边[v2 , v5 ] 。（4）：取圈 v3 , v4 , v5 , v5 , v3 ，去掉边[v3 , v4 ] 。
_____。 2：线性规划的目标函数的系数是其对偶问题的__右端常数______；而若线性规划为最大化 问题，则对偶问题为___最小化问题_____。
3：在运输问题模型中， m n 1个变量构成基变量的充要条件是__不含闭回路______。
4：动态规划方法的步骤可以总结为：逆序求解____最优目标函数____，顺序求____最优策 略、____、___最优路线_____和___最优目标函数值_____。
,
f3 (3) g3 (3) 16, u '3 (3) 3 ,
f3 (4) g3 (4) 17, u '3 (4) 4
.------
（3 分）
k 2 时， 0 x2 4, 0 u2 x2 ,
于是有：
f2 ( x2 )
max {
0u2 x2
g2
(
u2
)
f3 (x3 )} ,
f2
k 3 时， 0 x3 4, 0 u3 x3 ,
f3 ( x3 )
max{ u3
g3
(
u3
)
f4 (x4
)} ，
其中
于是有：
f4 (x4 ) 0
f3 (0) g3 (0) 0,
u
' 3
(0)
0
,
f3 (1) g3 (1) 10,
u
' 3
(1)
1
,
f3 (2) g3 (2) 14, u '3 (2) 2
4：若线性规划问题中的 bi , c j 值同时发生改变，反映到最终单纯形表中，不会出现原问题
1
与对偶问题均为非可行基的情况。（×） 5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（√ ） 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（√ ） 7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（× ） 8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 决策问题。（√ ） 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。（× ） 10：网络最短路线问题和最短树问题实质上是一个问题。（× ） 三、 填空题（每空 1 分，共 15 分） 1：线性规划中，满足非负条件的基本解称为___基本可行解_____，对应的基称为___可行基
四、计算题（每小题 15 分，45 分）
1：考虑线性规划问题：
maxz 2x1 4x2 3x3
3x1 4x2 2x3 60
s. t.
2
x1
x1
x2 3x2
2 x3 2x3
40 80
x1, x2 , x3 0
（a）：写出其对偶问题；
（b）：用单纯形方法求解原问题；
（c）：用对偶单纯形方法求解其对偶问题；
(0)
max{g
0u2 0
2
(u
2
)
f 3(x3)} 0,
u '2(0) 0
,
f2
(1)
max{g
0u2 1
2
(u
2
)
f3(x3)} 12,