IE10_OR11 CH3 运输问题3

1、第1页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 第二章习题讲解第二章习题讲解 3.4 3.4 应用举例应用举例CH4 CH4 整数规划整数规划|4.14.1整数规划问题的数学模型及解的特点整数规划问题的数学模型及解的特点|4.2 4.2 分支定界法分支定界法|4.3 0-14.3 0-1整数规划整数规划|4.4 4.4 指派问题指派问题|4.5 4.5 应用举例应用举例第2页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学 例例 设有三个化肥厂供应

2、四个地区的农用化肥。设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。假定等量的化肥在这些地区使用效果相同。 各化各化肥厂年产量，各地区年需要量及从各化肥厂到各地肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表所示。试求出总运费最区运送单位化肥的运价如表所示。试求出总运费最节省的化肥调拨方案。节省的化肥调拨方案。 运价：万元运价：万元/ /万吨万吨 需地区需地区 化肥厂化肥厂产量产量( (万吨万吨) )A AB BC C16161414191913131313202022221919232317171515- -505060605050最低需最低需

3、求求( (吨吨) )最高需最高需求求( (吨吨) )30305050707070700 030301010不限不限 第3页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学解解 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分：如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为

4、M（任意大正数），而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3-18）和单位运价表（表3-19）。第4页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学表表 3-183-18 销地 产地I 产量ABCD 50605050销 量3020703010 50 表表 3-193-19 销地 产地 ABCD161419M1614190131320M22192301715MM1715M0第5页西南

5、科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学用表上作业法求得这个问题的最优方案如表3-20所示。 表表3-203-20 销地 产地 产量ABCD 30 2050200 30 10 30 2050605050销 量3020703010 50 第6页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学例例 某厂按合同规定须于当年每个季度末分别某厂按合同规定须于当年每个季度末分别提供提供1010，1515，2525，2020台同一规格的柴油机。已知台同一规格的柴油机

6、。已知该厂各季度的生产能力及生产每台柴油机的成该厂各季度的生产能力及生产每台柴油机的成本如表本如表3-213-21所示。如果生产出来的柴油机当季不所示。如果生产出来的柴油机当季不交货的，每台每积压在一个季度需储存、维护交货的，每台每积压在一个季度需储存、维护等费用等费用0.150.15万元。要求在完成合同的情况下，做万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最出使该厂全年生产（包括储存、维护）费用最小的决策。小的决策。第7页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学季度生产能力（台）2535

7、301010.811.111.011.3表表3-213-21单位成本（万元）解解 由于每个季度生产出的柴油机不一定当季交货,所以设 为第 季度生产的用于第 季度交货的柴油机数。根据合同要求，必须满足： ijxij2025151044342414332313221211xxxxxxxxxx第8页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学每季度生产的用于当季和以后各季交货的柴油机数不能超过该季度的生产能力，即: 第 季度生产的用于 季度交货的每台柴油机的实际成本 应该是该季度单位成本加上储存、维护等费用。 的具体数值见表3

8、-22。1030352544343324232214131211xxxxxxxxxxijijcijc表表3-223-22ji 10.8 10.9511.1011.1011.2511.00 11.2511.4011.1511.30第9页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学设用 表示该厂第 季度的生产能力， 表示第 季度的第季度的合同供应量，则问题可写成：ijaijbj 4141minijijijxcz4 , 3 , 2 , 1,04 , 3 , 2 , 14 , 3 , 2 , 1. .4141jixjbxiaxt

9、sijijijjiij应注意，在该问题中，当 时应使 。为了实现这一要求，在上面模型中，应令对应的 ， 为一个充分大的正数。此外，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，其产销平衡表和单位运价表（合在一起）见表3-23。ji 0ijxMcijM第10页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学表表3-233-23 销地产地D产量000025353010销 量1015252030 11.2511.4011.1511.3011.1011.2511.00M10.9511.10M M 10.8MM M

10、第11页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学在原运输问题上增加若干转运站。运输方式有：产地在原运输问题上增加若干转运站。运输方式有：产地转运站、转转运站、转运站运站销地、产地销地、产地产地、产地产地、产地销地、销地销地、销地转运站、销地转运站、销地产产地等地等。例例1、腾飞电子仪器公司在大连和广州腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂有两个分厂生产同一种仪器，大连分厂每月生产每月生产400台，广州分厂每月生产台，广州分厂每月生产600台。该公司在上海和天津有两个销售公台。该公司在上海和天津

11、有两个销售公司负责对南京、济南、南昌、青岛四个司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，供货，运输费用如图，单位是百元。问应该如何调运仪器，可使总运输费用最低？可使总运输费用最低？图中图中1-广州、广州、2-大连、大连、3-上海、上海、4-天津、天津、5-南京、南京、6-济南、济南、7-南昌、南昌、8-青岛青岛第12页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强

12、石宇强运筹学运筹学解：解：设设xij为从为从i到到j的运输量，可得到有下列特点的线性规划模型：的运输量，可得到有下列特点的线性规划模型：目标函数：目标函数：Min f = Min f = 所有可能的运输费用（运输单价与运输量乘积之和）所有可能的运输费用（运输单价与运输量乘积之和）约束条件：约束条件： 对产地（发点）对产地（发点） i i ：输出量：输出量 - - 输入量输入量 = = 产量产量 对转运站（中转点）：输入量对转运站（中转点）：输入量 - - 输出量输出量 = 0= 0 对销地（收点）对销地（收点） j j ：输入量：输入量 - - 输出量输出量 = = 销量销量目标函数：目标函数

13、： Min f = 2Min f = 2x x1313+ 3+ 3x x1414+ 3+ 3x x2323+ + x x2424+ 4+ 4x x28 28 + 2+ 2x x3535+ 6+ 6x x3636+ 3+ 3x x3737+ 6+ 6x x3838+ + 4 4x x4545+ 4+ 4x x4646+ 6+ 6x x4747+ 5+ 5x x4848 约束条件：约束条件：s.t. s.t. x x1313+ + x x1414 600 ( 600 (广州分厂供应量限制）广州分厂供应量限制） x x2323+ + x x2424+ + x x2828 400 ( 400 (大连分

14、厂供应量限制）大连分厂供应量限制） - -x x1313- - x x2323 + + x x3535 + + x x3636+ + x x3737 + + x x3838 = 0 = 0 （上海销售公司，转运站）（上海销售公司，转运站） - -x x1414- - x x2424 + + x x4545 + + x x4646+ + x x4747 + + x x4848 = 0 = 0 （天津销售公司，转运站）（天津销售公司，转运站） x x3535+ + x x4545 = 200 = 200 （南京的销量）（南京的销量） x x3636+ + x x4646 = 150 = 150 （

15、济南的销量）（济南的销量） x x3737+ + x x4747 = 350 = 350 （南昌的销量）（南昌的销量） x x3838+ + x x4848 + + x x2828 = 300 = 300 （青岛的销量）（青岛的销量） x xijij 0 , i,j = 1,2,3,4,5,6,7,8 0 , i,j = 1,2,3,4,5,6,7,8图中图中 1- 1- 广州、广州、2 - 2 - 大连、大连、3 - 3 - 上海、上海、4 - 4 - 天津、天津、5 - 5 - 南京、南京、6 - 6 - 济南、济南、7 - 7 - 南昌、南昌、8 - 8 - 青岛青岛第13页西南科技大学

16、制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学求得结果： x13 = 550 x14 =50 ； x23 = 0 x24 = 100 x28 = 300 ； x35 = 200 x36 = 0 x37 = 350 x38 = 0 ； x45 = 0 x46 = 150 x47 = 0 x48 = 0 。最小运输费用为：4600百元第14页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学例例2、某公司有、某公司有A1、A2、A3三个分厂生产某种物资，分别供三个分厂生产

17、某种物资，分别供应应B1、B2、B3、B4四个地区的销售公司销售。假设质量四个地区的销售公司销售。假设质量相同，有关数据如下表：相同，有关数据如下表：试求总费用为最少的调运方案。试求总费用为最少的调运方案。假设：假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；个产地集中一起运；2.运往各销地的物资可以先运给其中几个销地，再转运给运往各销地的物资可以先运给其中几个销地，再转运给其他销地；其他销地；3.除产销地之外，还有几个中转站，在产地之间、销地之除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。

18、间或在产地与销地之间转运。B1B2B3B4产量A13113107A219284A3741059销量3656和=20运价如下表：解：解：把此转运问题转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20； Bi： 产量为 20， 销量为 20 +原销量，其中20为各点可能变化的最大流量； 4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21

19、-35-21928A33-1-2374105T12311322846T215-1114527T34-23121824T43232121-2621194858-121B332104222423B410856746213 扩大的运输问题产销平衡与运价表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1

20、 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 26 25 26 240 第17页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学4.1 4.1

21、整数规划问题的数学模型及解的特点整数规划问题的数学模型及解的特点max(min)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(. .22112222212111212111中部分或全部取整数nxxx,11例例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： 195 x1 + 273 x2

22、 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 为整数。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140 第19页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学全整数线性规划全整数线性规划混合整数线性规划混合整数线性规划0-10-1整数线性规划整数线性规划第20页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学当放弃整数约束时得到的线性规当放弃整数约束时得到的线性规划称为整

23、数规划的划称为整数规划的松弛问题松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。第21页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学4.2 4.2 分支定界法分支定界法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：iibx 1 iiiibxbx和加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个

24、界限解，则它的目标函数值就构成一个界限例例1 1取整数2121212121, 0,3121451149x . .xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S得：得：941 310,23 :21zxxA29/6132X254X1 231)310,23(AS2对对S分枝：分枝：构造约束：构造约束：21x和和11x形成分枝问题形成分枝问题S1和和S2，得解，得解B和和CS1)37, 1 (C)923, 2(B941923);(2, :zB31037);(1, :zCSA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:

25、x1=2,x2=23/9Z=41/911x21x132X254X1 231)310,23(AS2对对S1分枝：分枝：构造约束：构造约束：32x和和22x形成分枝问题形成分枝问题S11和和S12，得解，得解DS12)2 ,(1433D14611433);,2( :zDS11无可行解无可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21x132X254X1 231)310,23(AS2对对S12分枝：分枝：构造约束：构造

26、约束：31x和和21x形成分枝问题形成分枝问题S121和和S122，得解，得解E和和FS121) 1 , 3(E4);(3,1 :zES122)2 , 2(F4);(2,2 :zFSA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21x0 1 2 3 44 3 2 1x1x20 1 2 3 44 3 2 1x1x2X12X2 2X11X23P

27、1:(1,9/4)Z=43/4P4:(0,3)Z=9P2:(2,1/2)Z=19/2P3:(1,2)Z=10P:(6/5,21/10)Z=111/10第37页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学4.3 0-14.3 0-1整数规划整数规划变量只能取变量只能取0 0或或1 1的整数线性规划的整数线性规划第38页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学资金需求资金需求(1000$)项项 目目估计现值估计现值第一年第一年 第二年第二年 第三年

28、第三年 第四年第四年工厂扩建工厂扩建9015202015销售网点扩建销售网点扩建401015205新生产流水线新生产流水线1010004新产品研究新产品研究3715101010可用资金可用资金40504035 第39页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学模型模型变量假设变量假设:项目没有选中如果第选中目项第果如iixi 0 1max z= 90 x1+40 x2+10 x3+37x4s.t.15x1+10 x2+10 x3+15x44020 x1+15x2 + 10 x45020 x1+20 x2+ 10 x44

29、015x1+5x2+4x3+10 x435x1, x2, x3, x4, =0,1模型模型:第40页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第41页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第42页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第43页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第4

30、4页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学第45页西南科技大学制造科学与工程学院工业工程与设计系西南科技大学制造科学与工程学院工业工程与设计系 石宇强石宇强运筹学运筹学生产厂生产厂顾客需求顾客需求销售点销售点45DCBA7IIIII213I工厂工厂- -销售点配置问题销售点配置问题- -问题描述问题描述IIIIII生产能力生产能力1 18008001,0001,0001,2001,20030030035,00035,0002 240040050050070070020020045,00045,0003 380080060060050050030030040,00040,0004 450050060060070070020020042,000