《运筹学课件第三章 运输与指派问题》由会员分享，可在线阅读，更多相关《运筹学课件第三章 运输与指派问题（36页珍藏版）》请在金锄头文库上搜索。
1、第三章 运输与指派第三章 运输与指派运输与指派问题是实际中碰到的比较常见的两类线性规 划问题，它们在变量的取值、约束条件的系数矩阵等具 有一定的特殊性，所以有可能找到比单纯形法更为简便 的求解方法。 运输问题的提出P&J公司是美国的一家经营罐头加工和储运的小公司，该公司收购生菜 并在食品罐头厂中把他们加工成罐头，然后再把这些罐头分销到各地卖 出。该公司的一种主要产品是豆类罐头，这些罐头在三个食品罐头厂加 工，记为罐头厂1，罐头厂2，罐头厂3，然后用卡车把它们运送到位于 美国西部的四个仓库，记为仓库1，仓库2，仓库3和仓库4。现在的问题 是该公司采用怎样的运输方案才能使总运输成本最小。也就是公司
2、要决 定每个罐头加工厂生产的罐头如何被分配到各个仓库，才能保证运输费 用最小。P&J公司运输问题的数据表3-1 P&J公司运输问题参数表（单位：万元）仓库 罐头厂仓库1仓库2仓库3仓库4产地产量（车）罐头厂13113107罐头厂219284罐头厂3741059销地销量（车）3656P&J公司运输问题的模型运输问题的模型运输问题变量的系数矩阵模型的两个假设和两个性质需求假设：每一个出发地都有一个固定的供应量， 所有的供应量都必须配送到目的地。成本假设：从任何一个出发地到目的地的货物配送 成本和所配送的数量成线性比例关系，因此这个成 本等于单位运输成本乘以所运输的数量。性质1 可行解特性：当且仅当
3、供应量的总和与需求 量的总和相等时，运输问题才有可行解。 性质2 整数解特性：如果 都是整数，那么任何 有最优解的运输问题线性规划模型，其最优解也为 整数。 表上作业法求解运输问题 表上作业法是单纯形法在求解运输问题时的一种简化方法，其步骤如下：确定初始基可行解 两种比较简单的方法：最小元素法和Vogel法最小元素法基本思想是就近运输，即从单位运价表中最小的运价处开始确定运输关系，依次类推，直到给出全部方案为止。可 以证明用最小元素法给出的初始解是运输问题的基可行解最小元素法确定初始基可行解 以P&J为例最小元素法确定初始基可行解 确定初始基可行解 Vogel法 最小元素法的的缺点是为了节省一
4、处的费用，但由此可能造成在其他处要多花几倍的费用。VAM揭示，如果在任何行或列上，最便宜的选择没有被采用，那么至少次便宜的选择应该被采用，如果采用了次便宜的选择，就存在一个 罚金成本（penalty cost）,其数额至少等于该行或列中，最便宜的选择与次便宜的选择之间的差。 Vogel法确定初始基可行解 仍以P&J为例Vogel法确定初始基可行解 最优检验与方案的调整最小元素法或Vogel法给出了运输问题的初始基可行解，此时我们还需 通过最优性检验判别该解的目标函数值是否最优。如不是最优解，还需 进行适当的调整。闭回路法用于计算各非基变量（对应空格）的检验数 ，并对可行解进行调整。所谓闭回路是
5、指调运方案中由一个空格和若干个数字格的水平和垂直连 线构成的封闭回路。它是以某空格为起点，用水平或垂直线往前划，每 碰到一数字格转90，然后继续前进，直到回到起点为止。闭回路法举例仍以P&J公司运输问题为例针对最小元素法确定的初始初始调运方案进行的调整闭回路法举例相应的检验数表如果检验数表中所有数字都大于等于零，表明已经得到最优方案。如果检验数中还 存在负数，说明还需进一步调整。闭回路法举例进一步调整闭回路法举例最优运输方案运输问题的Excel描述 需要两个表格，第一个是参数表；第二个是求解表运输问题的Excel求解 求解参数设定运输问题的变体典型的运输问题，符合供需平衡等条件。但是在实际中，
6、常常有一个或 几个特征不符合运输问题的要求，统称其为运输问题的变体。典型的不 同特征体现为：1. 供应总量超出了需求总量2. 供应总量小于需求总量3. 目的地需求量不确定，仅有最小需求和最大需求4. 配送中不能使用特定的出发地目的地组合。5. 目标是使与配送数量有关的总利润最大而不是运输成本最小运输问题的变体举例一化肥调拨问题设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果 相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的 运价下表 运输问题的变体举例一产销平衡表单位运价表运输问题的变体举例一通过表上作业法或Excel可求得最优方案 运输问题的变体举
7、例二生产进度安排问题南方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后一 步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去。按照公司的 一些订单合同，不久公司要交付使用相当多数量的飞机。所以现在必须为未来 四个月喷气发动机的生产制定计划。以下为生产进度安排表生产进度安排问题Excel求解最优生产进度安排指派问题的提出欧洲的S&M公司，营销经理则面临一个更细节的决策问题。S&M公司将 要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商 会议，为更好地安排这次会议，营销经理雇用了四个临时工(An、Ean 、Jone、Shon)，每一个人负责完成下面的一项任务：1.
8、 书面陈述的 文字处理；2. 制作口头和书面陈述的电脑图；3. 会议材料的准备， 包括书面材料的抄写和组织；4. 处理与会者的提前和当场注册报到。 现在他需要确定要将哪项任务指派给哪一个人。指派问题指派问题（Assignment problem）若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同 ，各人完成任务的收益、成本也不同。于是产生应指派哪个人去完成 哪项任务，才能使完成n项任务的总收益最高或总成本最低。这类问题 统称为指派问题。 指派问题的假设1. 被指派者的数量和任务的数量是相同的；2. 每一个被指派者只完成一项任务；3. 每一项任务只能由一个被指派者来完成； 指派问题的模型一般指派问题的数学模型 指派问题的求解库恩(W.W.Kuhn)于1955年提出了指派问题的解法，他引用了匈牙利数 学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中独 立0元素的最多个数等于能覆盖所有0元素的最少直线数。因此，该算 法称为匈牙利法。 求解步骤：第一步：变换指派问题的系数矩阵；(1) 从系数矩阵的每行元素减去该行的最小元素； (2) 从所得系数矩阵每列元素中减去该列最小元素第二步：进行试指派，以寻求最优解。 指派问题的Excel描述及求解
