第6章 运输问题课件

第六章运输问题§1运输模型§2运输问题的计算机求解§3运输问题的应用§4*运输问题的表上作业法1第6章运输问题

问题的提出:

一般的运输问题就是要解决把某种产品（或原料、资源等）从若干个产地调运到若干个销地，在每个产地的供给量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。

§1运输模型2第6章运输问题

例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

§1运输模型3第6章运输问题

解：产销平衡问题：

总产量=总销量

设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

§1运输模型4第6章运输问题

MinZ=6x11+4x12+6x13+6x21+5x22+5x23

s.t.

x11

+x12+x13=200

x21+x22

+x23

=

300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）

§1运输模型5第6章运输问题§1运输模型一般运输模型：（1）A1、A2、…、Am

表示某物资的m个产地；

B1、B2、…、Bn

表示某物质的n个销地；（2）si

表示产地Ai的产量；

dj

表示销地Bj的销量；（3）cij

表示把物资从产地Ai运往销地Bj的单位运价。

xij表示从产地Ai运往销地Bj的运输量。（4）Z表示总的运输费用如果：

s1+s2+…+sm=d1+d2+…+dn

，

则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论产销平衡问题。6第6章运输问题

运输问题数据表

销地产地B1B2

…Bn产量A1A2┇Amc11c12

…c1nc21c22

…c2n┇┇┇┇cm1cm2

…cmns1s2┇sm销量d1d2

…dn

§1运输模型7第6章运输问题运输问题变量表§1运输模型

销地产地B1B2

…Bn产量A1A2┇Amx11x12

…x1nx21x22

…x2n┇┇┇┇xm1xm2

…xmns1s2┇sm销量d1d2

…dn

8第6章运输问题§1运输模型产销平衡运输问题的数学模型：

mnMinZ=∑

∑

cijxiji=1j=1n

s.t.∑

xij=sii=1,2,…,m

j=1m

∑

xij=djj=1,2,…,ni=1

xij≥0(i=1,2,…,m;j=1,2,…,n)在实际问题建模时，经常会出现如下一些变化（很值得关注）：

1）有时目标函数求最大，如求利润最大或营业额最大等；

2）产销不平衡时，可增加一个假想的产地（销大于产时）或销地（产大于销时），从而使得总产量＝总销量（因为计算机求解时需要保持是产销平衡的状态）。9第6章运输问题§2运输问题的计算机求解

例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？解：增加一个假想的销地B*4，由任意产地到该销地的单位运价为0，B*4的销量为100（600-500＝100）。10第6章运输问题§2运输问题的计算机求解

例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？

解：增加一个假想的产地A*3，由该产地到任意销地的单位运价为0，A*3的产量为150（650-500＝150）。11第6章运输问题§3运输问题的应用一、产销不平衡的运输问题

案例1、汽车客运公司有豪华、中档和普通三种型号的客车5辆、10辆和15辆，每辆车上均载客40人，汽运公司每天要送400人到B1城市，送600人到B2城市。每辆客车每天只能送一次，从客运公司到B1和B2城市的票价如下表所示：试建立平衡的运价表？甲（豪华）乙（中档）丙（普通）到B1城市（元/人）806050到B2城市（元/人）65504012第6章运输问题§3运输问题的应用

解：由于每辆车额定40人，所以到B1和B2两个城市各需要10辆车和15辆车。把豪华、中档和普通三种型号的客车看成是产地，把B1和B2两个城市看成是销地，总产量比总销量多出5，所以要假设一销地B*3。通过软件求解，甲每天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10车辆到B2城市，多余5辆，最大收入为Z=40（5×80+5×60+5×50+10×40）=54000（元）

销地产地B1B2B*3产量甲806505乙6050010丙5040015销量1015513第6章运输问题§3运输问题的应用

案例2、石家庄北方研究院有一、二、三共三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：

由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。14第6章运输问题§3运输问题的应用

解：根据题意，可把一区分成一区’（必须要满足供应）和一区’’（不需要一定满足），把三区分成三区’（必须要满足供应）和三区’’（不需要一定满足），作出产销平衡的单位运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。在计算机求解时，可把M设定成106或以上的数。

根据计算结果知道，一区只能得到2700吨煤，二区得到1000吨煤，三区只能得到1800吨。15第6章运输问题§3运输问题的应用

案例3、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设肥料效果相同，由三个化肥厂到四个地区的单位运价有关数据如下表：

试求总费用为最低的化肥调拨方案。16第6章运输问题§3运输问题的应用

解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把假想产地到1’、2和4’的相应单位运价设定为M；而最高要求与最低要求的差额按需要安排，因此把假想产地到1’’、3和4’’的相应单位运价设定为0。

4’’的销量50是考虑问题本身适当取的数据，是根据产销平衡要求（实际总产量减去最低需求量，即：160-110＝50），确定4’’的销量为50。D的产量50也是根据产销平衡要求适当取的数据，即最大总需求量减去实际总产量（210-160＝50）。17第6章运输问题§3运输问题的应用二、生产与储存问题案例4、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。18第6章运输问题§3运输问题的应用解：设xij为第i季度生产交付第j季度销售的柴油机数目，那么应满足：交货：生产：

x11=10x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个产地的产量；把第j季度销售的柴油机数目看作第j个销地的销量。把单位成本加上单位储存、维护等费用看作单位运价，可构造下列产销平衡的单位运价表：19第6章运输问题§3运输问题的应用目标函数：MinZ=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44D看作是每个季度多余的产能，实际并不生产，所以单位运价为0。20第6章运输问题§3运输问题的应用

案例5、光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：

已知上年末库存103台绣花机（需要在今年上半年全部售完），如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产2个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？21第6章运输问题§3运输问题的应用解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地

1）1--6月份合计生产能力为743台（包括上年末储存量103台），销量为707台（包括6月份预留的库存80台）。由于计算机计算时，需要是产销平衡的单位运价表，则假想一销地，其销量为36台；

2）一台绣花机的单位成本＝单位生产费用＋单位运输费＋单位仓储费*仓储月数，把单位成本看成是单位运价；

3）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况；

4）6月份的需求除70台销量外，还要80台预留库存，其需求应为70+80=150台；

5）上年末库存103台（需要运至分厂库房），只有仓储费和运输费，把它列为第0行，由于必须要售清，所以到虚拟地的单位运价为M；22第6章运输问题§3运输问题的应用产销平衡的单位运价表：23第6章运输问题§3运输问题的应用

用“管理运筹学”软件解得的结果是：1—6月最低生产费用为8307.5万元，每月的销售安排如下表所示：24第6章运输问题

案例6、某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：假定各航线使用的船只相同，各城市间的航程天数如下：

每条船每次装卸货时间各需1天，问该公司至少应配备多少条船？§3运输问题的应用三、转运问题25第6章运输问题

所需船只包括两个部分：载货船、调度船。

(1)载货航行需要的船只数：3*19+2*5+9+15=91条航线航行天数装卸天数合计航班数载货船数1234173713222219591532115710915§3运输问题的应用问题的核心是：如何使调度船的数量为最少？亦即如何按照最近原则调度船只。26第6章运输问题(2)各港口调度需要的船只数（即每天为以后载货准备的空载船只数）：各港口每天船只的余缺数为：§3运输问题的应用ABCDEF1213

调度中心27第6章运输问题§3运输问题的应用为使配备船只数尽可能少，建立如下运输模型：设xij表示每天从港口i调往港口j的空船数，则cijxij就表示i→j航线上周转的空船数，∑cijxij表示所有航线周转的空船总数。235141317783调度需要的船只数为：2+5+13+17+3=40条共计最少需要船只：91+40=131条28第6章运输问题§3运输问题的应用案例7、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：

假设：

1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；

2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；

3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。29第6章运输问题§3运输问题的应用分厂、中转站和销售公司之间的单位运价如下表所示：试求总费用为最低的调运方案？？？30第6章运输问题

解：设xij

为从i到j的运输量，可得到有下列特点的线性规划模型：目标函数：

MinZ=所有可能的运输费用（单价运价与运输量乘积之和）约束条件：对产地（分厂）i：输出量-输入量=产量对转运点（中转站）：输入量-输出量=0

对销地（销售公司）j：输入量-输出量=销量§3运输问题的应用31第6章运输问题§3运输问题的应用

把此转运问题转化为一般运输问题：1、把三个分厂、四个中转站和四个销售公司都同时看作是输出地（相当于运价表中的产地）和输入地（相当于销地）；

2、单位运价表中不可能方案的单位运价取作M，自身对自身的单位运价为0；

3、Ai：输出量为20（最大可能的发出量），输入量为13、16和11（最大可能的接受量），其中20为各点可能变化的最大流量；

Ti

：输入量、输出量均为20（最大可能的发出量和接受量）；

Bj：输出量分别为17、14、15和14（最大可能的发出量，因为各个销地要保留本身必要的销量），输入量为20（最大可能的接受量），其中20为各点可能变化的最大流量。

4、对于最优方案，其中xii

为自身对自身的运量，实际上不进行运作。32第6章运输问题§3运输问题的应用

扩大后的运输问题产销平衡的单位运价表：33第6章运输问题§3运输问题的应用经过计算机求解得：发点A1A2A3T1T2T3T4B1B2B3B4A1132000000050A2014000006000A300110000