第6章--运输问题.ppt

数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵第六章第六章 运运 输输 问问 题题11运运 输输 模模 型型22运输问题的计算机求解运输问题的计算机求解33运输问题的应用运输问题的应用44*运输问题的表上作业法运输问题的表上作业法1 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 问题的提出问题的提出:一般的运输问题就是要解决把某种产品（或原料、资源等）从若干个产地调运到若干个销地，在每个产地的供给量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。11运运 输输 模模 型型2 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？11运运 输输 模模 型型3 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 解：产销平衡问题：总产量总产量 =总销量总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：11运运 输输 模模 型型4 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 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）11运运 输输 模模 型型5 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵11运运 输输 模模 型型一般运输模型：一般运输模型：（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 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 运输问题数据表运输问题数据表 销地 产地B1 B2 Bn产 量A1 A2 Amc11 c12 c1nc21 c22 c2n cm1 cm2 cmns1 s2 sm销 量d1 d2 dn11运运 输输 模模 型型7 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵运输问题变量表运输问题变量表11运运 输输 模模 型型 销地 产地B1 B2 Bn产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量d1 d2 dn8 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵11运运 输输 模模 型型产销平衡运输问题的数学模型：产销平衡运输问题的数学模型：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=1 xij 0 (i=1,2,m;j=1,2,n)在实际问题建模时，经常会出现如下一些在实际问题建模时，经常会出现如下一些变化变化（很值得关注）（很值得关注）：1）有时目标函数求最大，如求利润最大或营业额最大等；2）产销不平衡时，可增加一个假想的产地（销大于产时）或销地（产大于销时），从而使得总产量总销量（因为计算机求（因为计算机求解时需要保持是产销平衡的状态）解时需要保持是产销平衡的状态）。9 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵22运输问题的计算机求解运输问题的计算机求解 例例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个假想的销地B*4，由任意产地到该销地的单位运价为0，B*4的销量为100（600-500100）。10 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵22运输问题的计算机求解运输问题的计算机求解 例例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地物品的单位运价如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个假想的产地A*3，由该产地到任意销地的单位运价为0，A*3的产量为150（650-500150）。11 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用一、产销不平衡的运输问题一、产销不平衡的运输问题 案例案例1、汽车客运公司有豪华、中档和普通三种型号的客车5辆、10辆和15辆，每辆车上均载客40人，汽运公司每天要送400人到B1城市，送600人到B2城市。每辆客车每天只能送一次，从客运公司到B1和B2城市的票价如下表所示：试建立平衡的运价表？甲（豪华）乙（中档）丙（普通）到B1城市（元/人）806050到B2城市（元/人）65504012 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 解：由于每辆车额定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（元）销地 产地B1B2B*3产 量甲806505乙6050010丙5040015销 量1015513 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 案例案例2、石家庄北方研究院有一、二、三共三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0-300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。14 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 解：解：根据题意，可把一区分成一区（必须要满足供应）和一区（不需要一定满足），把三区分成三区（必须要满足供应）和三区（不需要一定满足），作出产销平衡的单位运价表：这里 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34取值为0。在计算机求解时，可把M设定成106或以上的数。根据计算结果知道，一区只能得到2700吨煤，二区得到1000吨煤，三区只能得到1800吨。15 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 案例案例3、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设肥料效果相同，由三个化肥厂到四个地区的单位运价有关数据如下表：试求总费用为最低的化肥调拨方案。16 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 解：解：根据题意，作出产销平衡与运价表：最低要求必须满足，因此把假想产地到1、2和4的相应单位运价设定为M；而最高要求与最低要求的差额按需要安排，因此把假想产地到1、3和4的相应单位运价设定为 0。4的销量50是考虑问题本身适当取的数据，是根据产销平衡要求（实际总产量减去最低需求量，即：160-11050），确定 4的销量为 50。D的产量50也是根据产销平衡要求适当取的数据，即最大总需求量减去实际总产量（210-16050）。17 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用二、生产与储存问题二、生产与储存问题 案例案例4、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。18 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用解：解：设 xij为第 i 季度生产交付第 j 季度销售的柴油机数目，那么应满足：交 货：生 产：x11 =10 x11+x12+x13+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 个销地的销量。把单位成本加上单位储存、维护等费用看作单位运价，可构造下列产销平衡的单位运价表：19 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用目标函数：Min Z=10.8 x11+10.95 x12+11.1 x13+11.25 x14+11.1 x22+11.25 x23+11.4 x24 +11.0 x33+11.15 x34 +11.3 x44 D看作是每个季度多余的产能，实际并不生产，所以单位运价为0。20 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 案例案例5、光明仪器厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：已知上年末库存103台绣花机（需要在今年上半年全部售完），如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产2个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？21 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用解：解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地各月生产与交货分别视为产地和销地 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 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用产销平衡的单位运价表：产销平衡的单位运价表：23 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 用“管理运筹学”软件解得的结果是：16月最低生产费用为8307.5万元，每月的销售安排如下表所示：24 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 案例案例6、某航运公司承担六个港口城市A、B、C、D、E、F间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：假定各航线使用的船只相同，各城市间的航程天数如下：每条船每次装卸货时间各需1天，问该公司至少应配备多少条船？33运输问题的应用运输问题的应用三、转运问题三、转运问题25 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 所需船只包括两个部分：载货船、调度船。所需船只包括两个部分：载货船、调度船。(1)载货航行需要的船只数：3*19+2*5+9+15=91条航线航行天数装卸天数合计航班数载货船数123417371322221959153211571091533运输问题的应用运输问题的应用问题的核心是：如何使调度船的数量为最少？亦即如何按照最近原则调度船只。26 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 (2)各港口调度需要的船只数（即每天为以后载货准备的空载船只数）：各港口每天船只的余缺数为：33运输问题的应用运输问题的应用ABCDEF121 3 调度中心27 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用为使配备船只数尽可能少，建立如下运输模型：设xij表示每天从港口i调往港口j的空船数，则cijxij就表示 ij航线上周转的空船数，cijxij表示所有航线周转的空船总数。2 3 514 13 177 8 3调度需要的船只数为：2+5+13+17+3=40条共计最少需要船只：共计最少需要船只：91+40=131条条28 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用案例案例7、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。29 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用分厂、中转站和销售公司之间的单位运价如下表所示：分厂、中转站和销售公司之间的单位运价如下表所示：试求总费用为最低的调运方案？试求总费用为最低的调运方案？30 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵 解：解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：目标函数：目标函数：Min Z=所有可能的运输费用（单价运价与运输量乘积之和）约束条件：约束条件：对产地（分厂）i ：输出量-输入量=产量 对转运点（中转站）：输入量-输出量=0 对销地（销售公司）j ：输入量-输出量=销量33运输问题的应用运输问题的应用31 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 把此转运问题转化为一般运输问题：1、把三个分厂、四个中转站和四个销售公司都同时同时看作是输出地（相当于运价表中的产地）和输入地（相当于销地）；2、单位运价表中不可能方案的单位运价取作M，自身对自身的单位运价为0；3、Ai：输出量为 20（最大可能的发出量），输入量为13、16和11（最大可能的接受量），其中20为各点可能变化的最大流量；Ti：输入量、输出量均为 20（最大可能的发出量和接受量）；Bj：输出量分别为17、14、15和14（最大可能的发出量，因为各个销地要保留本身必要的销量），输入量为 20（最大可能的接受量），其中20为各点可能变化的最大流量。4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。32 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用 扩大后的运输问题产销平衡的单位运价表：33 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用经过计算机求解得：经过计算机求解得：发点A1A2A3T1T2T3T4B1B2B3B4A1132000000050A2014000006000A3001100000306T1000200000000T2000020000000T3000002000000T4000000200000B1000000014300B2000000001400B3000000000150B400000000001434 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵33运输问题的应用运输问题的应用各分厂到各销售公司的最佳运输方案为：A1A2：2A1B3：5A2B1：6A3B2：3A3B4：6B1B2：3总的运输费用为68*此此题题若没有中若没有中转转站，站，则总则总的运的运输费输费用将达到用将达到85 *35 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵44*运输问题的表上作业法运输问题的表上作业法表上作业法是一种求解运输问题的特殊方法，可通过计算机软件求解，但在没有软件的情况下，我们要熟悉怎么能快速地找出接近最优的满意解。这里给大家介绍二个方法：最小元素法最小元素法和伏格尔法伏格尔法。其中，伏格尔法确定的解更接近最优解。其中，伏格尔法确定的解更接近最优解。36 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵采用就近避远的原则（最小费用优先分配），现举例详述其过程采用就近避远的原则（最小费用优先分配），现举例详述其过程：()12 ()5()3()3 ()3 10 4A、满意解、满意解最小元素法（最小元素法（1）44*运输问题的表上作业法运输问题的表上作业法37 数 据 模 型 与 决 策江 苏 大 学 MBA 课 程 主讲：赵观兵B、满意解、满意解 伏格尔法（伏格尔法（Vogel）采用规避风险的原则，现举例详述其过程：采用规避风险的原则，现举例详述其过程：销地销地产地产地B1B2B3B4产量产量行罚数行罚数1234A137645111A2223220A34385311销量销量332210列列罚罚数数11132214130045233224*4*运输问题的表上作业法运输问题的表上作业法38