2021年运筹学中的运输问题讲义.ppt

本章内容要点
运输问题的基本概念及其各
种变形的建模与应用
指派问题的基本概念及其各
种变形的建模与应用
2021/1/26
1
运筹学中的运输问题
本章节内容






1 运输问题基本概念
2 运输问题数学模型和电子表格模型
3 各种变形的运输问题建模
4 运输问题应用举例
5 指派问题
6 各种变形的指派问题建模
2021/1/26
2
运筹学中的运输问题
 产大于销（总产量大于总销量）
运输问题 数学模型和电子表格模型
各种变形的建模
应用举例
 指派问题 数学模型和电子表格模型
本章主要内容框架图





 产销平衡（总产量等于总销量）
 
 销大于产（总产量小于总销量）
运输问题和指派问题
 平衡指派问题（总人数等于总任务数）
 
 各种变形的建模
2021/1/26
3
运筹学中的运输问题
1 运输问题



运输问题最初起源于人们在日常生活中把某
些物品或人们自身从一些地方转移到另一些
地方，要求所采用的运输路线或运输方案是
最经济或成本最低的，这就成为了一个运筹
学问题。
随着经济的不断发展，现代物流业蓬勃发展，
如何充分利用时间、信息、仓储、配送和联
运体系创造更多的价值，向运筹学提出了更
高的挑战。
要求科学地组织货源、运输和配送使得运输
问题变得日益复杂，但是其基本思想仍然是
实现现有资源的最优化配置。
2021/1/26
4
运筹学中的运输问题
1 运输问题基本概念


一般的运输问题就是解决如何把某种产品从若干个产地
调运到若干个销地，在每个产地的供应量和每个销地的
需求量已知，并知道各地之间的运输单价的前提下，如
何确定一个使得总的运输费用最小的方案。
平衡运输问题的条件：
1. 明确出发地（产地）、目的地（销地）、供应量（产量）、需求
量（销量）和单位成本。
2. 需求假设：每一个出发地都有一个固定的供应量，所有的供应量
都必须配送到目的地。与之类似，每一个目的地都有一个固定的
需求量，整个需求量都必须由出发地满足。即“总供应＝总需
求”。
3. 成本假设：从任何一个出发地到任何一个目的地的货物配送成本
与所配送的数量成线性比例关系，因此成本就等于配送的单位成
本乘以所配送的数量（目标函数是线性的）。
2021/1/26
5
运筹学中的运输问题
1 运输问题基本概念

例1 某公司有三个加工厂A1、A2、A3生产某产品，每日
的产量分别为：7吨、4吨、9吨；该公司把这些产品分别
运往四个销售点B1、B2、B3、B4，各销售点每日销量分
别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单
位产品运价如表1所示。问该公司应如何调运这些产品，
在满足各销售点的需要量的前提下，使总运费最少？
表1 各工厂到各销售点的单位产品运价（元/吨）
B1
B2
B3
B4
产量（吨）
7
4
9
A1
A2
A3
销量（吨）
3
1
7
3
11
9
4
6
3
2
10
5
10
8
5
6
2021/1/26
6
运筹学中的运输问题
对于例1，其数学模型如下：
首先，三个产地A1、A2、A3的总产量为7＋4＋9＝20；四个
销地B1、B2、B3、B4的总销量为3＋6＋5＋6＝20。由于总产
量等于总销量，故该问题是一个产销平衡的运输问题。
(1)决策变量
设xij为从产地Ai运往销地Bj的运输量(i＝1,2,3;j=1,2,3,4)
（2）目标函数
本问题的目标是使得总运输费最小
Min z =3x11 + 11x12 + 3x13 + 10 x14
+ x21 + 9 x22 + 2 x23 + 8 x24
+ 7 x31 + 4 x32 + 10 x33 + 5 x34
2021/1/26
7
运筹学中的运输问题
（3）约束条件
①满足产地产量
（3个产地的产
品都要全部配
送出去）
②满足销地销量
（4个销地的产
品都要全部得
到满足）
③非负
2021/1/26
8
运筹学中的运输问题
2 运输问题数学模型和电子表格模型


运输问题是一种特殊的