运筹学复习题解答

运筹学复习 题及其解答

1:某药厂生产A、B、C三种药物，可供选择的原 料有甲、乙、丙、丁，四种原料的成本分别是5元， 6元，7元，8元。每公斤不同原料所能提取的各种药 物的数量(单位：克/公斤)见下表 药厂要求每天生产A药恰好100克，B药至少 530克，C药不超过160克，要求选配各种原料的数 量既满足生产需要，又使总成本最小，试建立此问 题的数学模型。

药名 原料 甲 乙

A 1 1

B 5 4

C 2 1

成本(元/kg) 5 6

丙 丁生产量

1 1 恰好 100克

5 6

1 2

7 8

至少 不超过 530克 160克

解：设 x1 , x2 , x3 , x4 分别为原料甲、乙、丙、丁的选配数量(单位：公斤),则有

min z =5x1+6x2+7x3+8x4s.t. x1+ x2+ x3+ x4 = 100

5x1+4 x2+5 x3+ 6 x4 5302x1+ x2+ x3+ 2 x4 160x1 , x2 , x3 , x4 0

2:用单纯形法求解线性规划问题 max z 2 x1 x2 x3 3 x1 x 2 x 3 60 x x 2 x 10 1 2 3 x1 x 2 x 3 20 x1 , x 2 , x 3 0 解：化为标准形为 max z 2 x1 x2 x3 60 3 x1 x2 x3 x4 x5 10 x1 x2 2 x3 x6 20 x1 x2 x3 x1 , x2 , x3 , x4 , x5 , x6 0

C CB 0 0 0 0 2 XB x4 x5 x6 B-1b 60 10 20 0

2 x1 3 1 1 2

–1 x2 1 –1 1 –1

1 x3 1 2 –1 1

0 x4 1 0 0 0

0 x5 0 1 0 0 -3 0

0 x6 0 0 1 0

20 10 20 7.5 5

所以，所求最优解为, x4 60 3 30 0 x1=15 , x2=5 , x1 10 1 0 x6 20 1 0 10 最优值为：z*=25 0 0 2 20 0 x4 30 0 10 2 -1 x1 x2 10 15 5 10 25 1 0 0

1 1 1 4 -5 x31 , 2x4=10 – =0 0 -3 1 –1 0 2 -3 1 –1 1 0 4 –5 1 0 1 –1 0 1 2 0 2 0.5 –3 -1.5 -1.5 0 0 0

,

0 x51 6=0 =x 0 -1 0 1 -2 0 0 –3 0 -1 -2 1 0 0.5 0.5 –1 1 -0.5 0.5 -1.5 -0.5

3 : 用大M法计算下列线性规划max z = 2x1 + 3x2

s.t.

2x1 + x2 x1 + 3x2 x1 + x2 x 1, x 2 0

16 20 = 10

解：化为标准形并加入人工变量为： max z = 2x1 + 3x2 - Mx5 - Mx6

s.t.

2x1 + x2x1 + 3x2 - x3

+ x4+ x5

= 16= 20

x1 + x2

+ x6= 10

x 1, x 2 , x 3 , x 4 , x 5 , x 6 0

cB 0 -m -m

xB B-1b x4 16 x5 20 x6 10

j

0 x4 28/3 3 x2 20/3 -m x6 10/3 j

2 3 x1 x2 2 1 1 (3) 1 1 2m 4m 5/3 0 1/3 1 (2/3) 02/3m 0

0 x3 0 -1 0 -m 1/3 -1/3 1/31/3m

0 x4 1 0 0 0 1 0 00

-m x5 0 1 0 0 -1/3 1/3 -1/3-4/3m

-m x6 0 16 0 20/3 1 10 0 0 28/5 0 20 1 50

0 x4 3 x2 2 x1

j

1 5 5 25

0 0 1 0

0 1 0 0

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

1 0 0 0

1/2 -5/2 1/2 -1/2 -1/2 3/2 -m -m

cj CB 0 XB x4 B-1b 6

2 x1 1

3 x2 0

0 x3 0

0 x4 1

-M x5 0

-M x6 -1

30 j

x2x3

1010 30

21 -1

10 0

01 0

00 0

0-1

13

-M -M-3

最优解为(0,10)T , 最优值为 z* = 30

4: 利用两阶段法计算下题： max z = 30x1+40x2 100x3 s.t. 4x1+3x2 x3=30 x1+3x2 x3=12 x1, x2 , x3 30 第一阶段：m in z = x4+ x5 s.t. 4x1+3x2 x3 + x4 =30

x1+3x2 x3

+ x5 =12

x1, x2 , x3 , x4 , x5 30

C CB 1 1 XB x4

x5 b 30 12

0 x1 4 1

0 x2 3 3

0 x3 1 1

1 x4 1 0

1 x5 0 1

10 4

10

j x4x2 j x1

42 184 18 6

5 31/3 6 1

6 01 0 0

2 0 1/3 0 0

0 10 0 1/3

0 11/3 1 1/3

612

0

0 j

x2

2 18

00

10

1/30

1/9 1

4/9 1

第二阶段：CB 30 40 j C XB x1 x2 b 6 2 240 30 x1 1 0 0 40 x2 0 1 0 100

x3 0 1/3 260/3

原规划最优解为： x1=6 , x2=2 , x3=0 , z =240

5:写出下面问题的对偶问题max z =2x1 2x2 +2x3+x4

s. t .

x1 +x2 + x3 + x4 122 x1 x2 +3 x3 = 7

x1

x3 + 4x4 3

x1 0 ,x3 0 , x2, x4 无约束

6 : 求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。销地

产地A1

B1 3

B2 11

B3 3

B4 12

产量 7

A2A3

17

94

210

85

49

销量

3

6

5

6

20

解：由差额法得初始运输方案销 B1 产 A1 A2 A3 销量 B2 B3 B4 产 B1 量 B2 B3 B4

差额0 1 1 0 1 2

2

5

7

3 11 3 12

163 6 5

33

4 9

17

9

2

8

4 5 4 10 5 5 1 1 3 4

6 20 2 2

差 额

最优性检验销

产A1 A2

B1 3

B2 11

B3 3

B4 12

ui 3 1

21 9 2

785

27 4

110

A3

9

12

-2

vj

0

6

0

7

所有的非基变量的检验数都大于零。所以所得运输方案为最优方案，最少运费为：

Z* = 2 3+5 3+1 1+3 8+6 4+3 5 = 857:求解下列运费最少的运输问题销地 产地 A1 A2 A3 销量B1 10 8 9 15 B2 5 2 3 20 B3 6 7 4 30 B4 7 6 8 35 产量 25 25 50 100

由伏格法(差额法)得：销 B1 产 A1 B2 B3 B4 产 量 B1 B2 B3 B4

差额 1 1 3

25 25 10 5

6

7 76 68

A2A3

2015

2 5 25 8 2

74 4

4 1 21 4 1

30 5 50 9

3

销量 15 20 30 35 100

1 1 1

2 1 2

差 额

最优性检验：由位势法得销地 产地 A1 A2 A3 B1 B2 10 8 B3 5 2 B4 6 7 7 6 ui

1 1

2

3 5

1 0 2

9

-1 2

3

4

8

vj

7

2

6

从表中可以看出，a32 的检验数小于零，

需要进行调整，得销地 产地

B1

B2

B3

B425

A1A2 A3 15 20 –5

5 +5 30 5 –5

+5

新的运输方案为

本文来源：https://www.bwwdw.com/article/8m24.html