整数规划PPT格式课件下载.ppt
- 文档编号:4517530
- 上传时间:2023-05-03
- 格式:PPT
- 页数:77
- 大小:1.27MB
整数规划PPT格式课件下载.ppt
《整数规划PPT格式课件下载.ppt》由会员分享,可在线阅读,更多相关《整数规划PPT格式课件下载.ppt(77页珍藏版)》请在冰点文库上搜索。
为此,引入0-1变量:
设xij为由Ai运往Bj的物资数量(千吨),(i,j1,2,3,4)。
则问题的数学模型为:
二、整数规划模型的一般形式及解的特点,整数线性规划数学模型的一般形式为:
一般来说,整数线性规划可分为以下几种类型:
1.纯整数线性规划(PureIntegerLinearProgramming):
指全部决策变量都必须取整数值的整数线性规划,也称为全整数规划。
2.混合整数线性规划(MixedIntegerLinearProgramming):
指决策变量中一部分必须取整数值,而另一部分可以不取整数值的整数线性规划。
3.0-1整数线性规划(Zero-oneIntegerLinearProgramming):
指决策变量只能取0或1两个值的整数线性规划。
(三)整数规划与线性规划的关系,从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。
但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得倒的解是整数可行解。
举例说明。
例:
设整数规划问题如下,首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。
用解法求出最优解x13/2,x2=10/3且有Z=29/6,x1,x2,3,3,(3/2,10/3),现求整数解(最优解):
如用“舍入取整法”可得到4个点即(1,3)(2,3)(1,4)(2,4)。
显然,它们都不可能是整数规划的最优解。
按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。
故整数规划问题的可行解集是一个有限集,如图所示。
图,因此,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法。
如上例:
其中(2,2)(3,1)点为最大值,Z=4。
.若(LP)没有可行解,则(ILP)也没有可行解,停止计算。
.若(LP)有最优解,并符合(ILP)的整数条件,则(LP)的最优解即为(IP)的最优解,停止计算。
.若(LP)有最优解,但不符合(ILP)的整数条件,可用相应方法求解。
整数规划与其松驰问题解的关系:
目前,常用的求解整数规划的方法有:
分支定界法和割平面法;
对于特别的01规划问题采用隐枚举法和匈牙利法。
第二节割平面法,割平面法由高莫累(Gomory)于1958年提出。
其基本思想是放宽变量的整数约束,首先求对应的松弛问题最优解,当某个变量xi不满足整数约束时,寻找一个约束方程并添加到松弛问题中,其作用是割掉非整数部分,缩小原松弛问题的可行域,最后逼近整数问题的最优解。
一、割平面法的基本思想,考虑松弛问题为标准形线性规划问题的纯整数规划问题(ILP):
假设约束条件中aij(i1,2,m;
j1,2,,n)和bi(i1,2,m)均为整数(若不为整数,可令等式两边同乘一个倍数化为整数)。
下面先通过一个例子来说明割平面法的基本思想。
【例5-5】,将该问题图示如下图:
从图(a)中可以看出,松弛问题的最优解为X*=(5/3,5/2)T,它不是一个整数解。
因此我们设法给原线性规划问题增加一个约束条件,从而把包括X*在内的一部分不含整数点的可行域从原可行域中分割出去。
再求增加了这个约束条件后的新的线性规划问题的最优解。
二、Gomory约束,假设用单纯形法求得的线性规划问题最优解不是整数解,其中必然有某个或某几个基变量不为整数。
记B为松弛问题的最优基,则问题的基最优解为:
不妨设第r个分量不为整数,根据最优单纯形表可得:
(5.1),将和分成整数部分和非负真分数之和,即:
代入上式得:
(5.2),(5.3),(5.4),移项,得:
(5.5),因为变量必须取整数,即上式左边必须是整数,从上式右边看,因为0fi1,所以不能为正,即:
割平面方程,(5.6),即:
(5.7),割平面的两个性质:
(1)割平面(5.7)式割去了(ILP)的松弛问题(LP)的基最优解。
(2)割平面(5.7)式未割去原问题(ILP)的任一(整数)可行解。
三、割平面法的算法步骤,步骤1:
将约束条件系数及右端项化为整数,用单纯形法求解整数规划问题(ILP)的松弛问题(LP)。
设得到最优基B,相应的基最优解为X*。
步骤2:
判别X*的所有分量是否全为整数?
如是,则X*即为(ILP)的最优解,算法终止;
若否,则取X*中分数最大的分量,引入割平面(5.7)。
步骤3:
将式(5.7)引入松弛变量后加入原最终单纯形表,用对偶单纯形法继续求解。
转步骤2。
【例5-6】用割平面法求解例5-5。
首先,将整数约束去掉,将松弛问题化为标准形,并用单纯形法求解,结果见下表:
因基变量x15/3,x25/2,均为非整数,故该最优解不是整数规划的可行解。
若以变量x1所在的行为源行,得到相应的割平面为:
(5.8),对式(5.8)左端加入松弛变量,得到:
(5.9),将式(5.9)加入上表中,用对偶单纯形法继续求解如下表:
若以分数部分最大的变量x1所在的行为源行,得到相应的割平面为:
由上表可知,增加约束条件后的线性规划问题最优解为X*=(2,2,0,1,0)T,因此,原整数规划问题的最优解为X*=(2,2)T,其最优值z*=4。
如果将式(5.8)中的变量用原问题的决策变量来表示,就得到:
整理后得到:
用割平面法求解数规划问题,初始表,最终表,在松弛问题最优解中,x1,x2均为非整数解,由上表有:
将系数和常数都分解成整数和非负真分数之和:
以上式子只须考虑一个即可,解题经验表明,考虑式子右端最大真分数的式子,往往会较快地找到所需割平面约束条件。
以上两个式子右端真分数相等,可任选一个考虑。
现选第二个式子,并将真分数移到右边得:
引入松弛变量s1后得到下式,将此约束条件加到上表中,继续求解。
得到整数最优解,即为整数规划的最优解,而且此整数规划有两个最优解:
X=(0,4),z=4,或X=(2,2),z=4。
第三节分枝定界法,分枝定界法是在20世纪60年代初由LandDoing和Dakin等人提出的适合于解纯整数或混合正数规划问题。
分支定界法实际是一种隐枚举法或部分枚举法,它是在枚举法基础上的改进,在枚举过程中逐批把一部分可行解排斥在考察范围之外,从而大大减少了计算量。
分支定界法的关键是分支和定界。
一、分支定界法的基本思想,两个子问题的可行域的并集包含了原问题(ILP)的全部可行解,而包括原最优解在内的松弛问题的部分非整数解被剔除了。
然后分别求解两个子问题,根据需要,各子问题可以再产生自己的子问题。
这个过程就是分支。
在分支过程中,若某个子问题的最优解为整数解,其目标函数值就是整数规划问题的一个“界限”,可以此作为判断其他分支优劣的一个依据。
若某一子问题最优解(无论是否为整数解)的目标函数值小于或等于该界限,则可以将该子问题剔除而不予考虑了。
若有其他子问题的最优解为整数解,则将其目标函数值与原来的界限相比较,取更优的一个作为新的界限。
这个过程就是定界。
二、分支定界法的一般步骤,【例5-7】用分支定界法求解例5-5。
首先求解(LP),得到的最优解为x15/3,x25/2,z25/6。
由于(LP)的最优解不是整数解,可任选一个变量进行分支。
若选x15/3进行分支,则分支出的约束条件为:
(5.10),和,(5.10),分别将上述两个约束条件加入(LP)中,因此原问题的松弛问题(LP)被划分为两个子问题:
先求解(LP1),最优解为x11,x25/2,最优值z7/2,仍不是整数解(见图5-2)。
再求解(LP2),最优解为x12,x22,z4(见图5-3)。
故取z4作为(ILP)最优值的一个下界。
由于(LP1)的最优值为7/24,故其子问题的目标函数值不会超过7/2,也不会超过4。
因此(LP1)是一个失去希望的问题,不必再对它进行分支。
若(LP1)的最优值大于4,需要对它进一步分支。
上述求解过程可用图5-4来说明:
分支定界法解整数规划的一般步骤可归结如下:
步骤1:
取(ILP)的目标函数值的初始下界。
用单纯形法求解整数规划问题(ILP)的松弛问题(LP)。
若问题(LP)不可行,则(ILP)也不可行,算法终止;
若问题(LP)的最优解X*为(ILP)的可行解,则它就是(ILP)的最优解,算法终止。
若问题(LP)的最优解存在,但不满足(ILP)的整数要求,转步骤3。
任选X*中不满足整数要求的一个变量进行分支,即对问题(LP)分别增加约束条件和,形成两个子问题,并求解。
转步骤4。
步骤4:
考察所有子问题,有以下四种情况:
a.若某个子问题的最优解也是问题(ILP)的可行解,则将它的目标函数值与作比较,并取较优的一个作为新的界限。
如所有子问题都已考察完毕,则保留下来的及其对应的解即为问题(ILP)的最优解。
b.若某个子问题的最优解不是(ILP)的可行解,且其最优值不如,则将这一分支删掉。
c.若某个子问题不可行,则将这一分支删掉。
d.若某个子问题的最优解不是(ILP)的可行解,且其最优值优于,则该问题为待考察的问题。
如有多个问题待考察,优先对其中最优值最大的一个子问题进行考察,转步骤3。
用图解法解对应的(LP)问题,如表所示,获得最优解。
【例】用分枝定界法求解整数规划问题,(3.25,2.5),x1=13/4x2=5/2Z(0)=59/414.75,选x2进行分枝,即增加两个约束,x22和x23,分枝出以下两个问题:
(3.5,2),用图解法求对应的LP1和LP2问题:
接(IP1)继续分枝,加入约束x13和x14,分枝出以下两个问题:
(3,2),用图解法求对应的LP3和LP4问题:
树形图如下:
第四节01整数规划,一、0-1变量的应用,第一节中我们讨论过0-1变量,即只能取0或1的变量,它是逻辑变量,通常用来表示在是与否之间二选一的问题,如某个方案A是否被选中,可用下面的0-1变量来表示:
【例5-8】含有相互排斥的约束条件的问题。
设某厂生产第j种产品的数量为xj(j=1,2,3),其材料可在甲或乙中选择一种,当选择甲或乙时,相应的材料消耗的约束条件分别为:
和,(5.12a),(5.12a),试问这类相互排斥的约束条件如何体现在模型中?
引入0-1变量:
和,因而,两个相互排斥的约束条件可用下列线性约束条件统一起来:
其中M是一个充分大的数。
若y1=1,而y2=0,即选用材料乙,由(5.12d)式得:
式(5.12c)自然成立;
若y1=0,而y2=1,即选用材料甲,由(5.12c)式得:
式(5.12d)自然成立.,【例5-9】固定费用问题。
有一种自然资源被用于生产三种产品,资源量、产品单件可变费用及售价、资源单位消耗量及组织三种产品生产的固定费用见表5-5。
要求制订一个生产计划,使总收益最大。
设xj表示三种产品的产量(j=1,2,3)。
引入0-1变量:
则问题的数学模型可归结如下:
如果生产第j种产品,则其产量xj0,由xjMjyj知,yj1。
因此,相应的固定费用在目标函数中将被考虑。
同理,如果不生产第j种产品,则其产量xj=0,由xjMjyj知,yj可以取0或1。
因此,相应的固定费用不应在目标函数中将被考虑。
二、0-1型整数规划的解法,0-1型规划是一类特殊的整数规划,因为变量只有0或1两个可能的取值,故最多有2n个可行解,理论上可以用枚举法进行求解。
但当n较大时,采用完全枚举法求解几乎是不可能的。
隐枚举法是求解0-1整数规划问题的一种比较简便的方法。
其实质也是一种分支定界法。
隐枚举法是是在2n个可能的变量组合中,只有一部分是可行解。
只要发现某个变量组合不满足其中一个约束条件,就不必再检验是否满足其它约束。
如所有约束条件都满足,就是0-1规划的一个可行解,可根据相应的目标函数值产生一个过滤条件,对于目标函数值劣于该可行解的变量组合不必再去检验其可行性。
在以后的求解过程中,如发现某个可行解比原来保留的可行解更优,则用它替换原来的过滤条件。
【例5-11】求解0-1整数规划,解:
求解过程可以用表5-7表示。
0,z0,5,z5,-2,3,3,8,z8,1,6,所以,最优解(x1,x2,x3)T=(1,0,1)T,maxz=8。
为了使最优解尽可能早出现,可先将目标函数中各变量的顺序按其系数大小重新排列,这样可进一步减少计算量。
例5-12给出了用隐枚举法求解0-1整数规划问题的一般步骤。
【例5-12】求解0-1整数规划,步骤1:
将问题转化为如下标准形式:
如目标函数为maxz,令,可化为。
如某个变量的系数为负,令,使系数变正。
其中cj0,且c1c2cn。
如约束条件为,两边同乘(-1);
如约束条件为等式,可令变量,代入目标函数和其它约束条件中,将xn消掉。
按目标函数中系数由小到大的顺序重新排列变量,并将约束条件中的排列顺序做相应改变。
调整后的0-1规划问题变为:
令所有变量取0,求出目标函数值,并代入约束条件中检查是否可行,如果可行即为问题的最优解;
否则转下一步。
令,得-10,但不满足两个约束条件。
分支和定界。
依次令各变量分别取0或1,将问题划分为两个子问题,分别检查是否可行,如不可行继续对边界值较小的子问题分支,直到找出一个可行解为止,这时得到值的一个上界。
分支过程见下图5-5所示:
若某个子问题的边界值对应原问题的可行解,则将它的边界值与保留的值作比较,并取较优的一个作为新的值。
如所有子问题都已考察完毕,则保留下来的值及其对应的解即为0-1整数规划问题的最优解。
若某个子问题的边界值大于保留下来的值,不管其是否可行,则将这一分支剪掉。
若某个子问题不可行,则将这一分支剪掉。
若某个子问题可行且边界值优于值,但该边界值对应的解不是可行解,则该问题待考察。
分支边界值=-6-4,但相应的解不可行,需继续分支。
过程见下图5-6所示。
上述求解过程也可用表格表示:
所以,最优解:
即原问题的最优解为:
第五节指派问题,一、指派问题的数学模型,指派问题又称分配问题,是指将m项工作分配n个工人去完成(通常mn),应如何分工使总工时或总费用最少的一类问题。
这类问题一般有两个要求:
一是每项工作只能由一个工人去完成;
二是每个工人只能完成一项工作。
这类问题的标准提法如下:
现有n项工作分配n个工人去完成,已知工人j完成工作i需要花费时间cij。
要求每项工作只能由一个工人去完成,每个工人只能完成一项工作。
应如何分工,使总工时最少?
在实际中经常会遇到这样的问题,有n项不同的任务,需要n个人分别完成其中的一项,但由于任务的性质和各人的专长不同,因此各人去完成不同的任务的效率(或花费的时间或费用)也就不同。
于是产生了一个问题,应指派哪个人去完成哪项任务,使完成n项任务的总效率最高(或所需时间最少),这类问题称为指派问题或分派问题。
建立该问题的数学模型,需引入n2个0-1变量。
设:
则该问题的数学模型可写为:
【例5-13】某工厂要生产四种产品,该工厂有四个车间都可以生产这四种产品。
但由于设备情况与技术情况不同,所以生产成本不同,其单位产品的生产成本如表5-9所示。
问应当怎样分配这四种产品到各车间,才能使总的生产成本最小?
试建立该问题的数学模型。
这是一个标准形式的指派问题。
这个问题的约束条件如下:
(1)每个车间只能生产一种产品,即:
则问题的数学模型可归结为:
(2)一种产品只能由一个车间生产,即:
(3)变量工xij必须等于0或1,即xij=0或1。
二、匈牙利算法,分配问题是0-1规划的特例,也是运输问题的特例,当然可用整数规划,0-1规划或运输问题的解法去求解,这就如同用单纯型法求解运输问题一样是不合算的。
库恩(W.W.Kuhn)于1955年提出了指派问题的解法,他引用了匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理:
系数矩阵中独立0元素的最多个数等于能覆盖所有零元素的最小直线数,习惯上称之为匈牙利解法。
分配问题最优解的以下性质:
若从系数矩阵(cij)的某行(或某列)各元素分别减去该行(列)的最小元素,得到新矩阵(cij),那么以(cij)为系数矩阵求得的最优解和利用原系数矩阵求得的最优解相同。
匈牙利算法的一般步骤可以表述如下:
变换系数矩阵。
先把系数矩阵各行分别减去本行的最小元素,再把各列分别减去本列的最小元素,使系数矩阵中各行各列都至少有一个零元素,且不出现负数。
在新矩阵中找尽可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。
找独立0元素,常用的步骤为:
从只有一个0元素的行(列)开始,给这个0元素加。
然后划去所在列(行)的其它0元素,记作;
这表示这列所代表的任务已指派完。
给只有一个0元素的列(行)中的0元素加;
然后划去所在行的0元素,记作。
反复进行
(1),
(2)两步,直到尽可能多的0元素都被圈出和划掉为止。
确定独立零元素。
若某行(某列)只有一个零元素,将该零元素加一个三角符号(),同时将该零元素所在列(行)的其它零元素划去。
如此反复进行,直到系数矩阵中所有零元素都被标注或被划去。
若仍有没有划圈的0元素,且同行(列)的0元素至少有两个,则从剩有0元素最少的行(列)开始,比较这行各0元素所在列中0元素的数目,选择0元素少的那列的这个0元素加。
若元素的数目m等于矩阵的阶数n,那么这指派问题的最优解已得到。
若mn,则转入下一步。
若独立零元素有n个,则令独立零元素位置对应的变量取1,其它变量取0,这样得到的矩阵X即为最优分配方案。
若独立零元素不足n个,转步骤3。
做能覆盖所有零元素的最少直线组合。
对没有标的行打“”;
对打“”行中被划掉的零元素所在列打“”;
对打“”列中标的零元素所在行打“”;
重复和,直到再也不能找到可打“”行或列为止。
对未打“”的行画一直线,对打“”的列画一直线,这样就得到覆盖所有零元素的最少直线组合。
继续变换系数矩阵。
取未被直线覆盖的元素中的最小值,令打“”行中各元素减去该最小值,同时令打“”列中各元素加上该最小值以消除负数。
【例5-14】已知指派问题的系数矩阵为:
首先,将各行分别减去本行的最小元素,然后对各列也如此,即:
4,1,2,3,其次,确立独立零元素。
因独立零元素有4个,故得到最优解:
最优解表明:
车间1生产产品1,车间2生产产品2,车间3生产产品3,车间4生产产品4,得到最优值为z412613。
【例5-15】已知指派问题的系数矩阵如下,用匈牙利算法求解。
首先,变换成本矩阵。
其次,确立独立零元素。
因独立零元素只有3个,故不能得到最优分配方案。
需要继续进行下面的步骤。
第三步,做能覆盖所有零元素的最少直线组合。
第四步,变换矩阵。
未被直线覆盖的元素中的最小值为2,将第一、四行各元素减2,再将第一列各元素加2,得到:
在新的系数矩阵中确定独立零元素。
由于独立零元素有4个,因此得到最优分配方案:
最优值minz9411428。
【例】有一份中文说明书,需译成英、日、德、俄四种文字,分别记作A、B、C、D。
现有甲、乙、丙、丁四人,他们将中文说明书译成不同语种的说明书所需时间如下表所示,问如何分派任务,可使总时间最少?
求解过程如下:
第一步,变换系数矩阵:
5,找到3个独立零元素,但m=3n=4,其次,确立独立零元素。
独立零元素的个数m等于最少直线数l,即lm=3n=4;
第四步,变换矩阵以增加0元素。
没有被直线覆盖的所有元素中的最小元素为1,然后打各行都减去1;
打各列都加上1,得如下矩阵,并转第二步进行试指派:
+1,第六节WinQSB软件应用,一、求解一般的整数规划问题,WinQSB软件在一般的整数规划中的应用是通过调用软件中的线性规划与整数线性规划(LinearProgrammingandIntegerLinearProgramming)实现的,【例5-17】利用WinQSB软件求解例5-5的整数规划问题。
具体操作过程如下:
启动线性规划与整数线性规划程序。
依次点击:
开始程序WinQSBLinearandIntegerProgramming,系统出现如图5-7的界面。
建立新的数据文件或打开已有的数据文件。
在图5-7中点File出现下拉菜单NewProblem(建立新问题)和LoadProblem(调用已有问题)。
点击FileNewProblem,系统出现如图5-8的界面。
在图5-8的界面中,输入变量的数目(NumberofVariables)、约束条件数目(NumberofConstraints),将变量类型设定为非负的整数变量(Nonnegativeinteger),其他选择默认项。
单击OK后,并输入数据,系统显示如图5-9所示的界面。
输入数据。
输入数据,系统出现如图5-9的界面。
问题求解。
在SolveandAnalyze的下拉菜单项中选择SolvetheProblem(求解不显示迭代过程),系统给出如图5-10所示的求解结果。
二、求解指派问题,WinQSB软件在指派问题中的应用是通过调用软件中的NetworkModeling实现的。
例5-16指派问题的WinQSB软件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划
![提示](https://static.bingdoc.com/images/bang_tan.gif)