第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章章 运输问题

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

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

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

6、，整个需求量都必须由出发地满足。即定的需求量，整个需求量都必须由出发地满足。即“总供应总供应 总需求总需求”。 3.3.成本假设：从任何一个出发地到任何一个目的地的货物配送成成本假设：从任何一个出发地到任何一个目的地的货物配送成 本与所配送的数量成线性比例关系，因此成本就等于配送的单本与所配送的数量成线性比例关系，因此成本就等于配送的单 位成本乘以所配送的数量（目标函数是线性的）。位成本乘以所配送的数量（目标函数是线性的）。 第第4章章 运输问题运输问题 和指派问题和指派问题 4.1 4.1 运输问题基本概念运输问题基本概念 例例4.1 4.1 某公司有三个加工厂某公司有三个加工厂A1A1、A

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

8、1 1 各工厂到各销售点的单位产品运价（元各工厂到各销售点的单位产品运价（元/ /吨）吨） B1B1B2B2B3B3B4B4产量（吨）产量（吨） A1A13 311113 310107 7 A2A21 19 92 28 84 4 A3A37 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 B

9、j j（j1,2,1,2, ,n）的运输问题的数学模型为的运输问题的数学模型为 11 1 1 () () M in (1, 2,) s.t. (1, 2,) 0 (1, 2,; 1, 2,) mn ijij ij n iji j m ijj i ij zc x xaim xbjn ximjn 产 量 约 束 销 量 约 束 L L LL 11 mn ij ij ab 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 对于例对于例4.14.1，其数学模型如下：，其数学模型如下： 首先，三个产地首先，三个产地A1A1、

10、A2A2、A3A3的总产量为的总产量为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）目标函数）目标函数 本问题的目标是使得总运输费最小。本问题的目标是使得总运输费最小。 1 11 21 31 4 2

11、12 22 32 4 3 13 23 33 4 M in z31 1 31 0 9 2 8 741 0 5 xxxx xxxx xxxx 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 （3 3）约束条件）约束条件 满足产地产量满足产地产量 （3 3个产地的个产地的 产品都要全部产品都要全部 配送出去）配送出去） 满足销地销量满足销地销量 （4 4个销地的个销地的 产品都要全部产品都要全部 得到满足）得到满足） 非负非负 11121314 21222324 31323334 11121314 21222324 3

12、1323334 112131 122232 Min z311 310 9 2 8 7 410 5 7 4 9 3 s.t. 6 xxxx xxxx xxxx xxxx xxxx xxxx xxx xxx 132333 142434 5 6 0(1,2,3;1,2,3,4) ij xxx xxx xij 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 u运输问题是一种特殊的线性规划问题，一般采用运输问题是一种特殊的线性规划问题，一般采用“表上作表上作 业法业法”求解运输问题，但求解运输问题，但ExcelExcel的

13、的“规划求解规划求解”还是采用还是采用“ 单纯形法单纯形法”来求解。来求解。 u例例4.14.1的电子表格模型的电子表格模型 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 u 需要注意的是：运输问题有这样一个性质需要注意的是：运输问题有这样一个性质 （整数解性质整数解性质），只要它的），只要它的供应量供应量和和需求需求 量量都是都是整数整数，任何有可行解的运输问题必，任何有可行解的运输问题必 然有所有决策变量都是然有所有决策变量都是整数的最优解整数的最优解。因。因 此，没有必要加上所有变量都是整数的约此，没有必

14、要加上所有变量都是整数的约 束条件。束条件。 u 由于运输量经常以卡车、集装箱等为单位由于运输量经常以卡车、集装箱等为单位 ，如果卡车不能装满的话，就很不经济了，如果卡车不能装满的话，就很不经济了 。整数解性质就避免了运输量（运输方案。整数解性质就避免了运输量（运输方案 ）为小数的麻烦。）为小数的麻烦。 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 （2 2）产大于销（供过于求）产大于销（供过于求）运输问题运输问题 的数学模型的数学模型 （以满足小的销量为准以满足小的销量为准） 11 mn ij ij ab 1

15、1 1 1 () () Min z (1,2,) s.t. (1,2, ) 0 (1,2,;1,2, ) mn iji j ij n iji j m ijj i ij c x xaim xbjn xim jn 产量约束 销量约束 L L LL 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 （3 3）销大于产（供不应求）销大于产（供不应求）运输问题运输问题 的数学模型的数学模型 （以满足小的产量为准以满足小的产量为准） 11 mn ij ij ab 11 1 1 () () Min (1,2,) s.t. (1,

16、2, ) 0 (1,2,;1,2, ) mn iji j ij n iji j m ijj i ij zc x xaim xbjn xim jn 产量约束 销量约束 L L LL 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 例例4.2 4.2 某厂按合同规定须于当年每个季度末分别提某厂按合同规定须于当年每个季度末分别提 供供1010，1515，2525，2020台同一规格的柴油机。已知该厂台同一规格的柴油机。已知该厂 各季度的生产能力及生产每台柴油机的成本如表各季度的生产能力及生产每台柴油机的成本如表4 4

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

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

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

20、2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 表表4 45 5 柴油机生产的相关数据柴油机生产的相关数据 1 12 23 34 4生产能力生产能力 1 110.810.810.9510.9511.1011.1011.2511.252525 2 211.1011.1011.2511.2511.4011.403535 3 311.0011.0011.1511.153030 4 411.3011.301010 需求量需求量1010151525252020 由表由表4 45 5可知，总产量（生产能力）为可知，总产量（生产能力）为 25+35+30+10=10025+35+3

21、0+10=100，总销量（需求量）为，总销量（需求量）为 10+15+25+20=7010+15+25+20=70，因此是，因此是产大于销产大于销的运输问题。的运输问题。 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 该生产与该生产与 储存问题储存问题 （转化为（转化为 产大于销产大于销 的运输问的运输问 题）的数题）的数 学模型为学模型为 11121314 222324 3334 M in z10.8010.9511.1011.25 11.1011.2511.40 11.0011.15 xxxx xxx xx

22、 44 11121314 222324 3334 44 11 1222 132333 11.30 25 35 30 10 s.t. 10 15 x xxxx xxx xx x x xx xxx 14243444 25 20 0 ( ,1, 2,3, 4; ) ij xxxx xijij 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 例例4.24.2的电子表格模型的电子表格模型 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 例例4

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

24、4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 解：解：由表由表4 46 6知，总产量为知，总产量为78+45=12378+45=123，总销量为，总销量为 53+36+65=15453+36+65=154，销大于产销大于产( (供不应求供不应求) )。数学模型如下：。数学模型如下： 设设xij为产地为产地AiAi运往销地运往销地BjBj的物品数量的物品数量 111213212223 1112131 2122232 11211 12222 13233 Min z 131512112922 78 () 45 () 53

25、 () s.t. 36 () 65 () 0(1,2;1,2,3) ij xxxxxx xxxA xxxA xxB xxB xxB xij 产地 产地 销地 销地 销地 第第4章章 运输问题运输问题 和指派问题和指派问题 4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 例例4.34.3的电子表格模型的电子表格模型 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模 现实生活中符合产销平衡运输问题每一个条件的情况很少。一现实生活中符合产销平衡运输问题每一个条件的情况很少。一 个特征近似但其中的一个或者几个

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

27、而不是一个固定的数值, ,）。）。 （3 3）一个目的地）一个目的地同时存在着最小需求和最大需求同时存在着最小需求和最大需求，于是所有在，于是所有在 这两个数值之间的数量都是可以接收的这两个数值之间的数量都是可以接收的（, ,）。 （4 4）在配送中）在配送中不能使用不能使用特定的出发地特定的出发地目的地组合目的地组合（xij=0=0）。 （5 5）目标是使与配送数量有关的）目标是使与配送数量有关的总利润最大总利润最大而不是使总成本最而不是使总成本最 小小。（。（MinMin MaxMax） 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3 各种运输问题变形的建模各种运输问题

28、变形的建模 例例4.44.4 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。某公司决定使用三个有生产余力的工厂进行四种新产品的生产。 每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任 意种产品的数量来衡量（见表意种产品的数量来衡量（见表4 47 7的最右列）。而每种产品每天有一定的最右列）。而每种产品每天有一定 的需求量（见表的需求量（见表4 47 7的最后一行）。每家工厂都可以制造这些产品，除的最后一行）。每家工厂都可以制造这些产品，除 了工厂了工厂2 2不能生产产品不能生产产品3 3以外。然而，每种产品在

29、不同工厂中的单位成本以外。然而，每种产品在不同工厂中的单位成本 是有差异的（如表是有差异的（如表4 47 7所示）。所示）。 现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。 表表4 47 7 产品生产的有关数据产品生产的有关数据 单位成本（元）单位成本（元） 生产能力生产能力 产品产品1 1产品产品2 2产品产品3 3产品产品4 4 工厂工厂1 141412727282824247575 工厂工厂2 24040292923237575 工厂工厂3 337373030272721214545 需求量需求量2020303030304

30、040 第第4章章 运输问题运输问题 和指派问题和指派问题 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）。）。 其数学模型如下：其数学模型如下： 设设xij为工厂为工厂i生产产品生产产品j 的数量的数量

31、 11121314 212224 31323334 112131 122232 132333 142434 Min z41272824 4029 23 37302721 20 (1) 30 (2) 30 (3) 40 ( s.t. xxxx xxx xxxx xxx xxx xxx xxx 产品 产品 产品 11121314 21222324 31323334 23 4) 75 (1) 75 (2) 45 (3) 0 0(1,2,3;1,2,3,4) ij xxxx xxxx xxxx x xij 产品 工厂 工厂 工厂 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3 各种

32、运输问题变形的建模各种运输问题变形的建模 例例4.44.4的电子表格模型的电子表格模型 产品产品4 4分在分在2 2个工厂生产个工厂生产 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模 例例4.54.5 某公司在某公司在3 3个工厂中专门生产一种产品。在未来的个工厂中专门生产一种产品。在未来的4 4个月中，有四个月中，有四 个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客1 1是公司是公司 最好的顾客，所以他的全部订购量都应该满足；顾客最好的顾客，所以他的全部订

33、购量都应该满足；顾客2 2和顾客和顾客3 3也是公司很也是公司很 重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/31/3； 对于顾客对于顾客4 4，销售经理认为并不需要进行特殊考虑。由于运输成本上的差异，销售经理认为并不需要进行特殊考虑。由于运输成本上的差异 ，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪 个顾客（见表个顾客（见表4 48 8）。问应）。问应向每一个顾客供应多少货物向每一个顾客供应多少货物，以使公司总利润，以使公司总利润

34、 最大？最大？ 表表4 48 8 工厂供应顾客的相关数据工厂供应顾客的相关数据 单位利润（元）单位利润（元） 产量产量 顾客顾客1 1顾客顾客2 2顾客顾客3 3顾客顾客4 4 工厂工厂1 1555542424646535380008000 工厂工厂2 2373718183232484850005000 工厂工厂3 3292959595151353570007000 最小采购量最小采购量7000700030003000200020000 0 最大采购量最大采购量70007000900090006000600080008000 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3

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

36、 (1) 5000 (2) 7000 (3) s.t. xxxx xxxx xxxx xxxx xxxx xxxx x 工厂 工厂 工厂 112131 122232 132333 142434 7000 (1) 30009000 (2) 20006000 (3) 8000 (4) 0(1,2,3;1,2,3,4) ij xx xxx xxx xxx xij 顾客 顾客 顾客 顾客 第第4章章 运输问题运输问题 和指派问题和指派问题 4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模 例例4.54.5的电子表格模型的电子表格模型 第第4章章 运输问题运输问题 和指派问题和指派问题 4.

37、4 4.4 运输问题应用举例运输问题应用举例 例例4.64.6 某厂生产设备是以销定产的。已知某厂生产设备是以销定产的。已知1 16 6月份各月的生产能力、月份各月的生产能力、 合同销量和单台设备平均生产费用，如表合同销量和单台设备平均生产费用，如表4 49 9所示。所示。 已知上年末库存已知上年末库存103103台。如果当月生产出来的设备当月不交货，则台。如果当月生产出来的设备当月不交货，则 需要运到分厂库房，每台增加运输成本需要运到分厂库房，每台增加运输成本0.10.1万元，每台设备每月的平均万元，每台设备每月的平均 仓储费、维护费为仓储费、维护费为0.20.2万元。万元。7 78 8月份

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

39、0101075751414 3 3月月9090202011511513.513.5 4 4月月10010040401601601313 5 5月月10010040401031031313 6 6月月80804040707013.513.5 第第4章章 运输问题运输问题 和指派问题和指派问题 4.4 4.4 运输问题应用举例运输问题应用举例 解：解：这是一个生产与储存问题，但可以转化为运这是一个生产与储存问题，但可以转化为运 输问题来做。输问题来做。 （是否可以采用第（是否可以采用第3 3章的方法做？同学们可以试章的方法做？同学们可以试 试，然后进行比较）试，然后进行比较）生产方案不变，但总费用

40、为：生产方案不变，但总费用为：8329.78329.7万元万元 u根据已知条件可以列出生产能力（正常生产能根据已知条件可以列出生产能力（正常生产能 力和加班生产能力）和销量以及运价表（力和加班生产能力）和销量以及运价表（P120P120） u数学模型数学模型P120P120121121 u电子表格模型电子表格模型P122P122 u求解结果求解结果P123P123 第第4章章 运输问题运输问题 和指派问题和指派问题 4.4 4.4 运输问题应用举例运输问题应用举例 例例4.74.7 华中金刚石锯片厂有两条生产线，分别生产华中金刚石锯片厂有两条生产线，分别生产 直径直径900-1800mm900

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

42、90%90%的产量合理分配给的产量合理分配给五个石材五个石材 主产区和其他省区主产区和其他省区，以获取最大的利润。各个销售，以获取最大的利润。各个销售 区的最低需求、销售固定费用、每片平均运费、每区的最低需求、销售固定费用、每片平均运费、每 片从总厂库房的购进价与当地的销售价差贡献等自片从总厂库房的购进价与当地的销售价差贡献等自 然情况见表然情况见表4 41212。问应如何分配给各个销售区，。问应如何分配给各个销售区， 才能使得总利润为最大？才能使得总利润为最大？ 第第4章章 运输问题运输问题 和指派问题和指派问题 4.4 4.4 运输问题应用举例运输问题应用举例 解：解：该问题数据较多，但是

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

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

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

46、输问题 和指派问题和指派问题 4.5 4.5 指派问题指派问题 u设决策变量设决策变量xij为第为第i个人做第个人做第j项工作，而已项工作，而已 知目标函数系数知目标函数系数cij为第为第i个人完成第个人完成第j项工作所项工作所 需要的单位成本。需要的单位成本。 u平衡指派问题的数学模型为平衡指派问题的数学模型为 11 1 1 () Min z 1 (1,2, ) s.t. 1 (1,2, ) 0 ( ,1,2, ) nn ijij ij n ij j n ij i ij i j c x xin xjn xi jn (第 人只能做一项工作) (第 项工作只能一人做) 非负 L L L 第第4章

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

48、所有决策变量都是0-10-1变量变量的约束。的约束。 u指派问题是一种特殊的线性规划问题，有一指派问题是一种特殊的线性规划问题，有一 种快捷的求解方法：种快捷的求解方法：匈牙利方法匈牙利方法（Hungarian Hungarian MethodMethod），但），但ExcelExcel的的“规划求解规划求解”还是采用还是采用 “单纯形法单纯形法”来求解。来求解。 第第4章章 运输问题运输问题 和指派问题和指派问题 4.5 4.5 指派问题指派问题 例例4.84.8 某公司的营销经理将要主持召开一年一度的某公司的营销经理将要主持召开一年一度的 由营销区域经理以及销售人员参加的销售协商会议由营销

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

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

51、项工作 需求量为需求量为1 1代表每项工作也只能有一代表每项工作也只能有一 个人来完成个人来完成 总人数（总人数（4 4人）和总任务数（人）和总任务数（4 4项）项） 相等相等 第第4章章 运输问题运输问题 和指派问题和指派问题 4.5 4.5 指派问题指派问题 数学模型：数学模型： 设设xij为指派人员为指派人员i去做工作去做工作j（i，j1,2,3,4)1,2,3,4) 1 11 21 31 4 2 12 22 32 4 3 13 23 33 4 4 14 24 34 4 1 11 21 31 4 2 12 2 M in z 3 51 44 11 42 71 44 01 4 4 71 24

52、 51 23 21 25 11 2 3 91 35 61 33 61 34 31 3 3 21 55 11 52 51 54 61 5 1 s .t. xxxx xxxx xxxx xxxx xxxx xx （ 小 张 要 完 成 一 项 工 作 ） 2 32 4 3 13 23 33 4 4 14 24 34 4 1 12 13 14 1 1 22 23 24 2 1 32 33 34 3 1 42 43 44 4 D 1 1 1 1 1 1 1 xx xxxx xxxx xxxx xxxx xxxx xxxx （ 小 王 要 完 成 一 项 工 作 ） （ 小 李 要 完 成 一 项 工

53、作 ） （ 小 刘 要 完 成 一 项 工 作 ） （ 工 作 A 要 有 1 人 完 成 ） （ 工 作 B 要 有 1 人 完 成 ） （ 工 作 C 要 有 1 人 完 成 ） （ 工 作要 有 1 人 0 ( ,1, 2 , 3 , 4 ) ij xij 完 成 ） （ 非 负 ） 第第4章章 运输问题运输问题 和指派问题和指派问题 4.5 4.5 指派问题指派问题 电子表格模型电子表格模型 第第4章章 运输问题运输问题 和指派问题和指派问题 4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模 经常会遇到指派问题的经常会遇到指派问题的变形变形，之所以称它们为变形，之所以称它们

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

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

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

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

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

59、求量的转换问题供应量和需求量的转换问题：三个工厂生产：三个工厂生产 四种产品，但一种产品只能在一个工厂生产，根四种产品，但一种产品只能在一个工厂生产，根 据生产能力，工厂据生产能力，工厂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）”, , 为人多事少为人多事少 的指派问题的指派问题。 第第4章章 运输问题运

60、输问题 和指派问题和指派问题 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 4 2 12 22 4 3 13 23 33 4 1 11 21 31 4 2 12 22 32 4 3 13 23 33 4 1 M in z4 12 02 73 02 83 02 44 0 4 02 02 93 0 2 34 0 3 72 03 03 02 73 02 14 0 2 (1 ) 2 (2 ) 1 (3 ) s .t. xx