运筹学第四章习题答案.ppt

、写出下列线性规划问题的对偶问题。、写出下列线性规划问题的对偶问题。（）min z=x1+x2+2x3 X1+2x2+3x32 2x1+x2x34 3x1+2x2+4x36 Xi0 i=1、2、3解：其对偶问题为：解：其对偶问题为：max w=2y1+4y2+6y3 y1+2y2+3y31 2y1+y2+2y31 3y1y2+4y32 y10 y2、y30 s.ts.t（2）max z=4x12x2+3x3x4 X1+x2+2x3+x47 2x1x2+2x3x4=2 X12x2+x43 X1、x30 x2、x4无符号约束解：其对偶问题为：解：其对偶问题为：Min w=7y12y23y3 y1+2y2+y34 y1y22y3=2 2y1+2y23 y1y2+y3=1 y10 y2无符号约束 y30s、ts、t4、已知线性规划问题：、已知线性规划问题：Max z=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0 j=1、2、3、4其对偶问题最优解为其对偶问题最优解为y1=1.2 y2=0.2,由对偶理论直接求出原问由对偶理论直接求出原问题的最优解。题的最优解。解：将解：将Y*=（1.2，0.2）代入对偶问题的约束条件：）代入对偶问题的约束条件：y1+2y21 y3=1.6 2y1+y22 y4=2.6 2y1+3y23 y5=3 3y1+2y24 y6=4 y1、y20s、ts.t求得求得:第一第一,第二约束为松约束第二约束为松约束,第三第三,第四约束是紧约束第四约束是紧约束.因此因此,由互补松弛条件由互补松弛条件,原问题最优解中原问题最优解中,x1*=0,x2*=0 y1*0,y2*0是松约束是松约束,故原问题的约束必为紧约束故原问题的约束必为紧约束,即原问题即原问题约束必为等式约束必为等式:X1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20即即:2x3+3x4=20 3x3+2x4=20解之得解之得:x3*=4 x4*=4 x*=(0,0,4,4)8.已知线性规划问题已知线性规划问题:Maxz=2x12x2+x3 x1+x2x3=4 x1+kx2x36 x10 x2无符号约束 x30的最优解是的最优解是X*=(5,1,0)T(1)求出求出K的值的值.(2)写出其对偶问题写出其对偶问题,并求对偶最优解并求对偶最优解.解解:对偶问题为对偶问题为:min=4y1+6y2 y1+y22 y1+ky2=2 y1y21 y1无符号约束 y20s.ts.t将原问题的最优解代入原问题目标函数得原问题的最优值为将原问题的最优解代入原问题目标函数得原问题的最优值为:252(1)+0=8由此可知其对偶问题的最优值也为由此可知其对偶问题的最优值也为8.即即:4y1+6y2=8 又由于原问题的最优解又由于原问题的最优解X1*0,X2*0是松约束是松约束,故对偶问题的约束故对偶问题的约束必为紧约束必为紧约束,即对偶问题的前两个约束必为等式即对偶问题的前两个约束必为等式:y1+y2=2 y1+ky2=2 由由解得解得y1*=2 y2*=0,即对偶问题的最优解为即对偶问题的最优解为Y*=(2,0)将将y1*,y2*的值代入的值代入式得式得k=1