指派和网络最优化问题(学生版).ppt

1、Excel 在供应链管理中的应用和网络最优化问题,内容概要,运输问题 平衡的运输问题 不平衡的运输问题 运输问题扩展 选址 指派 网络最优化 最小费用流问题 最大流问题 最短路问题 最小支撑树问题 货郎担问题和中国邮路问题,指派问题,指派问题讨论的是n项工作分配给n个人去完成，每个人的工作效率不同，如何分配任务，能够使总的工作效率最高。 例如：n台机器加工n项任务，n条航线n艘船只航行等。 指派（分配）问题是0-1规划的特例，也是运输问题的特例，在指派问题模型中，每一个产地的提供量和每一个目的地的需求量均为1。,例1：A公司分别从3个客户（c1，c2，c3）那里得到了市场调研的项目，目前有3个

2、项目经理（m1，m2，m3）可以承担这些项目，完成每个项目所需的时间与这3位项目经理的经验和能力有关，管理层估算了每位经理完成各项目的可能时间（单位：天），见下表。如果每个客户项目分配一名项目经理，每名项目经理可以得到一个客户项目，管理层需要知道如何分配项目给各经理，可以使项目尽快完成（所用时间最短）？,解： 设xij为项目经理mi被分配了客户cj的项目，则：,目标函数：min Z =10 x11 + 15 x12+9 x13 +9 x21+18 x22+5 x23+ 6 x31+14 x32+3 x33 约束条件： x11 + x12+ x13 =1 x21 + x22+ x23=1 x31

3、 + x32+ x33=1 x11 + x21+ x31 = 1 x12 + x22+ x32 = 1 x13 + x23+ x33 = 1 xij 为0或1 其中（i=1、2、3; j=1、2、3),规划求解的电子表格模型,例2：某公司购买了3种不同的设备，但是车间里却有5个不同的地点可以安装。每一个可以安装的新设备的地点处理物料的小时成本列于下表中，公司寻求总物料处理成本最小的安装方案。其中设备2不能安装在地点2。,解： 设xij为设备Machine i 被分配安装在地点Location j，则：,目标函数：min Z = 13 x11 + 16 x12+12 x13 + 14 x14+1

4、5 x15 +15 x21 + 0 x22+13 x23 + 20 x24+16 x25 +4 x31 + 7 x32+10 x33 + 6 x34+7 x35 约束条件： x11 + x12+ x13 + x14+ x15 = 1 x21 + x22+ x23 + x24+ x25 =1 x31 + x32+ x33 + x34+ x35 =1 x11 + x21 + x31 =0 （i=1、2; j=1、2、3）,规划求解设置和结果,网络最优化问题,网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生

5、产、分配、项目计划、厂址选择、资源管理和财务策划等等。 网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。 近些年来，运筹学（管理科学）中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。,主要内容框架图,网络最优化基本概念,许多研究的对象往往可以用一个图表示，研究的目的归结为图的极值问题。 运筹学中研究的图具有下列特征： (1) 用点表示研究对象，用连线（不带箭头的边或带箭头的弧）表示对象之间某种关系； (2) 强调点与点之间的关联关系，不讲究图的比例大小与形状； (3) 每条边上都赋有一个

6、权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义； (4) 建立一个网络模型，求最大值或最小值。,网络最优化问题基本概念,对于该网络图，可以提出许多极值问题,网络最优化问题基本概念,（1）将某个点vi的物资或信息送到另一个点vj，使得运送总成本最小。这属于最小费用流问题。 （2）将某个点vi的物资或信息送到另一个点vj，使得总流量最大。这属于最大流问题。,网络最优化问题基本概念,（3）从某个点vi出发到达另一个点vj，怎样安排路线使得总距离最短或总费用最小，这属于最短路问题。 （4）点vi表示自来水厂及用户，vi与vj之间的边表示两点间可以铺设管道，权为v

7、i与vj间铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5个用户并且使总的费用最小。这属于最小支撑树问题。,网络最优化问题基本概念,（5）售货员从某个点vi出发走过其他所有点后回到原点vi，如何安排路线使总路程最短。这属于货郎担问题或旅行售货员问题。 （6）邮递员从邮局vi出发要经过每一条边将邮件送到用户手中，最后回到邮局vi，如何安排路线使总路程最短。这属于中国邮递员问题。,网络最优化问题基本概念,网络最优化问题类型主要包括： （1）最小费用流问题； （2）最大流问题； （3）最短路问题； （4）最小支撑树问题； （5）货郎担问题和中国邮路问题，等等,最小费用流问题,最小费用

8、流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使得配送网络的运营最优。 最小费用流问题的特殊类型包括运输问题和指派问题，以及在下面将要提到的两种重要类型：最大流问题和最短路问题。,例3：某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。其配送网络图如图所示。目标是确定一个运输方案（即每条路线运送多少单位的产品），使通过配送网络的总运输成本最小。,最小费用流问题,最小费用流问题的三个基本概念： 1、最小费用流问题的构成（网络表示）

9、（1）节点：包括供应点、需求点和转运点； （2）弧：可行的运输线路（节点i-节点j），经常有最大流量（容量）的限制。,最小费用流问题,最小费用流问题,2、最小费用流问题的假设 （1）至少一个供应点； （2）至少一个需求点； （3）剩下都是转运点； （4）通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量； （5）网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点；（有解） （6）在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比；（目标是线性的） （7）最小费用流问题的目标在满足给定需求条件下，使得通过网络供应的总成本最小（或总利润最大）。,最小

10、费用流问题,3、最小费用流问题的解的特征 （1）具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时（即平衡条件），最小费用流问题有可行解； （2）具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解（与运输问题和指派问题的解一样）。因此，没有必要加上所有决策变量都是整数的约束条件。,最小费用流问题,最小费用流问题的数学模型为： （1）决策变量：设fij为通过弧（节点i-节点j）的流量。 （2）目标是通过网络供应的总成本最小。 （3）约束条件 所有供应点：净流量（总流出总流入）为正；

11、 所有转运点：净流量为零； 所有需求点：净流量为负； 所有弧的流量fij受到弧的容量限制； 所有弧的流量fij非负。,最小费用流问题,例3的最小费用流问题的数学模型为： （1）决策变量：设fij为通过弧(节点i-节点j)的流量。 （2）目标函数 本问题的目标是总运输成本最小,最小费用流问题,（3）约束条件(节点净流量、弧的容量限制、非负） 供应点 F1: 供应点 F2: 转运点 DC: 需求点 W1: 需求点 W2: 弧的容量限制： 非负：,最小费用流问题,例3的电子表格模型：列出了网络中的弧和各弧所对应的容量、单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个节点的净流量为约束条

12、件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为0。 注意：净流量列放置了公示，这里用了一个窍门：用两个SUMIF函数的差来计算每个节点的净流量，这样快捷且不容易犯错。,最小费用流问题,最小费用流问题有五种重要的特殊类型： （1）运输问题：有出发地(供应点-供应量)和目的地(需求点-需求量)，没有转运点和弧的容量限制，目标是总运输成本最小（或总利润最大）。 （2）指派类型：出发地(供应点-供应量为1)是人，目的地(需求点-需求量为1)是任务，没有转运点和弧的容量限制，目标是总指派成本最小（或总利润最大）。 （3）转运问题：有出发地(供应点-供应量)和目的地(需求点-需求量)，有转运点，但没有弧的容量