您所在位置：网站首页 > 研究报告 > 综合/其它运筹学课件第三章运输与指派问题

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

36页

卖家[上传人]：飞***

文档编号：51733046

上传时间：2018-08-16

文档格式：PPT

文档大小：416KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 36 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第三章运输与指派第三章运输与指派运输与指派问题是实际中碰到的比较常见的两类线性规划问题，它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性，所以有可能找到比单纯形法更为简便的求解方法。运输问题的提出P&J公司是美国的一家经营罐头加工和储运的小公司，该公司收购生菜并在食品罐头厂中把他们加工成罐头，然后再把这些罐头分销到各地卖出。该公司的一种主要产品是豆类罐头，这些罐头在三个食品罐头厂加工，记为罐头厂1，罐头厂2，罐头厂3，然后用卡车把它们运送到位于美国西部的四个仓库，记为仓库1，仓库2，仓库3和仓库4。现在的问题是该公司采用怎样的运输方案才能使总运输成本最小。也就是公司要决定每个罐头加工厂生产的罐头如何被分配到各个仓库，才能保证运输费用最小。P&J公司运输问题的数据表3-1 P&J公司运输问题参数表（单位：万元）仓库罐头厂仓库1仓库2仓库3仓库4产地产量（车）罐头厂13113107罐头厂219284罐头厂3741059销地销量（车）3656P&J公司运输问题的模型运输问题的模型运输问题变量的系数矩阵模型的两个假设和两个性质需求假设：每一个出发地都有一个固定

2、的供应量，所有的供应量都必须配送到目的地。成本假设：从任何一个出发地到目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本等于单位运输成本乘以所运输的数量。性质1 可行解特性：当且仅当供应量的总和与需求量的总和相等时，运输问题才有可行解。性质2 整数解特性：如果都是整数，那么任何有最优解的运输问题线性规划模型，其最优解也为整数。表上作业法求解运输问题表上作业法是单纯形法在求解运输问题时的一种简化方法，其步骤如下：确定初始基可行解两种比较简单的方法：最小元素法和Vogel法最小元素法基本思想是就近运输，即从单位运价表中最小的运价处开始确定运输关系，依次类推，直到给出全部方案为止。可以证明用最小元素法给出的初始解是运输问题的基可行解最小元素法确定初始基可行解以P&J为例最小元素法确定初始基可行解确定初始基可行解 Vogel法最小元素法的的缺点是为了节省一处的费用，但由此可能造成在其他处要多花几倍的费用。VAM揭示，如果在任何行或列上，最便宜的选择没有被采用，那么至少次便宜的选择应该被采用，如果采用了次便宜的选择，就存在一个罚金成本（penalty

3、cost）,其数额至少等于该行或列中，最便宜的选择与次便宜的选择之间的差。 Vogel法确定初始基可行解仍以P&J为例Vogel法确定初始基可行解最优检验与方案的调整最小元素法或Vogel法给出了运输问题的初始基可行解，此时我们还需通过最优性检验判别该解的目标函数值是否最优。如不是最优解，还需进行适当的调整。闭回路法用于计算各非基变量（对应空格）的检验数，并对可行解进行调整。所谓闭回路是指调运方案中由一个空格和若干个数字格的水平和垂直连线构成的封闭回路。它是以某空格为起点，用水平或垂直线往前划，每碰到一数字格转90，然后继续前进，直到回到起点为止。闭回路法举例仍以P&J公司运输问题为例针对最小元素法确定的初始初始调运方案进行的调整闭回路法举例相应的检验数表如果检验数表中所有数字都大于等于零，表明已经得到最优方案。如果检验数中还存在负数，说明还需进一步调整。闭回路法举例进一步调整闭回路法举例最优运输方案运输问题的Excel描述需要两个表格，第一个是参数表；第二个是求解表运输问题的Excel求解求解参数设定运输问题的变体典型的运输问题，符合供需平衡等条件。但是在实际中，

4、常常有一个或几个特征不符合运输问题的要求，统称其为运输问题的变体。典型的不同特征体现为：1. 供应总量超出了需求总量2. 供应总量小于需求总量3. 目的地需求量不确定，仅有最小需求和最大需求4. 配送中不能使用特定的出发地目的地组合。5. 目标是使与配送数量有关的总利润最大而不是运输成本最小运输问题的变体举例一化肥调拨问题设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价下表运输问题的变体举例一产销平衡表单位运价表运输问题的变体举例一通过表上作业法或Excel可求得最优方案运输问题的变体举例二生产进度安排问题南方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去。按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以现在必须为未来四个月喷气发动机的生产制定计划。以下为生产进度安排表生产进度安排问题Excel求解最优生产进度安排指派问题的提出欧洲的S&M公司，营销经理则面临一个更细节的决策问题。S&

5、M公司将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议，为更好地安排这次会议，营销经理雇用了四个临时工(An、Ean 、Jone、Shon)，每一个人负责完成下面的一项任务：1. 书面陈述的文字处理；2. 制作口头和书面陈述的电脑图；3. 会议材料的准备，包括书面材料的抄写和组织；4. 处理与会者的提前和当场注册报到。现在他需要确定要将哪项任务指派给哪一个人。指派问题指派问题（Assignment problem）若需完成n项任务，分配给n个人承担。由于每人的专长、能力不同，各人完成任务的收益、成本也不同。于是产生应指派哪个人去完成哪项任务，才能使完成n项任务的总收益最高或总成本最低。这类问题统称为指派问题。指派问题的假设1. 被指派者的数量和任务的数量是相同的；2. 每一个被指派者只完成一项任务；3. 每一项任务只能由一个被指派者来完成；指派问题的模型一般指派问题的数学模型指派问题的求解库恩(W.W.Kuhn)于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。因此，该算法称为匈牙利法。求解步骤：第一步：变换指派问题的系数矩阵；(1) 从系数矩阵的每行元素减去该行的最小元素； (2) 从所得系数矩阵每列元素中减去该列最小元素第二步：进行试指派，以寻求最优解。指派问题的Excel描述及求解

《运筹学课件第三章运输与指派问题》由会员飞***分享，可在线阅读，更多相关《运筹学课件第三章运输与指派问题》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源