第6章运输问题

1、1,第六章 运 输 问 题,1运 输 模 型 2运输问题的计算机求解 3运输问题的应用 4*运输问题的表上作业法,2,问题的提出: 一般的运输问题就是要解决把某种产品（或原料、资源等）从若干个产地调运到若干个销地，在每个产地的供给量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,1运 输 模 型,3,例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各个销地每件物品的运费如下表所示， 问：应如何调运可使总运输费用最小？,1运 输 模 型,4,解： 产销平衡问题： 总产量 = 总销量 设

2、xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,1运 输 模 型,5,Min Z= 6x11+4x12+6x13+6x21+5x22+5x23,s.t. x11 + x12 + x13 = 200 x21 + x22 + x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0 (i=1、2；j=1、2、3）,1运 输 模 型,6,1运 输 模 型,一般运输模型： （1）A1、A2、Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地； （2）si 表示产地Ai的产量； dj 表示销地Bj 的销量

3、； （3）cij 表示把物资从产地Ai运往销地Bj的单位运价。 xij 表示从产地Ai运往销地Bj的运输量。 （4）Z 表示总的运输费用 如果： s1 + s2 + + sm = d1 + d2 + + dn ， 则称该运输问题为产销平衡问题；否则，称产销不平衡。 下面，首先讨论产销平衡问题。,7,运输问题数据表,1运 输 模 型,8,运输问题变量表,1运 输 模 型,9,1运 输 模 型,产销平衡运输问题的数学模型： m n Min Z = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i =

4、 1 xij 0 (i = 1,2,m ; j = 1,2,n) 在实际问题建模时，经常会出现如下一些变化（很值得关注）： 1）有时目标函数求最大，如求利润最大或营业额最大等； 2）产销不平衡时，可增加一个假想的产地（销大于产时）或销地（产大于销时），从而使得总产量总销量（因为计算机求解时需要保持是产销平衡的状态）。,10,2运输问题的计算机求解,例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个假想的销地B*4，由任意产地到该销地的单位运价为0， B*4的销

5、量为100（600-500100）。,11,2运输问题的计算机求解,例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个假想的产地A*3，由该产地到任意销地的单位运价为0， A*3的产量为150（650-500150）。,12,3运输问题的应用,一、产销不平衡的运输问题 案例1、汽车客运公司有豪华、中档和普通三种型号的客车5辆、10辆和15辆，每辆车上均载客40人，汽运公司每天要送400人到B1城市，送600人到B2城市。每辆客车每天只能送一次，从客运公司到B1

6、和B2城市的票价如下表所示： 试建立平衡的运价表？,13,3运输问题的应用,解：由于每辆车额定40人，所以到B1和B2两个城市各需要10辆车和15辆车。把豪华、中档和普通三种型号的客车看成是产地，把B1和B2两个城市看成是销地，总产量比总销量多出5，所以要假设一销地B*3。 通过软件求解，甲每天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10车辆到B2城市，多余5辆，最大收入为Z=40（580+560+550+1040）=54000（元）,14,3运输问题的应用,案例2、石家庄北方研究院有一、二、三共三个区。每年分别需要用煤3000、1000、2000吨，由河北临城

7、、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为： 由于需大于供，经院研究决定一区供应量可减少0-300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。,15,3运输问题的应用,解： 根据题意，可把一区分成一区（必须要满足供应）和一区（不需要一定满足），把三区分成三区（必须要满足供应）和三区（不需要一定满足），作出产销平衡的单位运价表： 这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。在计算机求解时，可把M设定成106或以上的数。 根据计算结果知道，一区只能得到2700吨煤，二区得到10

8、00吨煤，三区只能得到1800吨。,16,3运输问题的应用,案例3、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设肥料效果相同，由三个化肥厂到四个地区的单位运价有关数据如下表： 试求总费用为最低的化肥调拨方案。,17,3运输问题的应用,解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把假想产地到1、2和4的相应单位运价设定为M ；而最高要求与最低要求的差额按需要安排，因此把假想产地到1、3和4的相应单位运价设定为 0。 4的销量50是考虑问题本身适当取的数据，是根据产销平衡要求（实际总产量减去最低需求量，即：160-11050），确定 4的销量为 50。D的产

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

10、3 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个产地的产量； 把第 j 季度销售的柴油机数目看作第 j 个销地的销量。 把单位成本加上单位储存、维护等费用看作单位运价，可构造下列产销平衡的单位运价表：,20,3运输问题的应用,目标函数：Min Z= 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +1

11、1.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 D看作是每个季度多余的产能，实际并不生产，所以单位运价为0。,21,3运输问题的应用,案例5、光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 已知上年末库存103台绣花机（需要在今年上半年全部售完），如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产2个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排

12、1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？,22,3运输问题的应用,解： 这个生产存储问题可化为运输问题来做。 考虑：各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力为743台（包括上年末储存量103台） ，销量为707台（包括6月份预留的库存80台）。由于计算机计算时，需要是产销平衡的单位运价表，则假想一销地，其销量为36台； 2）一台绣花机的单位成本单位生产费用单位运输费单位仓储费*仓储月数，把单位成本看成是单位运价； 3） 1-6表示1-6月份正常生产情况， 1-6表示1-6月份加班生产情况； 4） 6月份的需求除70台销量外，还要80台预留库存，其需求

13、应为70+80=150台； 5）上年末库存103台（需要运至分厂库房），只有仓储费和运输费，把它列为第0行，由于必须要售清，所以到虚拟地的单位运价为M；,23,3运输问题的应用,产销平衡的单位运价表：,24,3运输问题的应用,用“管理运筹学”软件解得的结果是：16月最低生产费用为8307.5万元，每月的销售安排如下表所示：,25,案例6、某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：,假定各航线使用的船只相同，各城市间的航程天数如下：,每条船每次装卸货时间各需1天，问该公司至少应配备多少条船？,3运输问题的应用,三、转运问题,26,

14、所需船只包括两个部分：载货船、调度船。 (1)载货航行需要的船只数：3*19+2*5+9+15=91条,3运输问题的应用,问题的核心是：如何使调度船的数量为最少？ 亦即如何按照最近原则调度船只。,27,(2)各港口调度需要的船只数（即每天为以后载货准备的空载船只数）： 各港口每天船只的余缺数为：,3运输问题的应用,28,3运输问题的应用,为使配备船只数尽可能少，建立如下运输模型： 设xij表示每天从港口i调往港口j的空船数，则cijxij就表示 ij航线上周转的空船数，cijxij表示所有航线周转的空船总数。,2 3 5 14 13 17 7 8 3,调度需要的船只数为：2+5+13+17+3

15、=40条,共计最少需要船只：91+40=131条,29,3运输问题的应用,案例7、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表： 假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。,30,3运输问题的应用,分厂、中转站和销售公司之间的单位运价如下表所示： 试求总费用为最低的调运方案？,31,解：设 xij 为从 i 到 j 的运输量

16、，可得到有下列特点的线性规划模型： 目标函数： Min Z = 所有可能的运输费用（单价运价与运输量乘积之和） 约束条件： 对产地（分厂）i ：输出量 - 输入量 = 产量 对转运点（中转站）：输入量 - 输出量 = 0 对销地（销售公司）j ：输入量 - 输出量 = 销量,3运输问题的应用,32,3运输问题的应用,把此转运问题转化为一般运输问题： 1、把三个分厂、四个中转站和四个销售公司都同时看作是输出地（相当于运价表中的产地）和输入地（相当于销地）； 2、单位运价表中不可能方案的单位运价取作M，自身对自身的单位运价为0； 3、Ai：输出量为 20（最大可能的发出量）， 输入量为13、16和

17、11（最大可能的接受量），其中20为各点可能变化的最大流量； Ti ：输入量、输出量均为 20 （最大可能的发出量和接受量）； Bj： 输出量分别为17、14、15和14（最大可能的发出量，因为各个销地要保留本身必要的销量），输入量为 20（最大可能的接受量），其中20为各点可能变化的最大流量。 4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。,33,3运输问题的应用,扩大后的运输问题产销平衡的单位运价表：,34,3运输问题的应用,经过计算机求解得：,35,3运输问题的应用,各分厂到各销售公司的最佳运输方案为： A1A2：2 A1B3：5 A2B1：6 A3B2：3 A3B4：6 B1B2：3 总的运输费用为68 * 此题若没有中转站，则总的运输费用将达到85 *,36,4*运输问题的表上作业