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

第四章运输问题

物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）你怎么去分析这类问题呢？想想看！第四章运输问题物流中的一个普遍问题是如何1实例

某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量及各产地运往各销地的单位运费如表所示。如何调运，使总运费最少？销地产地B1B2B3产量A1646200A2655300销量150150200500500单位运费

x11x12x13

x21x22x23

实例某公司从两个产地A1、A2将物品运往三个销地B1、B22运输问题的说明需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。

成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量。整数解性质：只要它的供应量和需求量都是整数，任何运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。运输问题的说明需求假设：成本假设：整数解性质：3该运输问题的线性模型minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0该运输问题的线性模型minz=6x11+4x14推广为一般：收点B1B2Bn发量发点A1C11

x11C12x12

…C1nx1na1…AmCm1xm1Cm2xm2Cmn

xmnam收量b1b2bn∑ai=∑bj推广为一般：收点B1B2Bn发量发点A1C11x11C125(平衡)运输问题的线性规划模型Minz=S.t.(平衡)运输问题的线性规划模型Minz=6运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m+n)个。当m、n比较大时，若用单纯形法求解，计算工作是就相当大。运输问题是类特殊的线性规划问题，其特殊性体现在系数矩阵上，运输问题的系数矩阵A是0和1组成(0的个数远远大于1的个数)的稀疏阵，且r(A)=m+n-1运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m7定理1：运输问题的任何一组基变量都由m+n-1个变量组成定理2：运输问题中m+n-1个变量构成基的充分必要条件是它不包含闭回路定理1：运输问题的任何一组基变量都由m+n-1个变量8(平衡)运输问题的求解：表上作业法找一个初始基可行解;方法:最小元素法/Vogel近似法(VAM)检验,若所有的检验数都小于零,最优解已得,否则继续下一步;方法:位势检验法调整(实质是换基),得到一个新的基可行解,重复第二步.方法:闭回路法(平衡)运输问题的求解：表上作业法找一个初始基可行解;9举例销地产地B1B2B3产量A1646×200A265×5300销量15015020050050015020050100第一步：找初始方案举例销地产地B1B2B3产量A1646×200A26510第二步：位势检验

B1B2B3UiA1645-10A264-150Vj645以上所有检验数≤0，故初始方案已是最优方案不用进行第三步的调整第二步：位势检验B1B2B3UiA1645-10A2611不平衡运输问题当总供应量≠总需求量时，称为不平衡运输问题不平衡运输问题的求解：先化为平衡的运输问题，再用表上作业法供＞求，虚设一个收点，收量为供求之差，各发点到该虚收点的单位运价为0供＜求，虚设一个发点，发量为供求之差，该虚发点到各收点的单位运价为0不平衡运输问题当总供应量≠总需求量时，称为不平衡运输问题12运输问题的计算机求解用线性规划程序求解，输出部分信息多，但变量和约束输入较麻烦。用运输问题程序求解，只需输入产地个数、销地个数、各产地的产量、各销地的销量、各产地到各销地的单位运价。

前例输入后，得到的最优运输方案为：

销地产地B1B2B3产量A1501500200A21000200300销量150150200

运输问题的计算机求解用线性规划程序求解，输出部分信息多，但变13

运输问题的应用

(一)配送问题

东风电机公司接到上海一家商场(B1),青岛一家商场(B2),西安一家商场(B3)各一份订单,要求下月供应电机.B1的需求量为100台,B2的需求量为80台,而B3要求供应120台.该公司在北京和武汉设有两个仓库(A1,A2),预计A1,A2下月的库存量分别为200台和150台.已知每个仓库到每家商场运送1台电机的费用如表所示.问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少?B1B2B3A1152118A2202516运输问题的应用(一)配送问题B114(二)短缺资源的分配问题

石家庄北方研究院有三个区：一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北、山西两处煤矿负责供应，这两处的煤矿的价格相同，煤的质量也基本相同，山西和河北两处煤矿能供应北方研究院的数量分别为4000、1500吨，由煤矿至北方研究院的单位运价（百元/吨)如表。由于供应不足，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。请提交一个总运费最低的调运方案。单位运价一区二区三区山西煤矿1.651.701.75河北煤矿1.601.651.70(二)短缺资源的分配问题石家庄北方研究院有三个区：一区15(三)生产与存贮问题

某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。季度生产能力（台）单位成本（万元）Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3(三)生产与存贮问题某厂按合同规定须于当年每个季度末分16(四)转运问题

广州大连600400产地41332中转站供应量12345678(四)转运问题广州大连600400产地41332中转站供应17P&G重新设计制造和配送体系：90’S成百上千个供应商50多个产品类别超过60个的工厂15个配送中心超过1000个的顾客群体P&G重新设计制造和配送体系：90’S18为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择，为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少。在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题北美工厂数减少了20%，并且公司每年节省了2亿美元的税前费用为每个单独的产品种类设计并求解运输问题19运输问题的扩展－－指派问题

现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂。还有哪些这样的问题呢？想想看！运输问题的扩展－－指派问题现实生活之中，我们也经常遇到指20实例有4个工人,要指派他们分别完成4项工作,每人做各项工作所消耗的时间如下表。要求1人只做1件事，如何指派使总的消耗时间最少?人工作B1B2B3B4A115182124A219232218A326171619A419212317实例有4个工人,要指派他们分别完成4项工作,每人做21模型用0-1变量表示“是非”决策：1，第i人去做第j件事xij＝0，第i人不做第j件事minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(A1只能干一件事)x21+x22+x23+x24=1(A2只能干一件事)x31+x32+x33+x34=1(A3只能干一件事)x41+x42+x43+x44=1(A4只能干一件事)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或1模型用0-1变量表示“是非”决策：22指派问题的一般描述有n个人A1,A2,…An,要分派去做n件事B1,B2…Bn,要求每一件事都必须有一个人去做,而且不同的事由不同的人去做.已知每个人Ai做每件事Bj的效率(如劳动工时或成本,或创造的价值等)为Cij,应如何进行指派(哪个人做哪件事),才能使工作效益最好(如工时最少,或成本最低,或创造的价值最大)?指派问题既可以说是运输问题的特殊情形,也可以说是整数规划的特殊情形.指派问题的一般描述有n个人A1,A2,…An,要分派23指派问题的一般模型min（max）z=S.t.指派问题的一般模型min（max）z=24指派问题的变形人的数量≠任务的数量人的数量﹥任务的数量，一般模型中前面的约束∑xij=1改为∑xij≤1。由于某种原因，不能指派某个人做某件事如A1由于技能不达标，不能做B3，只须在一般模型中去掉x13变量。多重指派：一个人可以被分派做几件事，则一般模型中前面的约束∑xij＝1改为∑xij≤ai。(ai为第i人最多能承担的任务数)指派问题的变形人的数量≠任务的数量25平衡指派问题的求解：匈牙利法(适用“min”)第一步：使指派问题的效率矩阵经变换，在各行各列中都出现0从效率矩阵的每行减去该行的最小元素没有0的各列再减去该列的最小元素第二步：按下述规则圈0划线，若划掉所有0元素的直线个数=n，则计算停止，否则，转第三步找出矩阵中含0最少的一行(或一列)，从该行(或该列)中圈出一个0，再通过此0作一竖(横)线划去该列(或行)对余下各行各列重复进行，但已圈0的行或列不再圈第三步：在未划去的各数中找出最小值，作为调整量d调整：未划去的各数减d，两线交叉处的各数加d，其余不变，得一新矩阵，对此新矩阵重复第二步。平衡指派问题的求解：匈牙利法(适用“min”)第一步：使指26不平衡指派问题的求解：先化为平衡的指派问题，再用匈牙利法“max”型的指派问题，先转化为“min”型指派问题，再用匈牙利法取一个比效率矩阵中所有系数都大的常数减去该效率矩阵得一新矩阵，则解以新矩阵为效率矩阵的最小化问题就等于解原效率矩阵的最大化问题不平衡指派问题的求解：先化为平衡的指派问题，再用匈牙利法27指派问题的计算机求解用整数规划程序求解，输入：目标函数、约束条件直接用指派问题程序求解，输入：人数、任务数、效率矩阵。前例用指派问题程序得出任务指派的方案为：A1A2A3A4B1B2B3B4所用时间最少为70指派问题的计算机求解用整数规划程序求解，输入：目标函数、约束28指派问题的应用将出厂的产品分配到不同的市场将销售人员分派到不同的地区将建筑项目分派给不同的建筑公司分派人员负责不同的机器（或项目）分派工厂生产产品在各个地点分派设备设计学生入学区域安排轮船到不同的泊位卸货将书稿分配给不同的编辑指派问题的应用将出厂的产品分配到不同的市场29第四章运输问题

物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）你怎么去分析这类问题呢？想想看！第四章运输问题物流中的一个普遍问题是如何30实例

某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量及各产地运往各销地的单位运费如表所示。如何调运，使总运费最少？销地产地B1B2B3产量A1646200A2655300销量150150200500500单位运费

x11x12x13

x21x22x23

实例某公司从两个产地A1、A2将物品运往三个销地B1、B231运输问题的说明需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。

成本假设：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量。整数解性质：只要它的供应量和需求量都是整数，任何运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。运输问题的说明需求假设：成本假设：整数解性质：32该运输问题的线性模型minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0该运输问题的线性模型minz=6x11+4x133推广为一般：收点B1B2Bn发量发点A1C11

x11C12x12

…C1nx1na1…AmCm1xm1Cm2xm2Cmn

xmnam收量b1b2bn∑ai=∑bj推广为一般：收点B1B2Bn发量发点A1C11x11C1234(平衡)运输问题的线性规划模型Minz=S.t.(平衡)运输问题的线性规划模型Minz=35运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m+n)个。当m、n比较大时，若用单纯形法求解，计算工作是就相当大。运输问题是类特殊的线性规划问题，其特殊性体现在系数矩阵上，运输问题的系数矩阵A是0和1组成(0的个数远远大于1的个数)的稀疏阵，且r(A)=m+n-1运输问题属于线性规划问题，其变量个数为mn个，约束个数为(m36定理1：运输问题的任何一组基变量都由m+n-1个变量组成定理2：运输问题中m+n-1个变量构成基的充分必要条件是它不包含闭回路定理1：运输问题的任何一组基变量都由m+n-1个变量37(平衡)运输问题的求解：表上作业法找一个初始基可行解;方法:最小元素法/Vogel近似法(VAM)检验,若所有的检验数都小于零,最优解已得,否则继续下一步;方法:位势检验法调整(实质是换基),得到一个新的基可行解,重复第二步.方法:闭回路法(平衡)运输问题的求解：表上作业法找一个初始基可行解;38举例销地产地B1B2B3产量A1646×200A265×5300销量15015020050050015020050100第一步：找初始方案举例销地产地B1B2B3产量A1646×200A26539第二步：位势检验

B1B2B3UiA1645-10A264-150Vj645以上所有检验数≤0，故初始方案已是最优方案不用进行第三步的调整第二步：位势检验B1B2B3UiA1645-10A2640不平衡运输问题当总供应量≠总需求量时，称为不平衡运输问题不平衡运输问题的求解：先化为平衡的运输问题，再用表上作业法供＞求，虚设一个收点，收量为供求之差，各发点到该虚收点的单位运价为0供＜求，虚设一个发点，发量为供求之差，该虚发点到各收点的单位运价为0不平衡运输问题当总供应量≠总需求量时，称为不平衡运输问题41运输问题的计算机求解用线性规划程序求解，输出部分信息多，但变量和约束输入较麻烦。用运输问题程序求解，只需输入产地个数、销地个数、各产地的产量、各销地的销量、各产地到各销地的单位运价。

前例输入后，得到的最优运输方案为：

销地产地B1B2B3产量A1501500200A21000200300销量150150200

运输问题的计算机求解用线性规划程序求解，输出部分信息多，但变42

运输问题的应用

(一)配送问题

东风电机公司接到上海一家商场(B1),青岛一家商场(B2),西安一家商场(B3)各一份订单,要求下月供应电机.B1的需求量为100台,B2的需求量为80台,而B3要求供应120台.该公司在北京和武汉设有两个仓库(A1,A2),预计A1,A2下月的库存量分别为200台和150台.已知每个仓库到每家商场运送1台电机的费用如表所示.问该公司应如何调运电机,才能既满足用户的需要又使总的运费最少?B1B2B3A1152118A2202516运输问题的应用(一)配送问题B143(二)短缺资源的分配问题

石家庄北方研究院有三个区：一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北、山西两处煤矿负责供应，这两处的煤矿的价格相同，煤的质量也基本相同，山西和河北两处煤矿能供应北方研究院的数量分别为4000、1500吨，由煤矿至北方研究院的单位运价（百元/吨)如表。由于供应不足，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。请提交一个总运费最低的调运方案。单位运价一区二区三区山西煤矿1.651.701.75河北煤矿1.601.651.70(二)短缺资源的分配问题石家庄北方研究院有三个区：一区44(三)生产与存贮问题

某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。季度生产能力（台）单位成本（万元）Ⅰ2510.8Ⅱ3511.1Ⅲ3011.0Ⅳ1011.3(三)生产与存贮问题某厂按合同规定须于当年每个季度末分45(四)转运问题

广州大连600400产地41332中转站供应量12345678(四)转运问题广州大连600400产地41332中转站供应46P&G重新设计制造和配送体系：90’S成百上千个供应商50多个产品类别超过60个的工厂15个配送中心超过1000个的顾客群体P&G重新设计制造和配送体系：90’S47为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择，为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少。在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题北美工厂数减少了20%，并且公司每年节省了2亿美元的税前费用为每个单独的产品种类设计并求解运输问题48运输问题的扩展－－指派问题

现实生活之中，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂。还有哪些这样的问题呢？想想看！运输问题的扩展－－指派问题现实生活之中，我们也经常遇到指49实例有4个工人,要指派他们分别完成4项工作,每人做各项工作所消耗的时间如下表。要求1人只做1件事，如何指派使总的消耗时间最少?人工作B1B2B3B4A115182124A219232218A326171619A419212317实例有4个工人,要指派他们分别完成4项工作,每人做50模型用0-1变量表示“是非”决策：1，第i人去做第j件事xij＝0，第i人不做第j件事minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(A1只能干一件事)x21+x22+x23+x24=1(A2只能干一件事)x31+x32+x33+x34=1(A3只能干一件事)x41+x42+x43+x44=1(A4只能干一件事)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或1模型用0-1变量表示“是非”决策：51指派问题的一般描述有n个人A1,A2,…An,要分派去做n件事B1,B2…Bn,要求每一件事都必须有一个人去做,而且不同的事由不同的人去做