运输问题和指派问题-1.ppt

4.4 指派问题 指派问题的假设： （1）人的数量和工作的数量相等； （2）每个人只能完成一项工作； （3）每项工作只能由一个人来完成； （4）每个人和每项工作的组合都会有一个相关的成本（单位成本）； （5）目标是要确定如何指派才能使总成本最小。 4.4 指派问题 设决策变量xij为第i个人做第j项工作，而已知目标函数系数cij为第i个人完成第j项工作所需要的单位成本。 平衡指派问题的数学模型为 4.4 指派问题 需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是人，目的地是工作。只不过，每一个出发地的供应量都为1（因为每个人都要完成一项工作），每一个目的地的需求量都为1（因为每项工作都要完成）。由于运输问题有“整数解性质”，因此，没有必要加上所有决策变量都是0-1变量的约束。 指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：匈牙利方法（Hungarian Method），但Excel的“规划求解”还是采用“单纯形法”来求解。 4.4 指派问题 例4.5 某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项工作：A、B、C和D。 由于每个人完成每项任务的时间和工资不同（如表所示）。问如何指派，可使总成本最小。 人员 每一项工作所需要的时间（小时） 每小时工资 （元） 工作A 工作B 工作C 工作D 小张 35 41 27 40 14 小王 47 45 32 51 12 小李 39 56 36 43 13 小刘 32 51 25 46 15 第4章 运输问题 和指派问题 第4章 运输问题和指派问题 本章内容要点 运输问题的基本概念及其各种变形的建模与应用 指派问题的基本概念及其各种变形的建模与应用 本章节内容 4.1 运输问题基本概念 4.2 运输问题数学模型和电子表格模型 4.3 各种运输问题变形的建模 4.4 指派问题 4.5 各种指派问题变形的建模 本章主要内容框架图 4.1 运输问题基本概念 运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最低的，这就成为了一个运筹学问题。 随着经济的不断发展，现代物流业蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。 要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其基本思想仍然是实现现有资源的最优化配置。 4.1 运输问题基本概念 一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量和每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 平衡运输问题的条件： 1. 明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位成本。 2. 需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。即“总供应＝总需求”。 3. 成本假设：从任何一个出发地到任何一个目的地的货物配送成本与所配送的数量成线性比例关系，因此成本就等于配送的单位成本乘以所配送的数量（目标函数是线性的）。 4.1 运输问题基本概念 例4.1 某公司有三个加工厂A1、A2、A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4－1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？ 表4－1 各工厂到各销售点的单位产品运价（元/吨） B1 B2 B3 B4 产量（吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6 4.2 运输问题数学模型和电子表格模型 （1）产销平衡运输问题的数学模型 具有m个产地Ai（i＝1,2,?,m）和n个销地 Bj（j＝1,2,?,n）的运输问题的数学模型为 4.2 运输问题数学模型和电子表格模型 对于例4.1，其数学模型如下： 首先，三个产地A1、A2、A3的总产量为7＋4＋9＝20；四个销地B1、B2、B3、B4的总销量为3＋6＋5＋6＝20。由于总产量等于总销量，故该问题是一个产销平衡的运输问题。 (1)决策变量 设xij为从产地Ai运往销地Bj的运输量(i＝1,2,3;j=1,2,3,4) （2）目标函数 本问题的目标是使得总运