运筹学复习题课件

1、运筹学复习运筹学F_02,第1章 线性规划及单纯形法,一、判断题 （1）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 正确。 （2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会变小。 （3）线性规划问题的每一个基解对应可行域的一个顶点。 错误。线性规划的基本定理之一为：线性规划问题的基本可行解对应于可行域的顶点。,（4）如线性规划问题存在可行域，则可行域一定包含坐标的原点。 错误。 如果约束条件中有一个约束所对应的区域不包含坐标的原点，则即使有可行域，也不

2、包含坐标的原点。 （5）取值无约束的变量 ，通常令 = ，其中 0, 0，在用单纯形法求得的最优解中，有可能同时出现 0, 0。 错误。 （6）用单纯形法求解标准型式的线性规划问题时，与 0对应的变量都可以被选作入基变量。 正确。,（7）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 正确。 （8）一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 正确。 人工变量一般是为取得对应的初始基基向量而引入的，它一旦成为出基变量，其地位已被对应的入基变量取代，删除单纯形表中该变量及相应列的数字，不影响计算结

3、果。 （9）线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。 错误。 如果 =1 =1 ，则命题正确，否则，不正确。,（10）对一个有n个变量，m个约束的标准型的线性规划问题，其可行域顶点恰好是 个。 错误。 （11）线性规划问题的可行解如为最优解，则该可行解一定是基本可行解。 错误。 唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可行域的顶点。 （12）若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。 错误。 如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，这样就

4、有了无穷多的最优解。,(13)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。 错误。 二、用单纯形法求解标准型式的线性规划问题时，如何判别该问题具有唯一最优解、无穷多最优解、无界解或者无可行解？ 当所有 0，且非基变量的检验数0，有 0，有无界解 对于所有 0，而基变量中含非0人工变量，有无可行解。,三、下表中给出某一求极大化问题的单纯形表，问表中 1 ， 2 ， 1 ， 2 ，为何值时以及表中变量属哪一种类型时有： （a）表中解为唯一最优解； （b）表中解为无穷多最优解之一； （c）表中解为退化的可行解； （d）下一步迭代将以 1 替换 5 ； （e）该线性规划问题具有无界解

5、； （f）该线性规划问题无可行解。,答案： （a）d0， 1 0， 1 0，且 4 = 3 2 ； （d） 1 0， 1 2 ， 4 3 2 ； （e） 2 0， 1 0； （f） 5 为人工变量，且 1 0， 2 0。,四、已知某线性规划问题单纯形法迭代时得到中间某两步的单纯形表如下表所示，试将表中空白处的数字填上。,检验数：(0,0,0,-45/41,-24/41,-11/41),第2章 线性规划的对偶理论,一、判断题 （1）任何线性规划问题存在并具有唯一的对偶问题。 正确。 （2）对偶问题的对偶一定是原问题。 正确。 （3）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之

6、，当对偶问题无可行解时，其原问题具有无界解。 错误。 （4）设 和 分别是标准形式（P,max）和（D,min）的可行解， 和 分别为其最优解，则恒有 = b b。 正确。,（5）若原问题有可行解，则其对偶问题有可行解。 错误。 （6）若原问题无可行解，则其对偶问题也一定无可行解。 错误。 （7）若原问题有最优解，则其对偶问题也一定有最优解。 正确。 （8）若原问题和对偶问题均存在可行解，则两者均存在最优解。 正确。 （9）如果原问题的约束方程Ax b，变成Ax b，则其对偶问题的唯一改变就是非负的y0变成非正的 y0。 正确。,（10）已知 为线性规划的对偶问题的最优解的第i个分量，若 0，

7、说明在最优生产计划中第i种资源已经耗尽。 正确。 （11）已知 为线性规划的对偶问题的最优解第i个分量，若 =0说明在最优生产计划中第i种资源已经耗尽且一定有剩余。 错误。 （12）用对偶单纯形法求解线性规划的每一步，在单纯形表检验数行与基变量列对应的对偶问题与原问题的解代入各自的目标函数得到的值始终相等。 正确。,（13）如果某种资源的影子价格为k，在其它条件不变的前提下，当该种资源增加5个单位时，相应的目标函数值将增加5k。 错误。 （14）应用对偶单纯形法计算时，若单纯形表中某一基变量 0，又 所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。 错误。 （15）若线性规划问题

8、中的 、 值同时发生变化，反应到最终单纯形表中，不会出现原问题和对偶问题均为非可行解的情况。 错误。,（r）在线性规划问题的最优解中，如果某一变量 为非基变量，则在原来问题中，无论改变它在目标函数中的系数 或在各约束中的相应系数 ，反应到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。 正确。,二、已知线性规划问题： （a） 写出其对偶问题； （b）已知原问题用两阶段法求解时得到的最终单纯形表如下,试写出其对偶问题的最优解。,答案 (a)对偶问题 (b) y 1 =0， y 2 =1， y 3 =3 4 的检验数=0 y 1 =0 1 =14 2 y 2 + y 3 =5 3

9、=-4 3 y 2 + y 3 =6,三、,四、某厂生产、三种产品，分别经过A、B、C三种设备加工，已知生产单位各种产品所需要的设备台时，设备的现有加工能力以及每件产品的预期的利润如下表： （a）求获利最大的产品计划？ Maxz=10 1 +6 2 +4 3 1 + 2 + 3 100 10 1 + 4 2 +5 3 600 2 1 + 2 2 +6 3 100 0，=1,2,3,最优单纯形表 因此，获利最大的产品生产计划为 100 3, 200 3 ,0,0,0,100 = 2200 3,（b）产品每件的利润增加到多大时才值得安排生产？如果产品的每件利润增加到50/6元，求最优计划的变化？

10、200 3 (见下页PPT) （c）产品的利润在多大范围变化时，原最优计划保持不变？ 6,15 （d）设备A的能力如为 100+10，确定保持最优基不变的的变化范围？ -4,5 （e）如有一种新产品，加工一件设备A、B、C的台时为1、4、3小时，预期每件的利润为8元，是否值得安排生产？ 检验数为正，值得生产 （f）如合同规定该厂至少生产10件产品，试确定最优的变化？ 去掉生产10件产品的资源，重新计算，结论为95/3,175/3,10,第3章 运输问题,一、判断题 （1）在运输问题中，只要任意地给出一组含m+n-1个非零的 ，且满足 =1 = ， =1 = ，就可以作为一个初始基本可行解。 错

11、误。 （2）表上作业法实质上就是求解运输问题的单纯形法。 正确。 （3）按最小元素法（或Vogel法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。 正确。,（4）如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 正确。 （5）如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化。 错误。 （6）如果运输问题单位运价表的全部元素乘上一个常数k（k0），最优调运方案将不会发生变化。 正确。,（7）用位势法求运输问题某一调运方案的检验数时，其结果可能同闭回路法求得的结果有异。 错误。 （8）

12、运输问题初始方案的基本要求:（m+n-1）个数字格，不存在全部以数字格为顶点的闭回路。 正确。,二、,不是最优，因为不是基可行解。,3.5 某造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本如表。 已知加班生产情况下每条货轮成本比正常生产时高出70万元，又知造出的货轮如当年不交货，每条货轮每积压一年将增加维护保养等损失为40万元。在签订合同时该厂已有两条积压未交互的货轮，该厂希望在第三年末在交完合同任务后能储存一条备用。 问该厂应如何安排计划，使在满足上述要求的条件下，使总的费用支出为最小。,设,为期初库存用于第 j 年交货的数量,为第

13、 i 年正常生产用于第 j 年交货的数量,为第 i 年加班生产用于第 j 年交货的数量,约束条件：,生产能力限制,需求限制,目标函数：,其中费用系数见下表：,产地：每年正常生产、加班生产及其库存 销地：每一年的需求,第4章 整数规划与分配问题,一、判断题 （1）整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值； 错误。 （2）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界； 正确。 （3）用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝。 错误。,（4）指派问题效率

14、矩阵的每个元素都乘上同一个常数k，将不影响最优指派方案； 错误。 （5）指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解； 正确。 （6）用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数。 错误。,（7）分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各个子问题解的集合必须覆盖原问题的解。 正确。 （8）一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解。 错误。,二、某科学实验卫星拟从下列仪器装置中选若干件装上，有关数据资料如下表：,三、,四、,五、,第5章 目标规划,一、判断题 （1）线性规划问题是目标规划问题

15、的一种特殊形式。 正确。 （2）正偏差变量取正值，负偏差变量应取负值。 错误。 （3）目标规划模型中，可以不包含系统约束（绝对约束），但必须包含目标约束。 正确。,（4）同一个目标约束中的一对偏差变量 、 + 至少有一个取值为零。 正确。 （5）目标规划的目标函数中，既包含决策变量，又包含偏差变量。 错误。 （6）只含目标约束的目标规划模型一定存在满意解。 正确。,（7）目标规划模型中的目标函数按问题性质要求分别表示为求min或求max。 错误。 （8）目标规划模型中的优先级 1 、 2 ，其中 较之 +1 目标的重要性一般为数倍至数十倍之间。 错误。 （9）下列表达式均不能用来表达目标规划模

16、型的目标函数：maxz= 1 1 + 2 2 ； minz= 1 1 2 2 ； minz= 1 1 + 2 （ 2 2 + ）。 正确。,二、,五、,C点,第6章 图与网络分析,一、判断题。 （1）图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中 点与点的相对位置、边的长短曲直等都要严格注意。 错误。 （2）在任一图G中，当点集V确定后，树图是G中边数最少的连通图。 正确。 （3）如图中某点 有若干个相邻点，与其距离最远的相邻点为 ，则边i,j必不包含在最小支撑树内。 错误。,（4）求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。 正

17、确。 （5）任一图中奇点的个数可能为奇数个，也可能为偶数个。 错误。 （6）任何n个节点，（n-1）条边的图一定是树图。 错误。,（7）一个具有多个发点和多个收点的求网络最大流的问题一定可以转化为求具有单个发点和单个收点的求网络最大流问题。 正确。 （8）作为增广链上的弧，如属正向弧一定有 。 错误。,第7章 计划评审方法和关键路线法,一、判断题。 （1）网络图中只能有一个始点和一个终点； 正确。 （2）网络图中因虚作业的时间为零，因此在各项时间参数的计算中可将其忽略。 错误。 （3）网络图中关键路线的延续时间相当于求图中从起点到终点的最短路。 错误。,（4）网络图中求关键路线的问题可表达为求

18、解一个线性规划模型； 正确。 （5）网络图中从一个事件出发如果存在多项作业，则其中用时最长的一项作业必包含在该网络图的关键路线内。 错误。 （6）一项非关键路线上的作业在其最早开始于最迟结束的时间段内均可任意安排。 错误。 （7）若一项作业的总时差为10d，说明任何情况下该项作业从开始到结束之间总有10d的机动时间。 错误。,（8）一个网络只存在唯一的关键路线。 错误。 （9）为了在最短时间内完成项目，其关键路线上作业的开始或结束时间不允许有任何延迟。 正确。 （10）网络关键路线上的所有作业，其总时差和自由时差均为零。 正确。 （11）任何非关键路线上的作业，其总时差和自由时差均不为零。 错误。,（12）若一项作业的总时差为零，则其自由时差一定为零。 正确。 （13）若一项作业的自由时差为零，则其总时差比为零。 错误。 （14）当作业时间用a,m,b三点估计时，m等于完成该项作业的期望时间。 错误。,第8章 动态规划,一、判断题。 （1）动态规划的