第4讲- 运输问题及指派问题

1、运用运用ExcelExcel建模和求解建模和求解第第4 4章章运输问题和指派问题运输问题和指派问题本章内容要点本章内容要点 运输问题运输问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用 指派问题指派问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用本章节内容本章节内容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、派问题变形的建模各种指派问题变形的建模本章主要内容框架图本章主要内容框架图产销平衡（总产量等于总销量）产大于销（总产量大于总销量）销大于产（总产量小于总销量）运输问题数学模型和电子表格模型运输问题和指派问题各种变形的建模应用举例平衡指派问题（总人数等于总任务数）指派问题数学模型和电子表格模型各种变形的建模4.1 4.1 运输问题基本概念运输问题基本概念运输问题最初起源于人们在日常生活中把某些运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方物品或人们自身从一些地方转移到另一些地方，要求所采用的，要求所采用的运输路线运输路线或或运输方案是最经济运输方案是最经济或成本

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

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

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

6、.1 4.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 64.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（1 1）产销平衡产销平衡运输问题的数学模型运输问题的数学模型 具有具有m个产地个产地A Ai i（i1,2,1,2

8、, ,m）和和n个销地个销地 B Bj j（j1,2,1,2, ,n）的运输问题的数学模型为的运输问题的数学模型为1111()()M in (1, 2,) s.t. (1, 2,)0 (1, 2,; 1, 2,)mnijijijnijijmijjiijzc xxaimxbjnximjn 产 量 约 束销 量 约 束 LLLL11mnijijab4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型对于例对于例4.14.1，其数学模型如下：，其数学模型如下： 首先，三个产地首先，三个产地A1A1、A2A2、A3A3的总产量为的总产量为7 74 49 92020；四个；四个销

9、地销地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）目标函数）目标函数 本问题的目标是使得总运输费最小。本问题的目标是使得总运输费最小。1 11 21 31 42 12 22 32 43 13 23 33 4M in z31 1 31 0 9 2 8

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

11、23331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxij4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u运输问题是一种特殊的线性规划问题，一般采用运输问题是一种特殊的线性规划问题，一般采用“表上作表上作业法业法”求解运输问题，但求解运输问题，但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。u例例4.14.1的电子表格模型的电子表格模型4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（2 2）产大于销（供过于求）产大于销（供过于求）运输问题运输问题的数学模型的数学

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

13、jijmijjiijzc xxaimxbjnxim jn产量约束销量约束LLLL4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型该生产与该生产与储存问题储存问题（转化为（转化为产大于销产大于销的运输问的运输问题）的数题）的数学模型为学模型为111213142223243334M in z10.8010.9511.1011.25 11.1011.2511.40 11.0011.15 xxxxxxxxx4411121314222324333444111222132333 11.3025 35 30 10s.t. 10 15 xxxxxxxxxxxxxxxxx142434

14、44 25200 ( ,1, 2,3, 4; )ijxxxxxijij4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3 某公司从两个产地某公司从两个产地A1A1、A2A2将物品运往将物品运往三个销地三个销地 B1 B1、B2B2、B3B3，各产地的产量、各销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运地的销量和各产地运往各销地每件物品的运费如表费如表4 46 6所示。问应如何调运，可使得总所示。问应如何调运，可使得总运输费最小？运输费最小？表表4 46 6 例例4.34.3的运输费用表的运输费用表 B1B1B2B2B3B3产量产量A1A

15、11313151512127878A2A21111292922224545销量销量535336366565（销大于产）（销大于产）4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解：解：由表由表4 46 6知，总产量为知，总产量为78+45=12378+45=123，总销量为，总销量为53+36+65=15453+36+65=154，销大于产销大于产( (供不应求供不应求) )。数学模型如下：。数学模型如下： 设设xij为产地为产地AiAi运往销地运往销地BjBj的物品数量的物品数量11121321222311121312122232112111222213233M

16、in z 13151211292278 ()45 ()53 ()s.t. 36 ()65 ()0(1,2;1,2,3)ijxxxxxxxxxAxxxAxxBxxBxxBxij产地产地销地销地销地4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3的电子表格模型的电子表格模型4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模现实生活中符合产销平衡运输问题每一个条件的情况很少。一现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件

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

18、在着最小需求和最大需求，于是所有在，于是所有在这两个数值之间的数量都是可以接收的（这两个数值之间的数量都是可以接收的（, ,）。）。（4 4）在配送中）在配送中不能使用不能使用特定的出发地特定的出发地目的地组合（目的地组合（xij=0=0）。）。（5 5）目标是使与配送数量有关的）目标是使与配送数量有关的总利润最大总利润最大而不是使总成本最而不是使总成本最小。（小。（MinMin MaxMax）4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5 某公司在某公司在3 3个工厂中专门生产一种产品。在未来的个工厂中专门生产一种产品。在未来的4 4个月中，有四个月中，有四个处

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

20、销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客（见表个顾客（见表4 48 8）。问应）。问应向每一个顾客供应多少货物向每一个顾客供应多少货物，以使公司总利润，以使公司总利润最大？最大？表表4 48 8 工厂供应顾客的相关数据工厂供应顾客的相关数据单位利润（元）单位利润（元）产量产量顾客顾客1 1顾客顾客2 2顾客顾客3 3顾客顾客4 4工厂工厂1 1555542424646535380008000工厂工厂2 2373718183232484850005000工厂工厂3 3292959595151353570007000最小采购量最小采购量70007000300030002

21、00020000 0最大采购量最大采购量700070009000900060006000800080004.3 4.3 各种运输问题变形的建模各种运输问题变形的建模解：解：该问题要求满足不该问题要求满足不同顾客的需求（采购量同顾客的需求（采购量），解决办法：），解决办法：实际供给量实际供给量 最小采购量最小采购量实际供给量实际供给量 最大采购量最大采购量 目标是利润最大，而目标是利润最大，而不是成本最小。不是成本最小。其数学模型如下：其数学模型如下： 设设xij为工厂为工厂i供应给顾供应给顾客客j的产品数量的产品数量111213142122232431323334111213142122232

22、431323334Max 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.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5的电子表格模型的电子表格模型4.5 4.5 指派问题指派问题u在现实生活中，经常会遇到指派人员做某项在现实生活中，经

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

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

25、成本最小。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(第 人只能做一项工作)(第 项工作只能一人做)非负 LLL4.5 4.5 指派问题指派问题u需要说明的是：需要说明的是：指派问题指派问题实际上是一种实

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

27、快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形法”来求解。来求解。4.5 4.5 指派问题指派问题例例4.84.8 某公司的营销经理将要主持召开一年一度的某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、。为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项小李、小刘等四个人，每个人负责完成下面的一项

28、工作：工作：A A、B B、C C和和D D。 由于每个人完成每项任务的时间和工资不同（如由于每个人完成每项任务的时间和工资不同（如表表4 41414所示）。问如何指派，可使总成本最小。所示）。问如何指派，可使总成本最小。人员人员每一项工作所需要的时间（小时）每一项工作所需要的时间（小时）每小时工资每小时工资（元）（元）工作工作A A工作工作B B工作工作C C工作工作D D小张小张35354141272740401414小王小王47474545323251511212小李小李39395656363643431313小刘小刘323251512525464615154.5 4.5 指派问题指派问

29、题解解：该问题是一个：该问题是一个典型的指派问题典型的指派问题。单位成本单位成本为每个人做每项工作的总为每个人做每项工作的总工资工资目标目标是要确定哪个人做哪一项工作是要确定哪个人做哪一项工作，使总成本最小，使总成本最小供应量为供应量为1 1代表每个人都只能完成一代表每个人都只能完成一项工作项工作需求量为需求量为1 1代表每项工作也只能有一代表每项工作也只能有一个人来完成个人来完成总人数（总人数（4 4人）和总任务数（人）和总任务数（4 4项）项）相等相等4.5 4.5 指派问题指派问题数学模型：数学模型：设设xij为指派人员为指派人员i去做工作去做工作j（i，j1,2,3,4)1,2,3,4

30、) 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. xxxxxxxxxxxxxxxxxxxxxx（ 小 张 要 完 成 一 项 工 作 ） 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（ 小 王 要 完 成 一 项 工 作 ）（ 小 李 要 完 成 一 项 工 作 ）（ 小