版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1.整数规划的数学模型2.分枝定界法3.割平面法4.0-1型整数规划5.指派问题第五章整数规划2023/9/141.整数规划的数学模型第五章整数规划2023/8/31整数规划的数学模型max(min)(c1
x1+c2x2+…+
cnxn)a11
x1+a12x2+…+a1nxn(=,)
b1a21
x1+a22x2+…+a2nxn(=,)
b2……...am1
x1+am2x2+…+amnxn(=,)
bmx1~n
0
且取整数纯整数规划:所有变量都有取整约束混合整数规划:只有部分变量有取整约束2023/9/14整数规划的数学模型max(min)(c1x1+c2x22分枝定界法1.分枝定界法的基本思路2.第65页例5-13.练习题2023/9/14分枝定界法1.分枝定界法的基本思路2023/8/33分枝定界法的基本思路
2023/9/14分枝定界法的基本思路2023/8/34分枝定界法的基本思路2023/9/14分枝定界法的基本思路2023/8/35第65页例5-1maxz=40x1+90x29x1+7x2567x1+20x270x1,x20且取整
2023/9/14第65页例5-1maxz=40x1+90x22026用分枝定界法解例5-11.求解相应的线性规划L0maxz=40x1+90x29x1+7x2567x1+20x270x1,x202023/9/14用分枝定界法解例5-11.求解相应的线性规划L02023/87用分枝定界法解例5-1
x2
59x1+7x2=56
4
3
27x1+20x2=70
1
0
12345678910
x1L0:x*=(4.81,1.82),Z*=356
2023/9/14用分枝定界法解例5-12023/8/38用分枝定界法解例5-12.将L0分解为L1和L2L1:maxz=40x1+90x29x1+7x2567x1+20x270
x1
4x1,x20L2:maxz=40x1+90x29x1+7x2567x1+20x270
x1
5x1,x20L1:X*=(4,2.10),Z*=349
L2:X*=(5,1.57),Z*=341
2023/9/14用分枝定界法解例5-12.将L0分解为L1和L2L2:ma9用分枝定界法解例5-13.分解L1形成L3、L4,其中:
L3={L1,x22}L4={L1,x23}
L3:X*=(4,2),Z*=340
L4:X*=(1.42,3),Z*=327(1)取下界min=340(L3);(2)舍弃L42023/9/14用分枝定界法解例5-13.分解L1形成L3、L4,其中:2010用分枝定界法解例5-14.分解L2形成L5、L6,其中:
L5={L2,x21}L6={L2,x22}
L5:X*=(5.44,1),Z*=308
L6:无可行解(1)舍弃L5、L6;(2)得最优解X*=(4,2),Z*=340。
2023/9/14用分枝定界法解例5-14.分解L2形成L5、L6,其中:2011例5-1求解过程示意图L0(4.81,1.82)356L1(4,2.1)349L2(5,1.57)341L3(4,2)340L4(1.42,3)327L5(5.44,1)308L6无可行解2023/9/14例5-1求解过程示意图L0L1L2L3L4L5L62023/12练习题maxz=2x1+5x2+4x3x1+x2+x3
12x1+2x2154x1+5x326x1~30且取整2023/9/14练习题maxz=2x1+5x2+4x3202313求解练习题首先求解线性规划L0:maxz=2x1+5x2+4x3x1+x2+x3+x4=12x1+2x2+x5=154x1+5x3+x6=26x1~602023/9/14求解练习题首先求解线性规划L0:2023/8/314求解练习题
2023/9/14求解练习题2023/8/315求解练习题
2023/9/14求解练习题2023/8/316求解练习题
2023/9/14求解练习题2023/8/317求解练习题
2023/9/14求解练习题2023/8/318求解练习题L0(0,15/2,9/2)111/2
L1(0,7,5)55
L2无可行解2023/9/14求解练习题L0L1L22023/8/319割平面法1.割平面法的基本思路2.例3.练习题2023/9/14割平面法1.割平面法的基本思路2023/8/320割平面法的基本思路同分枝定界法一样,割平面法也是一种利用连续模型求解非连续问题的常用方法。割平面法的基本思路是:当得到的解不满足取整约束时,就设法在问题上增加一个约束条件,把包含这个非整数解的一部分可行域从原来的可行域中割除,但不割掉任何一个整数可行解。这个新增加的约束条件就称为割平面。2023/9/14割平面法的基本思路同分枝定界法一样,割平面法也是一种利用连续21例maxz=x1+x2-x1+x213x1+x24x1,x20且取整
2023/9/14例maxz=x1+x22023/8/322用割平面法解例1.求解相应的线性规划L0maxz=x1+x2-x1+x213x1+x24x1,x20
2023/9/14用割平面法解例1.求解相应的线性规划L02023/8/323用割平面法解例非整数解,为建立割平面,首先考虑非整数解中余数最大的基变量,此例中x1、x2的余数均为3/4,不妨选取x2:x2+3/4x3+1/4x4=7/4
2023/9/14用割平面法解例非整数解,为建立割平面,首先考虑非整数解中余数24用割平面法解例
x2+3/4x3+1/4x4=7/4现将各系数分成整数和非负真分数两部分,从而可得:(1+0)x2+(0+3/4)x3+(0+1/4)x4=(1+3/4)将整数部分的变量移至等式右端有:3/4x3+1/4x4=3/4+(1-x2)非负整数解(1-x2)为整数,左端非负故有:3/4x3+1/4x4=3/4+非负整数从而:3/4x3+1/4x4
3/4或x2
1以x2
1为割平面可使可行域减少一个包括A点在内的三角形。
2023/9/14用割平面法解例x2+3/4x3+125x2A1
01x1用割平面法解例
2023/9/14x2A用割平面法解例2026用割平面法解例2023/9/14用割平面法解例2023/8/327练习题maxz=2x1+5x2+4x3x1+x2+x3
12x1+2x2154x1+5x326x1~30且取整
2023/9/14练习题maxz=2x1+5x2+4x3202328求解练习题
2023/9/14求解练习题2023/8/329求解练习题选取x2:1/2x1+x2+1/2x5=15/21/2x1+1/2x5=1/2+(7-x2)
于是有割平面:1/2x1+1/2x5
1/2或
x272023/9/14求解练习题选取x2:2023/8/330求解练习题
2023/9/14求解练习题2023/8/331求解练习题2023/9/14求解练习题2023/8/3320-1型整数规划1.0-1规划:0-1规划是整数规划的特例,是所有决策变量仅取0和1的整数规划问题。2.引例(1)第69页例5-3(2)引例23.0-1规划的隐枚举法(1)隐枚举法的基本步骤(2)第70页例5-4(3)第71页例5-52023/9/140-1型整数规划1.0-1规划:0-1规划是整数规划的特例33第69页例5-3
某公司拟在东、西、南三个区建立销售门市部,拟议中有7个场点A1~7可供选择。东区的三个点A1~3最多选两个,西区的两个点A4~5最少选一个,南区的两个点A6~7最少选一个。如果建设Ai点,需要投资bi元,年可获利ci元,公司可筹集到的投资总额为B元,问应如何决策才能使年利潤最大。
2023/9/14第69页例5-3某公司拟在东、西、南三个区建立销售门市部,34例5-3
令xi=0或1,其中:
xi=0表示第I个点未被选取
xi=1表示第I个点被选取其数学模型为:
x1+x2+x32x4+x51
x6+x71
2023/9/14例5-3令xi=0或1,其中:2023/8/335引例2
两种运输方式的限制条件分别为:6x1+4x2307x1+3x240互斥的约束统一于一个模型中:6x1+4x230+Mx37x1+3x240+M(1-x3)
其中x3为0-1变量。2023/9/14引例2两种运输方式的限制条件分别为:2023/8/336隐枚举法的基本步骤
1.目标函数极小化;2.目标函数系数非负化,如果xj的系数为负数,可令xj=1-xj
;3.决策变量按其目标函数系数的大小排列;4.令所有变量为“0”,检查该解的可行性,如果可行此解即为最优解,如果不可行进入下一步;5.按变量的顺序依次令各变量分别取“0”或“1”,根据分枝定界的原理进行剪枝,直至结束。2023/9/14隐枚举法的基本步骤1.目标函数极小化;2023/8/337第70页例5-4Maxz=3x1-2x2+5x3
x1+2x2-x32x1+4x2+x34x1~3=0或1第一步:Minw=-3x1+2x2-5x3
x1+2x2-x32x1+4x2+x34x1~3=0或1
2023/9/14第70页例5-4Maxz=3x1-2x2+5x338例5-4第二步:令x1=1-x1,x3=1-x3Minw=3x1+2x2+5x3
-8-x1+2x2+x32-x1+4x2-x32x1~3=0或1第三步:Minw=2x2+3x1+5x3
-8
2x2-x1+x32
4x2-x1-x32x1~3=0或1第四步:令所有变量为“0”,得可行解,所以原问题的最优解为(1,0,1),最优值为8。2023/9/14例5-4第二步:令x1=1-x1,x3=1-x3239maxz=8x1+2x2-4x3-7x4-5x5
3x1+3x2+x3+2x4+3x54
5x1+3x2-2x3-x4+x54
x1~5=0或1经前三步有:令x1=1-x1,x2=1-x2minw=2x2+
4x3+5x5+7x4+8x1-10
3x2-x3-3x5-2x4+3x12
3x2+2x3-x5+x4+5x14
x1~5=0或1
第71页例5-52023/9/14maxz=8x1+2x2-4x3-7x4-40
例5-5
w=-8
x2=12
w=-101
x2=0
w=-63
2023/9/14例5-52023/8/341
例5-5
w=-44(可行解)
w=-8x3=1x2=12w=-10x3=0w=-315x2=0w=-632023/9/14例5-542例5-5
w=-6x5=18w=-1x3=16x5=0w=-69w=1w=23x3=0w=-5x4=112w=-5x5=1107x5=0w=-3x4=0w=311132023/9/14例5-543指派问题
1.指派问题的内涵2.指派问题的数学模型3.指派问题的求解4.指派问题的扩展2023/9/14指派问题1.指派问题的内涵2023/8/344指派问题的内涵
有m项工作,恰好有m个人来完成,一个人只完成一项工作,一项工作只由一个人来完成,由于个人的专长不同,完成任务的效率也就不同,于是产生了应指派哪个人去完成哪项任务,才能使完成m
项任务的总效率最高的问题,此类问题称为指派问题或分派问题。指派问题同运输问题一样,是具有一定模型特征一类问题的总称,如m项加工任务如何在m台机床上分配;m
条航线如何指定m
艘船去航行等等。指派问题是运输问题的特例,也是0-1规划问题的特例。这一点可由指派问题的数学模型体现出来。2023/9/14指派问题的内涵有m项工作,恰好有m个人来45指派问题的数学模型2023/9/14指派问题的数学模型2023/8/346指派问题的求解-匈牙利法2.匈牙利法的基本步骤(1)第73页例5-6(2)第74页例5-7(3)基本步骤总结2023/9/14指派问题的求解-匈牙利法2.匈牙利法的基本步骤2023/847指派问题的扩展
1.人员与工作不匹配:引入假想的工作或人员由于假想的工作或人员代表的是剩余的工作或人员,所以其对应的效率矩阵元素全都为零。
例2.目标函数求极大值:效率矩阵的每一元素乘“-1”,并进一步使其非负化。
第73页例5-62023/9/14指派问题的扩展1.人员与工作不匹配:引入假想的工作或人员48第73页例5-6
2023/9/14第73页例5-62023/8/349例5-62023/9/14例5-62023/8/350第74页例5-7
2023/9/14第74页例5-72023/8/351例5-7
2023/9/14例5-72023/8/352例5-7
2023/9/14例5-72023/8/353例5-7
2023/9/14例5-72023/8/354例5-7
2023/9/14例5-72023/8/355例5-7
2023/9/14例5-72023/8/356例5-7
2023/9/14例5-72023/8/357例5-72023/9/14例5-72023/8/358基本步骤总结
1.每行减去一个最小元素;2.每列减去一个最小元素;经此两步,效率矩阵每行、列都至少有一个“0”。3.每行、列若只有一个“0”元素,打上“()”,同时划去与其同列、行的其它零元素,先前已被划去的零元素不计算在内,如果出现零元素的闭合回路,则任选一个零元素打上“()”,同时划掉与其同行和同列的零元素。经过第三步可能出现两种结果:(1)每行均有打“()”的零元素,此时已得最优解;(2)并非每行均有打“()”的零元素,进入第四步。4.给没有“(0)”的行做标记“”;5.在做“”标记的行上对所有“0”所在的列做标记“”;6.覆盖掉没有“”标记行上的所有元素和有“”标记列上的所有元素。经过此步矩阵中的所有“0”均被覆盖掉了,只留下了部分非零元素。7.每一非零元素减去它们中的最小值,并给同时处在被覆盖掉行和被覆盖掉列的元素加上这一最小值。8.重复3~7直至得到最优解。2023/9/14基本步骤总结1.每行减去一个最小元素;2023/8/359例1279798966671712141215146610
2023/9/14例2023/8/360例127979896667171214121514661000000
2023/9/14例2023/8/361例5(0)20223(0)00(0)10575980(0)40000(0)方案1:甲-B、乙-C、丙-A、丁-D工作E剩余,minz=26
2023/9/14例2023/8/362例502(0)2230
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年高端医疗服务项目合作计划书
- 2024年1420MM五机架冷连轧机合作协议书
- 国家银行业个人贷款(中级)考试模拟题及其答案
- 环保演讲稿十篇
- 防爆电工复习题
- 小学英语观摩心得体会
- 端午节活动方案八篇
- 浙教新版八年级下学期《6 .3 反比例函数的应用》同步练习卷
- 2024年林芝道路旅客运输从业资格证模拟考试
- 2024年乌鲁木齐客运考试口诀图片高清版
- 二年级数学(上)计算题汇编
- JB-T 14314-2022 活塞式调流阀
- 【企业现金流量探究国内外探究综述2500字】
- 2024年开滦(集团)有限责任公司招聘笔试冲刺题(带答案解析)
- 模具修改履历表
- 《拓印》参考课件
- 硫化镍矿的湿法冶金-硫酸化焙烧-浸出-2焙砂浸出与金属共沉淀
- 《桥涵施工技术》课件-23 盖板涵施工
- 老年学概论(第3版) 课件 第1、2章 人类个体和群体老龄化、老年学的学科性质
- 物质与意识的辩证关系
- 《Unit 2 How often do you exercise?》单元测试卷及答案(附听力材料)
评论
0/150
提交评论