运筹学2015年学年第二学期
期末考试题（a卷）
注意事项：
1、答题前，考生务必将自己的姓名、班级填写在答题卡上。 2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。 3、考试结束，将试卷和答题卡一并交回。
一、 单项选择题(每小题1分，共10分)
1：在下面的数学模型中，属于线性规划模型的为（ ） ?maxS?4X?Y?min??A.?s.t.XY?3 B.?s.t.??X,Y?0???maxS?X2?Y2S?3X?Y?min??2X?Y??1 C.?s.t.X?Y?2 D.?s.t.??X,Y?0X,Y?0??S?2XYX?Y?3 X,Y?02．线性规划问题若有最优解，则一定可以在可行域的 （ ）上达到。 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：若运输问题已求得最优解，此时所求出的检验数一定是全部（ ） A．小于或等于零 B．大于零 C．小于零 D．大于或等于零 8：对于m个发点、n个收点的运输问题，叙述错误的是( ) A．该问题的系数矩阵有m×n列 B．该问题的系数矩阵有m+n行
C．该问题的系数矩阵的秩必为m+n-1 D．该问题的最优解必唯一 9：关于动态规划问题的下列命题中错误的是（ ） A、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性 D、动态规划的求解过程都可以用列表形式实现
10：若P为网络G的一条流量增广链，则P中所有正向弧都为G的（ ） A．对边 B．饱和边 C．邻边 D．不饱和边
二、 判断题（每小题1分，共10分）
1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（√） 2：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（× ） 3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（√ ） 4：若线性规划问题中的bi,cj值同时发生改变，反映到最终单纯形表中，不会出现原问题
与对偶问题均为非可行基的情况。（×） 5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（√ ） 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（√ ） 7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（× ） 8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（√ ）
9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（× ） 10：网络最短路线问题和最短树问题实质上是一个问题。（× ） 三、 填空题（每空1分，共15分）
1：线性规划中，满足非负条件的基本解称为___基本可行解_____，对应的基称为___可行基
_____。
2：线性规划的目标函数的系数是其对偶问题的__右端常数______；而若线性规划为最大化问题，则对偶问题为___最小化问题_____。
3：在运输问题模型中，m?n?1个变量构成基变量的充要条件是__不含闭回路______。 4：动态规划方法的步骤可以总结为：逆序求解____最优目标函数____，顺序求____最优策
略、____、___最优路线_____和___最优目标函数值_____。
5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有____函数____迭代法和____策略____迭代法两种方法。 6：在图论方法中，通常用____点____表示人们研究的对象，用___边_____表示对象之间的
某种联系。
7：一个_____无圈___且____连通____的图称为树。
四、计算题（每小题15分，45分）
1：考虑线性规划问题：
max??z?2x1?4x2?3x3?3x1?4x2?2x3?60?2x???x???2x?40 ?123s.t.??x1?3x2?2x3?80??x1,x2,x3?0（a）：写出其对偶问题；
（b）：用单纯形方法求解原问题； （c）：用对偶单纯形方法求解其对偶问题； （d）：比较（b）（c）计算结果。 1：解 a）：其对偶问题为
min??z?60y1?40y2?80y3?3y1?2y2?y3?2?4y??y???y?4?123s.t.??2y1?2y2?2y3?3??y1,y2,y3?0
------（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个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？ 利 地 销 售 店 0 1 2 3 4 润 区 1 2 3 0 16 25 30 32 0 12 17 21 22 0 10 14 16 17 2：解 该问题可以作为三段决策问题，对1，2，3地区分别设置销售店形成1， 2，3三个阶段。 xk表示给地区k设置销售店时拥有分配的数量，uk表示给地区k设置销售店的数量。 状态转移方程为：xk?1?xk?uk；阶段效应题中表所示；目标函数：maxR??gk(uk)； 其中gk(uk)表示在k地区设置uk个销售店时的收益； k?13------（3分） 首先逆序求解条件最有目标函数值集合和条件最有决策集合： k?3时，0?x3?4,0?u3?x3,f3(x3)?max{g3(u3)?f4(x4)}， 其中u3f4(x4)?0 于是有： f3(0)?g3(0)?0,f3(1)?g3(1)?10,u'3(0)?0, u'3(1)?1, , f3(2)?g3(2)?14,f3(3)?g3(3)?16,f3(4)?g3(4)?17,-----（3分） u'3(2)?2u'3(3)?3, u'3(4)?4 .-k?2时，0?x2?4,0?u2?x2,f2(x2)?max{g2(u2)?f3(x3)}, 0?u2?x2于是有： f2(0)?max{g2(u2)?f3(x3)}?0,u'2(0)?0, 0?u2?0f2(1)?max{g2(u2)?f3(x3)}?12,u'2(1)?1, 0?u2?1f2(2)?max{g2(u2)?f3(x3)}?22,u'2(2)?1, 0?u2?2f2(3)?max{g2(u2)?f3(x3)}?27,u'2(3)?2, 0?u2?3 f2(4)?max{g2(u2)?f3(x3)}?31,u2(4)?2or3. 0?u2?4'------（3分） k?3时，x1?4,0?u1?x1?4,于是有： f1(4)?max{g1(u1)?f2(x2)}?47,u'1(4)?2. .------（3分） 0?u1?4因此，最优的分配方案所能得到的最大利润位47，分配方案可由计算结果反向查出得： u*1(4)?2,u*2(2)?1,u*3(1)?1。即为地区1设置两个销售店，地区2设置1各销售店，地区3设置1个销售店。 3：对下图中的网络，分别用破圈法和生长法求最短树。
3：解 破圈法 （1）：取圈（3）：取圈
v1,v2,v3,v1v2,v3,v5,v2，去掉边
[v1,v3]。（2）：取圈
v2,v4,v3,v2，去掉边
[v2,v4]。
。
，去掉边
[v2,v5]。（4）：取圈
v3,v4,v5,v5,v3，去掉边
[v3,v4]在图中已无圈，此时，p?6，而q?p?1?5，因此所得的是最短树。结果如下图，其树的总长度为12。 .------（6
分）