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

1、第第4 4章章 运输问题和指派问题运输问题和指派问题The Transportation The Transportation and Assignment Problemsand Assignment Problems本章内容要点本章内容要点运输问题运输问题的基本概念的基本概念运输问题运输问题的各种变形的各种变形运输问题运输问题的建模求解与应用的建模求解与应用指派问题指派问题的基本概念的基本概念指派问题指派问题的各种变形的各种变形指派问题指派问题的建模求解与应用的建模求解与应用本章内容本章内容4.1 4.1 运输问题的基本概念运输问题的基本概念4.2 4.2 运输问题的数学模型和电子表格模型

2、运输问题的数学模型和电子表格模型4.3 4.3 表上作业法表上作业法( (补充补充) )4.4.4 4 运输问题的变形运输问题的变形4.4.5 5 运输问题的应用举例运输问题的应用举例4.4.6 6 指派问题的基本概念指派问题的基本概念4.7 4.7 匈牙利法匈牙利法( (补充补充) )4.4.8 8 指派问题的变形指派问题的变形4.4.9 9 指派问题的应用举例指派问题的应用举例本章主要内容框架图本章主要内容框架图产销平衡（总产量等于总销量）产大于销（总产量大于总销量）运输问题 销大于产（总产量小于总销量）数学模型和电子表格模型运输问题和指派问题运输问题的变形及其应用平衡指派问题（总人数等于

3、总任务数）指派问题 数学模型和电子表格模型指派问题的变形及其应用4.1 4.1 运输问题运输问题的的基本概念基本概念u 运输问题最初起源于在日常生活中人们把运输问题最初起源于在日常生活中人们把某些物品或人们自身从一些地方转移到另某些物品或人们自身从一些地方转移到另一些地方，要求所采用的一些地方，要求所采用的运输路线运输路线或或运输运输方案是最经济或成本最低方案是最经济或成本最低的，这就成为了的，这就成为了一个运筹学问题。一个运筹学问题。u 随着经济的不断发展，现代随着经济的不断发展，现代物流业物流业的蓬勃的蓬勃发展，如何充分利用时间、信息、仓储、发展，如何充分利用时间、信息、仓储、配送和联运体

4、系创造更多的价值，向运筹配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。学提出了更高的挑战。u 要求科学地组织货源、运输和配送，使得要求科学地组织货源、运输和配送，使得运输问题变得日益复杂，但是其基本思想运输问题变得日益复杂，但是其基本思想仍然是仍然是实现现有资源的最优化配置实现现有资源的最优化配置。4.1 4.1 运输问题运输问题的的基本概念基本概念u一般的运输问题就是解决如何把某种产品从若干个一般的运输问题就是解决如何把某种产品从若干个产地产地调运到若干个调运到若干个销地销地，在每个产地的，在每个产地的供应量供应量和每个销地的和每个销地的需求量需求量以及各地之间的以及各地之间的运输

5、单价运输单价已知的前提下，确定一已知的前提下，确定一个使得总运输成本最小的方案。个使得总运输成本最小的方案。u平衡运输问题平衡运输问题的条件如下：的条件如下：（1 1）明确出发地（）明确出发地（产地产地）、目的地（）、目的地（销地销地）、供应量（）、供应量（产量产量）、）、需求量（需求量（销量销量）和）和单位运输成本单位运输成本。（2 2）需求假设需求假设：每一个出发地（：每一个出发地（产地产地）都有一个）都有一个固定的供应量固定的供应量，所有的供应量都必须配送到目的地（所有的供应量都必须配送到目的地（销地销地）。与之类似，每一个）。与之类似，每一个目的地（目的地（销地销地）都有一个）都有一个

6、固定的需求量固定的需求量，整个需求量都必须由出，整个需求量都必须由出发（发（产地产地）地满足。即）地满足。即“总供应量总需求量总供应量总需求量”。（3 3）成本假设成本假设：从任何一个出发地（：从任何一个出发地（产地产地）到任何一个目的地（）到任何一个目的地（销地销地）的货物运输成本与所运送的货物数量成线性比例关系，因）的货物运输成本与所运送的货物数量成线性比例关系，因此，货物运输成本就等于单位运输成本乘以所运送的货物数量（此，货物运输成本就等于单位运输成本乘以所运送的货物数量（目标函数是线性的）。目标函数是线性的）。4.1 4.1 运输问题运输问题的的基本概念基本概念典型背景典型背景单一物资

7、运输调度问题单一物资运输调度问题 设某种物品有设某种物品有: m个产地：个产地： 产量：产量： n个销地：个销地： 销量：销量： 从产地从产地 到销地到销地 的单位运价是的单位运价是 。 求总运费最小的调度方案。求总运费最小的调度方案。mAAA,21nBBB,21maaa,21nbbb,21iAiBijc4.1 4.1 运输问题运输问题的的基本概念基本概念u产销平衡运输问题产销平衡运输问题的数学模型：的数学模型： 设从产地设从产地Ai运往销地运往销地bj的物资数量为的物资数量为xij（i=1,2,m; j=1,2,n) ) 11mnijijab njmixnjbxmiaxxczijjmiiji

8、njijminjijij,2,1,2,1,0,2,1,2,1,min1111Note 1: 平衡运输问题有平衡运输问题有m n 个变量，个变量，m+n 个约束个约束条件，规模很大。条件，规模很大。111111111111111111A1212111111111111111111mnaaaAbbbx11 x12 x1n x21 x22 x2n xm1 xm2 xmn 运输问题决策变量决策变量 表示由表示由 到到 的物品数量。的物品数量。iAiBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB2121222221211121

9、1121销地销地产地产地销量销量产量产量Note 2: 4.1 4.1 运输问题运输问题的的基本概念基本概念u例例4.1 4.1 某公司有某公司有三个加工厂三个加工厂（A1A1、A2A2和和A3A3）生产某种产）生产某种产品，每日的产量分别为：品，每日的产量分别为：7 7吨、吨、4 4吨、吨、9 9吨；该公司把这吨；该公司把这些产品分别运往些产品分别运往四个销售点四个销售点（B1B1、B2B2、B3B3和和B4B4），各销），各销售点每日的销量分别为：售点每日的销量分别为：3 3吨、吨、6 6吨、吨、5 5吨、吨、6 6吨；从三个吨；从三个加工厂（产地）到四个销售点（销地）的单位产品运价加工厂

10、（产地）到四个销售点（销地）的单位产品运价如表如表4-24-2所示。问该公司应如何调运产品，才能在满足所示。问该公司应如何调运产品，才能在满足四个销售点的需求量的前提下，使总运费最少？四个销售点的需求量的前提下，使总运费最少？ 表表4-2 4-2 三个加工厂到四个销售点的单位产品运价（千元三个加工厂到四个销售点的单位产品运价（千元/ /吨）吨）销售点销售点B1B1销售点销售点B2B2销售点销售点B3B3销售点销售点B4B4加工厂加工厂A1A13 311113 31010加工厂加工厂A2A21 19 92 28 8加工厂加工厂A3A37 74 410105 54.2 4.2 运输问题运输问题的的

11、数学模型和电子表格模型数学模型和电子表格模型解：解：首先，三个加工厂首先，三个加工厂A1A1、A2A2、A3A3的总产量为的总产量为7 74 49 92020（吨）；四个销售点（吨）；四个销售点B1B1、B2B2、B3B3、B4B4的总销量为的总销量为3 36 65 56 62020（吨）。也就是说，总产（吨）。也就是说，总产量等于总销量，故该运输问题是一个产销平衡的运输问题。量等于总销量，故该运输问题是一个产销平衡的运输问题。（1 1）决策变量）决策变量 设设xij为从加工厂为从加工厂Ai（i i1,2,31,2,3）运往销售点）运往销售点Bj（j=1,2,3,4j=1,2,3,4）的运输量

12、（）的运输量（吨）。吨）。（2 2）目标函数）目标函数 本问题的目标是使公司的总运费最少本问题的目标是使公司的总运费最少111213142122232431323334min z311 310 9 2 8 7410 5xxxxxxxxxxxx4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型（3 3）约束条件）约束条件 三个加工厂的三个加工厂的产品都要全部产品都要全部运送出去（产运送出去（产量约束）量约束） 四个销售点的四个销售点的产品都要全部产品都要全部得到满足（销得到满足（销量约束）量约束） 非负非负111213142122232431323334111213

13、142122232431323334112131122232min z311 310 9 2 8 7 410 57 4 9 3 s.t. 6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1323331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxij4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型u运输问题是一种特殊的线性规划问题，一般采用运输问题是一种特殊的线性规划问题，一般采用“表上作表上作业法业法”求解运输问题，但求解运输问题，但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来

14、求解。u例例4.14.1的电子表格模型的电子表格模型（1 1）设置）设置“条件格式条件格式”的的操作请参见本章附录操作请参见本章附录（P142P142）（2 2）将单元格的字体和背将单元格的字体和背景颜色设置为相同颜色以实景颜色设置为相同颜色以实现现“浑然一体浑然一体”的效果，这的效果，这样可以起到隐藏单元格内容样可以起到隐藏单元格内容的作用。当单元格被选中时的作用。当单元格被选中时，编辑栏中仍然会显示单元，编辑栏中仍然会显示单元格的真实数据。格的真实数据。（3）本章所有例题的最优本章所有例题的最优解（运输方案或指派方案）解（运输方案或指派方案）有一个共同特点：有一个共同特点：“0”值值较多，

15、所以都使用了较多，所以都使用了Excel的的“条件格式条件格式”功能。功能。4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型u 需要注意的是，运输问题有这样一个性需要注意的是，运输问题有这样一个性质（质（整数解性质整数解性质），即只要它的），即只要它的供应量供应量和和需求量需求量都是都是整数整数，任何有可行解的运，任何有可行解的运输问题就必然有所有决策变量都是输问题就必然有所有决策变量都是整数整数的最优解的最优解。因此，没有必要加上所有变。因此，没有必要加上所有变量都是整数的约束条件。量都是整数的约束条件。u 由于运输量经常以卡车、集装箱等为单由于运输量经常以卡

16、车、集装箱等为单位，如果卡车不能装满，就很不经济了位，如果卡车不能装满，就很不经济了。整数解性质避免了运输量（运输方案。整数解性质避免了运输量（运输方案）为小数的麻烦。）为小数的麻烦。4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型（1 1）销大于产（供不应求）销大于产（供不应求）运输问题运输问题的数学模型的数学模型（以满足小的产量为准以满足小的产量为准）1111 ()()min (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijzc xxaimxbjnxim jnLLLL产量约束销量约束11mniji

17、jab4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型（2 2）产大于销（供过于求）产大于销（供过于求）运输问题运输问题的数学模型的数学模型（以满足小的销量为准以满足小的销量为准）1111()()min z (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijc xxaimxbjnxim jnLLLL产量约束销量约束11mnijijab4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.2 4.2 自来水输送问题。某市有自来水输送问题。某市有甲、乙、丙、丁四个居民甲、乙

18、、丙、丁四个居民区区，自来水由，自来水由A、B、C三个水库三个水库供应。四个居民区每天必供应。四个居民区每天必须得到保证的须得到保证的基本生活用水基本生活用水量分别为量分别为30、70、10、10千吨千吨，但由于水源紧张，三个水库每天最多只能分别供应，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从千吨自来水。由于地理位置的差别，自来水公司从各水库向各居民区供水所需付出的引水管理费不同（见各水库向各居民区供水所需付出的引水管理费不同（见P95的的表表4 4，其中水库，其中水库C与丁区之间没有输水管道），与丁区之间没有输水管道），其他管理费

19、用都是其他管理费用都是 450元千吨。根据公司规定，各居民元千吨。根据公司规定，各居民区用户按照统一标准区用户按照统一标准900元千吨收费。此外，四个居民元千吨收费。此外，四个居民区都向公司申请了区都向公司申请了额外用水额外用水量，分别为每天量，分别为每天50、70、20、40千吨。问：千吨。问：（1）该公司应如何分配供水量，才能获利最多？）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司库每天的最大供水量都提高一倍，问那时供

20、水方案应如何改变？公司利润可增加到多少？利润可增加到多少？4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（1 1）的线性规划模型：）的线性规划模型：目标：从目标：从获利最多获利最多转化为转化为引水管理费最少引水管理费最少1234123412312341234123111222m in z1 6 01 3 02 2 01 7 0 1 4 01 3 01 9 01 5 0 1 9 02 0 02 3 05 06 0 5 03 08 0s.t.7 01AAAABBBBCCCAAAABBBBCCCABCABCxxxxxxxxxxxxxxxxx

21、xxxxxxxxxxx333444 01 03 01 0 5 00 ,;1, 2, 3, 4ABCABijxxxxxxiAB Cj（）4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（1 1）的电子表格模型：）的电子表格模型：4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（1 1）的最优供水方案网络图：）的最优供水方案网络图：B BC CA A乙乙丙丙甲甲丁丁50508080140140303050506060505050501010505040401010水库水库 供水量供水

22、量 居民居民区区最大最大供水量供水量最大最大用水量用水量4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（2 2）方法方法1 1的线性规划模型：的线性规划模型：目标：将目标：将获利最多获利最多转化为转化为引水管理费最少引水管理费最少1234123412312341234123111222min z160130220170 140130190150 190200230100120 10080s.t.140AAAABBBBCCCAAAABBBBCCCABCABCxxxxxxxxxxxxxxxxxxxxxxxxxxxxx3334430 500

23、 ,;1, 2,3, 4ABCABijxxxxxiA B Cj（）4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（2 2）方法方法1 1 的电子表格模型：的电子表格模型：4.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（2 2）的最优供水方案网络图：）的最优供水方案网络图：B BC CA A乙乙丙丙甲甲丁丁1001008080140140303050501201201001001001005050303050503030水库水库 供水量供水量 居民居民区区最大最大供水量供水量最

24、大最大用水量用水量40404.2 4.2 运输问题运输问题的的数学模型和电子表格模型数学模型和电子表格模型例例4.24.2问题（问题（2 2）方法方法2 2：目标为目标为获利最多获利最多12341234123max z290320230280 310320260300 260250220AAAABBBBCCCxxxxxxxxxxx4.4 4.4 运输问题的变形运输问题的变形 现实生活中符合产销平衡运输问题的每一个条件的情况很少。一个现实生活中符合产销平衡运输问题的每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件特征近似但其中的一个或者几个特征却并不符合产

25、销平衡运输问题条件的运输问题却经常出现。的运输问题却经常出现。下面是要讨论的一些特征：下面是要讨论的一些特征：（1 1）总供应量大于总需求量总供应量大于总需求量。每一个供应量（产量）代表了从其出发。每一个供应量（产量）代表了从其出发地（产地）中运送出去的最大数量（而不是一个固定的数值，地（产地）中运送出去的最大数量（而不是一个固定的数值，）。）。（2 2）总供应量小于总需求量总供应量小于总需求量。每一个需求量（销量）代表了在其目的。每一个需求量（销量）代表了在其目的地（销地）中所接收到的最大数量（而不是一个固定的数值，地（销地）中所接收到的最大数量（而不是一个固定的数值，）。）。（3 3）一个

26、目的地（销地）一个目的地（销地）同时存在着最小需求量和最大需求量同时存在着最小需求量和最大需求量，于是，于是所有在这两个数值之间的数量都是可以接收的（需求量可在一定范围内所有在这两个数值之间的数量都是可以接收的（需求量可在一定范围内变化，变化，、）。）。（4 4）在运输中）在运输中不能使用不能使用特定的出发地（产地）特定的出发地（产地）-目的地（销地）组合目的地（销地）组合（xij=0=0）。）。（5 5）目标是使与运输量有关的）目标是使与运输量有关的总利润最大总利润最大而不是使总成本最小（而不是使总成本最小（MinMin MaxMax）4.4 4.4 运输问题的变形运输问题的变形例例4.44

27、.4 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表意种产品的数量来衡量（见表4-74-7的最右列）。而每种产品每天有一定的最右列）。而每种产品每天有一定的需求量（见表的需求量（见表4-74-7的最后一行）。除了工厂的最后一行）。除了工厂2 2不能生产产品不能生产产品3 3以外，每以外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本个工厂都可以生产这些产品。然而，

28、每种产品在不同工厂中的单位成本是有差异的（如表是有差异的（如表4-74-7所示）。所示）。 现在需要决定的是：在哪个工厂生产哪种产品，可使总成本最小。现在需要决定的是：在哪个工厂生产哪种产品，可使总成本最小。表表4-7 4-7 三个工厂生产四种新产品的有关数据三个工厂生产四种新产品的有关数据单位成本单位成本生产能力生产能力产品产品1 1产品产品2 2产品产品3 3产品产品4 4工厂工厂1 141412727282824247575工厂工厂2 24040292923237575工厂工厂3 337373030272721214545需求量需求量20203030303040404.4 4.4 运输问

29、题的变形运输问题的变形解：解：把把“指定工厂生产指定工厂生产产品问题产品问题”看作看作“运输运输问题问题”。本问题中，工。本问题中，工厂厂2 2不能生产产品不能生产产品3 3，这，这样可以样可以增加约束条件增加约束条件x230 0 ；并且，总供应量；并且，总供应量（75+75+45=19575+75+45=195） 总需总需求量（求量（20+30+30+40=12020+30+30+40=120）。）。其数学模型如下：其数学模型如下： 设设xij为工厂为工厂i生产产品生产产品j的数量的数量1112131421222431323334112131122232132333142434min z41

30、272824 4029 23 3730272120 130 230 340 s.t.xxxxxxxxxxxxxxxxxxxxxxx（产品 ）（产品 ）（产品 ）（产11121314212223243132333423475 175 245 30 230 1,2,3;1,2,3,4ijxxxxxxxxxxxxxxij品 ）（工厂 ）（工厂 ）（工厂 ）（工厂 不生产产品 ）（）4.4 4.4 运输问题的变形运输问题的变形例例4.44.4的电子表格模型的电子表格模型产品产品4 4分在分在2 2个工厂（工厂个工厂（工厂2 2和工厂和工厂3 3）生产）生产4.4 4.4 运输问题的变形运输问题的变形例

31、例4.4 4.4 需求量存在最小需求量和最大需求量（需求量可在一定范围内变需求量存在最小需求量和最大需求量（需求量可在一定范围内变化）的问题化）的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客（批发商）很可能有大量订购。顾客，四个处于国内不同区域的潜在顾客（批发商）很可能有大量订购。顾客1 1是公司最好的顾客，所以他的订单要全部满足；顾客是公司最好的顾客，所以他的订单要全部满足；顾客2 2和顾客和顾客3 3也是公司也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的很重要的顾客，所以营销经理

32、认为至少要满足他们订单的1/31/3；对于顾客；对于顾客4 4，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表表4-84-8）。问）。问应向每一个顾客供应多少产品应向每一个顾客供应多少产品，才能使公司的总利润最大？，才能使公司的总利润最大？表表4-8 4-8 三个工厂供应四个顾客的相关数据三个工厂供应四个顾客的相关数据单位利润（元）单位利润（元）产量产量顾客顾客1 1顾客顾客2 2顾客顾

33、客3 3顾客顾客4 4工厂工厂1 1555542424646535380008000工厂工厂2 2373718183232484850005000工厂工厂3 3292959595151353570007000最少供应量最少供应量7000700030003000200020000 0要求订购量要求订购量700070009000900060006000800080004.4 4.4 运输问题的变形运输问题的变形解：解：该问题要求满足不该问题要求满足不同顾客的需求（订购量同顾客的需求（订购量），解决办法：），解决办法：实际供应量实际供应量最少供应最少供应量量实际供应量实际供应量要求订购要求订购量量

34、目标是总利润最大，目标是总利润最大，而不是总成本最小。而不是总成本最小。其数学模型如下：其数学模型如下： 设设xij为为工厂工厂i供应供应顾客顾客j的产品数量的产品数量111213142122232431323334111213142122232431323334max z55424653 37183248 295951358000 15000 27000 3s.t. xxxxxxxxxxxxxxxxxxxxxxxxx（工厂 ）（工厂 ）（工厂 ）1121311222321323331424347000 130009000 220006000 38000 40 1,2,3;1,2,3,4ijx

35、xxxxxxxxxxxij（顾客 ）（顾客 ）（顾客 ）（顾客 ）（）4.4 4.4 运输问题的变形运输问题的变形例例4.44.4的电子表格模型的电子表格模型4.5 4.5 运输问题运输问题的的应用举例应用举例例例4.54.5（了解即可）（了解即可） 某航运公司承担某航运公司承担六个港口六个港口城市城市A A、B B、C C、D D、E E、F F的的四条固定航线四条固定航线的物资运输任务的物资运输任务。各条航线的起点、终点城市及每天航班数如表。各条航线的起点、终点城市及每天航班数如表4-4-9 9所示。假定各条航线使用相同型号的船只，各城所示。假定各条航线使用相同型号的船只，各城市间的航程天

36、数见表市间的航程天数见表4-104-10。又知每艘船只每次装卸。又知每艘船只每次装卸货的时间各需货的时间各需1 1天。问该航运公司至少应配备多少天。问该航运公司至少应配备多少艘船，才能满足所有航线的运货需求？艘船，才能满足所有航线的运货需求？解：解：该公司所需配备船只分为两部分。该公司所需配备船只分为两部分。（1 1）载货航程需要的周转船只数：）载货航程需要的周转船只数：直接计算直接计算。（2 2）各港口间调度所需船只数：）各港口间调度所需船只数：运输问题运输问题。了解即可了解即可4.5 4.5 运输问题运输问题的的应用举例应用举例例例4.54.5的电子表格模型的电子表格模型了解即可了解即可4

37、.5 4.5 运输问题运输问题的的应用举例应用举例例例4.6 4.6 设有某种设有某种原料原料的三个产地的三个产地A1A1、A2A2和和A3A3，把这种原料经过，把这种原料经过加工制加工制成成品成成品，再运往销售地。假设用，再运往销售地。假设用4 4吨原料可制成吨原料可制成1 1吨成品。产地吨成品。产地A1A1年产年产原料原料3030万吨，同时需要成品万吨，同时需要成品7 7万吨；产地万吨；产地A2A2年产原料年产原料2626万吨，同时需要万吨，同时需要成品成品1313万吨；产地万吨；产地A3A3年产原料年产原料2424万吨，不需要成品。又知万吨，不需要成品。又知A1A1与与A2A2的距的距离

38、为离为150150公里，公里，A1A1与与A3A3的距离为的距离为100100公里，公里，A2A2与与A3A3的距离为的距离为200200公里。原公里。原料运费为料运费为3 3千元千元/ /万吨万吨公里，成品运费为公里，成品运费为2.52.5千元千元/ /万吨万吨公里。且已知在公里。且已知在产地产地A1A1把把4 4万吨原料制成万吨原料制成1 1万吨成品的加工费为万吨成品的加工费为5.55.5千元，在产地千元，在产地A2A2为为4 4千元，在产地千元，在产地A3A3为为3 3千元，见表千元，见表4-164-16。因条件限制，产地。因条件限制，产地A2A2的生产规模的生产规模不能超过年产成品不能

39、超过年产成品5 5万吨，而产地万吨，而产地A1A1和产地和产地A3A3没有限制。问应在何地设没有限制。问应在何地设厂，生产多少成品，才能使厂，生产多少成品，才能使总费用总费用（包括（包括原料运费原料运费、成品运费成品运费、加工加工费费等）最少？等）最少？ A1A2A3年产原料（万吨）年产原料（万吨）加工费（千元加工费（千元/万吨）万吨）A10150100305.5A21500200264A31002000243成品需求量（万吨）成品需求量（万吨）7130 4.5 4.5 运输问题运输问题的的应用举例应用举例解：解：该问题包含该问题包含两个运两个运输问题输问题，一个是，一个是原原料的运输问题料的

40、运输问题，另，另一个是一个是成品的运输成品的运输问题问题。还有将原料。还有将原料制成成品的问题，制成成品的问题，所以，总费用原所以，总费用原料运费成品运费料运费成品运费加工费。加工费。例例4.64.6的线性规的线性规划模型划模型33331231111111213212223313233112131112223221323A1A2A3A1A2min z32.55.54330 26 24 4 4 s.t. ijijijijijijc xc yzzzxxxxxxxxxxxxzxxxzxx（的年产原料）（的年产原料）（的年产原料）（在加工的原料）（在加工的原料）33311121312122232313

41、23331121311222321323332A3A1A2A3A1A2A34 7 13 0 5 xzyyyzyyyzyyyzyyyyyyyyyz（在加工的原料）（在加工的成品）（在加工的成品）（在加工的成品）（的成品需求量）（的成品需求量）（的成品需求量）A2 ,0 ,1,2,3ijijjxyzi j（的生产规模限制）（）4.5 4.5 运输问题运输问题的的应用举例应用举例例例4.64.6的电子表格模型的电子表格模型4.6 4.6 指派问题指派问题的基本概念的基本概念u在生活中经常会遇到这样的问题：某单位需完成在生活中经常会遇到这样的问题：某单位需完成n n项任务项任务，恰好有，恰好有n n个

42、人个人可以承担这些任务。由于每个人的专长不同可以承担这些任务。由于每个人的专长不同，各人完成的任务不同，所需的时间（或效率）也不同。于，各人完成的任务不同，所需的时间（或效率）也不同。于是产生是产生应指派哪个人去完成哪项任务，使完成应指派哪个人去完成哪项任务，使完成n n项任务所需项任务所需的总时间最短的总时间最短（或总效率最高）。这类问题称为（或总效率最高）。这类问题称为指派问题指派问题（assignment problemassignment problem）或）或分派问题分派问题。u平衡指派问题的假设：平衡指派问题的假设：（1 1）人的数量和任务的数量）人的数量和任务的数量相等相等；（2

43、 2）每个人）每个人只能完成一项只能完成一项任务；任务；（3 3）每项任务）每项任务只能由一个人只能由一个人来完成；来完成；（4 4）每个人和每项任务的组合都会有一个相关的成本）每个人和每项任务的组合都会有一个相关的成本（单位成本单位成本）；）；（5 5）目标是要确定如何指派才能使）目标是要确定如何指派才能使总成本最小总成本最小。4.6 4.6 指派问题的基本概念指派问题的基本概念u设设xij为是否指派为是否指派第第i个人个人去完成去完成第第j项任务项任务，目标函数，目标函数系数系数cij为第为第i个人完成第个人完成第j项任务所需要的项任务所需要的单位成本单位成本。u平衡指派问题的线性规划模型

44、如下平衡指派问题的线性规划模型如下：1111 min z1 1,2,s.t.1 1,2,0 ,1,2, nnijijijnijjnijiijc xxinxjnxi jnLLL（一个人做一件事）（一件事一个人做）（非负）（） （） （）4.6 4.6 指派问题的基本概念指派问题的基本概念u需要说明的是：需要说明的是：指派问题指派问题实际上是一种实际上是一种特殊的运输问特殊的运输问题题。其中出发地是。其中出发地是“人人”，目的地是，目的地是“任务任务”。只不过。只不过，每个出发地的，每个出发地的供应量都为供应量都为1 1（因为每个人都要完成一（因为每个人都要完成一项任务），每个目的地的项任务），每

45、个目的地的需求量也都为需求量也都为1 1（因为每项任（因为每项任务都要完成）。务都要完成）。u由于运输问题有由于运输问题有“整数解性质整数解性质”，因此，因此，指派问题指派问题没没有必要有必要加上所有决策变量都是加上所有决策变量都是0-10-1变量变量的约束条件。的约束条件。u指派问题是一种特殊的线性规划问题，有一种简便的指派问题是一种特殊的线性规划问题，有一种简便的求解方法：求解方法：匈牙利方法匈牙利方法（Hungarian MethodHungarian Method），但），但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。4.6 4.6

46、指派问题指派问题的基本概念的基本概念例例4.74.7 某公司的营销经理将要主持召开一年一度的由营销区某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排这次会议，他安排小张小张、小王小王、小李小李、小刘小刘四个人，每个人四个人，每个人负责完成一项负责完成一项任务：任务：A A、B B、C C和和D D。 由于每个人完成每项任务的时间和工资不同。问公司应指由于每个人完成每项任务的时间和工资不同。问公司应指派何人去完成何任务，才能使总成本最少？派何人去完成何任务，才能使总成本最少？完成

47、每项任务的时间（小时）完成每项任务的时间（小时）每小时工资每小时工资（元）（元）任务任务A A任务任务B B任务任务C C任务任务D D小张小张35354141272740401414小王小王47474545323251511212小李小李39395656363643431313小刘小刘323251512525464615154.6 4.6 指派问题指派问题的基本概念的基本概念解解： 该问题是一个该问题是一个典型的平衡指派问题典型的平衡指派问题。u单位成本单位成本为每个人完成每项任务的总工为每个人完成每项任务的总工资；资；u目标目标是要确定哪个人去完成哪项任务，是要确定哪个人去完成哪项任务，才

48、能使总成本最少；才能使总成本最少；u供应量为供应量为1 1表示每个人都只能完成一项任表示每个人都只能完成一项任务；务；u需求量为需求量为1 1表示每项任务也只能由一个人表示每项任务也只能由一个人来完成；来完成；u总人数（总人数（4 4人）和总任务数（人）和总任务数（4 4项）项）相等相等4.6 4.6 指派问题指派问题的基本概念的基本概念例例4.74.7的线性规划模型如下：的线性规划模型如下：设设xij为是否指派人员为是否指派人员i去完成任务去完成任务j 1A1112 A2223 A3334 A4441A11m in z 3514411427144014 4712451232125112 39

49、13561336134313 3215511525154615s.t.BCDBCDBCDBCDBCxxxxxxxxxxxxxxxxxxxx12 A2223 A3334 A4441A2 A3 A4 A1234123411 1 1 1 1 1 1 DBCDBCDBCDBBBBCCCCxxxxxxxxxxxxxxxxxxxxxxxxx（ 小 张 要 完 成 一 项 任 务 ）（ 小 王 要 完 成 一 项 任 务 ）（ 小 李 要 完 成 一 项 任 务 ）（ 小 刘 要 完 成 一 项 任 务 ）（ 任 务 A要 有 一 人 完 成 ）（ 任 务 B要 有 一 人 完 成 ）（ 任 务 C要 有

50、一 人 完 成 ）234D1 0 1, 2, 3, 4A , DDDDijxxxxijB CD（ 任 务要 有 一 人 完 成 ）（ 非 负 ）（；）4.6 4.6 指派问题指派问题的基本概念的基本概念例例4.74.7的电子表格模型的电子表格模型4.6 4.6 指派问题指派问题的基本概念的基本概念例例4.74.7的最优指派方案网络图的最优指派方案网络图小李小李小刘小刘小张小张B BC CA AD D人人 指派指派 任务任务 小王小王4.8 4.8 指派问题的变形指派问题的变形u 经常会遇到指派问题的经常会遇到指派问题的变形变形，之所以称它们为变形，是因为，之所以称它们为变形，是因为它们都不满足

51、平衡指派问题所有假设中的一个或者多个。它们都不满足平衡指派问题所有假设中的一个或者多个。u 一般考虑下面的一些特征：一般考虑下面的一些特征：（1 1）某人）某人不能不能完成某项任务（相应的完成某项任务（相应的xij0 0）; ;（2 2）每个人只能完成一项任务，但是任务数比人数多）每个人只能完成一项任务，但是任务数比人数多( (人少事多人少事多););（3 3）每项任务只由一个人完成，但是人数比任务数多（）每项任务只由一个人完成，但是人数比任务数多（人多事少人多事少）；）；（4 4）某人可以同时被指派多个任务（）某人可以同时被指派多个任务（一人可做多事一人可做多事）；）；（5 5）某事需要由多

52、人共同完成（）某事需要由多人共同完成（一事需多人做一事需多人做）；）；（6 6）目标是与指派有关的）目标是与指派有关的总利润最大总利润最大而不是总成本最小；而不是总成本最小；（7 7）实际需要完成的任务数不超过总人数也不超过总任务数。）实际需要完成的任务数不超过总人数也不超过总任务数。 4.8 4.8 指派问题的变形指派问题的变形例例4.84.8 题目见例题目见例4.44.4，即某公司需要安排三个工厂，即某公司需要安排三个工厂来生产四种新产品，相关的数据在表来生产四种新产品，相关的数据在表4-74-7中已经给中已经给出。在例出。在例4.44.4中，允许产品生产分解，但这将产生中，允许产品生产分

53、解，但这将产生与产品生产分解相关的隐性成本（包括额外的设置与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成本等）。因此，管理人员决定在、配送和管理成本等）。因此，管理人员决定在禁禁止产品生产分解止产品生产分解发生的情况下对问题进行分析。发生的情况下对问题进行分析。 新问题描述为：已知如表新问题描述为：已知如表4-74-7所示的数据，问如所示的数据，问如何把每个工厂指派给至少一个新产品（每种产品只何把每个工厂指派给至少一个新产品（每种产品只能在一个工厂生产），才能使总成本最少？能在一个工厂生产），才能使总成本最少？4.8 4.8 指派问题的变形指派问题的变形解：解： 该问题可视为该问题

54、可视为指派工厂生产产品问题指派工厂生产产品问题，工厂，工厂可以看作指派问题中的人，产品则可以看作需要可以看作指派问题中的人，产品则可以看作需要完成的任务。完成的任务。 由于有由于有四种产品四种产品和和三个工厂三个工厂，所以就需要有，所以就需要有一个工厂生产两种新产品，只有工厂一个工厂生产两种新产品，只有工厂1 1和工厂和工厂2 2有有生产两种产品的能力，这是因为工厂生产两种产品的能力，这是因为工厂1 1和工厂和工厂2 2的的生产能力都是生产能力都是7575，而工厂，而工厂3 3的生产能力是的生产能力是4545。 这里涉及如何把这里涉及如何把运输问题运输问题转化为转化为指派问题指派问题，关键之处

55、在于关键之处在于数据转化数据转化。4.8 4.8 指派问题的变形指派问题的变形数据转化：数据转化：（1 1）单位指派成本单位指派成本: : 原来的单位成本转化成原来的单位成本转化成整整批成本批成本（整批成本单位成本需求量），即单（整批成本单位成本需求量），即单位指派成本为位指派成本为每个工厂生产每种产品的成本每个工厂生产每种产品的成本。（2 2）供应量和需求量的转化供应量和需求量的转化：三个工厂生产四：三个工厂生产四种产品，但一种产品只能在一个工厂生产。根据种产品，但一种产品只能在一个工厂生产。根据生产能力，工厂生产能力，工厂3 3只能生产一种产品（供应量为只能生产一种产品（供应量为1 1），

56、而工厂），而工厂1 1和工厂和工厂2 2可以生产两种产品（供应量可以生产两种产品（供应量为为2 2），而四种产品的需求量都为），而四种产品的需求量都为1 1。还有。还有“总供总供应量（应量（2+2+1=52+2+1=5） 总需求量（总需求量（1+1+1+1=41+1+1+1=4）”, ,为为“人多事少人多事少”的的指派问题指派问题。4.8 4.8 指派问题的变形指派问题的变形例例4.84.8的线性规划模型：的线性规划模型：设设xij为指派工厂为指派工厂i（i=1,2,3=1,2,3）生产产品）生产产品j（j=1,2,3,4) =1,2,3,4) 111213142122243132333411

57、121314212223243132333411min z412027302830244040202930 234037203030273021402 12 21 3s.t.xxxxxxxxxxxxxxxxxxxxxxxxx（ 工 厂 ）（ 工 厂）（ 工 厂）2131122232132333142434231 11 21 31 4=0 230 1, 2,3;1, 2,3, 4ijxxxxxxxxxxxxij（ 产 品 ）（ 产 品）（ 产 品 ）（ 产 品）（ 工 厂不 能 生 产 产 品 ）（）4.8 4.8 指派问题的变形指派问题的变形例例4.84.8的电子表格模型的电子表格模型4.8

58、4.8 指派问题指派问题的应用举例的应用举例例例4.9 4.9 科学家选派问题。某制药公司准备开发新药，市场部科学家选派问题。某制药公司准备开发新药，市场部在进行了大量的市场调查之后，共有在进行了大量的市场调查之后，共有五个项目五个项目被公司选定。被公司选定。 项目项目1 1；开发一种更加有效的抗抑郁剂。；开发一种更加有效的抗抑郁剂。 项目项目2 2：开发一种治疗躁狂抑郁病的新药。：开发一种治疗躁狂抑郁病的新药。 项目项目3 3：为女性开发一种副作用更小的节育方法。：为女性开发一种副作用更小的节育方法。 项目项目4 4：开发一种预防：开发一种预防HIVHIV的疫苗。的疫苗。 项目项目5 5：开

59、发一种更有效的降压药。：开发一种更有效的降压药。公司将聘请公司将聘请五位科学家五位科学家来负责这些项目的研发，但每位科学来负责这些项目的研发，但每位科学家根据自己的学科领域对各个项目的兴趣程度不同。为了使家根据自己的学科领域对各个项目的兴趣程度不同。为了使这些科学家能够从事他们感兴趣的项目，而又使公司能够在这些科学家能够从事他们感兴趣的项目，而又使公司能够在开发新药中的成功性尽可能大，公司设立了一个开发新药中的成功性尽可能大，公司设立了一个投标系统投标系统，每位科学家都有每位科学家都有10001000点点，用来向自己感兴趣的项目投标。投，用来向自己感兴趣的项目投标。投标点数越多，则表示他对该项

60、目的兴趣程度越高。标点数越多，则表示他对该项目的兴趣程度越高。4.9 4.9 指派问题指派问题的应用举例的应用举例表表4-20 4-20 五位科学家的投标情况五位科学家的投标情况投标点投标点项目项目1项目项目2项目项目3项目项目4项目项目5合计合计李尔博士李尔博士10010040040020020020020010010010001000朱诺博士朱诺博士0 02002008008000 00 010001000刘哲博士刘哲博士10010010010010010010010060060010001000王凯博士王凯博士2672671531539999451451303010001000罗林博士罗