数据、模型与决策第6章分配与网络模型.ppt

《数据、模型与决策第6章分配与网络模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章分配与网络模型本章讨论的模型属于一类特殊的线性规划问题，通常被称为网络流问题。它分为5类不同的问题：(1)运输问题；(2)指派问题；(3)转运问题；(4)最短路径问题；(5)最大流问题。由于问题结果和求解步骤的相似性，我们专门拿出一章类研究这些问题。在每一个案例中，我们将以网络的形式建立问题的图解模型，然后再说明每个问题是怎么样被构建成线性规划模型并进行求解的。在本章的最后一节，我们提出一个生产与库存的问题，这是转运问题的一个有趣的应用。6．1运输问题运输问题经常出现在计划从某些供给地区到某些需求地

2、区配送货物与服务中，特别是每个供给地区（起点）的货物可获得量是有限的，每个需求地区（目的地）的货物需求量是已知的情况。运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。我们通过考虑福斯特发电公司面临的这个运输问题来进行介绍。这个问题包括从3个加工厂运输一种产品到4个分销中心。福斯特发电公司在俄亥俄州的克利夫兰、印第安纳州的贝德福德和宾夕法尼亚洲的约克有3个加工厂，未来3个月的计划期内的这种特殊型号的发电机的生产能力如下：起点加工厂3个月的生产能力（单位）1克利夫兰50002贝德福德60003约

3、克2500总计：13500公司通过坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心来分销这种发电机；每个分销中心3个月的需求预测如下：目的地分销中心3个月的生产能力（单位）目的地分销中心3个月的生产能力（单位）1波士顿60003圣路易斯20002芝加哥40004莱克星顿1500总计：13500管理层想知道从每个加工厂运输到分销中心的产品运输量为多少。图6-1显示了12条福斯特公司可以用的配送线路。这种图称为网络图；圆圈表示节点，连接节点的线条表示弧。每个起点和目的地都由节点表示，每个可能的运输路线都

4、由弧表示。供给量写在起始节点边上，需求量写在每个目的地的节点边上。从起始节点到目的地节点之间运输的货物数量表示了这个网络的流量。注意：直接流量（从起点到终点）使用带箭头的线条表示的。对应这个福斯特公司的运输问题的目标是要确定使用哪些路线以及每条路线上的流量是多少时，使得总的运输成本最低。每条线路单位运输产品的运输费用在表6-1中给定并在图6-1中的每条弧线上标明。1克利夫兰2贝德福德3约克1波士顿2芝加哥3圣路易斯4克利夫兰工厂（起点节点）分销中心（目的地节点）单位运输成本5000600025006000

5、400020001500图6-1327675232545线性规划模型可以用来解决这类运输问题，我们将用双下标决策变量来描述变量，用X11来表示从起点节点1（克利夫兰）到目的地节点1（波士顿）之间的运输量；用X12来表示从起点节点1（克利夫兰）到目的地节点2（芝加哥）之间的运输量，其他类似。一般情况子下，一个有m个起点和n个目的地的运输问题的决策变量常被表示成以下形式：Xij—从起点i到目的地j之间的运输量。式中，i=1,2,3,···，m,j=1,2,3,···,n。因为运输问题的目标是最小化运输成本，我

6、们可以使用表6-1中的成本数据或者图6-1中弧上的数据来构造如下的成本表达式：从克利夫兰出发运出的所有运输成本=3X11+2X12+7X13+6X14从贝德福德出发运出的所有运输成本=7X21+5X22+2X23+3X24从约克出发运出的所有运输成本=2X31+5X32+4X33+5X34这些表达式加起来的总和就是福斯特公司发电机运输总成本的目标函数。表6-1福特公司发电机运输问题的单位运输成本起点目的地波士顿芝加哥圣路易斯莱克星敦克利夫兰贝德福德约克327675232545每个起点的供给能力和目的地的特

7、定需求量是有限的，所以运输问题需要有约束条件。我们先考虑供给约束条件，克利夫兰工厂的生产能力是5000单位，从克利夫兰出发运出的所有发电机数量=X11+X12+X13+X14,所以克利夫兰的供给约束为X11+X12+X13+X14≤5000克利夫兰供给福斯特公司运输问题有3个起点（工厂），所以这个运输模型就有3个供给约束条件。贝德福德工厂的6000单位的生产能力，约克工厂的2500单位的生产能力决定了下面两个供给约束条件：X21+X22+X23+X24≤6000贝德福德供给X31+X32+X33+X34≤

8、2500约克供给由于有4个分销终点，所以要有四个约束条件来确保终点需求被满足：X11+X21+X31=6000波士顿需求X12+X22+X32=4000芝加哥需求X13+X23+X33=2000圣路易斯需求X14+X24+X34=1500莱克星敦需求联合这些目标函数和约束条件构成一个线性规划模型，这个福斯特公司运输问题是一个有12个变量，7个约束条件的线性规划模型：min3X11+2X12+7X13+6X14+7X21+5X2