运筹学胡运权第二版习题答案.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹学教程,School of Management,page,*,*,运筹学教程（第二版）习题解答,第1页,第二章习题解答,2.1 写出以下线性规划问题对偶问题。,第2页,第二章习题解答,第3页,第二章习题解答,第4页,第二章习题解答,第5页,第二章习题解答,第6页,2.2 判断以下说法是否正确，为何?,(1)假如线性规划原问题存在可行解，则其对偶问题也一定存在可行解；,答：不对！如原问题是无界解，对偶问题无可行解。,(2)假如线性规划对偶问题无可行解，则原问题也一定无可行解；,答：不对！道理同上。,第二章习题解答,第7页,(3)在互为对偶一对原问题与对偶问题中，不论原问题是求极大或极小，原问题可行解目标函数值一定不超出其对偶问题可行解目标函数值；,答：不对！假如原问题是求极小，结论相反。,(4)任何线性规划问题含有惟一对偶问题。,答：结论正确！,第二章习题解答,第8页,第二章习题解答,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,第9页,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),第10页,2.4 给出线性规划问题,(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)结果及依据对偶问题性质写出原问题最优解第二章习题解答,第11页,(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。,第二章习题解答,第12页,2.5 给出线性规划问题,(1)写出其对偶问题；(2)利用对偶问题性质证实原问题目标函数值z1。,第二章习题解答,第13页,(2)y,1,=y,3,=0,y,2,=1时对偶问题一个可行解，目标函数值为1，故原问题目标函数值小于等于1。,第二章习题解答,第14页,试依据对偶问题性质证实上述线性规划问题目标函数值无界。,2.6 已知线性规划问题,第二章习题解答,第15页,因为(1)和(4)是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。,解：x,1,=1,x,2,=x,3,=0是原问题可行解。原问题对偶问题为：,第二章习题解答,第16页,要求：(1)写出其对偶问题；(2)已知原问题最优解为X,*,=(2，2，4，0)，试依据对偶理论，直接求出对偶问题最优解。,2.7 给出线性规划问题,第二章习题解答,第17页,(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,第二章习题解答,第18页,2.8 已知线性规划问题A和B以下：,第二章习题解答,第19页,试分别写出y,i,同y,*,i,(i1，2，3)间关系式。,第二章习题解答,第20页,第二章习题解答,第21页,2.9 用对偶单纯形法求解以下线性规划问题。,第二章习题解答,第22页,第二章习题解答,第23页,要求：,(1),写出其对偶问题；,(2),用对偶单纯形法求解原问题；,(3),用单纯形法求解其对偶问题；,(4),对比,(2),与,(3),中每步计算得到结果。,2.10 考虑以下线性规划问题：,第二章习题解答,第24页,第二章习题解答,第25页,先用单纯形法求出最优解，再分析在以下条件单独改变情况下最优解改变。,解：最优解为x,1,=6,x,2,=x,3,=0,Z=12,2.11,已知线性规划问题：,第二章习题解答,第26页,第二章习题解答,第27页,2.12,给出线性规划问题,用单纯形法求解得最终单纯形表见下表：,第二章习题解答,第28页,项 目,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,试分析以下各种条件下最优解(基)改变：,第二章习题解答,第29页,第二章习题解答,第30页,第二章习题解答,第31页,2.13 分析以下线性规划问题中，当入改变时最优解改变，并画出Z(入)对入改变关系图。,第二章习题解答,第32页,第二章习题解答,第33页,第二章习题解答,第34页,第二章习题解答,第35页,第二章习题解答,第36页,第二章习题解答,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第37页,第二章习题解答,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,第38页,第二章习题解答,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,第39页,第二章习题解答,第40页,2.14 某厂生产A，B，C三种产品，其所需劳动力、材料等相关数据见,下,表,：,产品,资源,A,B,C,可用量,（单位）,劳动力,6,3,5,45,材料,3,4,5,30,产品利润（元/件）,3,1,4,第二章习题解答,第41页,要求：,(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,第42页,(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,第43页,(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,第44页,(4)假如劳动力数量不增，材料不足时可从市场购置，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。,答：由（1）可知材料对偶价格是0.6元，大于市场价格。故应该购进原材料进行生产。当购进原材料到达15时，利润到达最大值36。,第二章习题解答,第45页,2.15,已知线性规划问题：,当,t,1,=t,2,=0,时求解得最终单纯形表见下表：,第二章习题解答,第46页,(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,第二章习题解答,第47页,(2)当t,2,=0时，t,1,在什么范围内改变上述最优解不变；,答：,t,1,在-6,8之间变动时，最优解不变。,(3)当t,1,=0时，t,2,在什么范围内改变上述最优基不变。,答：,t,2,在-5/3,15之间变动时，最优基不变。,第二章习题解答,第48页,