第4章-运输问题和指派问题.ppt

《第4章-运输问题和指派问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章运输问题和指派问题TheTransportationandAssignmentProblems本章内容要点运输问题的基本概念运输问题的各种变形运输问题的建模求解与应用指派问题的基本概念指派问题的各种变形指派问题的建模求解与应用本章内容4.1运输问题的基本概念4.2运输问题的数学模型和电子表格模型4.3表上作业法(补充)4.4运输问题的变形4.5运输问题的应用举例4.6指派问题的基本概念4.7匈牙利法(补充)4.8指派问题的变形4.9指派问题的应用举例本章主要内容框架图4.1运输问题的基本概念运输问题最初起源于在日常生活

2、中人们把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最低的，这就成为了一个运筹学问题。随着经济的不断发展，现代物流业的蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。要求科学地组织货源、运输和配送，使得运输问题变得日益复杂，但是其基本思想仍然是实现现有资源的最优化配置。4.1运输问题的基本概念一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量和每个销地的需求量以及各地之间的运输单价已知的前提下，确定

3、一个使得总运输成本最小的方案。平衡运输问题的条件如下：（1）明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位运输成本。（2）需求假设：每一个出发地（产地）都有一个固定的供应量，所有的供应量都必须配送到目的地（销地）。与之类似，每一个目的地（销地）都有一个固定的需求量，整个需求量都必须由出发（产地）地满足。即“总供应量＝总需求量”。（3）成本假设：从任何一个出发地（产地）到任何一个目的地（销地）的货物运输成本与所运送的货物数量成线性比例关系，因此，货物运输成本就等于单位运输成本乘以所运送的货物数量（目标

4、函数是线性的）。4.1运输问题的基本概念典型背景——单一物资运输调度问题设某种物品有:m个产地：产量：n个销地：销量：从产地到销地的单位运价是。求总运费最小的调度方案。4.1运输问题的基本概念产销平衡运输问题的数学模型：设从产地Ai运往销地bj的物资数量为xij（i=1,2,⋯,m;j=1,2,⋯,n)Note1:平衡运输问题有mn个变量，m+n个约束条件，规模很大。x11x12x1nx21x22x2nxm1xm2xmn运输问题决策变量表示由到的物品数量。销地产地销量产量Note2:4.1运输问题的基本概念例4.1某

5、公司有三个加工厂（A1、A2和A3）生产某种产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点（B1、B2、B3和B4），各销售点每日的销量分别为：3吨、6吨、5吨、6吨；从三个加工厂（产地）到四个销售点（销地）的单位产品运价如表4-2所示。问该公司应如何调运产品，才能在满足四个销售点的需求量的前提下，使总运费最少？表4-2三个加工厂到四个销售点的单位产品运价（千元/吨）销售点B1销售点B2销售点B3销售点B4加工厂A1311310加工厂A21928加工厂A3741054.2运输问题的数学模型和电子

6、表格模型解：首先，三个加工厂A1、A2、A3的总产量为7＋4＋9＝20（吨）；四个销售点B1、B2、B3、B4的总销量为3＋6＋5＋6＝20（吨）。也就是说，总产量等于总销量，故该运输问题是一个产销平衡的运输问题。（1）决策变量设xij为从加工厂Ai（i＝1,2,3）运往销售点Bj（j=1,2,3,4）的运输量（吨）。（2）目标函数本问题的目标是使公司的总运费最少4.2运输问题的数学模型和电子表格模型（3）约束条件①三个加工厂的产品都要全部运送出去（产量约束）②四个销售点的产品都要全部得到满足（销量约束）③非负4.2运输问题

7、的数学模型和电子表格模型运输问题是一种特殊的线性规划问题，一般采用“表上作业法”求解运输问题，但Excel的“规划求解”还是采用“单纯形法”来求解。例4.1的电子表格模型（1）设置“条件格式”的操作请参见本章附录Ⅱ（P142）（2）将单元格的字体和背景颜色设置为相同颜色以实现“浑然一体”的效果，这样可以起到隐藏单元格内容的作用。当单元格被选中时，编辑栏中仍然会显示单元格的真实数据。（3）本章所有例题的最优解（运输方案或指派方案）有一个共同特点：“0”值较多，所以都使用了Excel的“条件格式”功能。4.2运输问题的数学模型和

8、电子表格模型需要注意的是，运输问题有这样一个性质（整数解性质），即只要它的供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满，就很不经济了。整数解性质避免了