




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
关于运筹学基础整数规划第1页,共41页,2023年,2月20日,星期日2§4.1整数规划解决整数规划问题不能仅仅是在线性规划求解中,将解“四舍五入”就行了,因为化整后的解不见得是可行解;即便是可行解,也不一定是优解。注意:在前面讨论的线性规划问题中,有些最优解可能是分数或小数,但对于某些具体的问题,常有要求解答必须是整数的情形(称为整数解),解决这样的问题即为整数规划。一、整数规划问题的提出整数规划第2页,共41页,2023年,2月20日,星期日3【例1】某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表:问两种货物各托运多少箱,可使利润为最大?建立线性规划模型为:
maxZ=
20x1+10x25x1+4x2≤242x1+5x2≤13
x1≥0,x2≥0利用单纯形法求得最优解为:x1=4.8,x2=0,maxZ=96整数规划第3页,共41页,2023年,2月20日,星期日4讨论:如何调整满足整数解(1)四舍五入:x1=5,x2=0,Z=100但破坏了体积限制条件,因而不是可行解(2)舍小数:x1=4,x2=0,Z=80是可行解,但不是最优解,因x1=4,x2=1,Z=90也是可行解C(4.8,0)
maxZ=
20x1+10x25x1+4x2≤242x1+5x2≤13
x1≥0,x2≥0x2x111023234567++++++++++++B(4,1)x1=4.8,x2=0,maxZ=96非整数解整数规划第4页,共41页,2023年,2月20日,星期日5二、整数规划的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整数规划第5页,共41页,2023年,2月20日,星期日61、整数规划之分枝定解法问题A:maxZ=
20x1+10x25x1+4x2≤242x1+5x2≤13
x1≥0,x2≥0
x1,x2整数问题B:maxZ=
20x1+10x25x1+4x2≤242x1+5x2≤13
x1≥0,x2≥0从问题B开始,若其最优解不符合A的整数条件,那么B的最优目标函数必是A的最优目标函数Z*的上界,记作,(如果是求最小值,即为下界)
分枝定界法就是将B的可行域分成子区域的方法,逐步减小和增大,最终逼近Z*。写出整数规划问题A的伴随线性规划问题为B
而A的任意可行解的目标函数值将是Z*的一个下界,记作,(如果是求最小值,即为上界)
≤Z*≤整数规划第6页,共41页,2023年,2月20日,星期日7第一步:寻找替代问题并求解问题B:maxZ=
20x1+10x25x1+4x2≤242x1+5x2≤13
x1≥0,x2≥0利用单纯形法求得最优解为:x1=4.8,x2=0,Z=96问题B1:maxZ=
20x1+10x2
5x1+4x2≤24
2x1+5x2≤13
x1≤4
x1≥0,x2≥0问题B2:maxZ=
20x1+10x2
5x1+4x2≤24
2x1+5x2≤13
x1≥5
x1≥0,x2≥0=0≤Z*≤96=利用单纯形法求得最优解为:x1=4,x2=1,Z=90无解;第二步:分枝与定界x2x111023234567++++++++++++最后得最优解为:x1=4,x2=1,Z=90整数规划第7页,共41页,2023年,2月20日,星期日8【例2】问题A:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≥0,x2≥0
x1,x2整数利用单纯形法求解问题B得最优解为:x1=4.81,x2=1.82,Z=356问题B2:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≥5
x1≥0,x2≥0=0≤Z*≤356=利用单纯形法求得最优解为:x1=4,x2=2.1,Z=349利用单纯形法求得最优解为:x1=5,x2=1.57,Z=341问题B:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≥0,x2≥0问题B1:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≤4
x1≥0,x2≥0=0≤Z*≤349=第一步:寻找替代问题并求解第二步:分枝与定界整数规划第8页,共41页,2023年,2月20日,星期日9
分枝定解法求解(续)利用单纯形法求得最优解为:x1=4,x2=2,Z=340利用单纯形法求得最优解为:x1=1.52,x2=3,Z=327问题B11:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≤4
x2≤2
x1≥0,x2≥0=340≤Z*≤349=x1=4x2=2.1Z=349问题B12:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≤4
x2≥3
x1≥0,x2≥0问题B21:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≥5
x2≤1
x1≥0,x2≥0x1=5x2=1.57Z=341x1=5.44,x2=1,Z=308问题B21:maxZ=
40x1+90x29x1+7x2≤567x1+20x2≤70
x1≥5
x2≥2
x1≥0,x2≥0无可行解整数规划第9页,共41页,2023年,2月20日,星期日10问题Bx1=4.81x2=1.82Z=356问题B1x1=4.00x2=2.1Z=349问题Bx1=5.00x2=1.57Z=341问题B11x1=4.00x2=2.00Z=340问题B12x1=1.42x2=3.00Z=327问题B21x1=5.44x2=1.00Z=308问题B22无可行解x1≤4x1≥5x2≤2x2≥3x2≤1x2≥2=0≤Z*≤356==0≤Z*≤349==340≤Z*≤349=Z*=340
分枝定解法求解框图整数规划第10页,共41页,2023年,2月20日,星期日11分枝为问题1、2后解可能出现如下几种情况序号问题1问题2说
明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解,目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解,目标函数优于问题1问题1停止分枝(剪枝),其整数解为界,对问题2继续分枝情况2,4,5
找到最优解情况3
在缩减的域上继续分枝定界法情况6
问题1的整数解作为界被保留,用于以后与问题2的后续分枝所得到的整数解进行比较,结论如情况4情况1
无可行解整数规划第11页,共41页,2023年,2月20日,星期日12分枝定界法的一般步骤如下
第一步,先不考虑原问题的整数限制,求解相应的松弛问题,若求得最优解,检查它是否符合整数约束条件;如符合整数约束条件,即转下一步。
第二步,定界。在各分枝问题中,找出目标函数值最大者Z*作为整数规划最优值的上界,从已符合整数条件的分枝中,找出目标函数值最大者作为下界,即
第三步,分枝。根据对变量重要性的了解,在最优解中选择一个不符合整数条件的xj
,令xj=b’j
,(b’j不为整数)则用下列两个约束条件:
第四步,应用对目标函数估界的方法,或对某一分枝重要性的了解,确定出首先要解的某一分枝的后继问题,并解此问题。若所获得的最优解符合整数条件,则就是原问题的解,若不符合整数条件,再回到第二步,并参照第四步终止后继问题。整数规划第12页,共41页,2023年,2月20日,星期日13分枝定界法的EXCEL演示
整数规划第13页,共41页,2023年,2月20日,星期日142、割平面解法
割平面法也是求解整数规划问题常用方法之一。【基本思路】
如果所得到最优解不满足整数约束条件,则在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问题的可行域,即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)。而把所有的整数解都保留下来,故称新增加的约束条件为割平面。
当经过多次切割后,就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点,它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题,与原整数规划问题具有相同的最优解。
先不考虑整数约束条件,求松弛问题的最优解,如果获得整数最优解,即为所求,运算停止。整数规划第14页,共41页,2023年,2月20日,星期日15
割平面法的具体求解步骤如下:1.对于所求的整数规划问题,先不考虑整数约束条件,求解相应的松弛问题2.如果该问题无可行解或已取得整数最优解,则运算停止;前者表示原问题也无可行解,后者表示已求得整数最优解。如果有一个或更多个变量取值不满足整数条件,则选择某个变量建立割平面。3.增加为割平面的新约束条件,用前面介绍的灵敏分析的方法继续求解,返回1。整数规划第15页,共41页,2023年,2月20日,星期日16【例1】求解下列整数规划问题解:引入松弛变量,写成标准形式(1)ïîïíì³=++=+++=,0,,,;2054;62;max432142132121xxxxxxxxxxxxz(2)对上述模型不考虑整数条件,用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411005/3105/6-1/68/301-2/31/3x1x211-13/300-1/6-1/6最优解为x1=5/3,x2=8/3不是整数解整数规划第16页,共41页,2023年,2月20日,星期日17
显然,x1=5/3,x2=8/3为非整数解。为求得整数解,想办法在原约束条件的基础下引入一个新的约束条件,以保证一个或几个变量取值为整数。为此,选择分数部分较大的非整数变量,如x2
,写出如下表达式:
将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。上式可以改写成
若将带有整数系数的变量留在方程的左边,其余移到方程的右边,则有
由于要求变量取值为正整数,方程的左边必为整数。当然,方程的右边也应为整数。又x3≥0,x4≥0于是,必有x3≥1,x4≥1(3)(4)≤0此时,也可以选择x2-x3-2≤0,只是因为先分析出方程右端≤0整数规划第17页,共41页,2023年,2月20日,星期日18
整理后得
为了直观地在图形上描述,可将(2)式的两个约束方程代入(5)式即ïîïíì³=++=+++=且为整数,0,,,;2054;62;max432142132121xxxxxxxxxxxxz则(5)式成为(5)这就是割平面的方程B(5/3,8/3)x1x2246246-20-4AECO
加入新的约束条件,便形成新的线性规划问题,其可行域为新的凸集OAEC。
即图中红色直线割去了红色直线以外的△ABE部分,其中包括原所求得的非整数最优解点B(5/3,8/3)。三个方程是等价的,任意一个都可增加的新的约束条件整数规划第18页,共41页,2023年,2月20日,星期日19
建立割平面以后,便可以把割平面方程作为新的约束条件加到原整数规划问题(2)式中,在仍然不考虑整数条件的情况下,利用单纯形法或对偶单纯形法继续求解。以选择第一个为例,引入松驰变量x5,代入新增加的约束条件中
从上面的推导过程可以看出,新约束对原约束方程起到了这样的作用:对整数规划(1)式所对应的线性规划的可行域,保留了其中的所有整数可行解,但割掉了一部分非整数解。三个约束条件任选其一-1/3x3-1/3x4+
x5=-2/3整数规划第19页,共41页,2023年,2月20日,星期日20
Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x5110000100-15/240101-2x1x2x6110-40000-1/220011-3x1=0,x2=4为最优解,最优值为Z=4整数规划第20页,共41页,2023年,2月20日,星期日21
Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x51100021010-1/2201-101x1x2x6110-40000-1/220011-3x1=2,x2=2为最优解,最优值为Z=4另一选择第21页,共41页,2023年,2月20日,星期日22分析因为上述的线性规划的最优解已是整数解,所以得整数规划问题(1)的最优解:E(2,2)A(0,4)x1x2246246-20-4x1=0,x2=4。此最优解位于图A点。x1=2,x2=2。此最优解位于图E点。整数规划第22页,共41页,2023年,2月20日,星期日23【例2】求解下列整数规划问题解:引入松弛变量,写成标准形式:(1)(2)
第一步:对上述模型不考虑整数条件,用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x432005/2011/2-1/213/410-1/43/4x2x123-59/400-1/4-5/4最优解为x2=5/2,x1=13/4此最优解非整数解整数规划第23页,共41页,2023年,2月20日,星期日24
第二步:x1
=13/4
,x2=5/2为非整数解,找出非整数解变量中分数部分最大的一个基变量x2,写出这一行的约束:将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式得:
若将带有整数系数的变量整数项留在方程的左边,其余移到方程的右边,则有
由于要求变量取值为正整数,方程的左边必为整数。方程的右边也应为整数。又由于x3≥0,x4≥0于是,有方程右端小于等于零。≤0整数规划第24页,共41页,2023年,2月20日,星期日25
即
为了直观地在图形上描述,可将标准式的两个约束方程代入上式,则成为-(14-2x1-3x2)
–(9-2x1-x2)≤-1三个方程的任意一个都可做为后面增加的新的约束条件整理后得2x1+2x2≤11这就是割平面的方程整数规划第25页,共41页,2023年,2月20日,星期日26
B(13/4,5/2)AEC2x1+2x2≤11F
加入新的约束条件,便形成新的线性规划问题,其可行域为新的凸集OAEFC。即图中所示的红色直线的下半部分。显然它割去了除红色直线上所有点以外的△BEF部分,其中包括原所求得的非整数最优解点B(13/4,5/2)。x1x2246246-20-4O这就是割平面的方程整数规划第26页,共41页,2023年,2月20日,星期日27
建立割平面以后,便可以把割平面方程作为新的约束条件加到原整数规划问题中,在仍然不考虑整数条件的情况下,利用单纯形法或对偶单纯形法继续求解。
将其作为新的约束条件,加入到前面的最终表中,便形成新的线性规划问题。用对偶单纯形法求解。
第三步:引入松驰变量x5,代入新增加的约束条件中-1/2x3-1/2x4
+x5=-1/22x1+2x2≤11任意一个都可做为增加的新的约束条件整数规划第27页,共41页,2023年,2月20日,星期日28
Cj比值CBXBb检验数jx1x2x3x4x5320005/2011/2-1/2013/410-1/4¾0-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb检验数jx1x2x3x4x5110002010-117/21001-1/2x2x1x3230-29/2000-1-1/210011-2x1=7/2,x2=2为最优解,最优值为Z=29/2,不是整数解第28页,共41页,2023年,2月20日,星期日29
由于仍有非整数解,重复第二步:写出另一行的约束:将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式得:
若将带有整数系数的变量整数项留在方程的左边,其余移到方程的右边,则有此得到新约束:整数规划第29页,共41页,2023年,2月20日,星期日30
2x1+2x2≤11
又加入的新约束条件,便形成新的线性规划问题,其可行域又随之改变B(13/4,5/2)AECFx1x2246246-20-4Ox1+x2≤5整数规划第30页,共41页,2023年,2月20日,星期日31
2010-110
将其作为新的约束条件,加入到前面的最终表中,便形成新的线性规划问题。用对偶单纯形法求解。
第三步:引入松驰变量x6,代入新增加的约束条件中-1/2x5+x6=-1/2Cj比值CBXBb检验数jx1x2x3x4x5x63200007/2100
1-1/20x2x1x3x62300-29/2000-1-1/2010011-20-1/20000-1/21新增加的约束条件整数规划第31页,共41页,2023年,2月20日,星期日32
Cj比值CBXBb检验数jx1x2x3x4x5x63200004100
10-1x2x1x3x62300-14000-10-1300110-41010-102100001-2x1=4,x2=1为最优解,最优值为Z=14,是整数解整数规划第32页,共41页,2023年,2月20日,星期日33
E‘(1,4)因为上述的线性规划的最优解已是整数解,所以得整数规划问题的最优解:x1=1,x2=4。maxZ=14B(13/4,5/2)AECFx1x2246246-20-4O整数规划第33页,共41页,2023年,2月20日,星期日34【例3】求解下列整数规划问题解引入松弛变量,写成标准形式:(1)ïîïíì³=++=+++=,0,,,;43;1-;max432142132121xxxxxxxxxxxxz(2)对上述模型不考虑整数条件,用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411003/410-1/41/47/4013/41/4x1x211-5/200-1/2-1/2ïîïíì³£+£++=且为整数,0,;43;1-;max21212121xxxxxxxxz最优解为x1=3/4,x2=7/4整数规划第34页,共41页,2023年,2月20日,星期日35
显然,x1=3/4,x2=7/4
为非整数解。找出非整数解变量中分数部分最大的一个基变量,写出相应的约束:将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。据此,上式可以改写成
若将带有整数系数的变量整数项留在方程的左边,其余移到方程的右边,则有
,4/34/14/1431=+-xxx,4/74/14/3432=++xxx,4/30)4/10()4/31()01(431+=+++-++xxx,4/31)4/10()4/30()01(432+=+++
++xxx43314/14/34/3xxxx--=-4324/14/34/31xxx--=-整数规划第35页,共41页,2023年,2月20日,星期日36
整理后得
为了直观地在图形上描述,可将标准式的两个约束方程代入上式,则成为
由于要求变量取值为正整数,方程的左边必为整数。当然,方程的右边也应为整数。又由于x3≥0,x4≥0于是,有,04/14/34/343£--xx-3x3-x4
≤-3x2
≤1ïîïíì³=++=+++=且为整数,0,,,;43;1-;max432142132121x
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《全通径管道视镜用耐压玻璃管》征求意见稿
- 人教宁夏 九年级 下册 语文 第三单元《 文言文主题阅读》习题课 课件
- 人教河南 九年级 下册 语文 期末专题训练《 专题七 古诗文默写》习题课 课件
- 计算机基础实践与创新课件 第六章 办公软件-WPS 演示
- 借款合同范例藏文
- 兑店合同范例
- 信息建设合同范例
- 出租各种塔吊合同范例
- 书籍出版英文合同范例
- 中纤板采购合同范例
- 小批量试制总结报告
- 新媒体部门配置人员架构文件
- 新外研版高二英语选择性必修三unit2 life behind the lens课件
- 黄芩种植时间什么时候最好 黄芩播种技术
- 平面广告之构图与版式设计课件
- 桩基工程竣工验收记录
- 铁路物流-物流产业大数据平台课件
- 《空气动力学基础》绪论课件
- 卡通插画幼儿园国防教育主题班会课程PPT实施课件
- 第一届全国中学生地球科学竞赛初赛试题试题含答案
- A4线缆标签数据模板
评论
0/150
提交评论