运筹学第二章运输问题

第二章线性规划2.1 2.2 2.3 2.4 2.5 2.6线性规划模型与图解法单纯形法对偶问题与灵敏度分析运输问题线性整数规划线性目标规划

第二章线性规划

一、问题提出【问题描述】现有一批货物，从m个仓库运往n个销售地，Si处有货物ai吨，Dj处需货物bj吨，从Si到Dj的运价为cij元/吨。问如何安排，既可满足各销地需要，又使总运费最小？

天津大学管理与经济学部

第二章线性规划

运输问题网络图供应地C11

运价C12 C13

需求地

D1 b1D2 b2 D3 b3

a1供应量

S1C1n

a2am

S2

…

需求量

Sm

…

Dn天津大学管理与经济学部

bn

第二章线性规划

产销平衡表销地产地 S1 S2… Sm销量

D1

D2

…

Dn

产量

X11 X21… Xm1 b1

x12 x22… xm2 b2

……………

x1n x2n… xmn bn

a1 a2… am

a bi 1 i j 1

m

n

j

天津大学管理与经济学部

第二章线性规划

单位运价表销地产地 S1 S2… Sm D1 D2… Dn

C11 C12 C21 C22…… Cm1 Cm2

… C1n… C2n……… Cmn

天津大学管理与经济学部

第二章线性规划

二、运输问题的数学模型min z c11 x11 c12 x12 c1n x1n c 21 x 21 c 22 x 22 c 2 n x 2 n .......... . c m1 x m1 c m 2 x m 2 c m n x m n

ci 1 j 1

m

n

ij

xij

天津大学管理与经济学部

第二章线性规划

约束条件为：(1)供销平衡运输问题，则有

( 2)供过于求运输问题，则有

xj 1 m

n

ij

a i, i 1,2, , m bj, j 1,2, , n

xj 1 m i 1

n

ij

ai, i 1,2, , m j 1,2, , n

xi 1

ij

xij b j,

( 3 )供不应求的运输问题，则有

xj 1 m

n

ij

a i, i 1,2, , m bj, j 1,2, , n

xi 1

ij

天津大学管理与经济学部

第二章线性规划将约束方程式展开可得

x11 x1n x x 21 2n xm1 xmn x21 xm1 x11 x12 x22 xm 2 x1n x2 n xmn 约束方程式中共m*n个变量，m+n个约束。天津大学管理与经济学部

a1 a2 am b1 b2 bn

第二章线性规划

1 1 1 1 技术系数矩阵 A= 1 1 1 1 1 1 1 1 天津大学管理与经济学部

第二章线性规划

三、运输问题的解法求解平衡运输问题的表上作业法(1)确定一个初始的可行调运方案：最小元素法、西北角法、Vogel法 (2)判断当前可行方案是否最优：闭回路法、位势法 (3

)方案调整：闭回路法

天津大学管理与经济学部

第二章线性规划

【例12】产销平衡表销地 D1 D2 D3 D4产量

产地 S1 S2 S3销量

7 4 9 3 6 5 6

天津大学管理与经济学部

第二章线性规划

单位运价表销地 D1产地 S1 S2 S3 3 1 7 11 9 4 3 2 10 10 8 5 D2 D3 D4

天津大学管理与经济学部

第二章线性规划(1)确定初始调运方案(最小元素法)运价表 D1 S1 3 D2 11 D3 3 D4 10 S1 S2 S3 3 6 5 6 3

产销平衡表 D1 D2 D3 D47 4 9

S2S3

17

94

210

85

天津大学管理与经济学部

第二章线性规划运价表D1 D2 D3 D4

产销平衡表 D1 D2 D3 1 6 5 6 D4

S1S2 S3

31 7

119 4

32 10

108 5

S1S2 3 3

74

S3

9

天津大学管理与经济学部

第二章线性规划运价表 D1 S1 S2 S3 3 1 7 D2 11 9 4 D3 3 2 10 D4 10 8 5 S1

产销平衡表 D1 D2 D3 4 D4 7

S2S3

3 3 6

1 5 6

49

天津大学管理与经济学部

第二章线性规划运价表 D1 S1 S2 S3 3 1 7 D2 11 9 4 D3 3 2 10 D4 10 8 5 S1 S2 S3 3 3 6 6 5 6

产销平衡表 D1 D2 D3 4 1 D4 7 4 9

天津大学管理与经济学部

第二章线性规划运价表 D1 S1 S2 S3 3 1 7 D2 11 9 4 D3 3 2 10 D4 10 8 5 S1 S2 3

产销平衡表 D1 D2 D3 4 1 D4 7 4

S3 3

6 6 5

3 6

9

天津大学管理与经济学部

第二章线性规划运价表 D1 S1 S2 S3 3 1 7 D2 11 9 4 D3 3 2 10 D4 10 8 5 S1 S2 3

产销平衡表 D1 D2 D3 4 1 D4 3 7 4

S3 3

6 6 5

3 6

9

天津大学管理与经济学部

第二章线性规划

(1)确定初始调运方案(西北角法)D 1 S1 S2 S3销量 D2 3 1 7 D3 11 9 4 3 2 10 D4 10 8产量

3

4 2

74

2 3 5

6 6

5

920

3

6

天津大学管理与经济学部