运筹学__五章(整数规划).ppt_第1页
运筹学__五章(整数规划).ppt_第2页
运筹学__五章(整数规划).ppt_第3页
运筹学__五章(整数规划).ppt_第4页
运筹学__五章(整数规划).ppt_第5页
已阅读5页,还剩32页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、运筹学,管理科学与工程系 经济与管理学院,2020/8/9,浙江科技学院经济管理学院管工系,2,第五章 整数规划,5.1 整数规划数学模型和解的特点 5.2 割平面法和分支定界法 5.3 0-1整数规划 5.4 隐枚举法 5.5 匈牙利法,2020/8/9,浙江科技学院经济管理学院管工系,3,本章学习要求,熟悉分支定界法和割平面法的原理及其应用 掌握求解0-1规划问题的隐枚举法 掌握求解指派问题的匈牙利法,2020/8/9,浙江科技学院经济管理学院管工系,4,5.1整数规划数学模型和解的特点,整数规划的类型 整数规划的数学模型实例 整数规划解的特点,2020/8/9,浙江科技学院经济管理学院管

2、工系,5,1.整数线性规划(ILP)的类型,纯ILP: Xj全为整数 混合ILP:部分Xj为整数 0-1 ILP:Xj为0或1,2020/8/9,浙江科技学院经济管理学院管工系,6,线性规划模型 max z=x1+4x2 s.t. 14x1+42x2196 -x1+ 2x2 5 x1, x20,整数规划模型 max z=x1+4x2 s.t. 14x1+42x2196 -x1+ 2x2 5 x1, x20 x1,x2 为整数,2.整数线性规划(ILP)实例,2020/8/9,浙江科技学院经济管理学院管工系,7,线性规划的最优解A(x1, x2)=(2.6, 3.8)不是整数解,目标函数值为z=

3、17.8。整数规划的最优解B(x1, x2)=(5,3)目标函数值为z=17。线性规划最优解A(2.6, 3.8)四舍五入得到的解为(3,4),不是可行解;舍去尾数取整的解为(2,3),目标函数值z=14。 因此整数规划的最优解一般不能由线性规划的最优解通过简单的取整得到。,2020/8/9,浙江科技学院经济管理学院管工系,8,3.整数线性规划(ILP)解的特点,ILP是其中LP的一个子问题,所有解也是LP的可行解,所以如果LP的最优解满足ILP的整数条件,则已得最优解。,2020/8/9,浙江科技学院经济管理学院管工系,9,5.2 割平面法和分支定界法,割平面法(Gomory法) 分支定界法

4、,2020/8/9,浙江科技学院经济管理学院管工系,10,1.割平面法,基本原理: 根据单纯形法求得其松弛问题的最优解,若不满足整数条件,则由最优解中选取具有最大真分数部分的非整分量所在行构造割平面约束,将其加入原松弛问题中形成一个新的线性规划求解,逐渐缩小解的范围,又不去掉整数解,直至找到最优解为整数解结束。,2020/8/9,浙江科技学院经济管理学院管工系,11,1.割平面法,割平面束构造: 设具有最大真分数部分的非整分量所在行为:,将该约束方程所在系数和常数分解为整数N和正真分数f之和,即:,则该约束方程等价于:,2020/8/9,浙江科技学院经济管理学院管工系,12,1.割平面法,例:

5、,j,1,1,0,0, , ,3,5,x1入 x3出, , ,6,8/3,x2入 x4出,由右边结果构造割平面束,2020/8/9,浙江科技学院经济管理学院管工系,13,例(接上):,由上面结果构造割平面束,2020/8/9,浙江科技学院经济管理学院管工系,14,2. 分支定界法,原理: 首先,不考虑变量的整数约束,求解松弛问题线性规划的最优解。如果线性规划的最优解恰好是整数解,则这个解就是整数规划的最优解。 如果线性规划的最优解中至少有一个变量不是整数,把线性规划的可行域切割成两部分,分别求解两个线性规划的最优解。 如果这两个线性规划的最优解还不是整数解,分别把每一个可行域再进行分割。这个过

6、程,叫做“分支”。 分支过程得到的整数解中,目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解,如果目标函数值劣于或等于这个“界”,就停止继续分支。这个过程,叫做“定界”。,2020/8/9,浙江科技学院经济管理学院管工系,15,步骤: 解整数规划问题(ILP)的松弛问题,结果可能有三种: 松弛问题没有可行解,ILP也没有可行解,停止计算。 松弛问题有最优解,并符合ILP的整数条件,则此最优解即为ILP的最优解,停止计算。 松弛问题有最优解,但不符合ILP的整数条件,记它的目标函数值为 ; 用观察法找问题ILP的一个整数可行解,求得其目标函数值,并记作 ,以

7、Z*表示ILP的最优目标函数值,则 分支,如松弛问题有一个最优解xj为非整数值bj,则可以构造两个分支。 xjbj xjbj+1 定界,以每个后继问题为一分支表明求解的结果。,2020/8/9,浙江科技学院经济管理学院管工系,16,(11/4,9/4),Z=31/4,(3,3/2),Z=15/2,(2,2),Z=6,无解,无解,例:,(11/4,9/4),x12,x13,(2,2),(3,3/2),x21,x22,(19/6,1),Z=22/3,(3,1),Z=7,(19/6,1),x13,x14,2020/8/9,浙江科技学院经济管理学院管工系,17,5.3 0-1整数规划,背包问题 厂址选

8、择问题 多决策问题 固定费用问题,2020/8/9,浙江科技学院经济管理学院管工系,18,1.背包问题,一只背包最大装载重量为50公斤。现有三种物品,每种物品数量无限。每种物品每件的重量、价格如下表:,求背包中装入每种物品各多少件,使背包中物品总价值最高。,2020/8/9,浙江科技学院经济管理学院管工系,19,设三种物品的件数各为x1,x2,x3件,总价值为z。 max z=17x1+72x2+35x3 s.t. 10 x1+41x2+20 x350 x1,x2,x30 x1,x2,x3为整数 这是一个整数规划问题(Integer Programming)。这个问题的最优解为: x1=1件,

9、x2=0件,x3=2件,最高价值z=87元,2020/8/9,浙江科技学院经济管理学院管工系,20,2.厂址选择模型,在5个备选地点中选择3处建设生产同一产品的工厂,每个地点建厂所需投资,占用农田,建成以后的生产能力如下。总投资不超过800万元,占有农田不超过60亩。如何选择厂址,使总生产能力最大。,设5个01变量x1,x2,x3,x4,x5,,2020/8/9,浙江科技学院经济管理学院管工系,21,max z=70 x1+55x2+42x3+28x4+11x5 s.t. 320 x1+280 x2+240 x3+210 x4+180 x5800 20 x1+ 18x2+ 15x3+ 11x4

10、+ 8x5 60 x1+ x2+ x3+ x4+ x5= 3 x1,x2,x3,x4,x5 为 01变量,这个01规划问题的最优解为: x1=1,x2=0,x3=1,x4=1,x5=0,max z=140 即在地点1、3和4建3个厂,总生产能力最大,可以达到140万吨。,2020/8/9,浙江科技学院经济管理学院管工系,22,3.多决策问题,一个工厂用3种设备生产5种产品,三种设备的能力(小时),生产每种产品需要占有的各种设备的能力(小时/件)以及5种产品的利润(元/件)如下:,求使总利润最大的生产计划。,2020/8/9,浙江科技学院经济管理学院管工系,23,max z=24x1+18x2+

11、21x3+17x4+22x5 s.t. 5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x1,x2,x3,x4,x50 x1,x2,x3,x4,x5为整数,设五种产品产量之间有以下逻辑关系: 五种产品中,安排生产的产品不能超过3种 每一种产品如果安排生产,最小批量为50件 如果产品1安排生产,产品2就不能生产 如果产品4生产,产品5必须生产,而且至少生产50件 设5个01变量y1,y2,y3,y4,y5,2020/8/9,浙

12、江科技学院经济管理学院管工系,24,max z=24x1+18x2+21x3+17x4+22x5 s.t. 5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x110000y1 x210000y2 x310000y3 x410000y4 x510000y5 y1+y2+y3+y4+y5 3 50y1x1 50y2x2 50y3x3 50y4x4 50y5x5 y1+y21 y4y5 x1,x2,x3,x4,x50 x1,x2,

13、x3,x4,x5为整数 y1,y2,y3,y4,y5为01变量,五种产品只生产3三种,最小批量为50件,产品1安排生产,产品2就不能生产,产品4生产,产品5必须生产,2020/8/9,浙江科技学院经济管理学院管工系,25,4.固定费用问题,即生产成本和产量成线性关系。如果产品不生产,不发生任何成本,如果产品生产,则产量增加一倍,成本也增加一倍。这样的成本称为变动成本。 在实际问题中,除了变动成本以外,还有固定成本。如果产品不生产,固定成本为0,如果产品生产,就发生固定成本,而且固定成本是一个常数,与产品产量无关。有固定成本的最小化目标函数的表达式为,一般的成本最小化目标函数表达式为,2020/

14、8/9,浙江科技学院经济管理学院管工系,26,设n种设备,第j种设备的产量为xj,设备运行的变动成本为cj,设备开工的固定成本为dj。引进0-1变量y1,y2,yn,yj=0表示设备j不生产,yj=1表示设备j生产。考虑变动成本和固定成本,使总成本最小化的目标函数为,设备开工与否与产量的逻辑关系,用以下约束条件表示 xjMyj 其中M为一个足够大的正数。,2020/8/9,浙江科技学院经济管理学院管工系,27,具有固定成本的最小生产费用问题,炼焦厂以原煤为原料生产焦炭,同时得到焦炉煤气和煤焦油。有4台不同生产能力的炼焦炉,有关的数据为,要求焦炭产量不低于280吨,煤气产量不低于10000m3,

15、煤焦油产量不低于60吨,编制使总成本最低的生产计划。,2020/8/9,浙江科技学院经济管理学院管工系,28,不考虑固定成本,使变动成本最小化 min z=85x1+81x2+78x3+76x4 s.t. 0.64x1+0.68x2+0.71x3+0.73x4280 23x1+ 25x2+ 27x3+ 28x410000 0.12x1+0.15x2+0.17x3+0.19x460 x1,x2,x3,x40 最优解为: x1=x2=0,x3=137.32,x4=250,max z=29711.27,2020/8/9,浙江科技学院经济管理学院管工系,29,考虑变动成本和固定成本,使总成本最小化。

16、Min z=85x1+81x2+78x3+76x4 +400y1+1200y1+2600y3+3100y4 s.t. 0.64x1+0.68x2+0.71x3+0.73x4280 23x1+ 25x2+ 27x3+ 28x410000 0.12x1+0.15x2+0.17x3+0.19x460 x1100y1 x2150y2 x3200y3 x4250y4 x1,x2,x3,x40,y1,y2,y3,y4:0-1变量 最优解为: y1=0,y2=1,y3=0,y4=1 x1=0,x2=143.38,x3=0,x4=250,max z=34913.97,2020/8/9,浙江科技学院经济管理学院

17、管工系,30,5.4 隐枚举法,基本原理 举例说明,2020/8/9,浙江科技学院经济管理学院管工系,31,1.基本原理,枚举法:检查变量取值为0或1的每一个组合,比较目标函数值的大小以求得最优解。 隐枚举法:只检查变量取值组合的一部分,就能求得问题的最优解的方法。 步骤: 如求极大化问题,根据目标函数中价值系数Cj的递增顺序,对目标函数和约束不等式中的变量重新排序,找一个可行解,其目标函数值定为过滤值。 考察各变量的组合,若产生Z劣于此时的过滤值,则不考虑,继续下一个组合,若优于此时的过滤值,则逐个考察是否满足约束条件,只要有一个不满足,则该组合为不可行解,继续下一个组合;如果满足所有约束,

18、则产生新的过滤值,继续下一个组合。,2020/8/9,浙江科技学院经济管理学院管工系,32,例:,0,0,5,5,3,8,8,-2,3,1,6,5,8,8,8,8,所以,该问题的最有解为(0,1,1),最优值为8,2020/8/9,浙江科技学院经济管理学院管工系,33,5.5 匈牙利法,标准指派问题 匈牙利法步骤 实例 非标准指派问题,2020/8/9,浙江科技学院经济管理学院管工系,34,1.标准指派问题,有n个任务,由n个人来做,已知第i人做第j件事的费用为Cij,求最佳任务分配方案,使总费用最少。,2020/8/9,浙江科技学院经济管理学院管工系,35,2.匈牙利法步骤,化指派问题为极小化问题,对各行或各列减去该行或该列的最小元素,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论