运筹学基础-运输问题(1)

第三章 运输问题运输问题是线性规划问题的特例。是在几个供应点与几个 需求点之间，运输品种、规格、质量等相同的货物时，选择 最佳的运输方案，以达到总的运输费用最低或获利的利润最 大等目标 产地： 产地：货物发出的地点。 产量： 产量：各产地的可供货量。 销地： 销地：货物接收的地点。 销量： 销量：各销地的需求数量。 X Y Z A B C

运输问题就是研究如何组织调运，既满足各销地的需求， 又使总运费最小。

第一节 运输模型一、 运输问题的线性规划模型例1:某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其 一级承销商有4个，分布在城市B1、B2、B3、B4,已知各厂的 产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij,为 发挥集团优势，公司要统一筹划运销问题，求运费最小的调运 方案。销地 产地 A1 A2 A3 销量 2 B1 6 7 3 3 B2 3 5 2 1 B3 2 8 9 4 B4 5 4 7 产量 5 2 3

销地

运输问题的LP模型 运输问题的 模型

产地 A1 A2 A3 销量

B1

B2 6 7 3

B3 3 5 2

B4 2 8 9

产量 5 4 7 5 2 3

x11 x21 x312

x12 x22 x323

x13 x23 x331

x14 x24 x344

(1)决策变量：设从Ai到Bj的运输量为xij, 决策变量：设从A (2)目标函数 (2)目标函数

minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件 (3)约束条件：产量之和等于销量之和,故要满足： 约束条件： x11+x12+x13+x14=5 – 供应平衡条件 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 – 销售平衡条件 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4– 非负性约束xij≥0 (i=1,2,3;j=1,2,3,4) ;

运输问题举例 (续)例2:某公司下属三个工厂(甲厂、乙厂、丙厂)生产同类 产品，供应不同地区的3个城市(A城、B城、C城),工厂 的供应量、城市的需求量及工厂到不同城市的单件运费如 表，写出本例数学模型 产销大于销销地 产地 甲厂 乙厂 丙厂 需求量 A城 8元 元 4元 元 7元 元 5000 B城 6元 元 3元 元 4元 元 7500 C城 7元 元 5元 元 6元 元 7500 供量 6000 600010000

销地

运输问题的LP模型 运输问题的 模型

产地 甲厂 乙厂 丙厂 需求量

A城

B城

C城 6元 元

供量 7元 元 5元 元 6元 元 6000 6000 10000

x11 x21 x31

8元 元 4元 元 7元 元

x12 x22 x32

x13

3元 x23 元 4元 x33 元

5000

7500

7500

(1)决策变量：设从 厂到 地的供应量为 ij, 决策变量：设从i厂到 地的供应量为x 厂到j地的供应量为 (2)目标函数 (2)目标函数 minZ=8x11+6x12+7x13+4x21+3x22+5x23+7x31+4x32+6x33 (3)约束条件 (3)约束条件：产量之和大于销量之和,故要满足： 约束条件： x11+x12+x13≤6000 – 供应平衡条件 x21+x22+x23≤4000 x31+x32+x33≤10000 – 销售平衡条件 x11+x21+x31=5000 x12+x22+x32=7500 x13+x23+x33=7500– 非负性约束

xij≥0 (i=1,2,3;j=1,2,3,

4) ;

二、运输问题的表式模型 运价表销地 产地

B1 c11 c21 … cm1

B2 c12 c22 … cm2

… … … … …

Bn c1n c2n … cmn 单位运价

A1 A2 … Am

产销平衡表销地 产地 A1 A2 … Am 销地 xm1 b1 xm b2 … xmn bn B1 x11 x21 B2 x12 x22 … Bn x1n x2n

运量

产量 a1 a2 … am

运输模型表--合二为一求 xij=?销地 产地A1 A2 … Am B1 B2 … Bn 产量 a1 a2 … am

c11 x11 x21 c21 x12 x22 … cm1 xm1 xmb1

c12 c22 … cm2b2 …

… c1n x1n … c2n x2n … …

… cmn xmnbn

销地

三、 运输问题的三种类型产销平衡

∑ a = ∑bi =1 i j =1

m

n

jm n

min Z = ∑∑ cij xiji =1 j =1 n销地 产地 A1 A2 … Am 销地 xm1 b1 B1 x11 x21 … cm1 xm b2 … c11 c21 x22 … cm2 … … xmn bn B2 x12 c12 c22 … … x1n … x2n … cmn Bn c1n c2n a2 … am产量

∑xj =1 m i =1

ij

= ai , = bj ,

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

a1

∑x

ij

xij ≥ 0

产大于销

∑a > ∑bi =1 i j =1销地 产地 A1 A2 … Am 销地 B1 x11 x21 … c11 c21 x22 … B2 x12 c12 c22

m

n

j

min Z = ∑∑ cij xiji =1 j =1 n

m

n

… …

Bn x1n … x2n … … xmn … cmn c1n c2n

产量

∑xj =1 m

ij

≤ ai , = bj ,

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

a1 a2 … am

∑xi =1

ij

cm1 cm2 xm1 xm b1 b2 …

xij ≥ 0

bn

产小于销

∑ ai < ∑ b ji =1 j =1销地 产地 A1 A2 … Am 销地 xm1 b1 B1 x11 x21 … cm1 xm b2 … c11 c21 x22 … cm2 … … xmn bn B2 x12 c12 c22 … … x1n … x2n … cmn Bn c1n c2n

m

n

min Z = ∑∑ cij xiji =1 j =1 n产量

m

n

∑xj =1 m i =1

ij

= ai , ≤ bj ,

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

a1 a2 … am

∑x

ij

xij ≥ 0

第二节 运输问题的求解方法-表上作业法

表上作业法适合于产销平衡的运输问题 求解步骤： 求解步骤： 建立运输模型表 找出初始方案：(一般来说这个方案不是最优的) 最优性检验 方案调整与改进

一、 建立运输模型图例1:设有一采石公司，它有3个采石厂：W厂、X厂、Y厂，它们每 周的采石能力(供应量)如下：W厂56车/周， X厂82车/周， Y厂为 77车/周；三个采石厂每周的供应量总和为215车。该采石公司已与某 筑路公司订阅了供应石子的合同。筑路公司现有3个工程段：A段、B 段、C段；3个工程段每周的石子需要量如下：A段为72车/周，B段为 102车/周，C段为41车/周，三个工程段每周的石子需要量总和为215 车。现求一个最佳的运输方案，以达到运输费用最低的目的。销地 …… 此处隐藏：1961字，全部文档内容请下载后查看。喜欢就下载吧 ……