运筹学08-整数规划.ppt
《运筹学08-整数规划.ppt》由会员分享,可在线阅读,更多相关《运筹学08-整数规划.ppt(77页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第八章 整数规划8.1 8.1 整数规划问题及其数学模型整数规划问题及其数学模型8.2 8.2 分支定界法分支定界法8.3 8.3 割平面法割平面法8.4 0-18.4 0-1整数规划整数规划8.5 8.5 指派问题指派问题一、整数规划问题的特征一、整数规划问题的特征 变量取值范围是离散的,经典连续数学中的理论和方法变量取值范围是离散的,经典连续数学中的理论和方法一般无法直接用来求解整数规划问题。一般无法直接用来求解整数规划问题。例例 某公司计划在某公司计划在m个地点建厂,可供选择的地点有个地点建厂,可供选择的地点有A1,A2Am,他们的生产能力分别是,他们的生产能力分别是a1,a2,am(假
2、设生(假设生产同一产品)。第产同一产品)。第i个工厂的建设费用为个工厂的建设费用为fi(i=1.2m),又又有有n个地点个地点B1,B2,Bn 需要销售这种产品,其销量分别需要销售这种产品,其销量分别为为b1.b2bn。从工厂运往销地的单位运费为。从工厂运往销地的单位运费为Cij。试决定。试决定应在哪些地方建厂,即满足各地需要,又使总建设费用和应在哪些地方建厂,即满足各地需要,又使总建设费用和总运输费用最省?总运输费用最省?8.1 整数规划问题及其数学模型二、整数规划的数学模型二、整数规划的数学模型纯整数规划纯整数规划:所有决策变量为非负整数;:所有决策变量为非负整数;全整数规划全整数规划:所
3、有变量、系数和常数均为整数;:所有变量、系数和常数均为整数;混合整数规划混合整数规划:只有一部分决策变量为非负整数,其余:只有一部分决策变量为非负整数,其余变量可为非负实数;变量可为非负实数;0-1整数规划整数规划:所有决策变量只能取:所有决策变量只能取0获获1两个整数。两个整数。三、整数规划与线性规划的关系三、整数规划与线性规划的关系n从数学模型上看整数规划似乎是线性规划的一种特殊形从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。但实际上两者却有很大的不求满足整数要求的解即
4、可。但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得倒的解是整数可行解。有时甚至不能保证所得倒的解是整数可行解。n目前,常用的求解整数规划的方法有:目前,常用的求解整数规划的方法有:n分支定界法和割平面法;分支定界法和割平面法;n对于特别的对于特别的01规划问题采用隐枚举法和匈牙利法。规划问题采用隐枚举法和匈牙利法。例例:设整数规划问题如下:设整数规划问题如下 首先不考虑整数约束,得到线性规划问题首先不考虑整数约束,得到线性规划问题(一般称为(一般称为松弛问题松弛问题)。)。用图解法求出最优解用图解法求
5、出最优解x13/2,x2=10/3且有且有z=29/6x1x233(3/2,10/3)现求整数解(最优解):现求整数解(最优解):如用如用“舍入取整法舍入取整法”可得可得到到4个点,即个点,即(1,3)(2,3)(1,4)(2,4)。显然,。显然,它们都不可能是整数规划它们都不可能是整数规划的最优解。的最优解。按整数规划约束条件,其按整数规划约束条件,其可行解肯定在线性规划问可行解肯定在线性规划问题的可行域内且为整数点。题的可行域内且为整数点。故整数规划问题的可行解故整数规划问题的可行解集是一个有限集,如图所集是一个有限集,如图所示。示。因此,可将集合内的整数点一一因此,可将集合内的整数点一一
6、找出,其最大目标函数的值为最找出,其最大目标函数的值为最优解,此法为优解,此法为完全枚举法完全枚举法。8.2 分支定界法 基本思路基本思路 1、先不考虑整数约束,解、先不考虑整数约束,解(IP)的松弛问题的松弛问题(LP),可能可能得到以下情况之一:得到以下情况之一:.若若(LP)没有可行解,则没有可行解,则(IP)也没有可行解,停止计也没有可行解,停止计算。算。.若若(LP)有最优解,并符合有最优解,并符合(IP)的整数条件,则的整数条件,则(LP)的最优解即为的最优解即为(IP)的最优解,停止计算。的最优解,停止计算。.若若(LP)有最优解,但不符合有最优解,但不符合(IP)的整数条件,转
7、入的整数条件,转入下一步。下一步。为讨论方便,设为讨论方便,设(LP)的的最优解为:最优解为:2、定界:、定界:记记(IP)的目标函数最优值为的目标函数最优值为Z*,以以Z(0)作为作为Z*的的上界,上界,记为记为 Z(0)。再用观察法找的一个整数可行解再用观察法找的一个整数可行解 X,并并以其相应的目标函数值以其相应的目标函数值 Z作为作为Z*的的下界,记为下界,记为Z Z,也可以令也可以令Z,则有:则有:Z Z*3、分枝:、分枝:在在(LP)的最优解的最优解 X(0)中,任选一个不符合整数条件的中,任选一个不符合整数条件的变量,例如变量,例如xr=(不为整数),以不为整数),以 表示不超过
8、表示不超过 的最的最大整数。构造两个约束条件大整数。构造两个约束条件 xr 和和 xr 1如此反复进行,直到得到如此反复进行,直到得到 Z Z*为止,即得最优解为止,即得最优解X*。将这两个约束条件分别加入问题将这两个约束条件分别加入问题(IP),形成两个子形成两个子问题问题(IP1)和和(IP2),再解这两个问题的松弛问题再解这两个问题的松弛问题(LP1)和和(LP2)。4、修改上、下界:按照以下两点规则进行。、修改上、下界:按照以下两点规则进行。.在各分枝问题中,找出目标函数值最大者作为新的上在各分枝问题中,找出目标函数值最大者作为新的上界;界;.从已符合整数条件的分枝中,找出目标函数值最
9、大者从已符合整数条件的分枝中,找出目标函数值最大者作为新的下界。作为新的下界。5、比较与剪枝、比较与剪枝:各分枝的目标函数值中,若有小于各分枝的目标函数值中,若有小于Z 者,则剪掉此枝,者,则剪掉此枝,表明此子问题已经探清,不必再分枝了表明此子问题已经探清,不必再分枝了;否则继续分枝。否则继续分枝。分支定界法是一种隐枚举方法(分支定界法是一种隐枚举方法(implicit enumeration)或或部分枚举方法,它不是一种有效的算法,是枚举方法基部分枚举方法,它不是一种有效的算法,是枚举方法基础上的改进。其关键是分支和定界。础上的改进。其关键是分支和定界。例例 Max Z=X1+X2 14X1
10、+9X2 51 -6X1+3X2 1 X1,X2 0 X1,X2 取整数取整数s.t.分支定界法图解整数规划分支定界法图解整数规划松弛问题松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1,X2 0该该整数规划松弛问题的解为:整数规划松弛问题的解为:(X1,X2)=(3/2,10/3)Z0=29/6松弛问题松弛问题 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1,X2 0(3/2,10/3)Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1,X2 0LP2 Max Z=X1+X
11、2 14X1+9X2 51 -6X1+3X2 1 X1 1 X1,X2 0LP2:解解(1,7/3)Z2=10/3LP1:解解(2,23/9)Z1=41/9(3/2,10/3)Z0=29/6LP1 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X1,X2 0LP2:解解(1,7/3)Z2=10/3LP1:解解(2,23/9)Z1=41/9LP11 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 3 X1,X2 0LP12 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1,X2
12、0LP12:解解(33/14,2)Z12=61/14(3/2,10/3)Z0=29/6LP2:解解(1,7/3)Z2=10/3LP12 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1,X2 0LP12:解解(33/14,2)Z12=61/14LP121 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 3 X2 2 X1,X2 0LP122 Max Z=X1+X2 14X1+9X2 51 -6X1+3X2 1 X1 2 X2 2 X1,X2 0LP121:解解(3,1)Z121=4LP122:解解(2,2)Z122=4L
13、P1:解解(2,23/9)Z1=41/9LP(3/2,10/3)Z0=29/6LP2(1,7/3)Z2=10/3LP1(2,23/9)Z1=41/9LP12(33/14,2)Z12=61/14LP11 无可无可行解行解LP122(2,2)Z122=4LP121(3,1)Z121=4#LP22(1,2)Z22=3LP21 无可无可行解行解#分支搜索法流程分支搜索法流程LP(3/2,10/3)Z0=29/6LP2(1,7/3)Z2=10/3LP1(2,23/9)Z1=41/9LP12(33/14,2)Z12=61/14LP11 无可无可行解行解LP122(2,2)Z122=4LP121(3,1)Z
14、121=4#分支定界法流程分支定界法流程3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优解。获得最优解。初始表初始表最终表最终表例例 用分支定界法求解整数规划问题(单纯形法)用分支定界法求解整数规划问题(单纯形法)x1=13/4 x2=5/2 Z(0)=59/414.75 选选 x2 进行分枝,即增加两个约束,进行分枝
15、,即增加两个约束,2 x2 3 有下式:有下式:分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6,将,将新加约新加约束条件加入上表计算。即束条件加入上表计算。即 x2+x5=2,x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4
16、100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2 Z(1)=14.5继续分枝,继续分枝,加入约束加入约束3 x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3
17、Z(2)=13.5 Z(2)Z(1)先不考虑先不考虑分枝分枝接接(LP1)继续分枝,加入约束继续分枝,加入约束 4 x1 3,有下式:有下式:分别引入松弛变量分别引入松弛变量x7 和和 x8,然后进行计算。然后进行计算。CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100
18、x420001-3-20 x310010-1-2-Z-130000-2-3x1=3,x2=2 Z(3)=13找到整数解,找到整数解,问题已探明,问题已探明,停止计算。停止计算。LP3CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x51
19、00-101-2-Z-1400-200-1x1=4x2=1 Z(4)=14找到整数找到整数解,问题解,问题已探明,已探明,停止计算。停止计算。LP4树形图如下:树形图如下:LP1x1=7/2,x2=2Z(1)29/2=14.5LPx1=13/4,x2=5/2Z(0)59/4=14.75LP2x1=5/2,x2=3Z(2)27/2=13.5LP3x1=3,x2=2Z(3)13LP4x1=4,x2=1Z(4)14x22x23x13x14#8.3 割平面法二、计算步骤二、计算步骤1、用单纯形法求解、用单纯形法求解(IP)对应的松弛问题对应的松弛问题(LP):.若若(LP)没有可行解,则没有可行解,则
20、(IP)也没有可行解,停止计也没有可行解,停止计算。算。.若若(LP)有最优解,并符合有最优解,并符合(IP)的整数条件,则的整数条件,则(LP)的最优解即为的最优解即为(IP)的最优解,停止计算。的最优解,停止计算。.若若(LP)有最优解,但不符合有最优解,但不符合(IP)的整数条件,转入的整数条件,转入下一步。下一步。2、从、从(LP)的最优解中,任选一个不为整数的分量的最优解中,任选一个不为整数的分量xr,将最优将最优单纯形表中该行的系数单纯形表中该行的系数 和和 分解为整数部分和小数部分之分解为整数部分和小数部分之和,并以该行为源行,按下式作割平面方程:和,并以该行为源行,按下式作割平
21、面方程:3、将所得的割平面方程作为一个新的约束条件置于最、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中(同时增加一个单位列向量),用对偶单优单纯形表中(同时增加一个单位列向量),用对偶单纯形法求出新的最优解,返回纯形法求出新的最优解,返回1。例例:用割平面法求解整数规划问题:用割平面法求解整数规划问题解解:增加松弛变量:增加松弛变量x3和和x4,得到得到(LP)的初始单纯形表和最优的初始单纯形表和最优单纯形表单纯形表:Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2
22、011/41/4Z-3/200-1/4-1/4此题的最优解为:此题的最优解为:X(1,3/2)Z=3/2 但不是整数最优但不是整数最优解,引入割平面。以解,引入割平面。以x2 为源行生成割平面,由于为源行生成割平面,由于 1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数,所以,我们已将所需要的数分解为整数和分数,所以,生成割平面的条件为生成割平面的条件为:也即:也即:将将 x3=6-3x1-2x2,x4=3x1-2x2 ,带入带入 中,中,得到等价的割平面条件:得到等价的割平面条件:x2 1 见下图。见下图。x1x233第一个割平面第一个割平面Cj01000CBXBb
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 08 整数 规划
限制150内