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

1、第第4章章 运输问题运输问题 和指派问题和指派问题实用运筹学实用运筹学运用运用ExcelExcel建模和求解建模和求解第第4 4章章运输问题和指派问题运输问题和指派问题第第4章章 运输问题运输问题 和指派问题和指派问题本章内容要点本章内容要点 运输问题运输问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用 指派问题指派问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用第第4章章 运输问题运输问题 和指派问题和指派问题本章节内容本章节内容4.1 4.1 运输问题基本概念运输问题基本概念4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子

2、表格模型4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模4.4 4.4 运输问题应用举例运输问题应用举例4.5 4.5 指派问题指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模第第4章章 运输问题运输问题 和指派问题和指派问题本章主要内容框架图本章主要内容框架图产销平衡（总产量等于总销量）产大于销（总产量大于总销量）销大于产（总产量小于总销量）运输问题数学模型和电子表格模型运输问题和指派问题各种变形的建模应用举例平衡指派问题（总人数等于总任务数）指派问题数学模型和电子表格模型各种变形的建模第第4章章 运输问题运输问题 和指派问题和指派问题4.1 4.1 运输问题

3、基本概念运输问题基本概念运输问题最初起源于人们在日常生活中把某些运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方物品或人们自身从一些地方转移到另一些地方，要求所采用的，要求所采用的运输路线运输路线或或运输方案是最经济运输方案是最经济或成本最低或成本最低的，这就成为了一个运筹学问题。的，这就成为了一个运筹学问题。随着经济的不断发展，现代随着经济的不断发展，现代物流业物流业蓬勃发展，蓬勃发展，如何充分利用时间、信息、仓储、配送和联运如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的体系创造更多的价值，向运筹学提出了更高的挑战。挑战。要求

4、科学地组织货源、运输和配送使得运输问要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其基本思想仍然是题变得日益复杂，但是其基本思想仍然是实现实现现有资源的最优化配置现有资源的最优化配置。第第4章章 运输问题运输问题 和指派问题和指派问题4.1 4.1 运输问题基本概念运输问题基本概念一般的运输问题就是解决如何把某种产品从若干个一般的运输问题就是解决如何把某种产品从若干个产地产地调运到若干个调运到若干个销地销地，在每个产地的，在每个产地的供应量供应量和每个销地的和每个销地的需求量需求量已知，并知道各地之间的已知，并知道各地之间的运输单价运输单价的前提下，如的前提下，如何确定一个使得总

5、的运输费用最小的方案。何确定一个使得总的运输费用最小的方案。平衡运输问题平衡运输问题的条件：的条件：1.1.明确出发地（产地）、目的地（销地）、供应量（产量）、需明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位成本。求量（销量）和单位成本。2.2.需求假设：每一个出发地都有一个固定的供应量，所有的供应需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有一个固量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。即定的需求量，整个需求量都必须由出发地满足。即“总供应总供应总需求总需

6、求”。3.3.成本假设：从任何一个出发地到任何一个目的地的货物配送成成本假设：从任何一个出发地到任何一个目的地的货物配送成本与所配送的数量成线性比例关系，因此成本就等于配送的单本与所配送的数量成线性比例关系，因此成本就等于配送的单位成本乘以所配送的数量（目标函数是线性的）。位成本乘以所配送的数量（目标函数是线性的）。第第4章章 运输问题运输问题 和指派问题和指派问题4.1 4.1 运输问题基本概念运输问题基本概念例例4.1 4.1 某公司有三个加工厂某公司有三个加工厂A1A1、A2A2、A3A3生产某产品，每生产某产品，每日的产量分别为：日的产量分别为：7 7吨、吨、4 4吨、吨、9 9吨；该

7、公司把这些产品吨；该公司把这些产品分别运往四个销售点分别运往四个销售点B1B1、B2B2、B3B3、B4B4，各销售点每日销，各销售点每日销量分别为：量分别为：3 3吨、吨、6 6吨、吨、5 5吨、吨、6 6吨；从各工厂到各销售点吨；从各工厂到各销售点的单位产品运价如表的单位产品运价如表4 41 1所示。问该公司应如何调运这所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费些产品，在满足各销售点的需要量的前提下，使总运费最少？最少？ 表表4 41 1 各工厂到各销售点的单位产品运价（元各工厂到各销售点的单位产品运价（元/ /吨）吨）B1B1B2B2B3B3B4B4产量（

8、吨）产量（吨）A1A13 311113 310107 7A2A21 19 92 28 84 4A3A37 74 410105 59 9销量（吨）销量（吨）3 36 65 56 6第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（1 1）产销平衡产销平衡运输问题的数学模型运输问题的数学模型 具有具有m个产地个产地A Ai i（i1,2,1,2, ,m）和和n个销地个销地 B Bj j（j1,2,1,2, ,n）的运输问题的数学模型为的运输问题的数学模型为1111()()M in (1, 2,) s.t. (1, 2,)

9、0 (1, 2,; 1, 2,)mnijijijnijijmijjiijzc xxaimxbjnximjn 产 量 约 束销 量 约 束 LLLL11mnijijab第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型对于例对于例4.14.1，其数学模型如下：，其数学模型如下： 首先，三个产地首先，三个产地A1A1、A2A2、A3A3的总产量为的总产量为7 74 49 92020；四个；四个销地销地B1B1、B2B2、B3B3、B4B4的总销量为的总销量为3 36 65 56 62020。由于总。由于总产量等于总销量，故

10、该问题是一个产销平衡的运输问题。产量等于总销量，故该问题是一个产销平衡的运输问题。(1)(1)决策变量决策变量 设设xij为从产地为从产地AiAi运往销地运往销地BjBj的运输量的运输量(i(i1,2,3;j=1,2,3,4)1,2,3;j=1,2,3,4) （2 2）目标函数）目标函数 本问题的目标是使得总运输费最小。本问题的目标是使得总运输费最小。1 11 21 31 42 12 22 32 43 13 23 33 4M in z31 1 31 0 9 2 8 741 0 5xxxxxxxxxxxx第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格

11、模型运输问题数学模型和电子表格模型（3 3）约束条件）约束条件满足产地产量满足产地产量（3 3个产地的个产地的产品都要全部产品都要全部配送出去）配送出去）满足销地销量满足销地销量（4 4个销地的个销地的产品都要全部产品都要全部得到满足）得到满足）非负非负111213142122232431323334111213142122232431323334112131122232Min z311 310 9 2 8 7 410 57 4 9 3 s.t. 6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1323331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxi

12、j第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u运输问题是一种特殊的线性规划问题，一般采用运输问题是一种特殊的线性规划问题，一般采用“表上作表上作业法业法”求解运输问题，但求解运输问题，但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。u例例4.14.1的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u 需要注意的是：运输问题有这样一个性质需要注意的是：运输问题

13、有这样一个性质（整数解性质整数解性质），只要它的），只要它的供应量供应量和和需求需求量量都是都是整数整数，任何有可行解的运输问题必，任何有可行解的运输问题必然有所有决策变量都是然有所有决策变量都是整数的最优解整数的最优解。因。因此，没有必要加上所有变量都是整数的约此，没有必要加上所有变量都是整数的约束条件。束条件。u 由于运输量经常以卡车、集装箱等为单位由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满的话，就很不经济了，如果卡车不能装满的话，就很不经济了。整数解性质就避免了运输量（运输方案。整数解性质就避免了运输量（运输方案）为小数的麻烦。）为小数的麻烦。第第4章章 运输问题运输问题 和

14、指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（2 2）产大于销（供过于求）产大于销（供过于求）运输问题运输问题的数学模型的数学模型（以满足小的销量为准以满足小的销量为准）11mnijijab1111()()Min z (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijc xxaimxbjnxim jn 产量约束销量约束LLLL第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（3 3）销大于产（供不应求）销大于

15、产（供不应求）运输问题运输问题的数学模型的数学模型（以满足小的产量为准以满足小的产量为准）11mnijijab1111 ()()Min (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, )mniji jijnijijmijjiijzc xxaimxbjnxim jn产量约束销量约束LLLL第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.2 4.2 某厂按合同规定须于当年每个季度末分别提某厂按合同规定须于当年每个季度末分别提供供1010，1515，2525，2020台同一规格的柴油机。已知该厂台

16、同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表各季度的生产能力及生产每台柴油机的成本如表4 44 4所示。如果生产出来的柴油机当季不交货的，每台所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用15001500元。要求元。要求在完成合同的情况下，做出使该厂全年生产（包括在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。储存、维护）费用最小的决策。表表4 44 4 各季度的生产能力及生产每台柴油机的成本各季度的生产能力及生产每台柴油机的成本季度季度生产能力（台）生产能力（台）单位成本（万元）单位

17、成本（万元）1 1252510.810.82 2353511.111.13 3303011.011.04 4101011.311.3第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解：解：这是一个这是一个生产与储存（库存）问题生产与储存（库存）问题，除了采用第，除了采用第3 3章的方法外，还可以转化为章的方法外，还可以转化为运输问题运输问题来做。来做。 由于每个季度生产出来的柴油机不一定当季交货，由于每个季度生产出来的柴油机不一定当季交货，所以设所以设xij为第为第i季度生产的第季度生产的第j季度交货的柴油机数季度交

18、货的柴油机数。则第则第i季度生产的第季度生产的第j季度交货的每台柴油机的实际成季度交货的每台柴油机的实际成本本cij为：为： cij= =第第i季度每台的生产成本季度每台的生产成本+0.15(+0.15(j-i) )（储存、维护等费用）（储存、维护等费用） 把第把第i季度生产的柴油机数看作第季度生产的柴油机数看作第i个生产厂商的个生产厂商的产量；把第产量；把第j季度交货的柴油机数看作第季度交货的柴油机数看作第j个销售点的个销售点的销量；生产成本加储存、维护等费用看作运费。将生销量；生产成本加储存、维护等费用看作运费。将生产与储存问题转化为运输问题，相关数据见表产与储存问题转化为运输问题，相关数

19、据见表4 45 5。第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型表表4 45 5 柴油机生产的相关数据柴油机生产的相关数据1 12 23 34 4生产能力生产能力1 110.810.810.9510.9511.1011.1011.2511.2525252 211.1011.1011.2511.2511.4011.4035353 311.0011.0011.1511.1530304 411.3011.301010需求量需求量1010151525252020由表由表4 45 5可知，总产量（生产能力）为可知，总产量（

20、生产能力）为25+35+30+10=10025+35+30+10=100，总销量（需求量）为，总销量（需求量）为10+15+25+20=7010+15+25+20=70，因此是，因此是产大于销产大于销的运输问题。的运输问题。 第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型该生产与该生产与储存问题储存问题（转化为（转化为产大于销产大于销的运输问的运输问题）的数题）的数学模型为学模型为111213142223243334M in z10.8010.9511.1011.25 11.1011.2511.40 11.0011

21、.15 xxxxxxxxx4411121314222324333444111222132333 11.3025 35 30 10s.t. 10 15 xxxxxxxxxxxxxxxxx14243444 25200 ( ,1, 2,3, 4; )ijxxxxxijij第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.24.2的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3 某公司从两个产地某公

22、司从两个产地A1A1、A2A2将物品运往将物品运往三个销地三个销地 B1 B1、B2B2、B3B3，各产地的产量、各销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运地的销量和各产地运往各销地每件物品的运费如表费如表4 46 6所示。问应如何调运，可使得总所示。问应如何调运，可使得总运输费最小？运输费最小？表表4 46 6 例例4.34.3的运输费用表的运输费用表 B1B1B2B2B3B3产量产量A1A11313151512127878A2A21111292922224545销量销量535336366565（销大于产）（销大于产）第第4章章 运输问题运输问题 和指派问题和指派问题4.

23、2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解：解：由表由表4 46 6知，总产量为知，总产量为78+45=12378+45=123，总销量为，总销量为53+36+65=15453+36+65=154，销大于产销大于产( (供不应求供不应求) )。数学模型如下：。数学模型如下： 设设xij为产地为产地AiAi运往销地运往销地BjBj的物品数量的物品数量11121321222311121312122232112111222213233Min z 13151211292278 ()45 ()53 ()s.t. 36 ()65 ()0(1,2;1,2,3)ijxxxxxx

24、xxxAxxxAxxBxxBxxBxij产地产地销地销地销地第第4章章 运输问题运输问题 和指派问题和指派问题4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模现实生活中符合产销平衡运输问题每一个条件的情况很少。一现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。输问题条件的

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

26、，于是所有在这两个数值之间的数量都是可以接收的（这两个数值之间的数量都是可以接收的（, ,）。）。（4 4）在配送中）在配送中不能使用不能使用特定的出发地特定的出发地目的地组合（目的地组合（xij=0=0）。）。（5 5）目标是使与配送数量有关的）目标是使与配送数量有关的总利润最大总利润最大而不是使总成本最而不是使总成本最小。（小。（MinMin MaxMax）第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.44.4 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。某公司决定使用三个有生产余力的工厂进行四种新产品的生

27、产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表意种产品的数量来衡量（见表4 47 7的最右列）。而每种产品每天有一定的最右列）。而每种产品每天有一定的需求量（见表的需求量（见表4 47 7的最后一行）。每家工厂都可以制造这些产品，除的最后一行）。每家工厂都可以制造这些产品，除了工厂了工厂2 2不能生产产品不能生产产品3 3以外。然而，每种产品在不同工厂中的单位成本以外。然而，每种产品在不同工厂中的单位成本是有差异的（如表是有差异的（如表4 47 7所示）。所示）。 现在需要决定的是在哪个

28、工厂生产哪种产品，可使总成本最小。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。表表4 47 7 产品生产的有关数据产品生产的有关数据单位成本（元）单位成本（元）生产能力生产能力产品产品1 1产品产品2 2产品产品3 3产品产品4 4工厂工厂1 141412727282824247575工厂工厂2 24040292923237575工厂工厂3 337373030272721214545需求量需求量2020303030304040第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模解：解：指定工厂生产产品指定工厂生产产品可以看作

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 z41272824 4029 23 3730272120 (1)30 (2)30 (3)

30、40 (s.t. xxxxxxxxxxxxxxxxxxxxxxx产品产品产品111213142122232431323334234)75 (1)75 (2)45 (3)00(1,2,3;1,2,3,4)ijxxxxxxxxxxxxxxij产品工厂工厂工厂第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.44.4的电子表格模型的电子表格模型产品产品4 4分在分在2 2个工厂生产个工厂生产第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5 某公司在某公司在

31、3 3个工厂中专门生产一种产品。在未来的个工厂中专门生产一种产品。在未来的4 4个月中，有四个月中，有四个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客1 1是公司是公司最好的顾客，所以他的全部订购量都应该满足；顾客最好的顾客，所以他的全部订购量都应该满足；顾客2 2和顾客和顾客3 3也是公司很也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/31/3；对于顾客对于顾客4 4，销售经理认为并不需要进行特殊考虑。由于运输成本上的差异，销售经理认为

32、并不需要进行特殊考虑。由于运输成本上的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客（见表个顾客（见表4 48 8）。问应）。问应向每一个顾客供应多少货物向每一个顾客供应多少货物，以使公司总利润，以使公司总利润最大？最大？表表4 48 8 工厂供应顾客的相关数据工厂供应顾客的相关数据单位利润（元）单位利润（元）产量产量顾客顾客1 1顾客顾客2 2顾客顾客3 3顾客顾客4 4工厂工厂1 1555542424646535380008000工厂工厂2 2373718183232484850005000工厂工厂

33、3 3292959595151353570007000最小采购量最小采购量7000700030003000200020000 0最大采购量最大采购量70007000900090006000600080008000第第4章章 运输问题运输问题 和指派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模解：解：该问题要求满足不该问题要求满足不同顾客的需求（采购量同顾客的需求（采购量），解决办法：），解决办法：实际供给量实际供给量 最小采购量最小采购量实际供给量实际供给量 最大采购量最大采购量 目标是利润最大，而目标是利润最大，而不是成本最小。不是成本最小。其数学模型如下：其数

34、学模型如下： 设设xij为工厂为工厂i供应给顾供应给顾客客j的产品数量的产品数量111213142122232431323334111213142122232431323334Max z55424653 37183248 295951358000 (1)5000 (2)7000 (3)s.t. xxxxxxxxxxxxxxxxxxxxxxxxx工厂工厂工厂1121311222321323331424347000 (1)30009000 (2)20006000 (3)8000 (4)0(1,2,3;1,2,3,4)ijxxxxxxxxxxxxij顾客顾客顾客顾客第第4章章 运输问题运输问题 和指

35、派问题和指派问题4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.4 4.4 运输问题应用举例运输问题应用举例例例4.64.6 某厂生产设备是以销定产的。已知某厂生产设备是以销定产的。已知1 16 6月份各月的生产能力、月份各月的生产能力、合同销量和单台设备平均生产费用，如表合同销量和单台设备平均生产费用，如表4 49 9所示。所示。 已知上年末库存已知上年末库存103103台。如果当月生产出来的设备当月不交货，则台。如果当月生产出来的设备当月不交货，则需要运到分厂库房，每台增加运输成本

36、需要运到分厂库房，每台增加运输成本0.10.1万元，每台设备每月的平均万元，每台设备每月的平均仓储费、维护费为仓储费、维护费为0.20.2万元。万元。7 78 8月份为销售淡季，全厂停产月份为销售淡季，全厂停产1 1个月，个月，因此在因此在6 6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存8080台。加班生产设备每台增台。加班生产设备每台增加成本加成本1 1万元。问应如何安排万元。问应如何安排1 16 6月份的生产，使总的生产（包括运输月份的生产，使总的生产（包括运输、仓储、维护）费用最少？、仓储、维护）费用最少？月份月份正常生产能力正常生产能力（台）（台）加班生产能力加班生产

37、能力（台）（台）合同销量合同销量（台）（台）单台费用单台费用（万元）（万元）1 1月月6060101010410415152 2月月50501010757514143 3月月9090202011511513.513.54 4月月100100404016016013135 5月月100100404010310313136 6月月80804040707013.513.5第第4章章 运输问题运输问题 和指派问题和指派问题4.4 4.4 运输问题应用举例运输问题应用举例解：解：这是一个生产与储存问题，但可以转化为运这是一个生产与储存问题，但可以转化为运输问题来做。输问题来做。（是否可以采用第（是否可以

38、采用第3 3章的方法做？同学们可以试章的方法做？同学们可以试试，然后进行比较）试，然后进行比较）生产方案不变，但总费用为：生产方案不变，但总费用为：8329.78329.7万元万元u根据已知条件可以列出生产能力（正常生产能根据已知条件可以列出生产能力（正常生产能力和加班生产能力）和销量以及运价表（力和加班生产能力）和销量以及运价表（P120P120）u数学模型数学模型P120P120121121u电子表格模型电子表格模型P122P122u求解结果求解结果P123P123第第4章章 运输问题运输问题 和指派问题和指派问题4.4 4.4 运输问题应用举例运输问题应用举例例例4.74.7 华中金刚石

39、锯片厂有两条生产线，分别生产华中金刚石锯片厂有两条生产线，分别生产直径直径900-1800mm900-1800mm大锯片基体大锯片基体2000020000片，直径片，直径350-350-800mm800mm中小锯片基体中小锯片基体4000040000片。公司在全国有片。公司在全国有2525个销个销售网点，主要销售区域集中在福建、广东、广西、售网点，主要销售区域集中在福建、广东、广西、四川、山东四川、山东5 5个石材主产区。为完成总厂的要求，个石材主产区。为完成总厂的要求，公司决定一方面拿出公司决定一方面拿出10%10%的产量稳定与前期各个客的产量稳定与前期各个客户的联系以保证将来的市场区域份额

40、，另一方面，户的联系以保证将来的市场区域份额，另一方面，面临如何将剩余的面临如何将剩余的90%90%的产量合理分配给的产量合理分配给五个石材五个石材主产区和其他省区主产区和其他省区，以获取最大的利润。各个销售，以获取最大的利润。各个销售区的最低需求、销售固定费用、每片平均运费、每区的最低需求、销售固定费用、每片平均运费、每片从总厂库房的购进价与当地的销售价差贡献等自片从总厂库房的购进价与当地的销售价差贡献等自然情况见表然情况见表4 41212。问应如何分配给各个销售区，。问应如何分配给各个销售区，才能使得总利润为最大？才能使得总利润为最大？第第4章章 运输问题运输问题 和指派问题和指派问题4.

41、4 4.4 运输问题应用举例运输问题应用举例解：解：该问题数据较多，但是经过分该问题数据较多，但是经过分析，其产量在最低需求和最高需求析，其产量在最低需求和最高需求之间，并且目标函数是最大利润，之间，并且目标函数是最大利润，可以化简为表可以化简为表4 41313（P124P124）u数学模型数学模型P124P124u电子表格模型电子表格模型P125P125u求解结果求解结果P126P126第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题u在现实生活中，经常会遇到指派人员做某项在现实生活中，经常会遇到指派人员做某项工作（任务）的情况。工作（任务）的情况。指派问题

42、指派问题的许多应用是的许多应用是用来帮助管理人员解决如何为一项即将开展的用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题。其他的一些应用如为工工作指派人员的问题。其他的一些应用如为工作指派机器、设备或工厂等。作指派机器、设备或工厂等。u指派问题也称指派问题也称分配问题分配问题，主要研究人和工作，主要研究人和工作（任务）间如何匹配，以使所有工作完成的效（任务）间如何匹配，以使所有工作完成的效率实现最优化。形式上，指派问题给定了一系率实现最优化。形式上，指派问题给定了一系列所要完成的工作以及一系列完成工作的人员列所要完成的工作以及一系列完成工作的人员，所需要解决的问题就是要确定出指派哪个

43、人，所需要解决的问题就是要确定出指派哪个人去完成哪项工作。去完成哪项工作。第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题u指派问题的假设：指派问题的假设：（1 1）人的数量和工作的数量）人的数量和工作的数量相等相等；（2 2）每个人）每个人只能完成一项只能完成一项工作；工作；（3 3）每项工作）每项工作只能由一个人只能由一个人来完成；来完成；（4 4）每个人和每项工作的组合都会有）每个人和每项工作的组合都会有一个相关的成本（一个相关的成本（单位成本单位成本）；）；（5 5）目标是要确定如何指派才能使）目标是要确定如何指派才能使总总成本最小成本最小。第第4章章

44、 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题u设决策变量设决策变量xij为第为第i个人做第个人做第j项工作，而已项工作，而已知目标函数系数知目标函数系数cij为第为第i个人完成第个人完成第j项工作所项工作所需要的单位成本。需要的单位成本。u平衡指派问题的数学模型为平衡指派问题的数学模型为1111 ()Min z1 (1,2, )s.t. 1 (1,2, )0 ( ,1,2, ) nnijijijnijjnijiijijc xxinxjnxi jn(第 人只能做一项工作)(第 项工作只能一人做)非负 LLL第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.

45、5 指派问题指派问题u需要说明的是：需要说明的是：指派问题指派问题实际上是一种实际上是一种特殊特殊的运输问题的运输问题。其中出发地是人，目的地是工作。其中出发地是人，目的地是工作。只不过，每一个出发地的。只不过，每一个出发地的供应量都为供应量都为1 1（因（因为每个人都要完成一项工作），每一个目的地为每个人都要完成一项工作），每一个目的地的的需求量都为需求量都为1 1（因为每项工作都要完成）。（因为每项工作都要完成）。由于运输问题有由于运输问题有“整数解性质整数解性质”，因此，没有，因此，没有必要加上所有决策变量都是必要加上所有决策变量都是0-10-1变量变量的约束。的约束。u指派问题是一种特

46、殊的线性规划问题，有一指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：种快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题例例4.84.8 某公司的营销经理将要主持召开一年一度的某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、。

47、为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项小李、小刘等四个人，每个人负责完成下面的一项工作：工作：A A、B B、C C和和D D。 由于每个人完成每项任务的时间和工资不同（如由于每个人完成每项任务的时间和工资不同（如表表4 41414所示）。问如何指派，可使总成本最小。所示）。问如何指派，可使总成本最小。人员人员每一项工作所需要的时间（小时）每一项工作所需要的时间（小时）每小时工资每小时工资（元）（元）工作工作A A工作工作B B工作工作C C工作工作D D小张小张35354141272740401414小王小王474745453232515112

48、12小李小李39395656363643431313小刘小刘32325151252546461515第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题解解：该问题是一个：该问题是一个典型的指派问题典型的指派问题。单位成本单位成本为每个人做每项工作的总为每个人做每项工作的总工资工资目标目标是要确定哪个人做哪一项工作是要确定哪个人做哪一项工作，使总成本最小，使总成本最小供应量为供应量为1 1代表每个人都只能完成一代表每个人都只能完成一项工作项工作需求量为需求量为1 1代表每项工作也只能有一代表每项工作也只能有一个人来完成个人来完成总人数（总人数（4 4人）和总任务数

49、（人）和总任务数（4 4项）项）相等相等第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题数学模型：数学模型：设设xij为指派人员为指派人员i去做工作去做工作j（i，j1,2,3,4)1,2,3,4) 1 11 21 31 42 12 22 32 43 13 23 33 44 14 24 34 41 11 21 31 42 12 2M in z 3 51 44 11 42 71 44 01 4 4 71 24 51 23 21 25 11 2 3 91 35 61 33 61 34 31 3 3 21 55 11 52 51 54 61 51 s .t. xxx

50、xxxxxxxxxxxxxxxxxxx（ 小 张 要 完 成 一 项 工 作 ） 2 32 43 13 23 33 44 14 24 34 41 12 13 14 11 22 23 24 21 32 33 34 31 42 43 44 4D1 1 1 1 1 1 1 xxxxxxxxxxxxxxxxxxxxxxxxxx（ 小 王 要 完 成 一 项 工 作 ）（ 小 李 要 完 成 一 项 工 作 ）（ 小 刘 要 完 成 一 项 工 作 ）（ 工 作 A 要 有 1 人 完 成 ）（ 工 作 B 要 有 1 人 完 成 ）（ 工 作 C 要 有 1 人 完 成 ）（ 工 作要 有 1 人0

51、( ,1, 2 , 3 , 4 ) ijxij完 成 ）（ 非 负 ）第第4章章 运输问题运输问题 和指派问题和指派问题4.5 4.5 指派问题指派问题电子表格模型电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模经常会遇到指派问题的经常会遇到指派问题的变形变形，之所以称它们为变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设之中的一是因为它们都不满足平衡指派问题所有假设之中的一个或者多个。一般考虑下面的一些特征：个或者多个。一般考虑下面的一些特征：（1 1）有些人并）有些人并不能不能进行某项工作（相应的进行

52、某项工作（相应的xij0 0）; ;（2 2）虽然每个人完成一项任务，但是任务比人多）虽然每个人完成一项任务，但是任务比人多( (人少事多人少事多););（3 3）虽然每一项任务只由一个人完成，但是人比任务多（）虽然每一项任务只由一个人完成，但是人比任务多（人人多事少多事少）；）；（4 4）某人可以同时被指派给多个任务（）某人可以同时被指派给多个任务（一人可做几件事一人可做几件事）；）；（5 5）某事可以由多人共同完成（）某事可以由多人共同完成（一事可由多人完成一事可由多人完成） ；（6 6）目标是与指派有关的）目标是与指派有关的总利润最大总利润最大而不是使总成本最小；而不是使总成本最小；（7

53、 7）实际需要完成任务数不超过总人数也不超过总任务数。）实际需要完成任务数不超过总人数也不超过总任务数。 第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模例例4.94.9 题目见例题目见例4.44.4，即某公司需要安排三，即某公司需要安排三个工厂来生产四种新产品，相关的数据在表个工厂来生产四种新产品，相关的数据在表4 47 7中已经给出。在例中已经给出。在例4.44.4中，允许产品生中，允许产品生产分解，但这将产生与产品生产分解相关的产分解，但这将产生与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成隐性成本（包括额外的设置

54、、配送和管理成本等）。因此，管理人员决定在本等）。因此，管理人员决定在禁止产品生禁止产品生产分解产分解发生的情况下对问题进行分析。发生的情况下对问题进行分析。新问题描述为：已知如表新问题描述为：已知如表4 47 7所示的数所示的数据，问如何把每一个工厂指派给至少一个新据，问如何把每一个工厂指派给至少一个新产品（每一种产品只能在一个工厂生产），产品（每一种产品只能在一个工厂生产），使总成本达到最小？使总成本达到最小？第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模解：解： 该问题可视为该问题可视为指派工厂生产产品问题指派工厂生产产品问

55、题，工，工厂可以看作指派问题中的人，产品则可以看作厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。由于有四种产品和需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工新产品，第三个工厂生产两种新产品。只有工厂厂1 1和工厂和工厂2 2有生产两种产品的能力。有生产两种产品的能力。这里涉及如何把这里涉及如何把运输问题转换为指派问题运输问题转换为指派问题，关，关键所在是键所在是数据转换数据转换。第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的

56、建模各种指派问题变形的建模数据转换：数据转换：（1 1）单位指派成本单位指派成本: : 原来的单位成本转换成原来的单位成本转换成整批整批成本（单位成本成本（单位成本需求量），即单位指派成本需求量），即单位指派成本为为每个工厂生产每种产品的成本每个工厂生产每种产品的成本。（2 2）供应量和需求量的转换问题供应量和需求量的转换问题：三个工厂生产：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂据生产能力，工厂3 3只能生产一种产品（供应量为只能生产一种产品（供应量为1 1），而工厂），而工厂1 1和工厂和工厂2 2可以生产可以生产2

57、2种产品（供应量种产品（供应量为为2 2），而产品的需求量为），而产品的需求量为1 1。还有。还有“总供应（总供应（2+2+1=52+2+1=5） 总需求（总需求（1+1+1+1=41+1+1+1=4）”, , 为人多事少为人多事少的指派问题的指派问题。第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模数学模型：数学模型：设设xij为指派工厂为指派工厂i生产产品生产产品j（i=1,2,3;=1,2,3;j=1,2,3,4)=1,2,3,4) 1 11 21 31 42 12 22 43 13 23 33 41 11 21 31 42

58、12 22 32 43 13 23 33 41M in z4 12 02 73 02 83 02 44 04 02 02 93 0 2 34 03 72 03 03 02 73 02 14 02 (1 )2 (2 )1 (3 )s .t. xxxxxxxxxxxxxxxxxxxxxxxx工 厂 工 厂工 厂12 13 11 22 23 21 32 33 31 42 43 42 31 (1 )1 (2 )1 (3 )1 (4 )= 00 (1, 2 , 3;1, 2 , 3 , 4 )ijxxxxxxxxxxxxxij产 品产 品产 品产 品第第4章章 运输问题运输问题 和指派问题和指派问题4.

59、6 4.6 各种指派问题变形的建模各种指派问题变形的建模电子表格模型电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模例例4.104.10 一家制药公司，为了提升企业的竞争一家制药公司，为了提升企业的竞争力，决定加大科研力度。在研究了市场的需要力，决定加大科研力度。在研究了市场的需要，分析了当前药物的不足并且拜会了大量对有，分析了当前药物的不足并且拜会了大量对有良好前景的医药领域进行研究的科学家之后，良好前景的医药领域进行研究的科学家之后，决定由五位科学家开发五个项目。为了保证这决定由五位科学家开发五个项目。为了保证这些科

60、学家都能够到他们感兴趣的项目中去，为些科学家都能够到他们感兴趣的项目中去，为此建立了一个此建立了一个投标系统投标系统。这五位科学家每个人。这五位科学家每个人都有都有10001000点的投标点。他们向每一个项目投标点的投标点。他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项，并且把较多的投标点投向自己最感兴趣的项目中。表目中。表4 41515显示了这显示了这5 5位科学家进行投标的位科学家进行投标的情况。情况。第第4章章 运输问题运输问题 和指派问题和指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模表表4 415 15 科学家项目投标表科学家项目投标表投投标标点点