运筹学基础(第2版)何坚勇 第四章习题答案

运筹学基础(第2版)何坚勇

第四章习题

运筹学基础(第2版)何坚勇

4.2

已知线性规划问题 max z=3x1+2x2 s.t -x1+2x2 4 min f=4w1+14w2 +3w2 s.t -w1+3w2 +3w2 3 2w1+2w2 -w2 2 w1,w2 ,w2 0

3x1 +2x2 14x 1- x 2 3

x1,x2 0

运筹学基础(第2版)何坚勇

(2)

如果愿问题与对偶问题都有可行解，则 二者都有最优解。 由原题可见，下列解是原问题与对偶问 题的可行解。 X(0)=(0,0)T W(0)=(0,1,0)T

运筹学基础(第2版)何坚勇

4.3

min z=2x1-x2 +2x3 s.t -x1+x2 +x3 = 4 -x1+x2 -Kx3 6

X1 0,X2 0, X3无约束(0)=(-5,0,-1)T 最优解: X

先变成变量大于0

运筹学基础(第2版)何坚勇

写出符合4.18,4.11,4.06条件的标准型

min z=2x1-x2 +2x3 s.t -x1+x2 +x3 = 4

max z=-2x1+x2 -2x3s.t -x1+x2 +x3 = 4 -x1+x2 -Kx3 6 X1 0,X2 0, X3无约束 最优解: X(0)=(-5,0,-1)T

-x1+x2 -Kx3 6X1 0,X2 0, X3无约束

最优解:X(0)=(-5,0,-1)T

运筹学基础(第2版)何坚勇

写出对偶问题

令X’1 = -X1 max z=2x’1+x2 -2x3s.t x’1+x2 +x3 = 4 x’1+x2 -Kx3 6 X’1

min f=4w1+6w2s.t w1+w2 2 w1+w2 1 w1-kw2 = -2

0 ,X2 0, X3无约束

(0)=(5,0,-1)T 最优解: X’

w1无约束 ，w2 0

运筹学基础(第2版)何坚勇

写出目标等式和互补松紧条件

根据定理4.2.5, X(0)=(-5,0,-1)T

Z*= 2x’1+x2 -2x3 = 2×(5)-0 -2(-1)=12 f*=Z*= 4w1+6w2 =12 4.2.7 4.2.7 w1+w2 = 2

w1= 0 w2 = 2

运筹学基础(第2版)何坚勇

求解

代入w1-kw2 = -1 求得K=1

A

运筹学基础(第2版)何坚勇

4.4对偶问题

min f=20w1+20w2s.t w1+2w2 1 2w1+w2 2 2w1+3w2 3 3w1+2w2 4

max z=x1+2x2 +3x3 +4x3s.t x1+2x2 +2x3 +3x4 20 2x1+x2 +3x3 +2x4 20 X1 ,X2, X3 0无约束

w1 0,w2 0

运筹学基础(第2版)何坚勇

续

W*1=1.2 0 W*2=0.2 0 由互补松弛条件可得:x1+2x2 +2x3 +3x4 = 20 2x1+x2 +3x3 +2x4 = 20 (4.4.1)

运筹学基础(第2版)何坚勇

续

将W*1=1.2,W*2=0.2代入对偶问题的约 束条件。

w1+2w2 = 1.2+2 0.2=1.6 12w1+w2 = 2 1.2 +0.2 =2.6 2

2w1+3w2 =2 1.2 +3 0.2 =33w1+2w2 = 3 1.2 +2 0.2 =4

运筹学基础(第2版)何坚勇

由互补松弛条件定理可知

X*1=0,X*2=0 代入(4.4.1) 得 x1+2x2 +2x3 +3x4 = 202x1+x2 +3x3 +2x4 = 20 解得: x*3 = 4 x*4 = 4

(4.4.1)

原问题最优解:X*=(0,0,4,4)T

运筹学基础(第2版)何坚勇

4.5

min z=8x1+6x2 +3x3 +6x4s.t x1+2x2 +x4 3 3x1+x2 +x3 +x4 6

x3 +x4 23x1 +x3 2

Xj 0, j=1,2,3,4最优解: X(0)=(1,1,2 , 0)T

运筹学基础(第2版)何坚勇

化标准型max z=-8x1-6x2 -3x3 -6x4 s.t -x1-2x2 -x4 3 ( 4.5.1) -3x1-x2 -x3 -x4 6 -x3 -x4 2 -3x1 -x3 2 Xj 0, j=1,2,3,4 最优解: X(0)=(1,1,2 , 0)T

运筹学基础(第2版)何坚勇

写对偶问题 min f=3w1+6w2 +2w3 +2w4 s.t -w1-3w2 –w4 -8max z=-8x1-6x2 -3x3 -6x4 s.t -x1-2x2 -x4 3

-2w1-w2 -6-w1-w3 –w4 -3 -w1-w2 -w3 - 4 wi 0 I=1,2,3,4 ( 4.5.2)

-3x1-x2 -x3 -x4 6 4.5.1) -x3 -x4 2 -3x1 -x3 2

Xj 0, j=1,2,3,4

最优解: X(0)=(1,1,2 , 0)T

运筹学基础(第2版)何坚勇

互补松弛条件 最优解: X(0)=(1,1,2 , 0)T

即Xj 0,

j=1,2,3

s.t -w1-3w2 –w4 =-8-2w1-w2 = -6 ( 4.5.3)

-w1-w3 –w4 =-3