(例题)运筹学-运输问题

Page:1

华东理工大学 工商经济学院

运筹学

QSC

Page:2

经典运输问题

销售商 生产能力 Boston Chicago St. Louis Lexington 供应商 (吨) Cleveland 3 2 7 6 5,000 Bedford 7 5 2 3 6,000 York 2 5 4 5 2,500 4,000 2,000 1,500 需求量(吨) 6,000 每吨运输成本(＄/吨)

华东理工大学 工商经济学院

运筹学

QSC

Page:3

网络表示

供应商

1

销售商

1 Boston

6,000

3 2 6 7 7

2 Chicago

5,000

Cleveland

4,000

2

5 2

6,000

Bedford

3 2

3 York

3

5 4 5

St. Louis

2,000

2,500

4 Lexington

1,500

QSC

华东理工大学 工商经济学院

运筹学

Page:4

线性规划模型

Min S. t.

Z=

3x 11 +2x 12 +7x 13 +6x 14 +7x 21 +5x 22 +2x 23 +3x 24 +2x 31 +5x 32 +4x 33 +5x 34 x 11 +x 12 +x 13 +x 14 x 21 +x 22 +x 23 +x 24 x 31 +x 32 +x 31 +x 21 x 11 +x 21 +x 31 +x 31 +x 33 +x 34

≤ 5000 ≤ 6000 ≤ 2500 = 6000 = 4000 = 2000 = 1500

x 11

x 11 x 11

+x 21

+x 21

+x 31

x ij

0 ,

华东理工大学 工商经济学院

运筹学

QSC

Page:5

运输问题线性规划的一般形式

Min z = cijxij

i 1 j 1 m n

st. 供应：

x

j 1

n

ij

si

i = 1,2, , m

需求：

x

i 1

m

ij

dj

j = 1,2, , n

i = 1,2, , m; j = 1, , n

QSC

x ij 0,

华东理工大学 工商经济学院 运筹学

Page:6

供求平衡问题的特征

s d

i 1 i j 1

m

n

j

基变量的个数=m+n-1

华东理工大学 工商经济学院

运筹学

QSC

Page:7

初始基本可行解的构造

华东理工大学 工商经济学院

运筹学

QSC

Page:8

西北角方法

Boston Chicago St. Louis Lexington 供应量 Cleveland 3 2 7 6 5,000

5000

0

Bedford

1000

7

4000

5

1000

2

1000

3

1500

6,000

1500

York 需求量

2 6,000

1000 0

5 4,000

0

4

5

2,500

5000 1000 0

2,000

1000 0

运筹学

1,500

华东理工大学 工商经济学院

QSC

Page:9

最小元素法

Boston Chicago St. Louis Lexington 供应量 Cleveland 3 2 7 6 5,000

1000

4000

1000 0

Bedford

2500

7 2

2500

5

2000

2

1500

3 5 1,500

0

4000 2500 0

6,000 2,500

York 需求量

5 4,000

0 0

4 2,000

6,000

3500 2500

华东理工大学 工商经济学院

运筹学

QSC

Page:10

运输问题的特殊解法 ——闭回路方法

检验数：非基变量增加一个单位引起的成本变化量

华东理工大学 工商经济学院

运筹学

QSC

Page:11

闭回路方法---例

Boston Chicago St. Louis Lexington 供应量 Cleveland 3 2 7 6 5,000 Bedford York 需求量 7 2 6,000 5 5 4,000 2 4 2,000 3 5 1,500 6,000 2,500

华东理工大学 工商经济学院

运筹学

QSC

Page:12

初始基本可行解：

基本可行解

Boston Chicago St. Louis Lexington 供应量 Cleveland 3 2 7 6 5,000 1000 4000 Bedford 7 5 2 3 6,000 2500 2000 1500 York 2 5 4 5 2,500 2500 6,000 4,000 2,000 1,500 需求量

华东理工大学 工商经济学院

运筹学

QSC

Page:13

检验数的计算：

闭回路

Boston Chicago St. Louis Lexington 供应量 Cleveland -1 3 2 +1 7 6 5,000 9 1000 4000 Bedfor