运筹学习题(共12页).doc

精选优质文档-倾情为你奉上P1 11. 判断下列说法是否正确：（a）图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；（b）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；（c）线性规划问题的每一个基解对应可行域的一个顶点；（d）如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；（e）对取值无约束的变量 ，通常令 xj=xj-xj，其中 xj0 , xj0 ,在用单纯形法求得的最优解中有可能同时出现xj>0, xj>0 ；（f）用单纯形法求解标准形式的线性规划问题时，与 j >0对应的变量都可以被选作换入变量；（g）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；（h）单纯形法计算中，选取最大正检验数k对应的变量 xk 作为换入变量，将使目标函数值得到最快的增长；（i）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；（j）线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；（k）若x1， x2分别是某一线性规划问题的最优解，则 X=1X1+2X2 也是该线性规划问题的最优解，其中1 , 2为正的实数；（l）线性规划用两阶段法求解时，第一阶段的目标函数通常写为min z=，但也可以写为min z=，只要所有ki均为大于零的常数；（m）对一个有 n个变量 m个约束的标准形的线性规划问题，其可行域的顶点恰好为C 个；（n）单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解；（o） 线性规划问题的可行解如为最优解 ，则该可行解一定是可行解；（p） 若线规划问题具有可行解，切其可行域有界，则该线性规划问题最多具有有限个数的最优解；（q）线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优。P8 1.20 下表（表1-3）为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为max z=5x1+3x2,约束形式为，x3,x4为松弛变量，表中解代入目标函数后得z=10.表 13x1x2x3x4x3 2x1 acd0e101/51cj-zjb-1fg (a)求ag的值；(b)表中给出的解是否为最优解P9 1.22 表1-5为某求极小值线性规划问题的初始单纯形表及迭代后的表,x4,x5为松弛变量,试求表中的al值及各变量下标mt的值表 15x1x2x3x4x5xm 6xn 1b-1c3de1001cj - zja1-200xs fxt 4gh2i-111/21/201cj - zj07jkLP10 1.28 表1-6中给出某极大化问题的单纯形表，问表中a1,a2,c1,c2,d为何值时以及表中变量属那一种类型时有：(a) 表中解唯一最优解；(b) 表中解为无穷多最优解之一；(c) 表中解为退化的可行解；(d)下一步迭代将以x1替换基变量x5；(e)该线性规划问题具有无界解；(f) 该线性规划问题无可行解。表 16x1x2x3x4x5x3 dx4 2x5 34-1a2a1-5-3100010001cj - zjc1c2000P20 10. 判断下列说法是否正确：（a） 任何线性规划问题存在并具有唯一的对偶问题；（b） 对偶问题的对偶问题一定是原问题;（c） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之当对偶问题无可行解时，其原问题具有无界解；（d） 设分别为标准形式的原问题与对偶问题的可行解， 分别为其最优解，则恒有 （e） 若线性规划原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；（f） 已知 y为线性规划的对偶问题的最优解，若y0，说明在最优生产计划中第 种资源已完全耗尽；（g） 已知 y为线性规划的对偶问题的最优解，若y=0，说明在最优生产计划中第 种资源一定有剩余；（h） 若某种资源的影子价格等于 k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k ；（i） 应用对偶单纯形法计算时，若单纯形法中某一基变量 xi<0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；（j） 若线性规划问题中的 bi，cj 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；（k） 线性规划问题的最优解中 ，如一变量 xj 为非基变量，则在原问题中，无论改变它 在目标函数中的系数 cj 或在各约束中的相应系数 aij ，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。P31已知 线性规划问题；max z=10x1+5x2st. 3x1+4x295x1+2x28x1,x20用单纯形法求得最终表为表2-9所示：x1x2x3x4x2 3/2x1 101105/14-1/7-3/142/7cj - zj00-5/14-25/14试用灵敏度分析的方法判断： 目标函数系数 c1 或c2 分别在什么范围内变动，上述最优解不变；(a) 约束条件右端顶 b1 ,b2当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变；11 1998(b) 约束条件右端顶由 变为 时上述最优解的变化。P34 2.36 某厂生产,三种产品,分别经过A,B,C三种设备加工. 已 知生产单位各种产品所需的 设备台时,设备现有的加工能力及每件产品的预期利润见表2-13表 2-13设备能力（台·h）ABC1102142156100600300单位产品利润（元）1064(a) 求获利最大的产品生产计划;(b) 产品每件的利润增加到多大时才值得安排生产?如产品每件利润增加到50/6元,求最优计划的变化;(c) 产品的利润在多大范围内变化时,原最优计划保持不变;(d) 设备A的能力如为100+10 ,确定保持最优基不变的的变化范围；(e) 如有一新产品,加工一件需设备A,B,C的台时各为1,4,3h ,预期每件的利润为8元,是否值得安排生产；(f) 如何同规定该厂至少生产10件产品,试确定最优计划的变化.P39 10.判断下列说法是否正确：（a） 运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解；（b） 在运输问题中，只要任意给出一组含（m+n-1）个非零的xij，且满足xij=ai, xij=bi,就可以作为一个初始基可行解；（c） 表上作业法实质上就是求解运输问题的单纯刑法。（d） 按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且能找出惟一的闭回路；（e） 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；（f） 如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化；（g） 如果在运输问或转运问题模型中，Cij都是从产地I到销地j的最小运输费用，则运输问题同转运问题将得到相同的最优解；（h） 当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值。P43 3.7 某玩具公司分别生产三种新型玩具，每月可供量分别为1000件，2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同。又知丙百货商店要求至少供应C玩具1000件，而拒绝进A种玩具。求满足下述条件下使总盈利额为最大的供销分配方案。甲乙丙可供量ABC516124810911100020002000P47 3.16 如表3-20所示的运输问题中，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为5，4和3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。 销地 产地ABC产量123112243253204030销量302020P57 8.判断下列说法是否正确（a） 整数规划解的目标函数值一般优于其相应的线性规划问题的解得目标函数值；（b） 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界；（c） 用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝；（d） 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解；（e） 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；（f） 指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案；（g） 指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；（h） 求解0-1规划的隐枚举法是分枝定界法的特例；（i） 分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解得集合必须覆盖原问题的解。P62 5.12 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 人ABCDE甲乙丙丁2539342429382742312628364220402337333245P87 11.判断下列说法是否正确：（a） 图论中得图不仅反应了研究对象之间的关系，而且是真实图像的写照，因而对图中点与点的相对位置、点与点的连线的长短曲直等都要严格注意；（b） 在任一图G中，当点集V确定后，树图是G中边数最少的连通图；（c） 如图中某点vi有若干个相邻点，与其距离最远的相邻点vj,则边i,j必不包含在最小支撑树内；（d） 如图中从v1至各点均有惟一的最短路，则连接v1至其他各点的最短路再去掉重置部分，恰好构成该图的最小支撑树；（e） 求图的最小支撑树以及求图中的一点至另一点的最短路问题，都可以归结为求整数规划问题；（f） 求网络最大流的问题可归结为求解一个线性规划模型。P101 7.判断下列说法是否正确：（a） 网络图中任何一个结点都表示前一工序的结束和后一工序的开始；（b） 在网络图中只能有一个始点和一个终点；（c） 结点最早时间同最迟时间相等的点连结的线路就是关键路线；（d） 工序的总时差越，表明该工序在整个网络中的机动时间就越大；（e） 总时差为零的各项工序所组成的线路就是网络图的关键路线；（f） 工序的最早开始时间等于该工序箭头事项最早开始时间；（g） 直接费用变动率的值g越小，则每缩短单位作业时间所增加的直接费用就越小； 专心-专注-专业