《运输问题和指派问题.pptx》由会员分享，可在线阅读，更多相关《运输问题和指派问题.pptx（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章内容要点本章内容要点运输问题运输问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用指派问题指派问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用第1页/共54页本章节内容本章节内容4.1 4.1 运输问题基本概念运输问题基本概念4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型4.3 4.3 各种变形的运输问题建模各种变形的运输问题建模4.4 4.4 运输问题应用举例运输问题应用举例4.5 4.5 指派问题指派问题4.6 4.6 各种变形的指派问题建模各种变形的指派问题建模第2页/共54页本章主要内容框架图本章主要内容框
2、架图第3页/共54页4.1 4.1 运输问题基本概念运输问题基本概念u运运输输问问题题最最初初起起源源于于人人们们在在日日常常生生活活中中把把某某些些物物品品或或人人们们自自身身从从一一些些地地方方转转移移到到另另一一些些地地方方，要要求求所所采采用用的的运运输输路路线线或或运运输输方方案案是是最最经经济济或或成成本本最最低低的的，这这就就成成为为了了一个运筹学问题。一个运筹学问题。u随随着着经经济济的的不不断断发发展展，现现代代物物流流业业蓬蓬勃勃发发展展，如如何何充充分分利利用用时时间间、信信息息、仓仓储储、配配送送和和联联运运体体系系创创造造更更多多的的价价值值，向向运运筹筹学学提出了更
3、高的挑战。提出了更高的挑战。u要要求求科科学学地地组组织织货货源源、运运输输和和配配送送使使得得运运输输问问题题变变得得日日益益复复杂杂，但但是是其其基基本本思思想想仍仍然是然是实现现有资源的最优化配置实现现有资源的最优化配置。第4页/共54页4.1 4.1 运输问题基本概念运输问题基本概念u一一般般的的运运输输问问题题就就是是解解决决如如何何把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地，在在每每个个产产地地的的供供应应量量和和每每个个销销地地的的需需求求量量已已知知，并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下，如何确定一个使得总的运输费用最
4、小的方案。下，如何确定一个使得总的运输费用最小的方案。u平衡运输问题平衡运输问题的条件：的条件：1.1.明明确确出出发发地地（产产地地）、目目的的地地（销销地地）、供供应应量量（产产量）、需求量（销量）和单位成本。量）、需求量（销量）和单位成本。2.2.需需求求假假设设：每每一一个个出出发发地地都都有有一一个个固固定定的的供供应应量量，所所有有的的供供应应量量都都必必须须配配送送到到目目的的地地。与与之之类类似似，每每一一个个目目的的地地都都有有一一个个固固定定的的需需求求量量，整整个个需需求求量量都都必必须须由由出出发发地地满满足足。即即“总供应总需求总供应总需求”。3.3.成成本本假假设设
5、：从从任任何何一一个个出出发发地地到到任任何何一一个个目目的的地地的的货货物物配配送送成成本本与与所所配配送送的的数数量量成成线线性性比比例例关关系系，因因此此成成本本就就等等于配送的单位成本乘以所配送的数量（目标函数是线性的）。于配送的单位成本乘以所配送的数量（目标函数是线性的）。第5页/共54页4.1 4.1 运输问题基本概念运输问题基本概念u例例4.1 4.1 某某公公司司有有三三个个加加工工厂厂A1A1、A2A2、A3A3生生产产某某产产品品，每每日日的的产产量量分分别别为为：7 7吨吨、4 4吨吨、9 9吨吨；该该公公司司把把这这些些产产品品分分别别运运往往四四个个销销售售点点B1B
6、1、B2B2、B3B3、B4B4，各各销销售售点点每每日日销销量量分分别别为为：3 3吨吨、6 6吨吨、5 5吨吨、6 6吨吨；从从各各工工厂厂到到各各销销售售点点的的单单位位产产品品运运价价如如表表4-14-1所所示示。问问该该公公司司应应如如何何调调运运这这些些产产品品，在在满满足足各各销销售售点点的的需需要要量量的的前前提提下下，使总运费最少？使总运费最少？表表4-1 4-1 各工厂到各销售点的单位产品运价（元各工厂到各销售点的单位产品运价（元/吨）吨）B1B1B2B2B3B3B4B4产量（吨）产量（吨）A1A13 311113 310107 7A2A21 19 92 28 84 4A3
7、A37 74 410105 59 9销量（吨）销量（吨）3 36 65 56 6第6页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型（1 1）产销平衡产销平衡运输问题的数学模型运输问题的数学模型 具有具有m个产地个产地A Ai i（i1,2,1,2,m）和和n个销地个销地 B Bj j（j1,2,1,2,n）的运输问题的数学模型为的运输问题的数学模型为第7页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型对于例，其数学模型如下：对于例，其数学模型如下：首首先先，三三个个产产地地A1A1、A2A2、A3A3的的总总产产
8、量量为为7 74 49 92020；四四个个销销地地B1B1、B2B2、B3B3、B4B4的的总总销销量量为为3 36 65 56 62020。由由于于总总产产量量等等于于总总销销量量，故故该该问问题题是是一一个个产产销销平平衡衡的的运运输输问题。问题。(1)(1)决策变量决策变量 设设 xij为为 从从 产产 地地 AiAi运运 往往 销销 地地 BjBj的的 运运 输输 量量(i(i1,2,3;j=1,2,3,4)1,2,3;j=1,2,3,4)（2 2）目标函数）目标函数 本问题的目标是使得总运输费最小本问题的目标是使得总运输费最小第8页/共54页4.2 4.2 运输问题数学模型和电子表
9、格模运输问题数学模型和电子表格模型型（3 3）约束条件）约束条件满满足足产产地地产产量量（3 3个个产产地地的的产品都要全部配送出去）产品都要全部配送出去）满满足足销销地地销销量量（4 4个个销销地地的的产品都要全部得到满足）产品都要全部得到满足）非负非负第9页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型u运运输输问问题题是是一一种种特特殊殊的的线线性性规规划划问问题题，一一般般采采用用“表表上上作作业业法法”求求解解运运输输问问题题，但但ExcelExcel的的“规规划划求求解解”工工具具还还是采用是采用“单纯形法单纯形法”来求解。来求解。u例的电子
10、表格模型例的电子表格模型第10页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型u需需要要注注意意的的是是：运运输输问问题题有有这这样样一一个个性性质质（整整数数解解性性质质），只只要要它它的的供供应应量量和和需需求求量量都都是是整整数数，任任何何有有可可行行解解的的运运输输问问题题必必然然有有所所有有决决策策变变量量都都是是整整数数的的最最优解优解。因此，没有必要加上所有变量都是整数的约束条件。因此，没有必要加上所有变量都是整数的约束条件。u由由于于运运输输量量经经常常以以卡卡车车、集集装装箱箱等等为为单单位位，如如果果卡卡车车不不能能装装满满的的话话，
11、就就很很不不经经济了。整数解性质就避免了运输量（运输方案）为小数的麻烦。济了。整数解性质就避免了运输量（运输方案）为小数的麻烦。第11页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型（2 2）产大于销（供过于求）产大于销（供过于求）运输问题的数学模型运输问题的数学模型（以满足小的销量为准以满足小的销量为准）第12页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型（3 3）销大于产（供不应求）销大于产（供不应求）运输问题的数学模型运输问题的数学模型（以满足小的产量为准以满足小的产量为准）第13页/共54页4.2 4.2
12、 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型例例4.2 4.2 某某厂厂按按合合同同规规定定须须于于当当年年每每个个季季度度末末分分别别提提供供1010，1515，2525，2020台台同同一一规规格格的的柴柴油油机机。已已知知该该厂厂各各季季度度的的生生产产能能力力及及生生产产每每台台柴柴油油机机的的成成本本如如表表4-44-4所所示示。如如果果生生产产出出来来的的柴柴油油机机当当季季不不交交货货的的，每每台台每每积积压压一一个个季季度度需需储储存存、维维护护等等费费用用15001500元元。要要求求在在完完成成合合同同的的情情况况下下，做做出出使使该该厂厂全年生产（包括储
13、存、维护）费用最小的决策。全年生产（包括储存、维护）费用最小的决策。表表4-4 4-4 各季度的生产能力及生产每台柴油机的成本各季度的生产能力及生产每台柴油机的成本季度季度生产能力（台）生产能力（台）单位成本（万元）单位成本（万元）1 1252510.810.82 2353511.111.13 3303011.011.04 4101011.311.3第14页/共54页4.2 4.2 运输问题数学模型和电子表格模运输问题数学模型和电子表格模型型解解：这这是是一一个个生生产产与与储储存存（库库存存）问问题题，除除了了采采用用第第3 3章的方法外，还可以转化为章的方法外，还可以转化为运输问题运输问题
14、来做。来做。由由于于每每个个季季度度生生产产出出来来的的柴柴油油机机不不一一定定当当季季交交货货，所所以以设设xij为为第第i季季度度生生产产的的第第j季季度度交交货货的的柴柴油油机机数数。则则第第i季季度度生生产产的的第第j季季度度交交货货的的每每台台柴柴油油机机的实际成本的实际成本cij为：为：cij=第第i季季度度每每台台的的生生产产成成本本+0.15(+0.15(j-i)（储储存存、维维护护等等费费用）用）把把第第i季季度度生生产产的的柴柴油油机机数数看看作作第第i个个生生产产厂厂商商的的产产量量；把把第第j季季度度交交货货的的柴柴油油机机数数看看作作第第j个个销销售售点点的的销销量量
15、；生生产产成成本本加加储储存存、维维护护等等费费用用看看作作运运费费。将将生生产产与与储储存存问问题题转转化化为为运运输输问问题题，相相关关数数据据见见表表4-54-5。第15页/共54页4.2 4.2 运输问题数学模型和电子表格运输问题数学模型和电子表格模型模型表表4-5 4-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.301
16、1.301010需求量需求量1010151525252020由表由表4-54-5可知，总产量（生产能力）为可知，总产量（生产能力）为25+35+30+10=10025+35+30+10=100，总销量（需求量）为，总销量（需求量）为10+15+25+20=7010+15+25+20=70，因此是，因此是产大于销产大于销的运输问题。的运输问题。第16页/共54页4.2 4.2 运输问题数学模型和电子表格运输问题数学模型和电子表格模型模型该生产与该生产与储存问题储存问题（转化为（转化为产大于销产大于销的运输问的运输问题）的数题）的数学模型为学模型为第17页/共54页4.2 4.2 运输问题数学模型
17、和电子表格运输问题数学模型和电子表格模型模型第18页/共54页4.2 4.2 运输问题数学模型和电子表格运输问题数学模型和电子表格模型模型 某公司从两个产地某公司从两个产地A1A1、A2A2将物品运往三个将物品运往三个销地销地 B1 B1、B2B2、B3B3，各产地的产量、各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费的销量和各产地运往各销地每件物品的运费如表如表4-64-6所示。问应如何调运，可使得总运所示。问应如何调运，可使得总运输费最小？输费最小？表表4-6 4-6 例的运输费用表例的运输费用表 B1B1B2B2B3B3产量产量A1A11313151512127878
18、A2A21111292922224545销量销量535336366565（销大于产）（销大于产）第19页/共54页4.2 4.2 运输问题数学模型和电子表格运输问题数学模型和电子表格模型模型解：解：由表由表4-64-6知，总产量为知，总产量为78+45=12378+45=123，总销量为，总销量为53+36+65=15453+36+65=154，销大于产销大于产(供不应求供不应求)。数学模型如。数学模型如下：下：设设xij为产地为产地AiAi运往销地运往销地BjBj的物品数量的物品数量第20页/共54页4.2 4.2 运输问题数学模型和电子表格运输问题数学模型和电子表格模型模型例的电子表格模型
19、例的电子表格模型第21页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模现实生活中符合产销平衡运输问题每一个条件的情况很少。现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。衡运输问题条件的运输问题却经常出现。下面是要讨论的一些特征：下面是要讨论的一些特征：（1 1）总供应大于总需求总供应大于总需求。每一个供应量（产量）代表了从。每一个供应量（产量）代表了从其出发地中配送出去的最大数量（而不是一个固定的数值其出发地中配送出去的最大数
20、量（而不是一个固定的数值,）。）。（2 2）总供应小于总需求总供应小于总需求。每一个需求量（销量）代表了在。每一个需求量（销量）代表了在其目的地中所接收到的最大数量（而不是一个固定的数值其目的地中所接收到的最大数量（而不是一个固定的数值,）。）。（3 3）一个目的地）一个目的地同时存在着最小需求和最大需求同时存在着最小需求和最大需求，于是所，于是所有在这两个数值之间的数量都是可以接收的（有在这两个数值之间的数量都是可以接收的（,）。（4 4）在配送中）在配送中不能使用不能使用特定的出发地特定的出发地目的地组合目的地组合（xij=0=0）。（5 5）目标是使与配送数量有关的）目标是使与配送数量有
21、关的总利润最大总利润最大而不是使总成而不是使总成本最小。（本最小。（MinMin MaxMax）第22页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模例例 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表的任意种产品的数量来衡量（见表4-74-7的最右列）。而每种产品每的最右列）。而每种产品每天有一定的需求量（见表天有一定的需求量（见表4-74-7的最后一行）。每
22、家工厂都可以制造的最后一行）。每家工厂都可以制造这些产品，除了工厂这些产品，除了工厂2 2不能生产产品不能生产产品3 3以外。然而，每种产品在不同以外。然而，每种产品在不同工厂中的单位成本是有差异的（如表工厂中的单位成本是有差异的（如表4-74-7所示）。所示）。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。表表4-7 4-7 产品生产的有关数据产品生产的有关数据单位成本（元）单位成本（元）生产能力生产能力产品产品1 1产品产品2 2产品产品3 3产品产品4 4工厂工厂1 141412727282824247575工厂工厂2 2
23、4040292923237575工厂工厂3 337373030272721214545需求量需求量2020303030304040第23页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模解：解：指定工厂生产产品指定工厂生产产品可以看作运输问题来求可以看作运输问题来求解。本题中，工厂解。本题中，工厂2 2不不能生产产品能生产产品3 3，这样可，这样可以以增加约束条件增加约束条件x230 0 ；并且，总供应；并且，总供应（75+75+45=19575+75+45=195）总总需求需求（20+30+30+40=12020+30+30+40=120）。）。其数学模型如下：其数学模
24、型如下：设设xij为工厂为工厂i生产产生产产品品j的数量的数量第24页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模例的电子表格模型例的电子表格模型产品产品4 4分在分在2 2个工厂生产个工厂生产第25页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模 某公司在某公司在3 3个工厂中专门生产一种产品。在未来的个工厂中专门生产一种产品。在未来的4 4个月中，有四个个月中，有四个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客1 1是是公司最好的顾客，所以他的全部订购量都应该满足；顾客公司
25、最好的顾客，所以他的全部订购量都应该满足；顾客2 2和顾客和顾客3 3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的足他们订单的1/31/3；对于顾客；对于顾客4 4，销售经理认为并不需要进行特殊考，销售经理认为并不需要进行特殊考虑。由于运输成本上的差异，销售一个产品得到的净利润也不同，虑。由于运输成本上的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客（见表很大程度上取决于哪个工厂供应哪个顾客（见表4-84-8）。问）。问应向每一应向每一个顾客供应多少货物个顾客供应多少货物，以使公司总
26、利润最大？，以使公司总利润最大？表表4-8 4-8 工厂供应顾客的相关数据工厂供应顾客的相关数据单位利润（元）单位利润（元）产量产量顾客顾客1 1顾客顾客2 2顾客顾客3 3顾客顾客4 4工厂工厂1 1555542424646535380008000工厂工厂2 2373718183232484850005000工厂工厂3 3292959595151353570007000最小采购量最小采购量7000700030003000200020000 0最大采购量最大采购量70007000900090006000600080008000第26页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输
27、问题建模模解：解：该问题要求满足不该问题要求满足不同顾客的需求（采购量）同顾客的需求（采购量），解决办法：，解决办法：实际供给量实际供给量 最小采购最小采购量量实际供给量实际供给量 最大采购最大采购量量 目标是利润最大，目标是利润最大，而不是成本最小。而不是成本最小。其数学模型如下：其数学模型如下：设设xij为为工厂工厂i供应给供应给顾客顾客j的产品数量的产品数量第27页/共54页4.3 4.3 各种变形的运输问题建各种变形的运输问题建模模例的电子表格模型例的电子表格模型第28页/共54页4.4 4.4 运输问题应用举例运输问题应用举例 某厂生产设备是以销定产的。已知某厂生产设备是以销定产的。
28、已知1 16 6月份各月的生产能力、合月份各月的生产能力、合同销量和单台设备平均生产费用，如表同销量和单台设备平均生产费用，如表4-94-9所示。所示。已知上年末库存已知上年末库存103103台。如果当月生产出来的设备当月不交货，台。如果当月生产出来的设备当月不交货，则需要运到分厂库房，每台增加运输成本万元，每台设备每月的则需要运到分厂库房，每台增加运输成本万元，每台设备每月的平均仓储费、维护费为万元。平均仓储费、维护费为万元。7 78 8月份为销售淡季，全厂停产月份为销售淡季，全厂停产1 1个个月，因此在月，因此在6 6月份完成销售合同后还要留出库存月份完成销售合同后还要留出库存8080台。
29、加班生产设台。加班生产设备每台增加成本备每台增加成本1 1万元。问应如何安排万元。问应如何安排1 16 6月份的生产，使总的生月份的生产，使总的生产（包括运输、仓储、维护）费用最少？产（包括运输、仓储、维护）费用最少？月份月份正常生产能力正常生产能力（台）（台）加班生产能力加班生产能力（台）（台）合同销量合同销量（台）（台）单台费用单台费用（万元）（万元）1 1月月6060101010410415152 2月月50501010757514143 3月月9090202011511513.513.54 4月月100100404016016013135 5月月10010040401031031313
30、6 6月月80804040707013.513.5第29页/共54页4.4 4.4 运输问题应用举例运输问题应用举例解：解：这是一个生产与储存问题，但可以转化为这是一个生产与储存问题，但可以转化为运输问题来做。运输问题来做。（是否可以采用第（是否可以采用第3 3章的方法做？同学们可以章的方法做？同学们可以试试，然后进行比较）试试，然后进行比较）生产方案不变，但总费用为：万元生产方案不变，但总费用为：万元u根据已知条件可以列出生产能力（正常生产能根据已知条件可以列出生产能力（正常生产能力和加班生产能力）和销量以及运价表力和加班生产能力）和销量以及运价表（P120P120）u数学模型数学模型P12
31、0P120121121u电子表格模型电子表格模型P122P122u求解结果求解结果P123P123第30页/共54页4.4 4.4 运输问题应用举例运输问题应用举例例例 华中金刚石锯片厂有两条生产线，分别生产华中金刚石锯片厂有两条生产线，分别生产直径直径900-1800mm900-1800mm大锯片基体大锯片基体2000020000片，直径片，直径350-350-800mm800mm中小锯片基体中小锯片基体4000040000片。公司在全国有片。公司在全国有2525个销售网点，主要销售区域集中在福建、广东、个销售网点，主要销售区域集中在福建、广东、广西、四川、山东广西、四川、山东5 5个石材主
32、产区。为完成总厂个石材主产区。为完成总厂的要求，公司决定一方面拿出的要求，公司决定一方面拿出10%10%的产量稳定与的产量稳定与前期各个客户的联系以保证将来的市场区域份额，前期各个客户的联系以保证将来的市场区域份额，另一方面，面临如何将剩余的另一方面，面临如何将剩余的90%90%的产量合理分的产量合理分配给配给五个石材主产区和其他省区五个石材主产区和其他省区，以获取最大的，以获取最大的利润。各个销售区的最低需求、销售固定费用、利润。各个销售区的最低需求、销售固定费用、每片平均运费、每片从总厂库房的购进价与当地每片平均运费、每片从总厂库房的购进价与当地的销售价差贡献等自然情况见表的销售价差贡献等
33、自然情况见表4-124-12。问应如。问应如何分配给各个销售区，才能使得总利润为最大？何分配给各个销售区，才能使得总利润为最大？第31页/共54页4.4 4.4 运输问题应用举例运输问题应用举例解：解：该问题数据较多，但是经过分该问题数据较多，但是经过分析，其产量在最低需求和最高需析，其产量在最低需求和最高需求之间，并且目标函数是最大利求之间，并且目标函数是最大利润，可以化简为表润，可以化简为表4-134-13（P124P124）u数学模型数学模型P124P124u电子表格模型电子表格模型P125P125u求解结果求解结果P126P126第32页/共54页4.5 4.5 指派问题指派问题u在现
34、实生活中，经常会遇到指派人员做某项在现实生活中，经常会遇到指派人员做某项工作（任务）的情况。工作（任务）的情况。指派问题指派问题的许多应用是的许多应用是用来帮助管理人员解决如何为一项即将开展的用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题。其他的一些应用如为工工作指派人员的问题。其他的一些应用如为工作指派机器、设备或工厂等。作指派机器、设备或工厂等。u指派问题也称指派问题也称分配问题分配问题，主要研究人和工作，主要研究人和工作（任务）间如何匹配，以使所有工作完成的效（任务）间如何匹配，以使所有工作完成的效率实现最优化。形式上，指派问题给定了一系率实现最优化。形式上，指派问题给定了一
35、系列所要完成的工作以及一系列完成工作的人员，列所要完成的工作以及一系列完成工作的人员，所需要解决的问题就是要确定出指派哪个人去所需要解决的问题就是要确定出指派哪个人去完成哪项工作。完成哪项工作。第33页/共54页4.5 4.5 指派问题指派问题u指派问题的假设：指派问题的假设：（1 1）人的数量和工作的数量）人的数量和工作的数量相等相等；（2 2）每个人）每个人只能完成一项只能完成一项工作；工作；（3 3）每项工作）每项工作只能由一个人只能由一个人来完成；来完成；（4 4）每个人和每项工作的组合都会有）每个人和每项工作的组合都会有一个相关的成本（一个相关的成本（单位成本单位成本）；）；（5 5
36、）目标是要确定如何指派才能使）目标是要确定如何指派才能使总总成本最小成本最小。第34页/共54页4.5 4.5 指派问题指派问题u设决策变量设决策变量xij为为第第i个人个人做做第第j项工作项工作，而，而已知目标函数系数已知目标函数系数cij为第为第i个人完成第个人完成第j项工项工作所需要的作所需要的单位成本单位成本。u平衡指派问题的数学模型为平衡指派问题的数学模型为第35页/共54页4.5 4.5 指派问题指派问题u需要说明的是：需要说明的是：指派问题指派问题实际上是一种实际上是一种特殊特殊的运输问题的运输问题。其中出发地是人，目的地是工作。其中出发地是人，目的地是工作。只不过，每一个出发地
37、的只不过，每一个出发地的供应量都为供应量都为1 1（因为（因为每个人都要完成一项工作），每一个目的地的每个人都要完成一项工作），每一个目的地的需求量都为需求量都为1 1（因为每项工作都要完成）。由（因为每项工作都要完成）。由于运输问题有于运输问题有“整数解性质整数解性质”，因此，因此，没有必没有必要要加上所有决策变量都是加上所有决策变量都是0-10-1变量变量的约束。的约束。u指派问题是一种特殊的线性规划问题，有一指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：种快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但Excel
38、Excel的的“规划求解规划求解”工具还是工具还是采用采用“单纯形法单纯形法”来求解。来求解。第36页/共54页4.5 4.5 指派问题指派问题例例 某公司的营销经理将要主持召开一年一度的由某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一小李、小刘等四个人，每个人负责完成下面的一项工作：项工作：A A、B B、C C和和D D。由于每个人完成每项任务的时间和工资不同由于每个人完成每项任务的时
39、间和工资不同（如表（如表4-144-14所示）。问如何指派，可使总成本最所示）。问如何指派，可使总成本最小。小。人员人员每一项工作所需要的时间（小时）每一项工作所需要的时间（小时）每小时工资每小时工资（元）（元）工作工作A A工作工作B B工作工作C C工作工作D D小张小张35354141272740401414小王小王47474545323251511212小李小李39395656363643431313小刘小刘32325151252546461515第37页/共54页4.5 4.5 指派问题指派问题解解：该问题是一个：该问题是一个典型的指派问题典型的指派问题。u单位成本单位成本为每个人做
40、每项工作的为每个人做每项工作的总工资总工资u目标目标是要确定哪个人做哪一项工是要确定哪个人做哪一项工作，使总成本最小作，使总成本最小u供应量为供应量为1 1代表每个人都只能完成代表每个人都只能完成一项工作一项工作u需求量为需求量为1 1代表每项工作也只能有代表每项工作也只能有一个人来完成一个人来完成u总人数（总人数（4 4人）和总任务数（人）和总任务数（4 4项）项）相等相等第38页/共54页4.5 4.5 指派问题指派问题数学模型：数学模型：设设xij为指派人员为指派人员i去做工作去做工作j（i，j1,2,3,4)1,2,3,4)第39页/共54页4.5 4.5 指派问题指派问题电子表格模型
41、电子表格模型第40页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模经常会遇到指派问题的经常会遇到指派问题的变形变形，之所以称它们为变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设之中的是因为它们都不满足平衡指派问题所有假设之中的一个或者多个。一般考虑下面的一些特征：一个或者多个。一般考虑下面的一些特征：（1 1）有些人并）有些人并不能不能进行某项工作（相应的进行某项工作（相应的xij0 0）;（2 2）虽然每个人完成一项任务，但是任务比人多）虽然每个人完成一项任务，但是任务比人多(人少事人少事多多););（3 3）虽然每一项任务只由一个人完成，但是人比任
42、务多）虽然每一项任务只由一个人完成，但是人比任务多（人多事少人多事少）；）；（4 4）某人可以同时被指派给多个任务（）某人可以同时被指派给多个任务（一人可做几件事一人可做几件事）；）；（5 5）某事可以由多人共同完成（）某事可以由多人共同完成（一事可由多人完成一事可由多人完成）；（6 6）目标是与指派有关的）目标是与指派有关的总利润最大总利润最大而不是使总成本最小；而不是使总成本最小；（7 7）实际需要完成任务数不超过总人数也不超过总任务数。）实际需要完成任务数不超过总人数也不超过总任务数。第41页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模例例 题目见例，即某公司需
43、要安排三个工厂题目见例，即某公司需要安排三个工厂来生产四种新产品，相关的数据在表来生产四种新产品，相关的数据在表4-74-7中中已经给出。在例中，允许产品生产分解，已经给出。在例中，允许产品生产分解，但这将产生与产品生产分解相关的隐性成但这将产生与产品生产分解相关的隐性成本（包括额外的设置、配送和管理成本等）本（包括额外的设置、配送和管理成本等）。因此，管理人员决定在。因此，管理人员决定在禁止产品生产分禁止产品生产分解解发生的情况下对问题进行分析。发生的情况下对问题进行分析。新问题描述为：已知如表新问题描述为：已知如表4-74-7所示的所示的数据，问如何把每一个工厂指派给至少一数据，问如何把每
44、一个工厂指派给至少一个新产品（每一种产品只能在一个工厂生个新产品（每一种产品只能在一个工厂生产），使总成本达到最小？产），使总成本达到最小？第42页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模解：解：该问题可视为该问题可视为指派工厂生产产品问指派工厂生产产品问题题，工厂可以看作指派问题中的人，产，工厂可以看作指派问题中的人，产品则可以看作需要完成的工作（任务）。品则可以看作需要完成的工作（任务）。由于有四种产品和三个工厂，所以就有由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂个工厂生
45、产两种新产品。只有工厂1 1和和工厂工厂2 2有生产两种产品的能力。有生产两种产品的能力。这里涉及如何把这里涉及如何把运输问题运输问题转换为转换为指指派问题派问题，关键所在是，关键所在是数据转换数据转换。第43页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模数据转换：数据转换：（1 1）单位指派成本单位指派成本:原来的单位成本转换成原来的单位成本转换成整整批批成本（单位成本成本（单位成本需求量），即单位指派需求量），即单位指派成本为成本为每个工厂生产每种产品的成本每个工厂生产每种产品的成本。（2 2）供应量和需求量的转换问题供应量和需求量的转换问题：三个工厂生：三个工厂
46、生产四种产品，但一种产品只能在一个工厂生产，产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂根据生产能力，工厂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）”,为人多事少的指派问题为人多事少的指派问题。第44页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模数学模型：数学模型：设设x
47、ij为指派工厂为指派工厂i生产产品生产产品j（i=1,2,3;=1,2,3;j=1,2,3,4)=1,2,3,4)第45页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模电子表格模型电子表格模型第46页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模例例 一家制药公司，为了提升企业的竞争力，一家制药公司，为了提升企业的竞争力，决定加大科研力度。在研究了市场的需要，决定加大科研力度。在研究了市场的需要，分析了当前药物的不足并且拜会了大量对分析了当前药物的不足并且拜会了大量对有良好前景的医药领域进行研究的科学家有良好前景的医药领域进行研究的科学家之后，决
48、定由之后，决定由五位科学家五位科学家领导领导开发五个项开发五个项目目。为了保证这些科学家都能够到他们感。为了保证这些科学家都能够到他们感兴趣的项目中去，为此建立了一个兴趣的项目中去，为此建立了一个投标系投标系统统。这五位科学家每个人都有。这五位科学家每个人都有10001000点点的投的投标点。他们向每一个项目投标，并且把较标点。他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项目中。多的投标点投向自己最感兴趣的项目中。表表4-154-15显示了这显示了这5 5位科学家进行投标的情位科学家进行投标的情况。况。第47页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模
49、表表4-15 4-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 3333 343480800 0第48页/共54页4.6 4.6 各种变形的指派问题建各种变形的指派问题建模模分析
50、：决定要对一些可能发生的情况进行评估。分析：决定要对一些可能发生的情况进行评估。（1 1）根据所给出的投标情况，需要为每一个项）根据所给出的投标情况，需要为每一个项目指派一位资深的科学家，使得科学家的总满目指派一位资深的科学家，使得科学家的总满意度最高。那么应当怎样指派？意度最高。那么应当怎样指派？（人数与项目数相等）（人数与项目数相等）P133P133134134（2 2）罗林博士接到了北大医学院的邀请去完成）罗林博士接到了北大医学院的邀请去完成一个教学任务，而公司却非常想把她留下来。一个教学任务，而公司却非常想把她留下来。但是北大的声望会使她离开公司。如果这种情但是北大的声望会使她离开公司