运筹学习题答案(第二章)2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹学教程,School of Management,page,*,*,运筹学教程（第二版）习题解答,第二章习题解答,2.1,写出下列线性规划问题的对偶问题。,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,2.2,判断下列说法是否正确，为什么,?,(1),如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；,答：不对！如原问题是无界解，对偶问题无可行解。,(2),如果线性规划的对偶问题无可行解，则原问题也一定无可行解；,答：不对！道理同上。,第二章习题解答,(3),在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；,答：不对！如果原问题是求极小，结论相反。,(4),任何线性规划问题具有惟一的对偶问题。,答：结论正确！,第二章习题解答,第二章习题解答,2.3,已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。,解：,l=1,k=0,h=-1/2,a=2,c=3,b=10,e=5/4,f=-1/2,d=1/4,g=-3/4,i=-1/4,j=-1/4,C,j,3,2,2,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,X,6,0,X,1,(b),1,1,1,1,0,0,0,X,2,15,(a),1,2,0,1,0,0,X,3,20,2,(c),1,0,0,1,C,j,Z,j,3,2,2,0,0,0,0,X,4,5/4,0,0,(d),(l),-1/4,-1/4,3,X,1,25/4,1,0,(e),0,3/4,(i),2,X,2,5/2,0,1,(f),0,(h),1/2,C,j,Z,j,0,(k),(g),0,-5/4,(j),2.4,给出线性规划问题,(1),写出其对偶问题；,(2),用图解法求解对偶问题；,(3),利用,(2),的结果及根据对偶问题性质写出原问题最优解。,第二章习题解答,(2),最优解是：,y,1,=-8/5,y,2,=1/5,目标函数值,-19/5,。,(3),由于,y,1,=-8/5,y,2,=1/5,都不等于零，原问题中的约束取等号。又上面第,4,个约束不等号成立，故,x,4,=0,，令,x,3,=0,就可以得到最优解：,x,1,=8/5,x,2,=1/5,。,第二章习题解答,2.5,给出线性规划问题,(1),写出其对偶问题；,(2),利用对偶问题性质证明原问题目标函数值,z,1,。,第二章习题解答,(2)y,1,=y,3,=0,y,2,=1,时对偶问题的一个可行解，目标函数值为,1,，故原问题的目标函数值小于等于,1,。,第二章习题解答,试根据对偶问题性质证明上述线性规划问题目标函数值无界。,2.6,已知线性规划问题,第二章习题解答,由于,(1),和,(4),是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。,解：,x,1,=1,x,2,=x,3,=0,是原问题的可行解。原问题的对偶问题为：,第二章习题解答,要求：,(1),写出其对偶问题；,(2),已知原问题最优解为,X,*,=(2,，,2,，,4,，,0),，,试根据对偶理论，直接求出对偶问题的最优解。,2.7,给出线性规划问题,第二章习题解答,(2),已知原问题最优解为,X,*,=(2,，,2,，,4,，,0),，,代入原问题，第,4,个约束不等式成立，故,y,4,=0,。,有由于,x,1,x,2,x,3,大于,0,，上面对偶问题前,3,个约束取等号，故得到最优解：,y,1,=4/5,y,2,=3/5,y,3,=1,y,4,=0,第二章习题解答,2.8,已知线性规划问题,A,和,B,如下：,第二章习题解答,试分别写出,y,i,同,y,*,i,(i,1,，,2,，,3),间的关系式。,第二章习题解答,第二章习题解答,2.9,用对偶单纯形法求解下列线性规划问题。,第二章习题解答,第二章习题解答,要求：,(1),写出其对偶问题；,(2),用对偶单纯形法求解原问题；,(3),用单纯形法求解其对偶问题；,(4),对比,(2),与,(3),中每步计算得到的结果。,2.10,考虑如下线性规划问题：,第二章习题解答,第二章习题解答,先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。,解：最优解为,x,1,=6,x,2,=x,3,=0,Z=12,2.11,已知线性规划问题：,第二章习题解答,第二章习题解答,2.12,给出线性规划问题,用单纯形法求解得最终单纯形表见下表：,第二章习题解答,项 目,2,3,1,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,2 X,1,6,1,0,-1,4,-1,3 X,2,1,0,1,2,-1,1,C,j,Z,j,0,0,-3,-5,-1,试分析下列各种条件下最优解,(,基,),的变化：,第二章习题解答,第二章习题解答,第二章习题解答,2.13,分析下列线性规划问题中，当入变化时最优解的变化，并画出,Z(,入,),对入的变化关系图。,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,C,j,3,2,5,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,X,6,2,X,2,5,-1/4,1,0,1/2,-1/4,0,5,X,3,30,3/2,0,1,0,1/2,0,0,X,6,10,2,0,0,-2,1,1,C,j,Z,j,-7,0,0,-1,-2,0,第二章习题解答,C,j,3,2,5,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,X,6,2,X,2,5-,-1/4,1,0,1/2,-1/4,0,5,X,3,30+,3/2,0,1,0,1/2,0,0,X,6,10-3,2,0,0,-2,1,1,C,j,Z,j,-7,0,0,-1,-2,0,第二章习题解答,C,j,3,2,5,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,X,6,2,X,2,15-7/4,1/4,1,0,0,0,1/4,5,X,3,30+,3/2,0,1,0,1/2,0,0,X,4,3/2,-5,-1,0,0,1,-1/2,-1/2,C,j,Z,j,-7,0,0,-1,-2,0,第二章习题解答,2.14,某厂生产,A,，,B,，,C,三种产品，其所需劳动力、材料等有关数据见,下,表,：,产品,资源,A,B,C,可用量,（单位）,劳动力,6,3,5,45,材料,3,4,5,30,产品利润（元,/,件）,3,1,4,第二章习题解答,要求：,(1),确定获利最大的产品生产计划；,答：最优生产计划为：,x,1,=5,x,2,=0,x,3,=3,Z=27,；,第二章习题解答,项 目,3,1,4,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,3 X,1,5,1,-1/3,0,1/3,-1/3,4 X,3,3,0,1,1,-1/5,2/5,C,j,Z,j,0,-2,0,-1/5,-3/5,(2),产品,A,的利润在什么范围内变动时，上述最优计划不变；,答：产品,A,的利润在,2.4,，,4.8,内变动，生产计划不变,(-3/5,9/5,),；,第二章习题解答,项 目,3+,1,4,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,3+,X,1,5,1,-1/3,0,1/3,-1/3,4 X,3,3,0,1,1,-1/5,2/5,C,j,Z,j,0,/3,-2,0,-,/3,-1/5,/3,-3/5,(3),如果设计一种新产品,D,，,单件劳动力消耗为,8,单位，材料消耗为,2,单位，每件可获利,3,元，问该种产品是否值得生产,?,答：增加新产品,D,，,最优解为,x,1,=0,x,2,=0,x,3,=5,x,6,=2.5 Z=27.5,第二章习题解答,项 目,3,1,4,0,0 3,C,B,基,b,X,1,X,2,X,3,X,4,X,5,X,6,3 X,1,5,1,-1/3,0,1/3,-1/3,2,4 X,3,3,0,1,1,-1/5,2/5 -4/5,C,j,Z,j,0,-2,0,-1/5,-3/5 1/5,(4),如果劳动力数量不增，材料不足时可从市场购买，每单位,0.4,元。问该厂要不要购进原材料扩大生产，以购多少为宜。,答：由（,1,）可知材料的对偶价格是,0.6,元，大于市场价格。故应该购进原材料进行生产。当购进的原材料达到,15,时，利润达到最大值,36,。,第二章习题解答,2.15,已知线性规划问题：,当,t,1,=t,2,=0,时求解得最终单纯形表见下表：,第二章习题解答,(1),确定,c,l,，,c,2,，,c,3,，,a,ll,，,a,12,，,a,13,，,a,2l,a,22,和,b,1,b,2,的值；,解：,a,11,=0,a,12,=1,a,13,=2,a,21,=3,a,22,=-1,a,23,=1,c,1,=6,c,2,=-2,c,3,=10,项 目,c,1,c,2,c,3,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,c,1,X,4,5/2,0,1/2,1,1/2,0,c,2,X,5,5/2,1,-1/2,0,-1/6,1/3,C,j,Z,j,0,-4,0,-4,-2,第二章习题解答,(2),当,t,2,=0,时，,t,1,在什么范围内变化上述最优解不变；,答：,t,1,在,-6,8,之间变动时，最优解不变。,(3),当,t,1,=0,时，,t,2,在什么范围内变化上述最优基不变。,答：,t,2,在,-5/3,15,之间变动时，最优基不变。,第二章习题解答,16,题,2.44,为答案,