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

第四章 运输问题 物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客） 实例 　某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量及各产地运往各销地的单位运费如表所示。如何调运，使总运费最少？ 运输问题的说明 需求假设： 　 每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。 该运输问题的线性模型 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=150 x13+ x23=200 xij≥0 运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m+n)个。当m、n比较大时，若用单纯形法求解，计算工作是就相当大。 运输问题是类特殊的线性规划问题，其特殊性体现在系数矩阵上，运输问题的系数矩阵A是0和1组成(0的个数远远大于1的个数)的稀疏阵，且r(A)=m+n-1 定理1：运输问题的任何一组基变量都由 m+n-1个变量组成 定理2：运输问题中m+n-1个变量构成基的充分必要条件是它不包含闭回路 (平衡)运输问题的求解：表上作业法 找一个初始基可行解; 方法:最小元素法/Vogel近似法(VAM) 检验,若所有的检验数都小于零,最优解已得,否则继续下一步; 方法:位势检验法 调整(实质是换基),得到一个新的基可行解,重复第二步. 方法:闭回路法 举例 第二步：位势检验 不平衡运输问题 当总供应量≠总需求量时，称为不平衡运输问题 不平衡运输问题的求解：先化为平衡的运输问题，再用表上作业法 供＞求，虚设一个收点，收量为供求之差，各发点到该虚收点的单位运价为0 供＜求，虚设一个发点，发量为供求之差，该虚发点到各收点的单位运价为0 运输问题的计算机求解 用线性规划程序求解，输出部分信息多，但变量和约束输入较麻烦。 用运输问题程序求解，只需输入产地个数、销地个数、各产地的产量、各销地的销量、各产地到各销地的单位运价。 　　前例输入后，得到的最优运输方案为： (二)短缺资源的分配问题 　　　石家庄北方研究院有三个区：一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北、山西两处煤矿负责供应，这两处的煤矿的价格相同，煤的质量也基本相同，山西和河北两处煤矿能供应北方研究院的数量分别为4000、1500吨，由煤矿至北方研究院的单位运价（百元/吨)如表。由于供应不足，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。请提交一个总运费最低的调运方案。 (三)生产与存贮问题 　　　某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。 (四)转运问题 　 PG重新设计制造和配送体系 ：90’S 成百上千个供应商 50多个产品类别 超过60个的工厂 15个配送中心 超过1000个的顾客群体 运输问题的扩展－－指派问题 　 现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂 。 模型 用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