运筹学(第5章割平面)_
- 格式:ppt
- 大小:2.29 MB
- 文档页数:48
第5章整数规划(割平面法)求解整数规划问题:Max Z=3x1+2x22x1+3x2≤144x1+2x2≤18x1,x2≥0,且为整数解:首先,将原问题的数学模型标准化,这里标准化有两层含义:(1)将不等式转化为等式约束,(2)将整数规划中所有非整数系数全部转化为整数,以便于构造切割平面。
从而有:Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9x1,x2≥0,且为整数利用单纯形法求解,得到最优单纯形表,见表1:表1最优解为:x1=13/4, x2=5/2, Z=59/4根据上表,写出非整数规划的约束方程,如:x2+1/2x3-1/2x4=5/2 (1)将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式,即:(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2把整数及带有整数系数的变量移到方程左边,分数及带有分数系数的变量称到方程右边,得:x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”,因此,在整数最优解中,x2和x4也必须取整数值,所以(2)式左端必为整数或零,因而其右端也必须是整数。
又因为x3,x4 0,所以必有:1/2-(1/2x3+1/2x4)<1由于(2)式右端必为整数,于是有:1/2-(1/2x3+1/2x4)≤0 (3)或x3+x4≥1 (4)这就是考虑整数约束的一个割平面约束方程,它是用非基变量表示的,如果用基变量来表示割平面约束方程,则有:2x1+2x2≤11 (5)从图1中可以看出,(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域,使点E(3.5,2)成为可行域的一个极点。
图1在(3)式中加入松弛变量x5,得:-1/2x3-1/2x4+x5=-1/2 (6)将(6)式增添到问题的约束条件中,得到新的整数规划问题:Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9-1/2x3-1/2x4+x5=-1/2x i≥0,且为整数,i=1,2,…,5该问题的求解可以在表1中加入(6)式,然后运用对偶单纯形法求出最优解。
割平面法的基本思想割平面法主要用于求解整数规划问题的方法。
1958年由美国格莫理提出。
基本思路是:先不考虑整数性约束,求解相应的线性规划问题。
若线性规划问题的最优解恰好是整数解,则此解即为整数规划问题的最优解。
否则,就增加一个新的约束条件,称为割平面。
割平面必须具有两条性质:(1)从线性规划问题的可行域中至少割掉目前的非整数最优解;(2)不割掉任何整数可行域,然后在缩小的可行域上继续解线性规划问题。
重复以上做法,经有限次切割后,必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。
混合整数线性规划(MILP)的割平面法通过将整数问题线性松弛为非整数线性问题,并对其进行求解,来求解MILP 问题。
线性规划理论说明,在温和的假定下(如果线性规划存在最优解,并且可行域不包含一条线),总存在一个极值点或顶点是最优的。
检验所获的最优解是否为整数解。
如否,则必然存在一线性不等式将最优点和真可行集的凸包分离。
找到这样的不等式是分离问题,而这样的不等式就是切割。
切割可以被加入到被松弛的线性规划中,使得当前的非整数解对松弛不再可行。
该过程不断重复,直到找到最优整数解。
用于普遍的凸连续优化和变体的割平面法有不同的名称:Kelley 法,Kelley-Cheney-Goldstein 法和捆绑法。
它们常用于不可微的凸最小化问题。
对于这类问题,通常的可微优化的梯度法无法使用,而使用这些方法可以高效地得到凸目标函数及其次梯度。
这种情况最常出现在双拉格朗日函数的凹优化中。
另一种常见情形是Dantzig-Wolfe分解应用于结构优化问题中,这类问题通常有含有指数级变量的表达式。
通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。
图1.割平面法例,如上图1,单位立方体与切割平面。
在三节点的旅行推销员问题中,该(弱)不等式表明每次旅行必须连接至少两个点。
2Gomory 切割切割平面法由Ralph Gomory 在19 世纪50 年代提出,用于解决整数规划和混合整数规划问题。
运筹学第五章作业题参考答案5.1 解:设在A j 处建Xj 幢住宅. 则数学模型为 Max z =∑=ni jx1⎪⎩⎪⎨⎧且为整数01≥≤≤∑=j jj ni jj x a x Ddx5.2 解:设每种毛坯截取Xj 根 则数学模型为 Max z =∑=ni jx1⎪⎩⎪⎨⎧≥≤∑=且为整数01jj j ni x l x a 5.4 解:设X i =⎩⎨⎧名队员不上场第名队员上场第i 0i 1数学模型为:Max Z =( 1.92X 1+1.92X 2+…+1.78X 8)/5⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≤+≤++≥++=+∑=5051211818264187621或i i i X X X X X X X X X X X X5.6 用割平面法解下列整数规划 (1) Max Z = X 1 + X 2 s.t⎪⎩⎪⎨⎧≥≤+≤+且为整数、0X 205462212121X X X X X 解:将其化为标准型为 Max Z = X 1 + X 2 s.t ⎪⎩⎪⎨⎧≥=++=++且为整数0,20546221421321X X X X X X X X从表中第二行产生割平面的约束条件: -1/3 X 3 - 1/3 X 43/2-≤ 引入松弛变量X 5为: -1/3 X 3 – 1/3 X 4 + X 5=-2/3∴X *=(0, 4)T 或 ( 2, 2)T , Z *=4(2) MinZ=51X +X 2⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+且为整数0,8859321212121X X X X X X X X 解: 化为标准型为 max z ‘=-51X -X 2⎪⎪⎩⎪⎪⎨⎧≥-=+---=+---=+--0,,,,8859354321521421321X X X X X X X X X X X X X X因此,原问题的最优解为X=( 0, 9 ) T ,最优值Z * = 9 5.7用分支定界法解下列整数规划 (1) Max Z=2X 1+X 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+-≤+且为整数0,21260521212121X X X X X X X X解:用图解法求得该整数规划的松弛问题的最优解为 X 1=X 2=21/8 选择X 1=21/8进行分支B1: B2: Max Z =2X 1+X 2 Max Z =2X 1+X 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤+≤+-≤+0,2212605211212121X X X X X X X X X ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤+≤+-≤+0,3212605211212121X X X X X X X X X 最优解为X 1=2 X 2=3 Z *=7; 最优解X 1=3 X 2= 3/2 Z *=15/2 > 7 选择X 2= 3/2进行分支B3 B4Max Z =2X 1+X 2 Max Z =2X 1+X 2⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≥≤+≤+-≤+0,132126052121212121X X X X X X X X X X ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≥≥≤+≤+-≤+0,223212605211212121X X X X X X X X X X 最优解为X 1=19/6 X 2=1 Z *=22/3 > 7; 无可行解 选择X 1=19/6 进行分支B5 B6 Max Z =2X 1+X 2⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤≥≤+≤+-≤+0,31321260521121212121X X X X X X X X X X X ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≥≤≥≤+≤+-≤+0,41321260521121212121X X X X X X X X X X X 最优解为X 1=3 X 2=1 Z *= 7; B6无可行解综上:原整数规划最优解为 X *= ( 2 , 3)或 ( 3 , 1) Z *=7 5.8 解下列0~1型 整数规划: (2) Max Z =2X 1+X 2- X 3⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥-+≤-+≤+≤++10,44225423,3,2132132132321或X X X X X X X X X X X X X X 解:最优解为X *=(1 , 0 , 0 )T Z *= 25.11(1) 解:引入一个虚拟人A 5,使之成为标准的指派问题,则系数矩阵为C = ⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0000071011151314129651214101178241110将各行元素减去本行的最小元素得C →⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0000003486974105734060298 = C ˊ由于只有4个独立零元素,小于系数矩阵阶数n=5,所以将第二行,第三行,第四行都减去1,第一列和第五列加上1得C ˊ→⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛---00012375863014623160298→⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛1000102376963005623070299= C 〞C 〞中有5个独立零元素,则可确定指派问题的最优指派方案。