(第四章)运输问题和指派问题

1、第四章 运输问题 物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）你怎么去分析这类问题呢？想想看！1.实例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量及各产地运往各销地的单位运费如表所示。如何调运，使总运费最少？销地产地B1B2B3产量A1646200A2655300销量150150200500500单位运费 x11 x12 x13 x21 x22 x23 2.运输问题的说明需求假设： 每一个出发地都有一个固定的供应量，所有的供应量都必须配送

2、到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。 成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量 。整数解性质：只要它的供应量和需求量都是整数，任何运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。 3.该运输问题的线性模型 min z=6 x11+4 x12+6 x13+6 x21+5 x22+5 x23 s.t. x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x21=150 x12+ x22

3、=150 x13+ x23=200 xij04.推广为一般：收点B1B2Bn发量发点A1C11 x11C12x12 C1nx1na1AmCm1xm1Cm2xm2Cmn xmnam收量b1b2bnai =bj5.(平衡)运输问题的线性规划模型Min z=S.t.6.运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m+n)个。当m、n比较大时，若用单纯形法求解，计算工作是就相当大。运输问题是类特殊的线性规划问题，其特殊性体现在系数矩阵上，运输问题的系数矩阵A是0和1组成(0的个数远远大于1的个数)的稀疏阵，且r(A)=m+n-17.定理1：运输问题的任何一组基变量都由 m+n-1个变量组

4、成定理2：运输问题中m+n-1个变量构成基的充分必要条件是它不包含闭回路8.(平衡)运输问题的求解：表上作业法找一个初始基可行解;方法:最小元素法/Vogel近似法(VAM)检验,若所有的检验数都小于零,最优解已得,否则继续下一步;方法:位势检验法调整(实质是换基),得到一个新的基可行解,重复第二步.方法:闭回路法9.举例销地产地B1B2B3产量A1646 200A265 5300销量15015020050050015020050100第一步：找初始方案10.第二步：位势检验B1B2B3UiA1645 -10A264 -150Vj645以上所有检验数0，故初始方案已是最优方案不用进行第三步的调

5、整11.不平衡运输问题当总供应量总需求量时，称为不平衡运输问题不平衡运输问题的求解：先化为平衡的运输问题，再用表上作业法供求，虚设一个收点，收量为供求之差，各发点到该虚收点的单位运价为0供求，虚设一个发点，发量为供求之差，该虚发点到各收点的单位运价为012.运输问题的计算机求解用线性规划程序求解，输出部分信息多，但变量和约束输入较麻烦。用运输问题程序求解，只需输入产地个数、销地个数、各产地的产量、各销地的销量、各产地到各销地的单位运价。前例输入后，得到的最优运输方案为：销地产地B1B2B3产量A1501500200A21000200300销 运输问题的应用(一)配送问

6、题 东风电机公司接到上海一家商场(B1),青岛一家商场(B2),西安一家商场(B3)各一份订单,要求下月供应电机.B1的需求量为100台,B2的需求量为80台,而B3要求供应120台.该公司在北京和武汉设有两个仓库(A1,A2),预计A1,A2下月的库存量分别为200台和150台.已知每个仓库到每家商场运送1 台电机的费用如表所示.问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少? B1 B2 B3 A1 15 21 18 A2 20 25 1614.(二)短缺资源的分配问题石家庄北方研究院有三个区：一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由

7、河北、山西两处煤矿负责供应，这两处的煤矿的价格相同，煤的质量也基本相同，山西和河北两处煤矿能供应北方研究院的数量分别为4000、1500吨，由煤矿至北方研究院的单位运价（百元/吨)如表。由于供应不足，经院研究平衡决定一区供应量可减少0200吨，二区需要量应全部满足，三区供应量不少于1700吨。请提交一个总运费最低的调运方案。单位运价一区二区三区山西煤矿1.651.701.75河北煤矿1.601.651.7015.(三)生产与存贮问题某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不

8、交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。季度生产能力（台）单位成本（万元）2510.83511.13011.01011.316.(四)转运问题广州大连600400产地41332中转站供应量1234567817.P&G重新设计制造和配送体系 ：90S 成百上千个供应商 50多个产品类别 超过60个的工厂 15个配送中心 超过1000个的顾客群体 18.为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择，为每 一个产品种类解决相应的运输问题体现了从这 些工厂运送产品到配送中心或顾客区所需要的 配送成本是

9、多少。在找出最好的新生产和配送系统的过程之中解 决了许多这样的运输问题 北美工厂数减少了20%，并且公司每年节省了2 亿美元的税前费用 19.运输问题的扩展指派问题 现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂 。还有哪些这样的问题呢？想想看！20.实例有4 个工人,要指派他们分别完成4 项工作,每人做各项工作所消耗的时间如下表。要求1人只做1件事，如何指派使总的消耗时间最少?人 工作B1B2B3B4A115182124A219232218A32617

10、1619A41921231721.模型用0-1变量表示“是非”决策： 1，第i人去做第j件事xij 0，第i人不做第j件事min z=15x11+18 x12 +21 x13+24 x14 + 19x21+ 23 x22+ 22x23 +18x24 +26x31 +17x32 + 16x33 + 19 x34 +19x41 +21x42 +23x43 +17x44 s.t. x11+x12+x13+x14 =1 (A1只能干一件事) x21+x22+x23+x24 =1 (A2只能干一件事) x31+x32+x33+x34 =1 (A3只能干一件事) x41+x42+x43+x44 =1 (A

11、4只能干一件事) x11+x21+x31+x41 =1 (B1只能由一个人干) x12+x22+x32+x42 =1 (B2只能由一个人干) x13+x23+x33+x43 =1 (B3只能由一个人干) x14+x24+x34+x44 =1 (B4只能由一个人干) xij 0或122.指派问题的一般描述有n 个人A1, A2, An,要分派去做n件事B1, B2 Bn,要求每一件事都 必须有一个人去做,而且不同的事由不同的人去做.已知每个人Ai做每件事Bj的效率(如劳动工时或成本,或创造的价值等)为Cij,应如何进行指派(哪个人做哪件事),才能使 工作效益最好(如工时最少,或成本最低,或创造的

12、价值最大)? 指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形.23.指派问题的一般模型min（max） z=S.t.24.指派问题的变形人的数量任务的数量人的数量任务的数量，一般模型中前面的约束xij=1改为xij1。由于某种原因，不能指派某个人做某件事如A1由于技能不达标，不能做B3，只须在一般模型中去掉x13变量。多重指派：一个人可以被分派做几件事，则一般模型中前面的约束xij1改为xijai。(ai为第i人最多能承担的任务数)25.平衡指派问题的求解：匈牙利法(适用 “min”)第一步：使指派问题的效率矩阵经变换，在各行各列中都出现0从效率矩阵的每行减去该行的最小元素

13、没有0的各列再减去该列的最小元素第二步：按下述规则圈0划线，若划掉所有0元素的直线个数=n，则计算停止，否则，转第三步找出矩阵中含0最少的一行(或一列)，从该行(或该列)中圈出一个0，再通过此0作一竖(横)线划去该列(或行)对余下各行各列重复进行，但已圈0的行或列不再圈第三步：在未划去的各数中找出最小值，作为调整量d调整：未划去的各数减d，两线交叉处的各数加d，其余不变，得一新矩阵，对此新矩阵重复第二步。26.不平衡指派问题的求解：先化为平衡的指派问题，再用匈牙利法“max”型的指派问题，先转化为“min”型指派问题，再用匈牙利法取一个比效率矩阵中所有系数都大的常数减去该效率矩阵得一新矩阵，则解以新矩阵为效率矩阵的最小化问题就等于解原效率矩阵的最大化问题27.指派问题的计算机求解用整数规划程序求解，输入：目