运输问题和指派问题

《运输问题和指派问题》由会员分享，可在线阅读，更多相关《运输问题和指派问题（55页珍藏版）》请在金锄头文库上搜索。

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

2、种运输问题变形的建模3.4 3.4 运输问题应用举例运输问题应用举例3.5 3.5 指派问题指派问题3.6 3.6 各种指派问题变形的建模各种指派问题变形的建模 运输问题运输问题 和指派问题和指派问题本章主要内容框架图本章主要内容框架图 运输问题运输问题 和指派问题和指派问题3 3.1 .1 运输问题基本概念运输问题基本概念运运输输问问题题最最初初起起源源于于人人们们在在日日常常生生活活中中把把某某些些物物品品或或人人们们自自身身从从一一些些地地方方转转移移到到另另一一些些地地方方，要要求求所所采采用用的的运运输输路路线线或或运运输输方方案案是是最最经经济济或或成本最低成本最低的，这就成为了一

3、个运筹学问题。的，这就成为了一个运筹学问题。随随着着经经济济的的不不断断发发展展，现现代代物物流流业业蓬蓬勃勃发发展展，如如何何充充分分利利用用时时间间、信信息息、仓仓储储、配配送送和和联联运运体体系系创创造造更更多多的的价价值值，向向运运筹筹学学提提出出了了更更高高的的挑战。挑战。要要求求科科学学地地组组织织货货源源、运运输输和和配配送送使使得得运运输输问问题题变变得得日日益益复复杂杂，但但是是其其基基本本思思想想仍仍然然是是实实现现现有资源的最优化配置现有资源的最优化配置。 运输问题运输问题 和指派问题和指派问题3 3.1 .1 运输问题基本概念运输问题基本概念一一般般的的运运输输问问题题

4、就就是是解解决决如如何何把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量和和每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下，如如何确定一个使得总的运输费用最小的方案。何确定一个使得总的运输费用最小的方案。平衡运输问题平衡运输问题的条件：的条件：1.1.明明确确出出发发地地（产产地地）、目目的的地地（销销地地）、供供应应量量（产产量量）、需需求量（销量）和单位成本。求量（销量）和单位成本。2.2.需需求求假假设设：每每一一个个出出发发地地都都有有一一个个固固定定的的供供应

5、应量量，所所有有的的供供应应量量都都必必须须配配送送到到目目的的地地。与与之之类类似似，每每一一个个目目的的地地都都有有一一个个固固定定的的需需求求量量，整整个个需需求求量量都都必必须须由由出出发发地地满满足足。即即“总总供供应应总需求总需求”。3.3.成成本本假假设设：从从任任何何一一个个出出发发地地到到任任何何一一个个目目的的地地的的货货物物配配送送成成本本与与所所配配送送的的数数量量成成线线性性比比例例关关系系，因因此此成成本本就就等等于于配配送送的的单单位成本乘以所配送的数量（目标函数是线性的）。位成本乘以所配送的数量（目标函数是线性的）。 运输问题运输问题 和指派问题和指派问题3 3

6、.1 .1 运输问题基本概念运输问题基本概念例例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吨吨；从从各各工工厂厂到到各各销销售售点点的的单单位位产产品品运运价价如如表表4 41 1所所示示。问问该该公公司司应应如如何何调调运运这这些些产产品品，在在满满足足各各销销售售点点的

7、的需需要要量量的的前前提提下下，使使总总运运费费最少？最少？ 表表4 41 1 各工厂到各销售点的单位产品运价（元各工厂到各销售点的单位产品运价（元/ /吨）吨）B1B1B2B2B3B3B4B4产量（吨）产量（吨）A1A13 311113 310107 7A2A21 19 92 28 84 4A3A37 74 410105 59 9销量（吨）销量（吨）3 36 65 56 6 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（1 1）产销平衡产销平衡运输问题的数学模型运输问题的数学模型 具有具有m个产地个产地A Ai i（i1

8、,2,1,2, ,m）和和n个销地个销地 B Bj j（j1,2,1,2, ,n）的运输问题的数学模型为的运输问题的数学模型为 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型对于例对于例4.14.1，其数学模型如下：，其数学模型如下： 首首先先，三三个个产产地地A1A1、A2A2、A3A3的的总总产产量量为为7 74 49 92020；四四个个销销地地B1B1、B2B2、B3B3、B4B4的的总总销销量量为为3 36 65 56 62020。由由于于总总产量等于总销量，故该问题是一个产销平衡的运输问题。产量等于总销量，故该问

9、题是一个产销平衡的运输问题。(1)(1)决策变量决策变量 设设xij为从产地为从产地AiAi运往销地运往销地BjBj的运输量的运输量(i(i1,2,3;j=1,2,3,4)1,2,3;j=1,2,3,4) （2 2）目标函数）目标函数 本问题的目标是使得总运输费最小。本问题的目标是使得总运输费最小。 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（3 3）约束条件）约束条件满满足足产产地地产产量量（3 3个个产产地地的的产产品品都都要要全全部部配送出去）配送出去）满满足足销销地地销销量量（4 4个个销销地地的的产产品品都都要

10、要全全部部得到满足）得到满足）非负非负 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u运运输输问问题题是是一一种种特特殊殊的的线线性性规规划划问问题题，一一般般采采用用“表表上上作作业业法法”求求解解运运输输问问题题，但但ExcelExcel的的“规规划划求求解解”还还是是采采用用“单纯形法单纯形法”来求解。来求解。u例例4.14.1的电子表格模型的电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u需需要要注注意意的的是是：运运输输问问题题有

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

12、3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（2 2）产产大大于于销销（供供过过于于求求）运运输输问问题题的数学模型的数学模型（以满足小的销量为准以满足小的销量为准） 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（3 3）销销大大于于产产（供供不不应应求求）运运输输问问题题的数学模型的数学模型（以满足小的产量为准以满足小的产量为准） 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.2 4.2 某某厂厂按按合合同同规规定

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

14、台柴油机的成本各季度的生产能力及生产每台柴油机的成本季度季度生产能力（台）生产能力（台）单位成本（万元）单位成本（万元）1 1252510.810.82 2353511.111.13 3303011.011.04 4101011.311.3 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解解：这这是是一一个个生生产产与与储储存存（库库存存）问问题题，除除了了采采用用第第3 3章的方法外，还可以转化为章的方法外，还可以转化为运输问题运输问题来做。来做。 由由于于每每个个季季度度生生产产出出来来的的柴柴油油机机不不一一定定当当季

15、季交交货货，所所以以设设xij为为第第i季季度度生生产产的的第第j季季度度交交货货的的柴柴油油机机数数。则则第第i季季度度生生产产的的第第j季季度度交交货货的的每每台台柴柴油油机机的的实实际际成成本本cij为：为： cij= =第第i季度每台的生产成本季度每台的生产成本+0.15(+0.15(j-i) )（储存、维护等费用）（储存、维护等费用） 把把第第i季季度度生生产产的的柴柴油油机机数数看看作作第第i个个生生产产厂厂商商的的产产量量；把把第第j季季度度交交货货的的柴柴油油机机数数看看作作第第j个个销销售售点点的的销销量量；生生产产成成本本加加储储存存、维维护护等等费费用用看看作作运运费费。

16、将将生生产产与储存问题转化为运输问题，相关数据见表与储存问题转化为运输问题，相关数据见表4 45 5。 运输问题运输问题 和指派问题和指派问题3 3.2 .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需求量需求量101015152

17、5252020由表由表4 45 5可知，总产量（生产能力）为可知，总产量（生产能力）为25+35+30+10=10025+35+30+10=100，总销量（需求量）为，总销量（需求量）为10+15+25+20=7010+15+25+20=70，因此是，因此是产大于销产大于销的运输问题。的运输问题。 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型该生产与该生产与储存问题储存问题（转化为（转化为产大于销产大于销的运输问的运输问题）的数题）的数学模型为学模型为 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模

18、型和电子表格模型运输问题数学模型和电子表格模型例例4.24.2的电子表格模型的电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3 某公司从两个产地某公司从两个产地A1A1、A2A2将物品运往将物品运往三个销地三个销地 B1 B1、B2B2、B3B3，各产地的产量、各销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运地的销量和各产地运往各销地每件物品的运费如表费如表4 46 6所示。问应如何调运，可使得总所示。问应如何调运，可使得总运输费最小？运输费最小？表表4 46 6 例例4.34.3的

19、运输费用表的运输费用表 B1B1B2B2B3B3产量产量A1A11313151512127878A2A21111292922224545销量销量535336366565（销大于产）（销大于产） 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解：解：由表由表4 46 6知，总产量为知，总产量为78+45=12378+45=123，总销量为，总销量为53+36+65=15453+36+65=154，销大于产销大于产( (供不应求供不应求) )。数学模型如下：。数学模型如下： 设设xij为产地为产地AiAi运往销地运往销地BjBj

20、的物品数量的物品数量 运输问题运输问题 和指派问题和指派问题3 3.2 .2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3的电子表格模型的电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形的建模各种运输问题变形的建模现实生活中符合产销平衡运输问题每一个条件的情况很少。一现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。输问题条件的运输问题却经常出现。下面是要讨论的一些特征：下面是要讨论

21、的一些特征：（1 1）总供应大于总需求总供应大于总需求。每一个供应量（产量）代表了从其出。每一个供应量（产量）代表了从其出发地中配送出去的最大数量（而不是一个固定的数值发地中配送出去的最大数量（而不是一个固定的数值, ,）。）。（2 2）总供应小于总需求总供应小于总需求。每一个需求量（销量）代表了在其目。每一个需求量（销量）代表了在其目的地中所接收到的最大数量（而不是一个固定的数值的地中所接收到的最大数量（而不是一个固定的数值, ,）。）。（3 3）一个目的地）一个目的地同时存在着最小需求和最大需求同时存在着最小需求和最大需求，于是所有在，于是所有在这两个数值之间的数量都是可以接收的（这两个数

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

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

24、，可使总成本最小。表表4 47 7 产品生产的有关数据产品生产的有关数据单位成本（元）单位成本（元）生产能力生产能力产品产品1 1产品产品2 2产品产品3 3产品产品4 4工厂工厂1 141412727282824247575工厂工厂2 24040292923237575工厂工厂3 337373030272721214545需求量需求量2020303030304040 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形的建模各种运输问题变形的建模解：解：指定工厂生产产品指定工厂生产产品可以看作运输问题来求可以看作运输问题来求解。本题中，工厂解。本题中，工厂2 2不能不能生

25、产产品生产产品3 3，这样可以，这样可以增增加约束条件加约束条件x230 0 ；并；并且，总供应且，总供应（75+75+45=19575+75+45=195） 总需总需求（求（20+30+30+40=12020+30+30+40=120）。）。其数学模型如下：其数学模型如下： 设设xij为工厂为工厂i生产产品生产产品j的数量的数量 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形的建模各种运输问题变形的建模例例4.44.4的电子表格模型的电子表格模型产品产品4 4分在分在2 2个工厂生产个工厂生产 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形

26、的建模各种运输问题变形的建模例例4.54.5 某公司在某公司在3 3个工厂中专门生产一种产品。在未来的个工厂中专门生产一种产品。在未来的4 4个月中，有四个个月中，有四个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客1 1是公司最是公司最好的顾客，所以他的全部订购量都应该满足；顾客好的顾客，所以他的全部订购量都应该满足；顾客2 2和顾客和顾客3 3也是公司很重也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/31/3；对；对于顾客于顾客4 4，销售

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

28、2 2373718183232484850005000工厂工厂3 3292959595151353570007000最小采购量最小采购量7000700030003000200020000 0最大采购量最大采购量70007000900090006000600080008000 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形的建模各种运输问题变形的建模解：解：该问题要求满足不该问题要求满足不同顾客的需求（采购量）同顾客的需求（采购量），解决办法：，解决办法：实际供给量实际供给量 最小采购量最小采购量实际供给量实际供给量 最大采购量最大采购量 目标是利润最大，而目标是利润最

29、大，而不是成本最小。不是成本最小。其数学模型如下：其数学模型如下： 设设xij为工厂为工厂i供应给顾供应给顾客客j的产品数量的产品数量 运输问题运输问题 和指派问题和指派问题3 3.3 .3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5的电子表格模型的电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.4 .4 运输问题应用举例运输问题应用举例例例4.64.6 某厂生产设备是以销定产的。已知某厂生产设备是以销定产的。已知1 16 6月份各月的生产能力、合月份各月的生产能力、合同销量和单台设备平均生产费用，如表同销量和单台设备平均生产费用，如表4 49 9所示。所示。 已

30、知上年末库存已知上年末库存103103台。如果当月生产出来的设备当月不交货，则需台。如果当月生产出来的设备当月不交货，则需要运到分厂库房，每台增加运输成本要运到分厂库房，每台增加运输成本0.10.1万元，每台设备每月的平均仓万元，每台设备每月的平均仓储费、维护费为储费、维护费为0.20.2万元。万元。7 78 8月份为销售淡季，全厂停产月份为销售淡季，全厂停产1 1个月，因此个月，因此在在6 6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存8080台。加班生产设备每台增加成台。加班生产设备每台增加成本本1 1万元。问应如何安排万元。问应如何安排1 16 6月份的生产，使总的生产（

31、包括运输、仓月份的生产，使总的生产（包括运输、仓储、维护）费用最少？储、维护）费用最少？月份月份正常生产能力正常生产能力（台）（台）加班生产能力加班生产能力（台）（台）合同销量合同销量（台）（台）单台费用单台费用（万元）（万元）1 1月月6060101010410415152 2月月50501010757514143 3月月9090202011511513.513.54 4月月100100404016016013135 5月月100100404010310313136 6月月80804040707013.513.5 运输问题运输问题 和指派问题和指派问题3 3.4 .4 运输问题应用举例运输问

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

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

34、题 和指派问题和指派问题表412 大锯片和小锯片的相关数据销售销售区域区域销售销售固定固定费用费用（万（万元）元）规格直径规格直径900mm900mm1800mm1800mm规格直径规格直径350mm350mm800mm800mm最低最低需求需求（片）（片）最高最高需求需求（片）（片）每片每片平均平均运费运费（元）（元）每片每片零售零售与出与出厂价厂价差差（元）（元）每片每片利润利润（元）（元）最低最低需求需求（片）（片）最高最高需求需求（片）（片）每片每片平均平均运费运费（元）（元）每片每片零售零售与出与出厂价厂价差差（元）（元）每片每片利润利润（元）（元）福建福建2121350035008

35、00080008080350350270270750075002200022000222285856363广东广东101020002000600060006060300300240240450045002000020000151575756060广西广西9 925002500600060007575370370295295400040001500015000252585856060四川四川8 825002500600060008080380380300300500050002000020000252589896464山东山东7 720002000800080007878320320242242

36、400040001800018000212180805959其他其他省区省区909020002000未作未作统计统计909035035026026040004000未作未作统计统计282885855757 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题u在现实生活中，经常会遇到指派人员做某项在现实生活中，经常会遇到指派人员做某项工作（任务）的情况。工作（任务）的情况。指派问题指派问题的许多应用是的许多应用是用来帮助管理人员解决如何为一项即将开展的用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题。其他的一些应用如为工工作指派人员的问题。其他的一些应用如为工作指

37、派机器、设备或工厂等。作指派机器、设备或工厂等。u指派问题也称指派问题也称分配问题分配问题，主要研究人和工作，主要研究人和工作（任务）间如何匹配，以使所有工作完成的效（任务）间如何匹配，以使所有工作完成的效率实现最优化。形式上，指派问题给定了一系率实现最优化。形式上，指派问题给定了一系列所要完成的工作以及一系列完成工作的人员，列所要完成的工作以及一系列完成工作的人员，所需要解决的问题就是要确定出指派哪个人去所需要解决的问题就是要确定出指派哪个人去完成哪项工作。完成哪项工作。 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题u指派问题的假设：指派问题的假设：（1 1）人的

38、数量和工作的数量）人的数量和工作的数量相等相等；（2 2）每个人）每个人只能完成一项只能完成一项工作；工作；（3 3）每项工作）每项工作只能由一个人只能由一个人来完成；来完成；（4 4）每个人和每项工作的组合都会有）每个人和每项工作的组合都会有一个相关的成本（一个相关的成本（单位成本单位成本）；）；（5 5）目标是要确定如何指派才能使）目标是要确定如何指派才能使总总成本最小成本最小。 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题u设决策变量设决策变量xij为第为第i个人做第个人做第j项工作，而已项工作，而已知目标函数系数知目标函数系数cij为第为第i个人完成第个人完

39、成第j项工作所项工作所需要的单位成本。需要的单位成本。u平衡指派问题的数学模型为平衡指派问题的数学模型为 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题u需要说明的是：需要说明的是：指派问题指派问题实际上是一种实际上是一种特殊特殊的运输问题的运输问题。其中出发地是人，目的地是工作。其中出发地是人，目的地是工作。只不过，每一个出发地的只不过，每一个出发地的供应量都为供应量都为1 1（因为（因为每个人都要完成一项工作），每一个目的地的每个人都要完成一项工作），每一个目的地的需求量都为需求量都为1 1（因为每项工作都要完成）。由（因为每项工作都要完成）。由于运输问题有于运输

40、问题有“整数解性质整数解性质”，因此，没有必，因此，没有必要加上所有决策变量都是要加上所有决策变量都是0-10-1变量变量的约束。的约束。u指派问题是一种特殊的线性规划问题，有一指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：种快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题例例4.84.8 某公司的营销经理将要主持召开一年一度的某公司的营销经理将要主持

41、召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项工李、小刘等四个人，每个人负责完成下面的一项工作：作：A A、B B、C C和和D D。 由于每个人完成每项任务的时间和工资不同（如由于每个人完成每项任务的时间和工资不同（如表表4 41414所示）。问如何指派，可使总成本最小。所示）。问如何指派，可使总成本最小。人员人员每一项工作所需要的时间（小时）每一项工作所需要的时间（小时）每小时工资每小时工资（元）（元）

42、工作工作A A工作工作B B工作工作C C工作工作D D小张小张35354141272740401414小王小王47474545323251511212小李小李39395656363643431313小刘小刘32325151252546461515 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题解解：该问题是一个：该问题是一个典型的指派问题典型的指派问题。单位成本单位成本为每个人做每项工作的总为每个人做每项工作的总工资工资目标目标是要确定哪个人做哪一项工作，是要确定哪个人做哪一项工作，使总成本最小使总成本最小供应量为供应量为1 1代表每个人都只能完成一代表每个人都只能

43、完成一项工作项工作需求量为需求量为1 1代表每项工作也只能有一代表每项工作也只能有一个人来完成个人来完成总人数（总人数（4 4人）和总任务数（人）和总任务数（4 4项）项）相等相等 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题数学模型：数学模型：设设xij为指派人员为指派人员i去做工作去做工作j（i，j1,2,3,4)1,2,3,4) 运输问题运输问题 和指派问题和指派问题3 3.5 .5 指派问题指派问题电子表格模型电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模经常会遇到指派问题的经常会遇到指派问

44、题的变形变形，之所以称它们为变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设之中的一是因为它们都不满足平衡指派问题所有假设之中的一个或者多个。一般考虑下面的一些特征：个或者多个。一般考虑下面的一些特征：（1 1）有些人并）有些人并不能不能进行某项工作（相应的进行某项工作（相应的xij0 0）; ;（2 2）虽然每个人完成一项任务，但是任务比人多）虽然每个人完成一项任务，但是任务比人多( (人少事多人少事多););（3 3）虽然每一项任务只由一个人完成，但是人比任务多（）虽然每一项任务只由一个人完成，但是人比任务多（人人多事少多事少）；）；（4 4）某人可以同时被指派给多个任务（

45、）某人可以同时被指派给多个任务（一人可做几件事一人可做几件事）；）；（5 5）某事可以由多人共同完成（）某事可以由多人共同完成（一事可由多人完成一事可由多人完成） ；（6 6）目标是与指派有关的）目标是与指派有关的总利润最大总利润最大而不是使总成本最小；而不是使总成本最小；（7 7）实际需要完成任务数不超过总人数也不超过总任务数。）实际需要完成任务数不超过总人数也不超过总任务数。 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模例例4.94.9 题目见例题目见例4.44.4，即某公司需要安排三个，即某公司需要安排三个工厂来生产四种新产品，相关

46、的数据在表工厂来生产四种新产品，相关的数据在表4 47 7中已经给出。在例中已经给出。在例4.44.4中，允许产品生产分中，允许产品生产分解，但这将产生与产品生产分解相关的隐性解，但这将产生与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成本等）成本（包括额外的设置、配送和管理成本等）。因此，管理人员决定在。因此，管理人员决定在禁止产品生产分解禁止产品生产分解发生的情况下对问题进行分析。发生的情况下对问题进行分析。新问题描述为：已知如表新问题描述为：已知如表4 47 7所示的数所示的数据，问如何把每一个工厂指派给至少一个新据，问如何把每一个工厂指派给至少一个新产品（每一种产品只能在一个

47、工厂生产），产品（每一种产品只能在一个工厂生产），使总成本达到最小？使总成本达到最小？ 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模解：解： 该问题可视为该问题可视为指派工厂生产产品问题指派工厂生产产品问题，工，工厂可以看作指派问题中的人，产品则可以看作厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。由于有四种产品和需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工新产品，第三个工厂生产两种新产品。只有工厂厂1 1

48、和工厂和工厂2 2有生产两种产品的能力。有生产两种产品的能力。这里涉及如何把这里涉及如何把运输问题转换为指派问题运输问题转换为指派问题，关，关键所在是键所在是数据转换数据转换。 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模数据转换：数据转换：（1 1）单位指派成本单位指派成本: : 原来的单位成本转换成原来的单位成本转换成整批整批成本（单位成本成本（单位成本需求量），即单位指派成本需求量），即单位指派成本为为每个工厂生产每种产品的成本每个工厂生产每种产品的成本。（2 2）供应量和需求量的转换问题供应量和需求量的转换问题：三个工厂生产：三个

49、工厂生产四种产品，但一种产品只能在一个工厂生产，根四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂据生产能力，工厂3 3只能生产一种产品（供应量为只能生产一种产品（供应量为1 1），而工厂），而工厂1 1和工厂和工厂2 2可以生产可以生产2 2种产品（供应量种产品（供应量为为2 2），而产品的需求量为），而产品的需求量为1 1。还有。还有“总供应总供应（2+2+1=52+2+1=5） 总需求（总需求（1+1+1+1=41+1+1+1=4）”, ”, 为人多事为人多事少的指派问题少的指派问题。 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变

50、形的建模数学模型：数学模型：设设xij为指派工厂为指派工厂i生产产品生产产品j（i=1,2,3;=1,2,3;j=1,2,3,4)=1,2,3,4) 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模电子表格模型电子表格模型 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模例例4.104.10 一家制药公司，为了提升企业的竞争一家制药公司，为了提升企业的竞争力，决定加大科研力度。在研究了市场的需要，力，决定加大科研力度。在研究了市场的需要，分析了当前药物的不足并且拜会了大量对有良分析了当前药物

51、的不足并且拜会了大量对有良好前景的医药领域进行研究的科学家之后，决好前景的医药领域进行研究的科学家之后，决定由五位科学家开发五个项目。为了保证这些定由五位科学家开发五个项目。为了保证这些科学家都能够到他们感兴趣的项目中去，为此科学家都能够到他们感兴趣的项目中去，为此建立了一个建立了一个投标系统投标系统。这五位科学家每个人都。这五位科学家每个人都有有10001000点的投标点。他们向每一个项目投标，点的投标点。他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项目并且把较多的投标点投向自己最感兴趣的项目中。表中。表4 41515显示了这显示了这5 5位科学家进行投标的情位科学家进行投标的

52、情况。况。 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模表表4 415 15 科学家项目投标表科学家项目投标表投投标标点点a a项项目目b b项项目目c c项项目目d d项项目目e e项项目目李李尔尔博博士士10100 040400 020200 020200 010100 0朱朱诺诺博博士士0 020200 080800 00 00 0刘刘哲哲博博士士10100 010100 010100 010100 060600 0王王凯凯博博士士26267 715153 3999945451 13030罗罗林林博博士士10100 03333 33

53、33 343480800 0 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模分析：决定要对一些可能发生的情况进行评估。分析：决定要对一些可能发生的情况进行评估。（1 1）根据所给出的投标情况，需要为每一个项目）根据所给出的投标情况，需要为每一个项目指派一位资深的科学家并且使得科学家的总满意指派一位资深的科学家并且使得科学家的总满意度最高。那么应当怎样进行指派？度最高。那么应当怎样进行指派？ （人数与项目数相等）（人数与项目数相等）（2 2）罗林博士接到了北大医学院的邀请去完成一）罗林博士接到了北大医学院的邀请去完成一个教学任务，而公司却非常

54、想把她留下来。但是个教学任务，而公司却非常想把她留下来。但是北大的声望会使她离开公司。如果这种情况真的北大的声望会使她离开公司。如果这种情况真的发生的话，公司就只有放弃那个最缺乏热情的项发生的话，公司就只有放弃那个最缺乏热情的项目。公司应当放弃那一个项目？目。公司应当放弃那一个项目？（人少项目多）人少项目多） 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模（3 3）当然公司并不愿意放弃任何一个项目。公司决）当然公司并不愿意放弃任何一个项目。公司决定让朱诺博士或者王凯博士同时领导两个项目。在只定让朱诺博士或者王凯博士同时领导两个项目。在只有有

55、4 4位科学家的情况下，让哪一位科学家领导哪一个位科学家的情况下，让哪一位科学家领导哪一个项目才能使得对项目的热情最大？项目才能使得对项目的热情最大？ （有人可以（有人可以同时领导两个项目）同时领导两个项目）（4 4）还是来分析拥有）还是来分析拥有5 5位科学家的情况，但由于各方位科学家的情况，但由于各方面的原因，有三位科学家不能领导几个特定的项目，面的原因，有三位科学家不能领导几个特定的项目，具体如表具体如表4 41616所示。由于不能领导，需重新调整这所示。由于不能领导，需重新调整这三位科学家的投标点，使其总投标点还是三位科学家的投标点，使其总投标点还是10001000点，具点，具体的调整

56、方法是将不能领导的投标点全部投到他自己体的调整方法是将不能领导的投标点全部投到他自己最感兴趣的项目上。在这种情况下，让哪个科学家领最感兴趣的项目上。在这种情况下，让哪个科学家领导哪个项目才能使得对项目的总热情最大？导哪个项目才能使得对项目的总热情最大？（有人不能领导几个特定的项目）（有人不能领导几个特定的项目） 运输问题运输问题 和指派问题和指派问题表416 有三位科学家不能领导几个特定项目的相关数据投标点投标点a a项目项目b b项目项目c c项目项目d d项目项目e e项目项目李尔博士李尔博士100100700700200200不能不能领导领导不能不能领导领导王凯博士王凯博士871871不

57、能不能领导领导9999不能不能领导领导3030罗林博士罗林博士不能不能领导领导333333333434900900 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模（5 5）公司觉得）公司觉得d d项目和项目和e e项目太复杂了，各让一位科学家分别项目太复杂了，各让一位科学家分别进行领导是不大合适的。因此这两个项目都要指派两位科学家进行领导是不大合适的。因此这两个项目都要指派两位科学家进行领导（需求量由进行领导（需求量由1 1改为改为2 2）。现在需要雇佣更多的科学家来）。现在需要雇佣更多的科学家来领导所有的项目：陈加博士和郑斯博士。由于身体

58、的原因，这领导所有的项目：陈加博士和郑斯博士。由于身体的原因，这两位新加入的科学家都不能领导两位新加入的科学家都不能领导c c项目。表项目。表4 41717显示了显示了2 2位科位科学家的投标情况。学家的投标情况。 （项目可由多人领导）项目可由多人领导）（6 6）还是来分析五位科学家五个项目的情况，它们的投标点）还是来分析五位科学家五个项目的情况，它们的投标点如表如表4 41515所示。假设受到资金的限制，希望从五个项目中选所示。假设受到资金的限制，希望从五个项目中选取取三个三个，让三位最有热情的科学家来领导，此时应该选取哪三，让三位最有热情的科学家来领导，此时应该选取哪三个项目和哪三位科学家

59、？个项目和哪三位科学家？（从中选几个项目）（从中选几个项目） 运输问题运输问题 和指派问题和指派问题表417 两位新加入科学家的相关数据投标点投标点a a项目项目b b项目项目c c项目项目d d项目项目e e项目项目陈加博士陈加博士250250250250不能不能领导领导250250250250郑斯博郑斯博士士1111111 1不能不能领导领导333333555555 运输问题运输问题 和指派问题和指派问题3 3.6 .6 各种指派问题变形的建模各种指派问题变形的建模以上以上6 6种可能发生的情况，利用种可能发生的情况，利用ExcelExcel求得的最佳指派方案见表求得的最佳指派方案见表4

60、41818。其中括号内的。其中括号内的“是是”和和“否否”代表科学家是否领导他代表科学家是否领导他最感兴趣（最有热情）的项目。最感兴趣（最有热情）的项目。 表表4 418 18 各种最佳指派方案各种最佳指派方案题目题目a a项目项目b b项目项目c c项目项目d d项目项目e e项目项目总投标点总投标点（1 1）刘哲（刘哲（否否）李尔（是）李尔（是）朱诺（是）朱诺（是）王凯（是）王凯（是）罗林（是）罗林（是）25512551（2 2）放弃放弃李尔（是）李尔（是）朱诺（是）朱诺（是）王凯（是）王凯（是）刘哲（是）刘哲（是）22512251（3 3）王凯（王凯（否否）李尔（是）李尔（是）朱诺（是）

61、朱诺（是）王凯（是）王凯（是）刘哲（是）刘哲（是）25182518（4 4）王凯（是）王凯（是）李尔（是）李尔（是）朱诺（是）朱诺（是）刘哲（刘哲（否否）罗林（是）罗林（是）33713371（5 5）王凯（是）王凯（是）李尔（是）李尔（是）朱诺（是）朱诺（是）陈加（是）陈加（是）郑斯（郑斯（否否）刘哲（是）刘哲（是）罗林（是）罗林（是）44544454（6 6）放弃放弃放弃放弃朱诺（是）朱诺（是）王凯（是）王凯（是）罗林（是）罗林（是）20512051 运输问题运输问题 和指派问题和指派问题上机上机实验四实验四 运输问题和指派问题运输问题和指派问题（）实验目的：熟悉运用（）实验目的：熟悉运用E

62、xcel软件求解运输问题软件求解运输问题和指派问题，掌握其求解方法。和指派问题，掌握其求解方法。（二）内容和要求：求解（二）内容和要求：求解习题习题4.1、4.2、4.6、4.11、案例案例4。（。（选作题：习题选作题：习题4.7、4.15 ）（三）操作步骤：（三）操作步骤：（1）建立电子表格模型；）建立电子表格模型；（2）使用）使用Excel规划求解功能求解运输问题和规划求解功能求解运输问题和指派问题；指派问题；（3）结果分析；）结果分析；（4）在）在Excel或或Word文档中写实验报告，包文档中写实验报告，包括数学模型（括数学模型（手写手写）、电子表格模型和结果分析等。）、电子表格模型和结果分析等。