运筹学试题讲解

1、习题讲解一、判断题（共计10分，每小题1分，对的打，错的打X）1. 无孤立点的图一定是连通图。2. 对于线性规划的原题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。4对偶问题的对偶问题一定是原问题。5用单纯形求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。6若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。7. 度为0的点称为悬挂点。8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。10. 任何线性规划问题都存在且有唯一的

2、对偶问题。 10XXXX一、判断题（对的打，错的打X. 共计10分，答在下面的表格中）1、单纯形法计算中，选取最大正检验数对应的变量作为换入变量，可使目标函数值得到最快的减少。2、单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 3、对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。4、应用对偶单纯形法计算时，若单纯形表中某一基变量，且所在行的所有元素都大于或等于零，则其对偶问题具有无界解。5、用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。 6、动态规划的最短路问题也可以用图论中求最短路问题的

3、方法求解。 7、图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。 8、 动态规划只是用来解决和时间有关的问题。 9、在画网络计划图时，允许有多个起点和多个终点。10、因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。10XXXXXXX一、 判断题（每题1分，共15分）（ ）1、 若线性规划问题存在两个不同的最优解，则必然有无穷多个最优解。（ ）2、 图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的。（ ）3、 连通图G的生成树是取G的部分点和部分边所组成的树。（ ）4、 如线性规划

4、问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ）5、 按最小元素法（或Vogel法）给出的初始基可行解，从每一空格出发可以找到而且仅能找到惟一的闭回路。（ ）6、 已知yi*为线性规划的对偶问题的最优解，若yi*=0，说明在最优生产计划中第i种资源一定有剩余。（ ）7、 对偶问题的对偶问题未必是原问题。（ ）8、 当目标规划模型中存在x1 + x2 + d- = 4的约束条件，则该约束为系统约束。（ ）9、目标规划中的正偏差变量大于等于零，负偏差变量小于等于零。（ ）10、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函值。（ ）11、树图是边数最多的无圈的连通图。（

5、 ）12、求网络最大流的问题可以归结为求解一个线性规划模型。（ ）13、图论中的图不论反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置，点与点连线的长短曲直等都要严格注意。（ ）14、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（ ）15、在动态规划模型中，问题的阶段数等于问题的子问题的数目。二、 单项选择题（正确得2 分，选错、多选或不选得0 分。共20 分）1原问题与对偶问题都有可行解，则（ ）。A原问题有最优解，对偶问题没有最优解 B. 原问题与对偶问题可能都没有最优解C. 一个问题有最优解，另一个问题有无界解 D. 原

6、问题与对偶问题都有最优解2、当线性规划问题的可行解集合非空时一定（ ）。 A. 包含原点X=（0，0，） B. 有界 C. 无界 D. 是凸集3、 若原问题中xi 为自由变量，那么对偶问题中的第i个约束一定为（ ）。A. 等式约束 B. “”型约束 C. “”约束 D. 无法确定4在目标规划中，要求不低于第一目标值，恰好完成第二目标值，则其目标函数为（ ）。A. min Z = P1d1- + P2（d2- + d2+） B. min Z = P1d1+ + P2（d2- + d2+）C. min Z = P1（d1- + d1+） + P2（d2- + d2+） D. min Z = P1（

7、d2- + d2+） + P2d2-5若树 T 有 n 个点，那么它的边数一定是（ ）。A. 2n B. n C. n+1 D. n-16完全决定确定型动态规划问题第k+1阶段的状态Sk+1 的是（ ）。 A. 阶段数k B. 决策Uk C. 状态Sk D. 状态Sk 与决策Uk7任何图中，次为奇数的顶点的个数必为（ ）。A. 奇数 B. 偶数 C. 奇偶性无法判断 D. 奇数偶数均可8图G=(V,E)有生成树的充要条件是（ ）。A. G是欧拉图 B. G是完全图 C. G是连通图 D. G是有限图9求m个产地，n个销地的运输问题的表上作业法中，用最小元素法确定初始可行解时基变量（即填有数字格

8、）的个数为（ ） A. m+n-1 B. m+n C. m+n+1 D. mn10求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。A. 非负的 B. 大于零 C. 无约束 D. 非零常数三、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15分）（1）写出问题的数学模型 （2）求获最大利润的方案。甲乙设备能力设备A3265设备B2140设备C0375利润（元/件）15002500三、 已知下表（表31）为求解某线性规划问题的最终单纯形表，表中为松弛变量，问题的约束为 £

9、 形式 表 315/201/211/25/211/201/61/300（） 写出原线性规划问题；（） 写出原问题的对偶问题；直接由表写出对偶问题的最优解。三、现在有线性规划问题（15分）max z=-5+5+13的最优单纯形表如下：Cj-551300b5X2-11310200X5160-2-4110r00-2-50-100（1）约束条件2的右端常数由90变为了70,对最优基、最优解有何影响？如果有影响请求出最优解。（2）目标函数中的系数由13变为8,对最优基、最优解有何影响？如果有影响请求出最优解。三、灵敏度分析（10分）已知原问题的最终单纯形表为：23000基23101/201/504002

10、14/53301001/500101/5试分析：1. 试计算原问题的检验数，并判断解的类型。2. 分析在什么范围变动，最优解不变？（可以直接在上表中添加）答：1. 原问题检验数如上图，所有非基变量检验数小于零，有唯一的最优解。（3分）2. 考虑目标函数系数（产品价格）变化后的最终单纯形表为：（3分）cj 23000CB基bx1x2x3x4x52x13101/201/50x4400214/53x2301001/5cjzj00(2)/20(1)/5最优解条件为：，可得：（4分）六、有一运输问题平衡作业表如下：（10分，每小题5分）销地产地B1B1B2B3产量A19 3 8 73A249 45 3A

11、35 7 6 25销量12351） 为此运输问题确定初始调运方案；2） 计算检验数填于表中，并判断初始调运方案是否为最优方案。五、运输问题（10分）某糖果经销公司的3个加工厂A1、A2、A3每天产量分别为7吨、4吨、9吨；这些产品要运往4处经销点B1、B2、B3、B4，每天的销量为3吨、6吨、5吨、6吨；产销地点之间距离不同等因素形成的运价如下表：产地 销地B1B2B3B4A1311310A21928A3741051请列出该问题的产销平衡表（问题2可在该表上分析）？2请采用表上作业法的最小元素法求出初始分配方案？ 3现已知仅有一处空格可以改进，请采用闭回路法对空格A2B4进行最优性检验，并求出最佳总费用。六、 学校游泳队有四名队员，现在需组织参加全国大学生运动会的游泳比赛，其中200米混合泳接力赛是一项反映综合实力的项目，教