运输问题与指派问题ppt课件.ppt

第六章运输问题与指派问题 运输问题 TransportationProblem 和指派问题 AssignmentProblem 属于线性规划问题 是线性规划的两类常见问题 并且这两类问题具有特殊的数学性质 使得管理科学家能够开发出多种高效独特的求解算法 所以我们专门用一章来研究 1 本章内容 6 1案例研究 L食品公司的运输问题 6 2运输问题的模型与性质 6 3应用EXCEL和LINGO求解运输问题 6 4运输问题变形的一些应用 6 5指派问题 2 6 1L食品公司的运输问题 例1湖南L食品公司是生产食品罐头的企业 有桔子 竹笋 野山菌三个罐头厂 三个工厂的厂址分别在A B C三个靠近不同原料产地的城镇 每个工厂都能生产不同品种的罐头 但每个工厂生产不同品种罐头的产能不同 各工厂生产与厂名相同的罐头的设计产能要大一些 2009年6月份来自深圳 武汉 成都和西安的四个配送中心的野山菌罐头订单和各工厂的野山菌罐头的计划产量如表6 1所示 2009年6月每箱野山菌罐头从各个工厂到各个配送中心的具体运价如表6 2所示 3 表6 1罐头的产能和配送中心需求 单位 箱 表6 2各工厂到配送中心的野山菌罐头运价 单位 元 箱 4 表6 1 表6 2可以用下图表示 5 小张的运输方案 单位 箱 小张的运输方案需要运费成本是 6 小刘的运输方案 单位 箱 小刘的运输方案需要运费成本是 7 杨经理的思考 小刘的运输方案比小张的节约了140元 于是 杨经理决定用小刘的方案 但是 会不会还有更节约的运输方案呢 杨经理开始琢磨这个问题 或许以后能找到更好的方案吧 不管怎么样 以后要在运输方案安排上多用点心思了 因为每隔几天运输部都要为公司不同的产品订单集中安排一次运输 如果每次都能用最好的方案 一年下来也是一笔可观的费用呢 8 6 2运输问题的模型与性质 1运输问题的模型例1中提到的湖南某食品公司的问题就是一个典型的运输问题 在运输问题中 寻求从产地到销地的最小的运输成本 运输问题的一般提法是这样的 某种物资有若干个产地和销地 若已知各个产地的产量 各个销地的销量以及各产地到各销地的单位运价 或运输距离 问应如何组织运输 才能使总运费 或总的运输量 最省 假定有m个产地 n个销地 我们定义如下变量 9 第产地的供应量 i 1 2 m 第销地的需求量 j 1 2 n 从产地到销地的单位运费 i 1 2 m j 1 2 n 产地到销地的运输数量 i 1 2 m j 1 2 n 则该问题为求解最佳运输方案 即求解所有的值 使总的运输费用达到最少 决策变量为 10 该问题的数学模型形式为 11 把例1的问题用数学模型表达出来就是 12 2运输问题的性质运输问题中每一个产地都有一定的供应量 supply 配送到销地 每一个销地都有一定的需求量 demand 接收从产地发出的产品 基本的运输问题有如下性质 1 需求假设 TheRequirementsAssumption 每一个产地都有一个固定的供应量 所有的供应量都必须配送到销地 与之相类似 每一个销地都有一个固定的需求量 整个需求量都必须由产地满足 13 2 可行解特性 TheFeasibleSolutionsProperty 当且仅当供应量的总和等于需求量的总和 也就是产销平衡时 运输问题才有可行解 3 成本假设 TheCostAssumption 从任何一个产地到任何一个销地的货物配送成本和所配送的数量成线性比例关系 因此这个成本就等于配送的单位成本乘以配送的数量 4 整数解性质 IntegerSolutionsProperty 只要运输问题的供应量和需求量都是整数 任何有可行解的运输问题必然有所有决策变量都是整数的最优解 因此 没有必要加上所有变量都是整数的约束条件 这使得求解运输问题避免了整数约束所导致的计算复杂性大幅度增加的麻烦 14 6 3应用EXCEL和LINGO求解运输问题 1应用EXCEL求解运输问题由于运输问题是线性规划问题 我们可以很方便地在电子表格中建模求解 见图6 2 应用 规划求解 后 我们得到一个最优解 由图6 2中表格的阴影部分的数据可知 A厂运50箱到武汉 运30箱到西安 B厂运100箱到西安 C厂运85箱到深圳 60箱到武汉 75箱到成都 此时总运费最低 最优值是31530元 采用这个方案 食品公司6月份这批野山菌罐头订单的运输费用比小张的方案 32390元 节约了860元 比小刘的方案 32250元 节约了720元 15 16 2LINGO使用简介 LINGO是用来求解线性和非线性优化问题的简易工具 LINGO内置了一种建立最优化模型的语言 可以简便地表达大规模问题 利用LINGO高效的求解器可快速求解并分析结果 因为篇幅所限 本小节只对LINGO最基本的应用和功能结构进行介绍 每个功能详细的应用技巧请见本书相关的例子和LINGO的帮助文件 17 1 LINGO快速入门当你在windows下开始运行LINGO系统时 会得到类似下面的一个窗口 18 线性规划模型在电子表格中布局的好坏关系到问题可读性和求解方便性的高低 本节以第一章中的例1 资源分配问题 为例来说明一下如