第4章 运输问题和指派问题.pptVIP

4.4 运输问题的变形 例4.4的电子表格模型 4.5 运输问题的应用举例 例4.5（了解即可） 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。各条航线的起点、终点城市及每天航班数如表4-9所示。假定各条航线使用相同型号的船只，各城市间的航程天数见表4-10。又知每艘船只每次装卸货的时间各需1天。问该航运公司至少应配备多少艘船，才能满足所有航线的运货需求？ 解：该公司所需配备船只分为两部分。 （1）载货航程需要的周转船只数：直接计算。 （2）各港口间调度所需船只数：运输问题。 了解即可 4.5 运输问题的应用举例 例4.5的电子表格模型 了解即可 4.5 运输问题的应用举例 例4.6 设有某种原料的三个产地A1、A2和A3，把这种原料经过加工制成成品，再运往销售地。假设用4吨原料可制成1吨成品。产地A1年产原料30万吨，同时需要成品7万吨；产地A2年产原料26万吨，同时需要成品13万吨；产地A3年产原料24万吨，不需要成品。又知A1与A2的距离为150公里，A1与A3的距离为100公里，A2与A3的距离为200公里。原料运费为3千元/万吨?公里，成品运费为2.5千元/万吨?公里。且已知在产地A1把4万吨原料制成1万吨成品的加工费为5.5千元，在产地A2为4千元，在产地A3为3千元，见表4-16。因条件限制，产地A2的生产规模不能超过年产成品5万吨，而产地A1和产地A3没有限制。问应在何地设厂，生产多少成品，才能使总费用（包括原料运费、成品运费、加工费等）最少？ ? A1 A2 A3 年产原料（万吨） 加工费（千元/万吨） A1 0 150 100 30 5.5 A2 150 0 200 26 4 A3 100 200 0 24 3 成品需求量（万吨） 7 13 0 ? ? 4.5 运输问题的应用举例 解： 该问题包含两个运输问题，一个是原料的运输问题，另一个是成品的运输问题。还有将原料制成成品的问题，所以，总费用＝原料运费＋成品运费＋加工费。 例4.6的线性规划模型 4.5 运输问题的应用举例 例4.6的电子表格模型 4.6 指派问题的基本概念 在生活中经常会遇到这样的问题：某单位需完成n项任务，恰好有n个人可以承担这些任务。由于每个人的专长不同，各人完成的任务不同，所需的时间（或效率）也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务所需的总时间最短（或总效率最高）。这类问题称为指派问题（assignment problem）或分派问题。 平衡指派问题的假设： （1）人的数量和任务的数量相等； （2）每个人只能完成一项任务； （3）每项任务只能由一个人来完成； （4）每个人和每项任务的组合都会有一个相关的成本（单位成本）； （5）目标是要确定如何指派才能使总成本最小。 4.6 指派问题的基本概念 设xij为是否指派第i个人去完成第j项任务，目标函数系数cij为第i个人完成第j项任务所需要的单位成本。 平衡指派问题的线性规划模型如下： 4.6 指派问题的基本概念 需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是“人”，目的地是“任务”。只不过，每个出发地的供应量都为1（因为每个人都要完成一项任务），每个目的地的需求量也都为1（因为每项任务都要完成）。 由于运输问题有“整数解性质”，因此，指派问题没有必要加上所有决策变量都是0-1变量的约束条件。 指派问题是一种特殊的线性规划问题，有一种简便的求解方法：匈牙利方法（Hungarian Method），但Excel的“规划求解”还是采用“单纯形法”来求解。 4.6 指派问题的基本概念 例4.7 某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：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.6 指派问题的基本概念 解： 该问题是一个典型的平衡指派问题。 单位成本为每个人完成每项任务的总工资； 目标是要确定哪个人去完成哪项任务，才能使总成本最少； 供应量为1表示每个人都只能完成一项任务； 需求量为1表示每项任务也只能由一个人来完成； 总人数（4人）和总任务数（4项）相等 4.6 指派问题的基本概念 例4.7的线性规划模型如下： 设xij为是否指派人员i去完成任务j 4.6 指派问题的基本概念 例4.7的电子表格模型