运筹学习题集(第二章).doc

判 断 题 判断正误，如果错误请更正 第二章 线形规划的对偶理论 原问题第i个约束是=约束,则对偶变量yi=0. 互为对偶问题,或则同时都有最优解,或则同时都无最优解. 原问题有多重解,对偶问题也有多重解. 对偶问题有可行解,原问题无可行解,则对偶问题具有无界解. 原问题无最优解,则对偶问题无可行解. 设X,Y分别为｛minZ=CX｜AX=b,X=0｝ 和｛maxw=Yb｜YA=C,Y=0｝ 的可行解,则有(1)CX=Yb; (2)CX是w的上界; (3)当X,Y为最优解,CX=Yb; (4)当CX=Yb 时,有YXs+YsX=0; (5)X为最优解且B是最优基时,则Y=CBB-1是最优解; (6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优解. 7.原问题与对偶问题都可行,则都有最优解. 8.原问题具有无界解,则对偶问题可行. 9.若X,Y是原问题与对偶问题的最优解.则X=Y. 10.若某种资源影子价格为0,则该资源一定有剩余. 11影子价格就是资源的价格. 12.原问题可行对偶问题不可行,可用对偶单纯形法计算. 13.对偶单纯形法比值失效说明原问题具有无界解. 14.对偶单纯形法是直接解对偶问题的一种解法. 15.减少一个约束,目标值不会比原来变差. 16.增加一个约束,目标值不会比原来变好. 17增加一个变量, 目标值不会比原来变差. 18.减少一个非基变量, 目标值不变. 19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。 选择题 在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。 第二章 线性规划的对偶理论 如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划 A约束条件相同 B目标函数相同 C最优目标函数值相同 D以上结论都不对 对偶单纯形法的最小比值规则是为了保证 A使原问题保持可行 B使对偶问题保持可行 C逐步消除原问题不可行性 D逐步消除对偶问题不可行性 互为对偶的两个线性规划问题的解存在关系 A若最优解存在，则最优解相同 B原问题无可行解，则对偶问题也无可行解 C对偶问题无可行解，原问题可能无可行解 D一个问题无界，则另一个问题无可行解 E一个问题无可行解，则另一个问题具有无界解 已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为 A—（λ1，λ2，……λn） B （λ1，λ2，……λn） C —（λn+1,λn+2,……λn+m）D（λn+1,λn+2,……λn+m） 原问题与对偶问题都有可行解，则 A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解 C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解 计算题 线性规划问题和对偶问题 2.1 对于如下的线性规划问题 min z = 3x1 + 2x2 +x3 s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、写出题目中线性规划问题的对偶问题； 2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解答：1、写出题目中线性规划问题的对偶问题； 解：max w = 15y1 + 9y2 + 8y3 s.t. y1 + 2y2 - y3 3 (1) y1 - y2 + 2y3 2 (2) y1 + y2 + 2y3 1 (3) y1 0、 y2 0、y3 0 2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解：先将原问题化成以下形式，则有 min z = 3x1 + 2x2 + x3 s.t. x1 + x2 + x3 + x4 = 15 (1) -2x1 + x2 - x3 + x5 = -9 (2) -x1 + 2x2 +2x3 +x6 = 8