运筹学 第四章习题答案

、写出下列线性规划问题的对偶问题。 （ ） min z=x1+x2+2x3 X1+2x2+3x32 2x1+x2 x34 3x1+2x2+4x36 Xi0 i=1、 2、 3解：其对偶问题为： max w =2y 1+4y2+6y3 y1+2y2+3y31 2y1+y2+2y31 3y1 y2+4y32 y10 y2、 y30 s.ts.t （ 2） max z=4x1 2x2+3x3 x4 X1+x2+2x3+x47 2x1 x2+2x3 x4= 2 X1 2x2+x4 3 X1、 x30 x2、 x4无 符 号 约 束解：其对偶问题为： Min w=7y1 2y2 3y3 y 1+2y2+y34 y1 y2 2y3= 2 2y1+2y23 y1 y2+y3= 1 y10 y2无 符 号 约 束 y30s、 ts、 t 4、已知线性规划问题：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）代入对偶问题的约束条件： y 1+2y21 y3=1.6 2y1+y22 y4=2.6 2y1+3y23 y5=3 3y1+2y24 y6=4 y1、 y20s、 t s.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解之得: x 3*=4 x4*=4 x*=(0,0,4,4) 8.已知线性规划问题:Maxz= 2x1 2x2+x3 x1+x2 x3=4 x1+kx2 x36 x10 x2无 符 号 约 束 x30的最优解是X*=(5, 1,0)T(1)求出K的值.(2)写出其对偶问题,并求对偶最优解.解:对偶问题为:min=4y 1+6y2 y1+y2 2 y1+ky2= 2 y1 y21 y1无 符 号 约 束 y20s.ts.t 将原问题的最优解代入原问题目标函数得原问题的最优值为: 2 5 2 ( 1)+0= 8由此可知其对偶问题的最优值也为 8.即:4y1+6y2= 8 又由于原问题的最优解X1* 0,X2* 0是松约束,故对偶问题的约束必为紧约束,即对偶问题的前两个约束必为等式: y1+y2= 2 y 1+ky2= 2 由解得y1*= 2 y2*=0,即对偶问题的最优解为Y*=( 2,0)将y1*,y2*的值代入式得k= 1