第6章-分配与网络模型ppt课件.ppt

《第6章-分配与网络模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章分配与网络模型教师：朱玉春教授单位：经济管理学院2011年西北农林科技大学本章主要内容6.1运输问题6.2指派问题6.3转运问题6.4最短路径问题6.5最大流问题6.6生产和库存应用运输问题经常出现在计划货物配送和从某些供给地区到达某些需求地区之间的服务中，特别是每个供给地区的货物可获得量是有限的，每个需求地区的货物需求量是已知的。运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。让我们通过考虑福斯特发电机公司面临的这个运输问题来进行介绍。这个问题包括从3个加工厂运输一种产品到4个分销中心。福斯特发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝

2、德福德和宾夕法尼亚州的约克有3个加工厂，下3个月的计划期内的这个特殊型号的发电机的生产能力以及坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心3个月的需求预测，详见教材162页。6.1运输问题6.1运输问题6.1运输问题管理者想知道从每个加工厂运输到分销中心的产品运输量应为多少。图6-1显示了12条福斯特公司可以用的配送路线。这种图称为网络图；圆圈表示节点，连接节点的线条表示弧。每个起点和目的地都由节点表示，每个可能的运输路线都由弧表示。供给量写在起始节点边上，需求量写在每个目的地节点边上。从起始节点到目的地节点之间运输的货物数量表示了这个网络的流量。注

3、意：直接流量（从起点到终点）是用带箭头的线条表示的。6.1运输问题6.1运输问题对应这个福斯特公司的运输问题的目标是要确定使用哪些路线以及每条线路上的流量是多少时，使得总的运输成本最低。每条线路单位产品的运输费用在图6-1中的每条弧上标明。线性规划模型可以用来解决这类运输问题，我们将用双下标决策变量来描述变量。一般情况下，一个有m个起点和n个目的地的运输问题的决策变量常被表示成以下形式：xij——从起点i到目的地j之间的运输量式中，i=1,2,3,...,m,j=1,2,3,...,n。根据所给信息，我们可以构建一个有12个变量，7个约束的线性规划模型6.1运

4、输问题Max3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34s.t.x11+x12+x13+x14≤5000克里夫兰供给x21+x22+x23+x24≤6000贝德福德供给x31+x32+x33+x34≤2500约克供给x11+x21+x31=6000波士顿需求x12+x22+x32=4000芝加哥需求x13+x23+x33=2000圣路易斯需求x14+x24+x34=1500莱克星顿需求xij≥0，其中，i=1,2,3；j=1,2,3,4比较线性规划模型与图6-1中的网络，会发现几个观察值

5、。所有线性规划模型所需的信息都能在网络图中找到，每个节点需要一个约束条件，每一条弧需要一个变量。对应的每个起点节点出发的每条弧上的变量值之和必须小于或者等于这个起点节点的供给，对应的去往每个目的地节点的弧上的变量值之和必须等于这个目的地节点的需求6.1运输问题路线运输量单位成本（美元）总成本（美元）从到克利夫兰波士顿3500310500克利夫兰芝加哥150023000贝德福德芝加哥2500512500贝德福德圣路易斯200024000贝德福德莱克星顿150034500约克波士顿2500250006.1.1问题的变化福斯特公司发电机问题阐述了基本的运输模型的应用

6、，基本运输模型的变化可能有以下几种情况：1、总供给不等于总需求通常情况下总供给不等于总需求。如果总供给超过总需求，线性规划模型不需要修改。多余的供给总量在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解为未使用的供给或者未从起点运输的货物数量。如果总供给小于总需求，运输问题的线性规划模型没有可行解，在这种情况下，我们可以对网络图做如下修改：增加一个虚拟起点，这个起点的供给恰好等于不被满足的需求。增加从这个虚拟起点到每个终点的弧，线性规划模型就会有可行的解决办法了。我们规定每条从虚拟起点出发的弧上单位的运输成本为0。6.1运输问题这样，经过修改的问题的

7、最优解将会代表实际运输的货物的运输成本（从虚拟起点出发的线路没有实际运输发生）。当我们执行这个最优解时，目的地节点处显示的运输量是这个节点需求不被满足的货物短缺量。2、最大化目标函数在某些运输问题中，目标是要找到最大化利润或者收入的解决方案。这种情况下我们只要把单位利润或者收入作为一个系数列入目标函数中，简单地把最小改成最大，约束条件不变，就可求得线性规划的最大值而不是最小值。3、路线容量和或路线最小量运输问题的线性规划模型也能够包含一条或者更多的路线容量或者最小数量问题。例如，假设在福斯特公司发电机问题中，约克——波士顿路线（起点3到终点1）因为其常规的运输

8、模式中有限空间的限制，只有1000单位