2004-7-15,【第七章：运输、指派问题*36*】 有动画,1,管理系统工程,第七章 管理系统决策定量分析模型（二） 第一节 运输问题 一、运输问题的提出 二、运输问题数学模型及模型特点 三、运输问题模型求解的表上作业法 四、利用Excel Solver对运输模型予以求解。 第二节 指派问题 一、指派问题的提出 二、指派问题的数学模型 三、利用Excel Solver对指派问题数学模型求解。,（七）,2004-7-15,【第七章：运输、指派问题*36*】 有动画,2,第一节 运输问题 一、运输问题的提出 在物质供应系统中，存在着多个生产单位和多个需求单位，由于生产、需求单位之间的距离不同，运输方式的不同，所以单位产品的运费有一定的差别。运输问题就是怎样以最小的总运费来完成物资的调运。 运输问题的类型： 1、产销平衡问题（总产量和总销量相等） 2、产销不平衡问题（总产量和总销量不相等） 参看下例：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,3,例1： 某公司从三个地区购买了14个单位的某种物资，分别运往下属的四个厂家，已知资料如下表所示，求总运费最小的物资调运方案。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,4,该例中ai=bj，故该例属于产销平衡问题 （若aibj，则属于产销不平衡问题） 一般地： 1、设有m个产地，n个销地 2、ai为第i个产地的产量，bj为第j个销地的需要量 3、cij为从Ai至Bj的单位物资运价 则运输问题的资料表为：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,5,运输问题资料表,2004-7-15,【第七章：运输、指派问题*36*】 有动画,6,二、运输模型 设xij为Ai至Bj的运输量，则该运输问题的模型为：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,7,运输问题模型的特点： 1、变量较多，共mn个 2、约束条件较多，共m+n个 3、约束条件均为等式 4、系数矩阵A为一个稀疏矩阵 运输问题模型求解的方法： 1、表上作业法 2、线性规划的方法（Excel Solver）,2004-7-15,【第七章：运输、指派问题*36*】 有动画,8,运输模型一般形式： 矩阵形式：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,9,运输模型的特点： 1、系数矩阵为一个稀疏矩阵，秩rank(A)=m+n-1 , Pij=ei+em+j，例如：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,10,2、决策变量mn个；约束条件m+n个（m+n-1个线性无关） 基变量m+n-1个 3、运输问题恒有最优解 4、运输模型的对偶模型对偶变量 Y=（u1 、u2、um、v1、v2、vn) =CBB-1 5、检验数ij=CBB-1Pij-cij=（u1 、u2、um、v1、v2、vn) -cij =(ui+vj)-cij,2004-7-15,【第七章：运输、指派问题*36*】 有动画,11,例2 设某产品从产地A1,A2,A3运往销地B1,B2,B3,B4,B5，已知资料如下表所示，求最佳调运方案。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,12,（一）第一个可行方案的确定 方法一：最小元素法 1、找出运价中最小的运价（3） 取x31=min(a3,b1)=30=b1,第一列满足，第一列其余的格点打； 注：若行得以满足，则行其余格点打，若列、行均得以满足，则在列或行中 任 取一空格取0值，其余的格点打 。 2、重复1，可得第一个可行调运方案：总运费为Z=950百元 X14=20、x15=20、x22=40、x23=0、x24=0、x31=30、x33=60 、余xij=0,初始方案第一个可行方案,2004-7-15,【第七章：运输、指派问题*36*】 有动画,13,（二）方案是否最优的判定 1、闭回路（口述闭回路概念） 2、任一非基变量格点具有且只有一个这样的闭回路 任一基变量格点没有一个这样的闭回路 3、检验数ij的计算：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,14,检验数ij的计算方法 方法一：闭回路法： 对于非基变量格点的闭回路，从起点开始按箭头方向将顶点上的运价规定+、-相间的符号，则ij= -（标符号后运价的代数和） 例如11= -（7-6+12-7+5-3）= -8 （x11由0变1时运费改变的相反数） 各非基变量检验数为： 11= -8 、12= -7 、13= -7 、21= 0 25=4、 32=1、 34=2 、 35= -3 有大于零检验数，故此方案不是最优方案。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,15,检验数ij的计算方法 方法二：位势法： 1、运输模型的对偶变量ui、vj称之为行位势、列位势，共m+n个。 2、运输模型的检验数ij=CBB-1Pij-cij =(ui+vj)-cij 只要有位势值，则检验数可计算出来。 基变量的检验数ij=(ui+vj)-cij=0共有（m+n-1) ，因为基变量共有（m+n-1)个。ui、vj共m+n个，可见其中有一个为自由取值，由此计算位势值。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,16,闭回路法计算的检验数： 11= -8 、12= -7 、13= -7 、21= 0 25=4、 32=1、 34=2 、 35= -3（学生验证计算） 位势法计算 ： 11=（u1+v1）-c11= -1-7 = -8 12=（u1+v2）-c12= 3-10 = -7 13=（u1+v3）-c13= 1-8 = -7 21=（u2+v1）-c21= 5-5 =0,2004-7-15,【第七章：运输、指派问题*36*】 有动画,17,（三）方案的调整 1、取25=4、 32=1、 34=2中的最大者对应的回路为调整回路 2、调整量=min标负号运价格点原调运量：此例=min0，20=0 3、标正号格点的变量加调整量；标负号格点的变量减调整量；,调整后的第二方案,初始方案须调整确定回路,调整量为0,2004-7-15,【第七章：运输、指派问题*36*】 有动画,18,判定最优否 计算此时的非基变量的检验数如下： 11= -4 、12= -3 、13= -3 、21= 0 24=-4、 32=1、 34=-12 、 35= -7 可知此解非最优，须再调整。,第二方案非最优需调整,调整量为40,调整量为40,2004-7-15,【第七章：运输、指派问题*36*】 有动画,19,调整后得下表： 计算检验数为： 11= -4 、12= -4 、13= -3 、21= 0 22=0、 24=-4、 34=-2 、 35= -7 可知此解为最优解。 最优解为：x14=20、x15=20、x23=40、x25=0、x31=30 x32=40、x33=20 、余xij=0 总运费为Z=910百元,调整后第三方案经判定为最优,2004-7-15,【第七章：运输、指派问题*36*】 有动画,20,利用Excel Solver求解运输模型,步骤： 1、确定运价表 2、确定活动单元格，目标单元格 3、利用数据组相乘公式，利用常用函数里的公式： （SUMPRODUCT）确定好约束条件的左边单元格 4、执行规划求解程序的求解结果,2004-7-15,【第七章：运输、指派问题*36*】 有动画,21,利用Excel Solver求解运输模型,求解结果为：x*13=1、x*21=1、x*23=3、 x*24=5、 x*31=2、x*32=2 Z*min =39,链接,2004-7-15,【第七章：运输、指派问题*36*】 有动画,22,产销不平衡问题之例,例2： 三个物资出产地A1、A2、A3，三个物资需要地B1、B2、B3，出产量和需要量如下表所示，求最低成本运输方案。（已知资料见P11） 解： 因为aibj，所以该运输问题为一个产销不平衡问题； 虚设一个需求地B4，需求量为2000，单位运费为0。 （求解见P12） 结论：A1运送至B22500单位、运送至B33500单位； A2运送至B34000单位； A3运送至B15000单位、运送至B25000单位。 最小总运费：114500（费用单位）,2004-7-15,【第七章：运输、指派问题*36*】 有动画,23,产销不平衡问题之例,2004-7-15,【第七章：运输、指派问题*36*】 有动画,24,产销不平衡问题之例Excel Solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 有动画,25,物质配送问题之例,例3： 两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如下： 1、工厂1的产品通过铁路只能送到仓库1，产品的数量不限，单位运输成本为700元/单位。 2、工厂2的产品通过铁路只能送到仓库2，产品的数量不限，单位运输成本为900元/单位。 3、卡车可将多达50个单位的产品由工厂送到配送中心，再从配送中心以最多50个单位的载运量运到各仓库，其单位运费如图所示。 4、各厂的生产量、各仓库的所需量如图所示。 求最低运输成本对应的运输方案。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,26,例3的配送网络示意图,2004-7-15,【第七章：运输、指派问题*36*】 有动画,27,例3的变量设置,设： x1 工厂1 至 仓库1 的运输量 x2工厂2 至 仓库2 的运输量 x3工厂1 至 配送中心 的运输量 x4工厂2 至 配送中心 的运输量 x5配送中心 至 仓库1 的运输量 x6配送中心 至 仓库2 的运输量 根据条件分析建立模型如下：,2004-7-15,【第七章：运输、指派问题*36*】 有动画,28,例3的（LP）模型,2004-7-15,【第七章：运输、指派问题*36*】 有动画,29,例3Excel Solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 有动画,30,例3求解结果：运输方案,运输方案： x1 工厂1仓库1：x*1=30 x2 工厂2仓库2：x*2=40 x3 工厂1配送中心：x*3=50 x4 工厂2配送中心：x*4=30 x5 配送中心仓库1：x*5=30 x6 配送中心仓库2：x*6=50 Z 总运费为： Zmin=110000（费用单位）,2004-7-15,【第七章：运输、指派问题*36*】 有动画,31,运输问题变体问题处理,例4：求最佳产品生产安排方案 某公司决定使用三个有生产余力的工厂进行四种新产品的生产制造，每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。 资料如下表所示（见P20）。 各种产品的生产允许分解（即一种产品可以在不同的工厂生产，如工厂1生产产品4：15件；工厂2生产产品4：25件）。 现需确定一个产品生产安排方案，使每天总生产成本最小。,2004-7-15,【第七章：运输、指派问题*36*】 有动画,32,2004-7-15,【第七章：运输、指派问题*36*】 有动画,33,资料分析及建模问题,