运筹学课件第三章 运输与指派问题

《运筹学课件第三章 运输与指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章运输与指派第三章运输与指派运输与指派问题是实际中碰到的比较常见的两类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以有可能找到比单纯形法更为简便的求解方法。运输问题的提出P&J公司是美国的一家经营罐头加工和储运的小公司，该公司收购生菜并在食品罐头厂中把他们加工成罐头，然后再把这些罐头分销到各地卖出。该公司的一种主要产品是豆类罐头，这些罐头在三个食品罐头厂加工，记为罐头厂1，罐头厂2，罐头厂3，然后用卡车把它们运送到位于美国西部的四个仓库，记为仓库1，仓库2，仓库3和仓库4。现在的问题是该公司采用怎样的运输方案才能使总

2、运输成本最小。也就是公司要决定每个罐头加工厂生产的罐头如何被分配到各个仓库，才能保证运输费用最小。P&J公司运输问题的数据表3-1P&J公司运输问题参数表（单位：万元）仓库罐头厂仓库1仓库2仓库3仓库4产地产量（车）罐头厂13113107罐头厂219284罐头厂3741059销地销量（车）3656——P&J公司运输问题的模型运输问题的模型运输问题变量的系数矩阵模型的两个假设和两个性质需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。成本假设：从任何一个出发地到目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本等

3、于单位运输成本乘以所运输的数量。性质1可行解特性：当且仅当供应量的总和与需求量的总和相等时，运输问题才有可行解。性质2整数解特性：如果都是整数，那么任何有最优解的运输问题线性规划模型，其最优解也为整数。表上作业法求解运输问题表上作业法是单纯形法在求解运输问题时的一种简化方法，其步骤如下：确定初始基可行解两种比较简单的方法：最小元素法和Vogel法最小元素法基本思想是就近运输，即从单位运价表中最小的运价处开始确定运输关系，依次类推，直到给出全部方案为止。可以证明用最小元素法给出的初始解是运输问题的基可行解最小元素法确定初始基可行解以P&J为例最小元素

4、法确定初始基可行解确定初始基可行解Vogel法最小元素法的的缺点是为了节省一处的费用，但由此可能造成在其他处要多花几倍的费用。VAM揭示，如果在任何行或列上，最便宜的选择没有被采用，那么至少次便宜的选择应该被采用，如果采用了次便宜的选择，就存在一个罚金成本（penaltycost）,其数额至少等于该行或列中，最便宜的选择与次便宜的选择之间的差。Vogel法确定初始基可行解仍以P&J为例Vogel法确定初始基可行解最优检验与方案的调整最小元素法或Vogel法给出了运输问题的初始基可行解，此时我们还需通过最优性检验判别该解的目标函数值是否最优。如不是最

5、优解，还需进行适当的调整。闭回路法用于计算各非基变量（对应空格）的检验数，并对可行解进行调整。所谓闭回路是指调运方案中由一个空格和若干个数字格的水平和垂直连线构成的封闭回路。它是以某空格为起点，用水平或垂直线往前划，每碰到一数字格转90°，然后继续前进，直到回到起点为止。闭回路法举例仍以P&J公司运输问题为例针对最小元素法确定的初始初始调运方案进行的调整闭回路法举例相应的检验数表如果检验数表中所有数字都大于等于零，表明已经得到最优方案。如果检验数中还存在负数，说明还需进一步调整。闭回路法举例进一步调整闭回路法举例最优运输方案运输问题的Excel描述

6、需要两个表格，第一个是参数表；第二个是求解表运输问题的Excel求解求解参数设定运输问题的变体典型的运输问题，符合供需平衡等条件。但是在实际中，常常有一个或几个特征不符合运输问题的要求，统称其为运输问题的变体。典型的不同特征体现为：1.供应总量超出了需求总量2.供应总量小于需求总量3.目的地需求量不确定，仅有最小需求和最大需求4.配送中不能使用特定的出发地——目的地组合。5.目标是使与配送数量有关的总利润最大而不是运输成本最小运输问题的变体举例一化肥调拨问题设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，

7、各地区年需要量及从各化肥厂到各地区运送单位化肥的运价下表运输问题的变体举例一产销平衡表单位运价表运输问题的变体举例一通过表上作业法或Excel可求得最优方案运输问题的变体举例二生产进度安排问题南方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去。按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以现在必须为未来四个月喷气发动机的生产制定计划。以下为生产进度安排表生产进度安排问题Excel求解最优生产进度安排指派问题的提出欧洲的S&M公司，营销经理则面临一个更细节的决

8、策问题。S&M公司将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议，为更好地安排这次会议，营销经理雇用了