《b无动画 7管理系统工程教学课件第七章：运输指派》由会员分享，可在线阅读，更多相关《b无动画 7管理系统工程教学课件第七章：运输指派（36页珍藏版）》请在金锄头文库上搜索。
1、2004-7-15,【第七章：运输、指派问题*36*】 无动画,1,管理系统工程,第七章 管理系统决策定量分析模型（二） 第一节 运输问题 一、运输问题的提出 二、运输问题数学模型及模型特点 三、运输问题模型求解的表上作业法 四、利用Excel Solver对运输模型予以求解。 第二节 指派问题 一、指派问题的提出 二、指派问题的数学模型 三、利用Excel Solver对指派问题数学模型求解。,（七）,2004-7-15,【第七章：运输、指派问题*36*】 无动画,2,第一节 运输问题 一、运输问题的提出 在物质供应系统中，存在着多个生产单位和多个需求单位，由于生产、需求单位之间的距离不同，
2、运输方式的不同，所以单位产品的运费有一定的差别。运输问题就是怎样以最小的总运费来完成物资的调运。 运输问题的类型： 1、产销平衡问题（总产量和总销量相等） 2、产销不平衡问题（总产量和总销量不相等） 参看下例：,2004-7-15,【第七章：运输、指派问题*36*】 无动画,3,例1： 某公司从三个地区购买了14个单位的某种物资，分别运往下属的四个厂家，已知资料如下表所示，求总运费最小的物资调运方案。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,4,该例中ai=bj，故该例属于产销平衡问题 （若aibj，则属于产销不平衡问题） 一般地： 1、设有m个产地，n个销地 2、ai
3、为第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
4、Solver）,2004-7-15,【第七章：运输、指派问题*36*】 无动画,8,利用Excel Solver求解运输模型,步骤： 1、确定运价表 2、确定活动单元格，目标单元格 3、利用数据组相乘公式，利用常用函数里的公式： （SUMPRODUCT）确定好约束条件的左边单元格 4、执行规划求解程序的求解结果,2004-7-15,【第七章：运输、指派问题*36*】 无动画,9,利用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
5、*】 无动画,10,产销不平衡问题之例,例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*】 无动画,11,产销不平衡问题之例,2004-7-15
6、,【第七章：运输、指派问题*36*】 无动画,12,产销不平衡问题之例Excel Solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 无动画,13,物质配送问题之例,例3： 两个工厂生产同一种新产品，配送公司将该产品送到两个仓库。运送情况如下： 1、工厂1的产品通过铁路只能送到仓库1，产品的数量不限，单位运输成本为700元/单位。 2、工厂2的产品通过铁路只能送到仓库2，产品的数量不限，单位运输成本为900元/单位。 3、卡车可将多达50个单位的产品由工厂送到配送中心，再从配送中心以最多50个单位的载运量运到各仓库，其单位运费如图所示。 4、各厂的生产量、各仓库的所
7、需量如图所示。 求最低运输成本对应的运输方案。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,14,例3的配送网络示意图,2004-7-15,【第七章：运输、指派问题*36*】 无动画,15,例3的变量设置,设： x1 工厂1 至 仓库1 的运输量 x2工厂2 至 仓库2 的运输量 x3工厂1 至 配送中心 的运输量 x4工厂2 至 配送中心 的运输量 x5配送中心 至 仓库1 的运输量 x6配送中心 至 仓库2 的运输量 根据条件分析建立模型如下：,2004-7-15,【第七章：运输、指派问题*36*】 无动画,16,例3的（LP）模型,2004-7-15,【第七章：运输、
8、指派问题*36*】 无动画,17,例3Excel Solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 无动画,18,例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*】 无动画,19,运输问题变体问题处理,例4：求最佳产品生产安排方案 某公司决定使用三个有生产余力的工厂
9、进行四种新产品的生产制造，每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。 资料如下表所示（见P20）。 各种产品的生产允许分解（即一种产品可以在不同的工厂生产，如工厂1生产产品4：15件；工厂2生产产品4：25件）。 现需确定一个产品生产安排方案，使每天总生产成本最小。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,20,2004-7-15,【第七章：运输、指派问题*36*】 无动画,21,资料分析及建模问题,资料分析： 1、每单位产品需要等量的工作是指：不论哪种产品、在那个厂家生产，一件产品所需的工作量是一样的。这样各厂的有效生产能力便
10、可以用生产产品（不管哪种）的数量来衡量。 2、各种产品的生产允许分解是指：一种产品（日需生产数量）可以在不同生产厂家分开生产。 例如：产品1日需生产20件： 由工厂1生产15件； 由工厂2生产5件。 3、将各工厂的能力视作供应量、各种产品的生产量视作需要量，则可化为运输问题处理。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,22,建模问题,建模分析： 1、目标函数minZ=cijxij（运输问题的目标函数） 2、行约束：生产厂提供的能力用不完，故左右 （左、右参看电子表格） 3、列约束：需生产的产品数量需完成，故上=下 （上、下参看电子表格） 4、工厂2不能生产产品2，故x
11、23=0要作为约束条件,2004-7-15,【第七章：运输、指派问题*36*】 无动画,23,例4：产品生产安排方案Excel solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 无动画,24,例4：求最佳产品生产安排方案求解结论,求解结果：x12=30、x13=30、x24=15、x31=20、x34=25 工厂1生产产品2、产品3各（30件） （工厂1可生产75） 工厂2生产产品4（15件） （工厂2可生产75） 工厂3生产产品1（20件）产品4（25件） （工厂3可生产45） 最小生产成本3260元 各种产品需生产的数量： 产品1（20）、产品2（30）、产品
12、3（30）、产品4（40）,2004-7-15,【第七章：运输、指派问题*36*】 无动画,25,第二节 指派问题 一、指派问题的提出 指派问题是一种特殊的线性规划问题，它是讨论一些有关指派的问题。比如：指派人员做某项工作；指派机器或工厂完成某项生产任务等。 指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员，或为生产（产品）指派机器设备等诸问题。 例1 某公司安排甲、乙、丙、丁四个人员每人完成A、B、C、D四项工作任务中的某一项任务，根据各人的能力和各人单位小时的工资综合分析得出“每个人完成各项任务的费用”如下表所示：,2004-7-15,【第七章：运输、指派问题*
13、36*】 无动画,26,2004-7-15,【第七章：运输、指派问题*36*】 无动画,27,二、指派问题的特征 1、被指派者的数量与任务的数量相同 2、每一个被指派者只能完成一项任务 3、每一项任务只能由一个被指派者来完成 4、每一个被指派者与每一项任务的组合都会有一个相关的成本（效率） 5、问题的目标是如何指派能使总成本最小（或总效率最高）,2004-7-15,【第七章：运输、指派问题*36*】 无动画,28,三、指派问题的模型 设：xij=1表示第i个人员指派第j项任务 Xij=0表示第i个人员不指派第j项任务 则模型形式为： minZ=cijxij xij=1 （按行加共m个） xij
14、=1 （按列加共m个） xij=1、0,2004-7-15,【第七章：运输、指派问题*36*】 无动画,29,例1之模型,例1的模型如下：,2004-7-15,【第七章：运输、指派问题*36*】 无动画,30,例1模型的Exsel Solver求解,链接,2004-7-15,【第七章：运输、指派问题*36*】 无动画,31,指派问题变体问题,例2：求最佳产品 某公司决定使用三个有生产余力的工厂进行四种新产品的生产制造，每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。 资料如下表所示。 各种产品的生产不允许分解（即每种产品只能在一家工厂生产）。 现需确定在哪一
15、个工厂生产哪一种（或几种）产品，使每天总生产成本最小。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,32,2004-7-15,【第七章：运输、指派问题*36*】 无动画,33,资料分析及建模问题,分析： 1、每单位产品需要等量的工作是指：不论哪种产品、在那个厂家生产，一件产品所需的工作量是一样的。这样各厂的有效生产能力便可以用生产产品（不管哪种）的数量来衡量。 2、各种产品的生产不允许分解是指：一种产品（日生产数量）只能在一家生产厂家生产， 例如：产品1日生产20件只能由工厂3生产。 3、将“各种产品的日需生产量”均看作整体1，则可转化为指派问题的工作任务。 4、将各厂的“剩余生产能力”转化为至多能完成几项工作任务，以便按指派问题予以处理。,2004-7-15,【第七章：运输、指派问题*36*】 无动画,34,资料分析及建模问题,建模分析： 1、原始资料需先转换为：各厂完成一种产品（日生产量）的生产所需成本。 2、约束条件： （1）工厂1和工厂2生产能力的应用2 （2）工厂3生产能力的应用=1 （3）各种产品的（日生产量）生产=1 （4）工厂2不能生产产品3，故x23=0 3、目标函数： min Z=各厂完成一种（或两种）产品（日生产量） 的生产所需成本之和。,
