运筹学判断题

1、复习思考题第一章11判断下列说法是否正确：（a）图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。正确。（b）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。正确。这里注意：增加约束，可行域不会变大；减少约束，可行域不会变小。（c）线性规划问题的每一个基解对应可行域的一个顶点。错误。线性规划的一个基本定理为：线性规划问题的基本可行解对应于可行域的顶点。（d）如线性规划问题存在可行域，则可行域一定包含坐标的原点。错误。如果约束条件中有一个约束不包含坐标的原点，则即使有可行域，也不包含坐标的原点。（e）取值无约束的变量，通常令，其中

2、，在用单纯形法求得的最优解中，有可能同时出现。错误。由于，因此， 中至多只有一个是下的基变量，从而中至多只有一个取大于零的值。（f）用单纯形法标准型的线性规划问题时，与对应的变量都可以被选作入基变量。正确。如表1-1，取为入基变量，旋转变换后的目标函数值相反数的新值为：即旋转变换后的目标函数值增量为，由于，只要就能保证，满足单纯形法基变换后目标函数值不劣化的要求。表1-1cj ck cBxBb （） （） -z-（） （）（g）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。正确。假定单纯形法计算中，比值至少有两个不同的值。对表1-2，设表1-2cj c

3、k cBxBb （） （） （） （）-z- 如果取为出基变量，则有。（h）单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数值得到最快的增长。错误。假设存在正检验数，其中最大者为，取为入基变量，参考（f），可知旋转变换后的目标函数值增量为，无法肯定目标函数值得到了最快的增长。（i）一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 人工变量一般是以初始基基向量的地位引入的，它一旦出基，其地位已被对应的入基变量取代，删除单纯形表中该变量及相应列的数字，不影响计算结果。（j）线性规划问题的任一可行解都可以用全部基可行解的线性组

4、合表示。错误。对可行域非空有界，上述说法中线性组合改为凸组合就是正确的；对可行域无界，很明显，说法不正确。(k)若和分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中和为任意正的实数。错误。如果增加约束，说法正确。（l）线性规划用两阶段法求解时，第一阶段的目标函数通常写为（为人工变量），但也可以写为，只要所有均为大于零的常数。正确。由于所有，所有，因此等价于，说法正确。（m）对一个有个变量，个约束的标准型的线性规划问题，其可行域顶点恰好是个。错误。约束个数应该是个；如果为约束组约束个数（系数矩阵的行数），则可行基的最大数目为，由于线性规划问题的基本可行解对应于可行域的顶点，因此

5、说法不对。（n)单纯形法的迭代计算过程是从一个可行解转到目标函数值更大的另一个可行解。错误。迭代计算前后的解是基本可行解；据（h），旋转变换后的目标函数值增量为，由于，只要故，不排除的可能。（o）线性规划问题的可行解如为最优解，则该可行解一定是基本可行解。错误。唯一最优解时，最优解是可行域顶点，对应基本可行解；无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是可行域的顶点，。（p）若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。错误。如果在不止一个可行解上达到最优，它们的凸组合仍然是最优解，这样就有了无穷多的最优解。(q) 线性规划可行域的

6、某一顶点若其目标函数值优于相邻所有顶点的目标函数值，则该顶点处的目标函数值达到最优。错误。不妨考虑以下两种情形：线性规划问题可行域无界图1-1中的例1-1说明了说法不成立。该线性规划问题可行域有界设是某线性规划问题可行域的一个顶点，且其目标函数值优于相邻所有顶点（）的目标函数值，如果不是最优解，则设最优解为，这时有：。其中为可行域的第个顶点，为可行域顶点的数目。又有：，矛盾；或，则与均优于，与是顶点矛盾。这就说明了是最优点。x1x2OAB551010PZ=0Z=5图1-1 (r)将线性规划约束条件的号及好变换成号，将使问题的最优目标函数值得到改善。错误。设线性规划的第个约束为或，它们代表以为边

7、界面的半空间，显然，把上述约束中的不等号换成代号换成等号，可行域将变小，问题最优值变化的情况有下述三种：改善、不改善或劣化。(s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值。错误。图1-2中的例1-2说明了说法不成立。x1x2OAB551010PZ=10图1-2-5-2.5(t) 一个企业利用3种资源生产5种产品，建立线性规划模型求解到的最优解中，最多只含有3种产品的组合。错误。对例1-4的求解，说明了说法错误。例1-4cj0 -0.1 -0.2 -0.3 -0.8 -M -M -McBxBbx1 x2 x3 x4 x5 x6 x7 x8-M -M-Mx6x7x810010010

8、01 2 0 1 0 1 0 00 0 2 2 1 0 1 0 1 2 0 3 0 0 1100/1-100/3z300 M4M -0.2+4M -0.8+4M 0-0.1+3M -0.3+3M 0 0cj0 -0.1 -0.2 -0.3 -0.8 -M -McBxBbx1 x2 x3 x4 x5 x6 x7-M -M0x6x7x1200/3100100/30 5/3 -2/3 1 -1 1 00 0 2 1 0 1 1 1/3 2/3 0 1 0 0200/350-z500/3 M0 -0.2+4/3M -0.8 0-0.1+5/3M -0.3+3M 0cj0 -0.1 -0.2 -0.3

9、-0.8 -McBxBbx1 x2 x3 x4 x5 x6-M -0.30x6x4x150/350100/30 5/3 -5/3 0 -3/2 10 0 1 1 1/2 0 1 1/3 2/3 0 1 010-100z15+50/3 M0 0.1-53M -13/20-3/2 M-0.1+5/3M 0 0cj0 -0.1 -0.2 -0.3 -0.8cBxBbx1 x2 x3 x4 x5-0.1 -0.30x2x4x11050300 1 -1 0 -9/100 0 1 1 1/2 1 0 0 13/10-5030z160 0 -37/500 0cj0 -0.1 -0.2 -0.3 -0.8cB

10、xBbx1 x2 x3 x4 x5-0.1 -0.3-0.2x2x4x34020301 1 0 0 2/50 0 0 1 -4/5 0 1 0 13/1040-30z160 0 -37/500 0时，显然，说法不成立。(u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。错误。图1-4中的例1-5，说明了说法不对。x1x2OAB551010P，opt=maxZ=0Z=5图1-3P，opt=min(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系较少。 以标准型为例，系数矩阵，限定向量，价值向量，在迭代方法给定的前提下，它们的大小决定了迭代的工作量

11、。这里为约束组约束个数，为变量个数，不能简单地说迭代的工作量与的关系较少。第二章10判断下列说法是否正确：（a）任何线性规划问题存在并具有唯一的 对偶问题。正确。有原问题和对偶问题数学模型之间的对应关系易知说法成立。（b）对偶问题的对偶一定是原问题。正确。根据对偶问题的对称性，说法成立。（c）根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题具有无界解。错误。根据若对偶性，当原问题解无界时，其对偶问题无可行解；当对偶问题无可行解时，原问题解无界或无可行解。（d）设和分别是标准形式和的可行解，和分别为其最优解，则恒有。正确。根据弱对偶性，有，；据可行

12、解是最优解时的性质，有。综上，有。（e）若线性规划问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。错误。例2-1 如下：其对偶问题为 ；。原问题无穷多最优解，其对偶问题唯一最优解。（f）若原问题有可行解，则其对偶问题有可行解。错误。据弱对偶性，若原问题解无界，则其对偶问题无可行解。（g）若原问题无可行解，则其对偶问题也一定无可行解。错误。例2-2 如下：其对偶问题为例2-2无 可行解，其对偶问题有可行解。（h）若原问题有最优解，则其对偶问题也一定有最优解。正确。不妨讨论例2-3：其对偶问题为：设例2-3有最优解，为其最优基，令，则，即是其对偶问题的可行解，由于，因此是其对偶问题的最优解

13、。（i）若原问题和对偶问题均存在可行解，则两者均存在最优解。正确。设若原问题和对偶问题均存在可行解，又设不成立两者均存在最优解，则两者中至少有一个问题解无界。当两者中只有一个问题解无界时，另一个问题无可行解，与原问题和对偶问题均存在可行解矛盾，当两者均解无界时，据弱对偶性知，这是不可能的。（j）原问题决策变量与约束条件数量之和等于其对偶问题的决策变量与约束条件数量之和。错误。不妨讨论如下互为对偶的两个问题：和 原问题的决策变量为个，约束条件数量为个，决策变量数量与约束条件数量之和为个；其对偶问题的决策变量为个，约束条件数量为个，决策变量数量与约束条件数量之和为个；如果引入剩余变量，使约束组约束

14、成为等于型约束，这时候决策变量数量与约束条件数量之和为个。（k）用对偶单纯形法求解线性规划的每一步，在单纯形表检验数行与基变量列对应的原问题与对偶问题的解代入各自的目标函数得到的值始终相等。正确。在（h），我们已经看到了这种相等。（l）如果原问题的约束方程变成，则其对偶问题的唯一改变就是非负的变成非正的。正确。不妨讨论如下两个问题：和它们的对偶问题分别为：对，令，则有（m）已知为线性规划的对偶问题的最优解，若说明在最优生产计划中第种资源已经耗尽。正确。据互补松弛性，有。当，即。（n）已知为线性规划的对偶问题的最优解，若说明在最优生产计划中第种资源已经耗尽一定有剩余。错误。据互补松弛性，有，当，

15、不一定等于0。（o）如果某种资源的影子价格为，在其它条件不变的前提下，当该种资源增加5个单位时，相应的目标函数值将增加5。正确。设，为最优基。（p）应用对偶单纯形法计算时，若单纯形表中某一基变量，又所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解。错误。这时，问题无可行解，其对偶问题无可行解或解无界。（q）若线性规划问题中的，发生变化，反应到最终单纯形表中，不会出现原问题和对偶问题均为非可行解的情况。错误。对极大化线性规划问题求解时，如果单纯形表有时，问题解不可行；有时，其对偶问题解不可行。设，只要取适当值，就可以有，从而问题解不可行。又设为非基变量，则，当取适当值，就可以有，从而

16、其对偶问题解不可行。注意和的变化可以是独立的，所以本说法错误。（r）在线性规划问题的最优解中，如果某一变量为非基变量，则在原来问题中，无论改变它在目标函数中的系数或在各约束中的相应系数，反应到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。正确。如果为非基变量，则基矩阵中不包含，中不包含，因此的变化只能影响和，变化只能影响。第三章10判断下列说法是否正确：（a）运输问题是一种特殊的线性规划模型，因而求解的结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。错误。如果运输问题模型中没有相互矛盾的约束，有最优解；否则，无可行解。（b）在运输问题中，只要任

17、意地给出一组含个非零的，且满足，就可以作为一个初始基本可行解。错误。例3-1 表3-1说明了说法不对。表3-1 某产销平衡运输问题的一个可行解销地产地B1B2B3aiA1347A211A3314bj165（c）表上作业法实质上就是求解运输问题的单纯形法。正确。表上作业法的一个基本调运方案对应一个基本可行解；从当前基本调运方案变换到新的基本调运方案是在目标函数值不劣化的前提下进行的，包含了单纯形法中基变换和旋转变换两项内容；基本调运方案的检验通过检验数进行，检验数本质上与单纯形的检验数相同。因此可以认为，表上作业法实质上就是求解运输问题的单纯形法。（d）按最小元素法（或伏格尔法）给出的初始基可行

18、解，从每一空格出发可以找出而且仅能找出唯一的闭回路。正确。按最小元素法（或伏格尔法）给出的初始解是基本可行解，共有个基变量，对应的基向量组是线性无关组，因此基变量中不含闭回路。如果基变量加上任意一个空格，对应的系数列向量组是线性相关组，在基变量和添加的一个空格上可以得到闭回路；如果这种闭回路不唯一，不妨取其中两条，它们的相异部分形成一条闭回路，与基变量中不含闭回路矛盾。（e）如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数，最优调运方案将不会发生变化。正确。不妨设单位运价表第行元素分别加上一个常数，则新问题的目标函数为：注意新问题和原来问题的约束相同，常数不影响寻优，所以这两个问

19、题最优解相同。（f）如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数，最优调运方案将不会发生变化。错误。如，本说法正确；，且单位运价表中元素均大于零，最优调运方案将可能发生变化。（g）如果在运输问题或转运问题中，是从产地到销地的最小运输费用，则运输问题和转运问题将得到相同的最优解。错误。 最小运输费用与单位运价是不同的。（h）当所有产地的产量和所有销地的销量均为整数时，运输问题的最优解也为整数值。错误。 易知问题有整数最优解。如果不止一个整数最优解，它们的凸组合也是最优解，其中包含了许多非整数最优解。（i）如果运输问题单位运价表的全部元素乘上一个常数（），最优调运方案将不会发生变

20、化。正确。 易知，最优调运方案将不会发生变化。（j）产销平衡运输问题中含有个约束条件，但其中总有一个是多余的。错误。产销平衡运输问题中含有个约束条件。产销平衡运输问题约束方程组有个约束条件，其中系数矩阵为：因此，有。也就是一个方程是多余的。（k）用位势法求运输问题某一调运方案的检验数时，其结果可能同闭回路法求得的结果有异。错误。设为非基变量，按位势法的检验数计算式为又在基变量和空格中存在一条唯一的闭回路为：其中：。注意满足或满足所以这是闭回路法计算检验数的公式，与位势法的检验数计算公式相同。第四章5判断下列说法是否正确：（a）线性规划问题是目标规划问题的一种特殊形式。正确。目标规划模型的一般形

21、式为：线性规划模型的一般形式为：目标规划模型在、偏差变量取零，对决策值寻优的特例。（b）正偏差变量取正值，负偏差变量应取负值。错误。对目标约束，因而，说法不对。（c）目标规划模型中，可以不包含系统约束（绝对约束），但必须包含目标约束。错误。变量的非负要求就是绝对约束。（d）同一个目标约束中的一对偏差变量、至少有一个取值为零。正确。参见（b）。（e）目标规划的目标函数中，既包含决策变量，又包含偏差变量。正确。如求决策值尽可能大的目标函数可以用决策变量表达，也可以用该约束的偏差变量表达。（f）只含目标约束的目标规划模型一定存在满意解。错误。目标规划模型都有绝对约束。本说法可能是指不含第一组硬约束（

22、）的目标规划模型一定存在满意解，这时说法是正确的。（g）目标规划模型中的目标函数按问题性质要求分别表示为求或求。错误。一般，各级目标函数的优化方向都取为求极小化，这样是为了求解的方便，也是答案选择的依据。从原理上说，是可以有另外的，例如各级目标函数的优化方向都取为求极大化，等等。（h）目标规划模型中的优先级，其中较之目标的重要性一般为数倍至数十倍之间。错误。较之的重要性并不能以数倍至数十倍之间的程度来衡量，它是一种寻优意义上的优先权：对，在可行域上寻优；对，在的最优区域上寻优。第五章8判断下列说法是否正确： （a）整数规划的目标函数值一般优于其相应的线性规划问题的解的目标函数值。错误。整数规划

23、解除变量的整数要求后得到对应的松弛问题，两者可行域的关系如表3-1所示。表3-1序号可行域松弛问题D整数规划DI1空集2单点集3多点集据表3-1整数规划的目标函数值不会优于其相应的线性规划问题的解的目标函数值。（b）用分支定界法求解一个求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。正确。不妨假定是某整数规划问题按分支定界法求解时的第个子问题的可行解，按最优性衡量，如果它是最优解，那么其目标函数值等于最优值；如果它不是最优解，那么其目标函数值是最优值的一个下界。（c）用分支定界法求解一个求极大化的整数规划问题时，当得到多于一个可行解时，通常可以任取一个作为下界值，再进行比较剪枝。错误。应取这些可行解中的最大目标函数值作为下界值，再进行比较剪枝。（d）用割平面法求解整数规划问题时，构造的割平面可能切去一些不属于最优解的整数解。错误。设为当前可行基，中的第个分量不是整数，则有 移项得：上式等号左右两边都是整数，且，所以有割平面方程如下：很明显，所有整数解均满足，因此，没有割去任何整数解。（e）用割平面法求解纯整数规划时，要求包括松弛变量在内的所以变量必须取整数值。错误。考虑以下两种情况： ，松弛变量，。在当前可行基下：即使满足整数要求，也不能保证取整数值。，松弛