第3章+线性规划(运输问题)

运筹学

第3章 运输问题线性规划续1

运筹学

主要内容

运输问题的特点及模型描述 网络图 线性规划模型 表上作业

表上作业法 平衡运输问题

不平衡运输问题

运筹学

一、运输问题的特点及模型

原问题：产地到销地之间运送货物的最佳 路径 特点：

多个产地和多个销地； 每个产地的产量不同，每个销地的销量也不同； 各产销两地之间的运价不同。

目标 合理组织调运，既满足各销地的要求，又使总

的运输费用(或里程、时间等)最小。3

运筹学

运输问题设有同一种货物从m个出发地1,2,…,m运往n个到 达地1,2,…,n。第i个出发地的供应量(Supply) 为si(si≥0),第j个到达地的需求量(Demand)为 dj (dj≥0)。 每单位货物从产地 i 运到销地 j 的运价为 Cij。求一个使总运费最小的运输方案。1出 发 地

2

3

…

n

供应

1 2 m

c11 c21 … cm1

成本 cij

c1n s1 c2n s2 … … cmn sm

需求

d1

到达地

dn

∑

运筹学

运输问题

引例：设某电视机厂有三个分厂，生产同 一种彩色电视机，供应该厂在市内的四个 门市部销售。已知三个分厂的日生产能力 分别是50,60,50台，四个门市部的日销 量分别为40,40,60,20台。从各个分厂 运往各门市部的运费如下表所示，试安排 一个运费最低的运输计划。

运筹学

单位：元/台 门市部

工厂1 2 3 需求量总计

19 7 6 40

212 3 5 40

39 7 9 60

46 7 11 20

供应量总计50 60 50 1606

运筹学

运输问题网络图供应地s1=509 12 9

运价

需求地1 d1=40

1

供 应 量

s2=60 s3=50

2

3

6 7 3 7 7 6 5 9 11

2

d2=40d3=60

需 求 量

3

4

d4=20

运筹学

运输问题线性规划模型 设xij为由第i个工厂运到第j个门市部的

电视机台数，cij为由第i个工厂运到第j 个门市部的运费，则原运输问题的线 性规划模型为：

运筹学

Min Z= 9x11 +12x12 +9x13 +6x14 +7x21 +3x22 +7x23 +7x24 +6x31 +5x32 +9x33 +11x34 x11 +x12 +x13 +x14 x21 s.t. x11 x12 x13 x14 +x21 +x22 +x23 +x24 +x22 +x23 +x24 x31 + x31 +x32 +x33 +x34 +x32 +x33 +x34 =50 =60 =50 =40 =40 =60 =20

供 应 地 约 束 需 求 地 约 束

xij ≥0

i= 1,2,3; j=1,2, 3,4

m×n个变量，m+n个条件

运筹学

cij

运输问题的表格表示1 1 2 9 X11 7 X21 3 X22 2 12 X12 7 X23 3 9 X13 7 X24 4 6 X14 60 50

xij供应量

3

6X31

5X32

9X33

11X34

50

需求量 40

40

60

20

运筹学

运输问题三类运输问题： 产销平衡： Si d ji 1m

m

n

j 1n

产大于销： Si d j i 1 j 1 产小于销： Si d ji 1 j 111

m

n

运筹学

运输问题产销平衡的运输问题模型令xij为 从i地运到j地的数量Min Z =

cij xiji 1 j 1n

n

n

(Cij≥0) (i= 1,2, ,m) (j= 1,2, ,n) 供应约束 需求约束

xj 1

ij

si

xij d ji 1

m

xij≥0,i=1,

1,…,m; j=1,2,…,n 由 cij、si、dj 组成的 (m+1)×(n+1) 矩阵称为运输矩阵12

运筹学

约束方程共有m+n个，由于∑si=∑dj,

因此约束方程只有m+n-1个方程是线性 独立的。因此运输问题的基本可行解 有m+n-1个分量。

运筹学

引例——方程组中方程的线性独立问题： x1+x2+x3=3 2x1+x2+x4=6 3x1+2x2+x3+x4=9 系数的增广矩阵为： 1 1 1 0 3 1 1 1 0 3 2 1 0 1 6 → 2 1 0 1 6 3 2 1 4 9 0 0 0 0 0 14

运筹学

运输问题产销不平衡的运输问题模型

产大于销时约束条件

产小于销时约束条件

xi 1

m

ij

dj

(j= 1,2,…,n)

xj 1m

n

ij

si (i= 1,2,…,m) d j (j= 1,2,…,n)

xj 1

n

ij

si (i= 1,2,…,m)

xi 1

ij

运筹学

不平衡的运输问题门市部 工 厂 1 2 1 2 3 供应量总 计

9 7

12 3

9 7

50 60

需求量总计

40

40

6016