运筹学试题讲解.pdf

《运筹学试题讲解.pdf》由会员分享，可在线阅读，更多相关《运筹学试题讲解.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、解。7、图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。8、动态规划只是用来解决和时间有关的问题。9、在画网络计划图时，允许有多个起点和多个终点。10、因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。XXXXXX10XXXX10 0 xx 0 x一、判断题（每题 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、树图是边数最多的无圈的连通图。（）12、

5、求网络最大流的问题可以归结为求解一个线性规划模型。（）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（d2+d2）+P2d25若树 T 有 n 个点，那么它的边数一定是（）。-+-+-+-+-+-A.2n B.n C.n

7、+1 D.n-16完全决定确定型动态规划问题第 k+1 阶段的状态 Sk+1的是（）。A.阶段数 kB.决策 UkC.状态 SkD.状态 Sk与决策 Uk7任何图中，次为奇数的顶点的个数必为（）。A.奇数 B.偶数 C.奇偶性无法判断 D.奇数偶数均可8图 G=(V,E)有生成树的充要条件是（）。A.G 是欧拉图 B.G 是完全图 C.G 是连通图 D.G 是有限图9求 m 个产地，n 个销地的运输问题的表上作业法中，用最小元素法确定初始可行解时基变量（即填有数字格）的个数为（）A.m+n-1B.m+nC.m+n+1D.mn10求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（）。A.非负的

8、B.大于零C.无约束D.非零常数三、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15 分）（1）写出问题的数学模型（2）求获最大利润的方案。设备 A设备 B设备 C甲320乙2132500设备能力654075利润（元/件）1500三、已知下表（表 31）为求解某线性规划问题的最终单纯形表，表中x4,x5为松弛变量，问题的约束为 形式表 31x1x3x15/25/2010 x21/21/2x3100 x41/21/6x51/3cjzj（）写出原线性规划问题；（）写出原问题的对偶问题；直接

9、由表写出对偶问题的最优解。三、现在有线性规划问题（15 分）max z=-5X1+5X2+13X3 X1 X23X3 2012X1 4X210X3 90X,X,X 0123的最优单纯形表如下：Cj-5-1153131000b205X20X5160-2-4110r00-2-50-100（1）约束条件 2 的右端常数由 90 变为了 70,对最优基、最优解有何影响？如果有影响请求出最优解。（2）目标函数中X3的系数由 13 变为 8,对最优基、最优解有何影响？如果有影响请求出最优解。三、灵敏度分析（10 分）max z (2)x13x22x1 2x2124x16s.t.1 5 x215x1,x2

10、0已知原问题的最终单纯形表为：cjC CB B2基b23000 x11x20 x31/2x40 x51/5x1303x4x2430000102011004/51/51/5试分析：1.试计算原问题的检验数，并判断解的类型。2.分析在什么范围变动，最优解不变？（可以直接在上表中添加）答：1.原问题检验数如上图，所有非基变量检验数小于零，有唯一的最优解。（3 分）2.考虑目标函数系数（产品价格）变化后的最终单纯形表为：（3 分）cjCB203基x1x4x2cjzjb3432x110003x200100 x31/220(2)/20 x401000 x51/54/51/5(1)/5最优解条件为：(2)/

11、20,(1)/5 0，可得：21（4 分）六、有一运输问题平衡作业表如下：（10 分，每小题 5 分）1）为此运输问题确定初始调运方案；A3销量1235A257 6 25A149 453销地B1产地938 73B1B2B3产量2）计算检验数填于表中，并判断初始调运方案是否为最优方案。五、运输问题（10 分）某糖果经销公司的 3 个加工厂 A1、A2、A3每天产量分别为 7 吨、4 吨、9 吨；这些产品要运往 4 处经销点 B1、B2、B3、B4，每天的销量为 3 吨、6 吨、5 吨、6 吨；产销地点之间距离不同等因素形成的运价如下表：产地销地A1A2A31请列出该问题的产销平衡表（问题2 可在

12、该表上分析）？2请采用表上作业法的最小元素法求出初始分配方案？3现已知仅有一处空格可以改进，请采用闭回路法对空格 A2B4进行最优性检验，并求出最佳总费用。六、学校游泳队有四名队员，现在需组织参加全国大学生运动会的游泳比赛，其中200 米混合泳接力赛是一项反映综合实力的项目，教练小组为了确定由哪名队员游哪种泳姿而费尽心思。下列表格给出了这四名队员的各种泳姿的游泳成绩（50 米），你能帮助教练小组解决这一问题吗？（10 分单位：秒时间效率仰泳蛙泳蝶泳四、请运用 0-1 变量将下列逻辑关系表示成一般的约束（每小题5 分，共 10 分）：（1）x1 x2 2或2x1+3x25（2）变量x只能取 0、3、5、7 中的一个答：（1）定义 01 变量y赵37.743.433.3钱32.933.128.5孙33.842.238.9李37.034.730.4B1317B21194B33210B410851,第1个约束不起作用x1x22My，则：0，第1个约束起作用2x1+3x2M(1 y)5（2）定义yi1,选择第 i个值x=3y2+5y37y4，则：0，不选择第 i个值y1 y2+y3 y41