文档介绍：第三章整数规划
整数规划问题的概念
分枝定界解法
割平面解法
0—1型整数规划
整数规划问题的概念
在前面讨论过的线性规划问题中,某些最优解是分数或小数,但对有些具体问题常要求解答必须是整数的情形(称为整数解)。我们称这样的问题为整数规划(Integer, Programming),简称IP。整数规划是近二十年发展起来的规划论中一个重要分枝。
纯整数规划:整数规划中如果所有的变量都限制为(非负)整数;
混合整数规划:如果仅一部分变量限制为整数;
0—1整数规划:所有决策变量取值仅限于0或1。
分枝定界解法
,解(IP)的相应线性规划问题(LP),可能有以下情况:
(1)若(LP)没有可行解,则(IP)也没有可行解。
(2)若(LP)有最优解,并符合(IP)的整数条件,则(LP)的最优解即为(IP)的最优解。
(3)若(LP)有最优解,但不符合(IP)的整数
条件,记(LP)最优解为Z0,转入下一步。
:记(IP)的目标函数最优值为Z*,以Z0为的Z*上界,记为Ẑ,再用观察法找(IP)一个整数可行解,其目标函数值作为下界,记为Z,则有: Ẑ≤Z* ≤ Z
:在(LP)最优解X0中,任选一个不符合整数条件的变量,例如xi=bi,以表示[bi]不超过bi的最大整数,构造两个约束条件:
xi ≤[bi] , xi ≥[bi]+1
将它们分别加入问题(IP) ,形成两个子问题(IP1)和(IP2) ,再解这两个子问题的线性规划问题(LP1)和(LP2)。
、下界:按照以下两点规则
(1)在各分枝问题中,找出目标函数值最大者作为新的上界;
(2)从已符合整数条件的分枝中,找出目标函数值最大者作为新的下界。
:各分枝的目标函数值中,若有小于下界Z者,则剪掉此枝,以后不再考虑。若大于Z,且不符合整数条件,则重复以上步骤,直到最后
Ẑ=Z*= Z
例: Max Z=3x1+2x2 2x1+x2≤9; 2x1+3x2≤14; x1,x2≥0; 且为整数。
先不考虑整数约束的条件,解相应的线性规划问题,得最优解为
x1= , x2= , z0= 则: Ẑ=;由题意取 Z =0; 0≤Z*≤
14/3
3
0
2
3
4
x1
x2
问题B
X1=,X2=,Z0=
0≤Z*≤
问题B1
X1=,X2=2,Z1=
问题B2
X1=,X2=3,Z2=
问题B4
X1=4,X2=1,Z4=14
问题B3
X1=3,X2=2,Z3=13
X2≤2
X2≥3
X1≤3
X1≥4
Z*=14
0≤Z*≤
14≤Z*≤14
这个方法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑对变量的整数要求,球的对应的线性规划问题的最优解。如果得到最优解是一个非整数解,构造一个新的约束条件(用几何术语,称为割平面),从原可行域中切割掉一部分,这部分只包含非整数解,但没有切割掉任何整数可行解。
这个方法就是指出怎样找到适当的割平面(不见得一次就找到),使切割后最终得到这样的可行域,它的一个有整数坐标的极点(顶点)恰好是问题的最优解。. Gomory提出来的,所以又称为Gomory的割平面法。
割平面解法
例:Max Z=x1+x2 -x1+x2≤1; 3x1+x2≤4; x1 ,x2 ≥0; 且为整数。
如不考虑整数约束,可求得相应的线性规划的最优解为:x1=3/4, x2=7/4, max z =10/4