运输问题和指派问题课件.ppt

1、第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院3.3 3.3 网络配送问题网络配送问题，称之为网络配送问题。，称之为网络配送问题。u在网络配送问题中，必须确定需求以及相在网络配送问题中，必须确定需求以及相应地确定需求的约束条件。应地确定需求的约束条件。的形式如下：的形式如下：第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院3.3 3.3 网络配送问题网络配送问题C2F2C1F1C3700元/个900元/个800元/个800元/个900元/个700元/个10个8个9个12个15个第第4章章 运输

2、问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院实用运筹学实用运筹学运用运用ExcelExcel建模和求解建模和求解第第4 4章章运输问题和指派问题运输问题和指派问题第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院本章内容要点本章内容要点运输问题运输问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用指派问题指派问题的基本概念及其的基本概念及其各种变形的建模与应用各种变形的建模与应用第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院本章节内容本

3、章节内容4.1 4.1 运输问题基本概念运输问题基本概念4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模4.4 4.4 运输问题应用举例运输问题应用举例4.5 4.5 指派问题指派问题4.6 4.6 各种指派问题变形的建模各种指派问题变形的建模第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院本章主要内容框架图本章主要内容框架图产销平衡（总产量等于总销量）产大于销（总产量大于总销量）销大于产（总产量小于总销量）运输问题数学模型和电子表格模型运输问题和指派问题各

4、种变形的建模应用举例平衡指派问题（总人数等于总任务数）指派问题数学模型和电子表格模型各种变形的建模第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.1 4.1 运输问题基本概念运输问题基本概念运输问题最初起源于人们在日常生活中把某些运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方物品或人们自身从一些地方转移到另一些地方，要求所采用的，要求所采用的运输路线运输路线或或运输方案是最经济运输方案是最经济或成本最低或成本最低的，这就成为了一个运筹学问题。的，这就成为了一个运筹学问题。随着经济的不断发展，现代随着经济的不

5、断发展，现代物流业物流业蓬勃发展，蓬勃发展，如何充分利用时间、信息、仓储、配送和联运如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的体系创造更多的价值，向运筹学提出了更高的挑战。挑战。要求科学地组织货源、运输和配送使得运输问要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其基本思想仍然是题变得日益复杂，但是其基本思想仍然是实现实现现有资源的最优化配置现有资源的最优化配置。第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.1 4.1 运输问题基本概念运输问题基本概念一般的运输问题就是解决如何把某种产品

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

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

8、输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.1 4.1 运输问题基本概念运输问题基本概念u例例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吨；从各工厂到各销售点吨；从各工厂到各销售点的单位产品运价如表的单位产品运

9、价如表4-14-1所示。问该公司应如何调运这所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费些产品，在满足各销售点的需要量的前提下，使总运费最少？最少？表表4-1 4-1 各工厂到各销售点的单位产品运价（元各工厂到各销售点的单位产品运价（元/吨）吨）B1B1B2B2B3B3B4B4产量（吨）产量（吨）A1A13 311113 310107 7A2A21 19 92 28 84 4A3A37 74 410105 59 9销量（吨）销量（吨）3 36 65 56 6第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院B2A2B

10、1A1B3806585A3B475125100704.1 4.1 运输问题基本概念运输问题基本概念第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型 销售点销售点销售点销售点加工厂加工厂A1A2AmB1 B2 Bn产量产量 a1a2am销量销量 b1 b2 bnc11 c12 c1nc21 c22 c2n cij cm1 cm2 cmn第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表

11、格模型运输问题数学模型和电子表格模型（1 1）产销平衡产销平衡运输问题的数学模型运输问题的数学模型 1111()()M in (1,2,)s.t.(1,2,)0 (1,2,;1,2,)mnijijijnijijmijjiijzc xxaimxbjnximjn 产 量 约 束销 量 约 束 LLLL11mnijijab第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型对于例对于例4.14.1，其数学模型如下：，其数学模型如下：首先，三个产地首先，三个产地A1A1、A2A2、

12、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）目标函数）目标函数 本问题的目标是使得总运输费最小本问题的目标是使得总运输费最小111213142122232431323334Min

13、 z311 310 9 2 8 7410 5xxxxxxxxxxxx第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（3 3）约束条件）约束条件满足产地产量满足产地产量（3 3个产地的个产地的产品都要全部产品都要全部配送出去）配送出去）满足销地销量满足销地销量（4 4个销地的个销地的产品都要全部产品都要全部得到满足）得到满足）非负非负111213142122232431323334111213142122232431323334112131122232Min z311

14、310 9 2 8 7 410 57 4 9 3 s.t.6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1323331424345 6 0(1,2,3;1,2,3,4)ijxxxxxxxij第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u运输问题是一种特殊的线性规划问题，一般采用运输问题是一种特殊的线性规划问题，一般采用“表上作表上作业法业法”求解运输问题，但求解运输问题，但ExcelExcel的的“规划求解规划求解”还是采用还是采用“单纯形法单纯形

15、法”来求解。来求解。u例例4.14.1的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型u 需要注意的是：运输问题有这样一个性质需要注意的是：运输问题有这样一个性质（整数解性质整数解性质），只要它的），只要它的供应量供应量和和需求需求量量都是都是整数整数，任何有可行解的运输问题必，任何有可行解的运输问题必然有所有决策变量都是然有所有决策变量都是整数的最优解整数的最优解。因。因此，没有必要加上所有变量都是整数的约此，没有必要加上所有变量都是整数的

16、约束条件。束条件。u 由于运输量经常以卡车、集装箱等为单位由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满的话，就很不经济了，如果卡车不能装满的话，就很不经济了。整数解性质就避免了运输量（运输方案。整数解性质就避免了运输量（运输方案）为小数的麻烦。）为小数的麻烦。第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（2 2）产大于销（供过于求）产大于销（供过于求）运输问题运输问题的数学模型的数学模型（以满足小的销量为准以满足小的销量为准）1111()()Min z (

17、1,2,)s.t.(1,2,)0 (1,2,;1,2,)mniji jijnijijmijjiijc xxaimxbjnxim jn产量约束销量约束LLLL11mnijijab第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型（3 3）销大于产（供不应求）销大于产（供不应求）运输问题运输问题的数学模型的数学模型（以满足小的产量为准以满足小的产量为准）1111()()Min (1,2,)s.t.(1,2,)0 (1,2,;1,2,)mniji jijnijijmijjiij

18、zc xxaimxbjnxim jn产量约束销量约束LLLL11mnijijab第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.2 4.2 某厂按合同规定须于当年每个季度末分别提某厂按合同规定须于当年每个季度末分别提供供1010，1515，2525，2020台同一规格的柴油机。已知该厂台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表各季度的生产能力及生产每台柴油机的成本如表4 44 4所示。如果生产出来的柴油机当季不交货的，每台所示。如果生

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

20、311.3第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院例例3.73.7 某公司根据订单进行生产。已知半年内对某产品某公司根据订单进行生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用的需求量、单位生产费用和单位存储费用,还已知公还已知公司司每月的生产能力为每月的生产能力为100100，每月仓库容量为每月仓库容量为5050。问：。问：如何确定产品未来半年内每月最佳生产量和存储量，如何确定产品未来半年内每月最佳生产量和存储量，以使总费用最少。以使总费用最少。表表3-10 3-10 生产与库存的有关数据生产与库存的有关数据月份月份1 1

21、2 23 34 45 56 6需求量需求量505040405050454555553030单位生产费用单位生产费用825825775775850850850850775775825825单位存储费用单位存储费用4040303035352020404040404.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院解：解：(1)(1)决策变量决策变量 设每月生产量为设每月生产量为xi(i=1,2,=1,2,6,6)，每月月末库，每月月末库存量为存量为si(i=1,2,(i=1,2

22、,6,6)。上月库存量（上月库存量（si-1）本月生产量（）本月生产量（xi）-市场需求市场需求本月月末库存量（本月月末库存量（si）4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院数学模型数学模型（线性规划模型）（线性规划模型）12345612345611122233344455566M in z825775850850775825 40 30 35 20 40 4050405045s.t.5530100 (1,2,6)50 (1,2iixxxxxxssssssxss

23、xssxssxssxssxsxisiL,6),0 (1,2,6)iix siLL4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院例例3.73.7的电子表格模型的电子表格模型4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型解：解：这是一个这是一个生产与储存（库存）问题生产与

24、储存（库存）问题，除了采用第，除了采用第3 3章的方法外，还可以转化为章的方法外，还可以转化为运输问题运输问题来做。来做。由于每个季度生产出来的柴油机不一定当季交货，由于每个季度生产出来的柴油机不一定当季交货，所以设所以设xij为第为第i季度生产的第季度生产的第j季度交货的柴油机数季度交货的柴油机数。则第则第i季度生产的第季度生产的第j季度交货的每台柴油机的实际成季度交货的每台柴油机的实际成本本cij为：为：把第把第i季度生产的柴油机数看作第季度生产的柴油机数看作第i个生产厂商的个生产厂商的产量；把第产量；把第j季度交货的柴油机数看作第季度交货的柴油机数看作第j个销售点的个销售点的销量；生产成

25、本加储存、维护等费用看作运费。将生销量；生产成本加储存、维护等费用看作运费。将生产与储存问题转化为运输问题，相关数据见表产与储存问题转化为运输问题，相关数据见表4 45 5。第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型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.153

26、0304 411.3011.301010需求量需求量1010151525252020 由表由表4 45 5可知，总产量（生产能力）为可知，总产量（生产能力）为25+35+30+10=10025+35+30+10=100，总，总销量（需求量）为销量（需求量）为10+15+25+20=7010+15+25+20=70，因此是，因此是产大于销产大于销的运输问题的运输问题季度季度生产能力（台）生产能力（台）需求量（台）需求量（台）单位成本（万元）单位成本（万元）1 12525101010.810.82 23535151511.111.13 33030252511.011.04 41010202011.

27、311.3第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.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 xxxxxxxxxx

28、xxxxxxx14243444 25200 (,1,2,3,4;)ijxxxxxijij第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.24.2的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表格模型运输问题数学模型和电子表格模型例例4.34.3 某公司从两个产地某公司从两个产地A1A1、A2A2将物品运往将物品运往三个销地三个销地 B1B1、B2

29、B2、B3B3，各产地的产量、各销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运地的销量和各产地运往各销地每件物品的运费如表费如表4 46 6所示。问应如何调运，可使得总所示。问应如何调运，可使得总运输费最小？运输费最小？表表4 46 6 例例4.34.3的运输费用表的运输费用表 B1B1B2B2B3B3产量产量A1A11313151512127878A2A21111292922224545销量销量535336366565（销大于产）（销大于产）第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.2 4.2 运输问题数学模型和电子表

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

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

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

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

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

35、定的是在哪个工厂生产哪种所示）。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小产品，可使总成本最小?表表4 47 7 产品生产的有关数据产品生产的有关数据单位成本（元）单位成本（元）生产能力生产能力产品产品1 1产品产品2 2产品产品3 3产品产品4 4工厂工厂1 141412727282824247575工厂工厂2 24040292923237575工厂工厂3 337373030272721214545需求量需求量2020303030304040第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.3 4.3 各种变形的运输问题建模各种

36、变形的运输问题建模解：解：指定工厂生产产品指定工厂生产产品可以看作运输问题来求可以看作运输问题来求解。本题中，工厂解。本题中，工厂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 402

37、9 23 3730272120 (1)30 (2)30 (3)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章章 运输问题运输问题 和指派

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

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

40、顾客3 3顾客顾客4 4工厂工厂1 1555542424646535380008000工厂工厂2 2373718183232484850005000工厂工厂3 3292959595151353570007000最小采购量最小采购量7000700030003000200020000 0最大采购量最大采购量70007000900090006000600080008000第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模解：解：该问题要求满足不该问题要求满足不同顾客的需求（采购量同顾客的需求（

41、采购量），解决办法：），解决办法：实际供给量实际供给量 最小采购量最小采购量实际供给量实际供给量 最大采购量最大采购量 目标是目标是利润最大利润最大，而，而不是成本最小。不是成本最小。其数学模型如下：其数学模型如下：设设xij为工厂为工厂i供应给顾供应给顾客客j的产品数量的产品数量111213142122232431323334111213142122232431323334Max z55424653 37183248 295951358000 (1)5000 (2)7000 (3)s.t.xxxxxxxxxxxxxxxxxxxxxxxxx工厂工厂工厂112131122232132333142

42、4347000 (1)30009000 (2)20006000 (3)8000 (4)0(1,2,3;1,2,3,4)ijxxxxxxxxxxxxij顾客顾客顾客顾客第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.3 4.3 各种运输问题变形的建模各种运输问题变形的建模例例4.54.5的电子表格模型的电子表格模型第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.4 4.4 运输问题应用举例运输问题应用举例例例4.64.6 某厂生产设备是某厂生产设备是以销定产以销定产的。已知的。已知1 16

43、 6月份各月的生产能力、月份各月的生产能力、合同销量和单台设备平均生产费用，如表合同销量和单台设备平均生产费用，如表4 49 9所示。所示。已知上年末库存已知上年末库存103103台。如果当月生产出来的设备当月不交货，则台。如果当月生产出来的设备当月不交货，则需要运到分厂库房，每台需要运到分厂库房，每台增加运输成本增加运输成本0.10.1万元万元，每台设备，每台设备每月每月的平均的平均仓储费、维护费为仓储费、维护费为0.20.2万元万元。7 78 8月份为销售淡季，全厂停产月份为销售淡季，全厂停产1 1个月，个月，因此在因此在6 6月份完成销售合同后还要月份完成销售合同后还要留出库存留出库存8

44、080台。台。加班生产设备每台增加班生产设备每台增加成本加成本1 1万元。问应如何安排万元。问应如何安排1 16 6月份的生产，使总的生产（包括运输月份的生产，使总的生产（包括运输、仓储、维护）费用最少？、仓储、维护）费用最少？月份月份正常生产能力正常生产能力（台）（台）加班生产能力加班生产能力（台）（台）合同销量合同销量（台）（台）单台费用单台费用（万元）（万元）1 1月月6060101010410415152 2月月50501010757514143 3月月9090202011511513.513.54 4月月100100404016016013135 5月月100100404010310

45、313136 6月月80804040707013.513.5第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.4 4.4 运输问题应用举例运输问题应用举例解：解：这是一个生产与储存问题，但可以转化为运这是一个生产与储存问题，但可以转化为运输问题来做。输问题来做。（是否可以采用第（是否可以采用第3 3章的方法做？同学们可以试章的方法做？同学们可以试试，然后进行比较）试，然后进行比较）生产方案不变，但总费用为：生产方案不变，但总费用为：8329.78329.7万元万元u根据已知条件可以列出生产能力（正常生产能根据已知条件可以列出生产能力（正常生产

46、能力和加班生产能力）和销量以及运价表（力和加班生产能力）和销量以及运价表（P120P120）u数学模型数学模型P120P120121121u电子表格模型电子表格模型P122P122u求解结果求解结果P123P123第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.4 4.4 运输问题应用举例运输问题应用举例例例4.74.7 华中金刚石锯片厂有华中金刚石锯片厂有两条生产线两条生产线，分别生产，分别生产直径直径900-1800mm900-1800mm大锯片大锯片基体基体2000020000片，直径片，直径350-350-800mm800mm中小锯

47、片中小锯片基体基体4000040000片。公司在全国有片。公司在全国有2525个销个销售网点，售网点，主要销售区域主要销售区域集中在福建、广东、广西、集中在福建、广东、广西、四川、山东四川、山东5 5个个石材主产区。为完成总厂的要求，石材主产区。为完成总厂的要求，公司决定一方面拿出公司决定一方面拿出10%10%的产量稳定与前期各个客的产量稳定与前期各个客户的联系以保证将来的市场区域份额，另一方面，户的联系以保证将来的市场区域份额，另一方面，面临如何将剩余的面临如何将剩余的90%90%的产量合理分配给的产量合理分配给五个石材五个石材主产区和其他省区主产区和其他省区，以获取最大的利润。各个销售，以

48、获取最大的利润。各个销售区的最低需求、销售固定费用、每片平均运费、每区的最低需求、销售固定费用、每片平均运费、每片从总厂库房的购进价与当地的销售价差贡献等自片从总厂库房的购进价与当地的销售价差贡献等自然情况见表然情况见表4 41212。问应如何分配给各个销售区，。问应如何分配给各个销售区，才能使得总利润为最大？才能使得总利润为最大？第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.4 4.4 运输问题应用举例运输问题应用举例解：解：该问题数据较多，但是经过分该问题数据较多，但是经过分析，其产量在最低需求和最高需求析，其产量在最低需求和最高需求

49、之间，并且目标函数是最大利润，之间，并且目标函数是最大利润，可以化简为表可以化简为表4 41313（124124）u数学模型数学模型P124P124u电子表格模型电子表格模型P125P125u求解结果求解结果P126P126第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院4.4 4.4 运输问题应用举例运输问题应用举例转运问题转运问题 （转运问题）小麦收割于榆树和昌图，然后运往大连、营口和锦州，再运往海口、广州以及珠海的面粉加工厂。每地收获300吨，海口、广州以及珠海的需求量分别是200、100和300.运费如表，求最小运输成本的运输量。大连营

50、口锦州榆树161012昌图151417大连营口锦州大连海口6746广州81158珠海10111210第第4章章 运输问题运输问题 和指派问题和指派问题东北财经大学工商管理学院东北财经大学工商管理学院u例例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吨；从各