1、运筹学 2015 年学年第二学期期末考试题（a 卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、 单项选择题(每小题 1 分，共 10 分)1：在下面的数学模型中，属于线性规划模型的为（ ）0Y,X3.ts4SmaxA0Y,X12.ts3SminB0Y,X2.tsSmaxC0Y,X3.ts2SminD2线性规划问题若有最优解，则一定可以在可行域的 （ ）上达到。 A内点 B顶点 C外点 D几何点 3：在线性规划模型中，没有非负约束的变量称为 （ ） A多余变量 B松弛变量 C.自
2、由变量 D人工变量 4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ ）A.两个 B.零个 C.无穷多个 D.有限多个5：原问题与对偶问题的最优（ ）相同。 A解 B目标值 C 解结构 D解的分量个数6：若原问题中 为自由变量，那么对偶问题中的第 个约束一定为 （ ） ixiA等式约束 B “”型约束 C “”约束 D无法确定 7：若运输问题已求得最优解，此时所求出的检验数一定是全部（ ） A小于或等于零 B大于零 C小于零 D大于或等于零 8：对于 m 个发点、n 个收点的运输问题，叙述错误的是( )A该问题的系数矩阵有 mn 列 B该问题的系数矩阵有
3、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：单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可
4、行解。 （ ） 3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 （ ） 4：若线性规划问题中的 值同时发生改变，反映到最终单纯形表中，不会出现原问题,ijbc与对偶问题均为非可行基的情况。 （） 5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。 （ ） 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。 （ ） 7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 （ ） 8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。 （ ） 9：图论中的图不仅反
5、映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。 （ ） 10：网络最短路线问题和最短树问题实质上是一个问题。 （ ）三、 填空题（每空 1 分，共 15 分）1：线性规划中，满足非负条件的基本解称为_基本可行解_，对应的基称为_可行基_。2：线性规划的目标函数的系数是其对偶问题的_右端常数_；而若线性规划为最大化问题，则对偶问题为_最小化问题_。3：在运输问题模型中， 个变量构成基变量的充要条件是_不含闭回路_。1mn4：动态规划方法的步骤可以总结为：逆序求解_最优目标函数_，顺序求_最优策略、_、_最优路线_和_最优目标函数值_
6、 _。5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有_函数_迭代法和_策略_迭代法两种方法。6：在图论方法中，通常用_点_表示人们研究的对象，用_边_表示对象之间的某种联系。7：一个_无圈_且_连通_的图称为树。四、计算题（每小题 15 分，45 分）1：考虑线性规划问题：1231236max4308.,zxstx（a）：写出其对偶问题；（b）：用单纯形方法求解原问题；（c）：用对偶单纯形方法求解其对偶问题；（d）：比较（b） （c）计算结果。1：解 a）：其对偶问题为 123123min604803.,0zyysty-（3 分）
7、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 个销售点，根据市场预测部门
8、的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？0 1 2 销 售店利润地区3 41230 16 25 30 320 12 17 21 220 10 14 16 172：解 该问题可以作为三段决策问题，对 1，2，3 地区分别设置销售店形成1，2，3 三个阶段。 表示给地区 k 设置销售店时拥有分配的数量， 表示给地kx ku区 k 设置销售店的数量。状态转移方程为： ；阶段效应题中表所示；目标函数：1kku； 其中 表示在 k 地区设置 个销售店时的收益； 31max()kRg()kgku-（3 分）
9、首先逆序求解条件最有目标函数值集合和条件最有决策集合：时， ， 其中k 333340()max(4, ), ugxf xxuf40于是有：, ,333(0),(0)fgu33(1)0,(1)fgu, 2()142,333()6,()f.-4()74gu（3 分）时， ,2k 22222300()max(4),ugxuxfxf于是有：,22320 2()ma(),()0ufgf,2 1x1xu,2 2 2023()a(),()uf f,2 373gx. -2 20234()ma()1,(4)uf fuor -（3 分）时， 于是有：3k11,4,xx.-1 20 14()a()47,()2.ug
10、fxuf-（3 分）因此，最优的分配方案所能得到的最大利润位 47，分配方案可由计算结果反向查出得：。即为地区 1 设置两个销售店，123*(4),()1,()uu地区 2 设置 1 各销售店，地区 3 设置 1 个销售店。 3：对下图中的网络，分别用破圈法和生长法求最短树。3：解 破圈法（1）：取圈 ，去掉边 。 （2）：取圈 ，去掉边 。3121,v13,v2432,v24,v（3）：取圈 ，去掉边 。 （4）：取圈 ，去掉边555,。4,v在图中已无圈，此时， ，而 ，因此所得的是最短树。结果如下图，6p1qp其树的总长度为 12。 .-（6 分）.-（3 分）生长法根据生长法的基本原理
11、，得以下计算表2v3v4v5v6v1S2 6 2v3 8 93 8 93v5 3 S5 35v 145 16v35S3据此也得到与破圈法相同的最短树。 .-（6 分）五、简答题(每小题 10 分，共 20 分)1试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解。解：1：单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。第二步：判断最优，检验各非基变量 的检验数 。jx1jBjjCP若所有的 ，则基 B 为最优基，相应的基可行解即为基本最优解，计算停止。0j若所有的检验数 ，又存在某个非基变量的检验数所有的 ，则线性规划j 0k问题有无
12、穷多最优解。若有某个非基变量的检验数 ，并且所对应的列向量的全部分量都非正，则该线0j性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代当存在 ，选 进基来改善目标函数。若检验数大于 0 的非基变量不止一个，0kkx则可以任选其中之一来作为进基变量。进基变量 确定后，按最小比值原则选择出基变量 。若比值最小的不止一个，选择k rx其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。 -（3 分）2简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的
13、问题。如果已知流过弧 的单位流量要发生 的费用，要求使总费用为最小(,)ijvijc的最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：。这种问题称为最小费用最大流问题。模型可以描述为：minijxcminax0,.0ijijjiijijcfiststfixb采用对偶法求解最大流最小费用问题，其原理为：用福德富克逊算法求出网络的最大流量，然后用 Ford 算法找出从起点 到终点 的最短增广链。在该增广链上，找出最svt大调整量 ，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用最大流，否则应继续调整。对偶法的步骤归纳如下：第 0 步：用最大流方法找出网络最大流量 ，并以 0 流作为初始可行流。maxf第一步：对于当前可行流，绘制其扩展费用网络图。第二步：用 Ford 算法求出扩展费用网络图中从 到 的最短路。svt第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。第四步：绘制可行流图。若可行流的流量等于最大流量 ，则已找到最小费用最大maxf流，算法结束；否则从第一步开始重复上述过程
