好文档 - 专业文书写作范文服务资料分享网站

运筹学 线性规划的对偶理论复习题

天下 分享 时间: 加入收藏 我要投稿 点赞

4x1+2x3≥10 x1,x2,x3≥0

解:先将问题化为标准式

maxz'=?10x1?5x2?4x3+0x4+0x5st.  -3x1?2x2+3x3+x4 =?3   -4x1?2x3  +x5  =?10  xi(i=1,2,3,4,5)≥0

则原问题已化为关于基B 的典式, C CB0 0

XBX4X5

2 X1

3 X2

1 0 X3

X4

0 X50 1 0

-3 -100 B

取初始正则基 B = (p4 p5) = I

-3 -2 -4 0

3 1 -2 0 -4 0 0 1 1 0 0 0

检验数 -10 -5 0

X4

-9 -2 2

0

3/2 -18-1/25 -2

20

-4 X3

检验数 -2 -5 -10 X1-4 X3

1 0

2/9

0 -1/9 -1/62

-4/9 1 2/9 -1/61 -41/9 0 -2/9 -7/324

检验数 0

可得原问题的最优解为:

Tx*=(2,0,1,0,0),Z*=?24,Z=24,y*=(2/9,7/3),w*=24.

(2) minz=2x1+3x2+4x3 s.t. x1+2x2+x3≥3 2x1?x2+3x3≥4

x1,x2,x3≥0

将问题化为:

11

maxz'=?2x1?3x2?4x3

st.  ?x1?2x2?x3+x4   =?3  -2x1+x2?3x3  +x5  =?4  xi(i=1,2,3,4,5)≥0C CB

XB

3 2 X1

X2

1 X3-1 -3 -4

0 X41 0 0 1 0 0

0 X50 1 0

-3 -4 B

0 X40 X5

-1 -2 -21

检验数 -2 -3 0 X43 X1

0 -5/21/2 1 -1/2 3/2

-1

-1/2 -1 -1/2 2 -1

250 2/5

检验数 0 -4 2 X23 X1

0 1 1 0

-1/5 -2/5 1/5

14/10 -1/5 -4/1011/5 -9/5 -8/5 -1/5 -28/5

检验数 0 0

x*=(11/5,2/5,0)T; Z'*=?28/5; Z*=28/5

(3) minz=2x1+x2 s.t. 3x1+x2≥3

4x1+3x2≥6 x1+2x2≤3 x1,x2≥0

解:

(3)maxz'=?2x1?x2

st.  -3x1?x2+x4   =?3  -4x1?3x3  +x5  =?6    x1+2x2    +x6 =3  xi(i=1,2,3,4,5,6)≥0

12

C CB0 0 0

XBX4X5X6

3 X1

5 X2

0 0 X3

X4

0 X50 1 0 0 0

0X600100

B

-3 -1 -4 0 1

2

0 1 -30 0 0 0 0 0 1 1 0 0 0 0 0

-3 -6 3 -3 2 3 1 2/32 2

检验数 -2 -1 0 0 0

X4X3X6

-3

-1

4/3 0 1

2

-1/300 0

100

检验数 -2 -1 -2 X10 0

X3X6

1 0 0

1/3 0 -1/3 0

-4/9 1 4/9 -1/305/3 0 1/3 0 -1/3 0 -2/3 0

10

检验数 0

(4) minz=3x1+2x2+x3 s.t. x1+x2+x3≤6

x1+x3≥4 x2?x3≥3

xj≥0(j=1,2,3)

解:化为:

maxz'=?3x1?2x2?x3

st.  x1+x2+x3+x4   =6   -x1?x3  +x5  =?4=?3   ?x2+x3    +x6   xi(i=1,2,3,4,5,6)≥0

13

C CB

XB

-3 -2 -10 0 0 b X1

X2

X3

X4X5

X6

0 X40 X50 X6

1 1 1 1 0 0 6 -1 0 -10 1 0 -40 -1 1 0 0 1 -3

检验数 -3 -2 -10 0 0 0 X4-1 X30 X6

0 1 0 1 1 0 2 1 0 1 0 -1 0 4 -1-1 0 0 1 1 -7

检验数 -2 -2 0 0 -1 0 0 X4-1 X3-3 X1

0 1 0 1 1 0 2 0 -11 0 0 1 -31 1 0 0 -1 -1 7

检验数 0 0 0 0 -3 -2 0 X4-2 X2-3 X1

0 0 1 1 1 1 -10 1 -10 0 -1 3 1 0 1 0 -1 0 4

检验数 0 0 0 0 -3 -2 由表知,此题无可行解。

13、已知线性规划问题

maxz=3x1+8x2 s.t.

cj cBxB3 x10 x4x28

检验数 3

8

表2-3 0

0 0 1 0 0

0 -2 10 1

x11 0 0 0

x20 0 1 0

x31/2-3 0 -3/2

x4 x5

b

100 500 350

2x1+4x2≤1600 6x1+2x2≤1800 x2≤350 x1,x2≥0

-2 -3100

用单纯形法求解时得最终单纯形表如表2-3所示.

14

(1)要保持现有最优解不变,分别求c1,c2的变化范围; (2)要保持现有最优解不变,分别求b1,b2,b3的变化范围; (3)当b3变为500时,求新的最优解. 解:

(1)由表知,C1C2为基变量的系数

??3/2?

∴ΔC1?=max?+?=?3

?1/2???2?

ΔC1+=min?+?=1

??2?∴C1∈[0,4]

??2?

ΔC2?=max?+?=?2

?1??3/2?

ΔC2+=min?+?=∞

0??

∴C2∈[6,+∞)

(2)参见教材P67的方法求之 (3) ∵b3=500?[300,400]   ∴最优解将发生变化;

Δb=(0,0,150)

T

?1/20?2??0???300????=?1500? 0∴Δb'=B-1Δb=??3110??????

?001??150??150???????

C CB

XB

3 X11 0 0

8 0 X2X3

0 0 b X4X5

3 X10 X48 X2

0 1/2 0 -2-200 0 -3 1 0

1 10 2000 0 1 500

检验数 0 0 X50 X4

0 -3/2 0 -2

-1/2 0 -1/4 0 1 100 5

0 -1/2 1 0 1000

15

运筹学 线性规划的对偶理论复习题

4x1+2x3≥10x1,x2,x3≥0解:先将问题化为标准式maxz'=?10x1?5x2?4x3+0x4+0x5st.  -3x1?2x2+3x3+x4 =?3  -4x1?2x3  +x5  =?10  xi(i=1,2,3,4,5)≥0则原问题已化为关于基B的典式,CCB00XBX4X52X1
推荐度:
点击下载文档文档为doc格式
04o4d5exdp6c4rp7oypx5gf8x599ez00syj
领取福利

微信扫码领取福利

微信扫码分享