第5章整数规划–第1–4节.ppt

第5章 整数规划 第1节 整数规划问题的提出 LP问题中，有些最优解可能是分数或小数，但对于某些问题，要求解答必须是整数(称为整数解)，称这样的问题为整数规划(integer programming)，简称IP 如果所有的变量都限制为整数——纯整数线性规划或全整数线性规划 如果仅一部分变量限制为整数——混合整数规划 变量取值仅限于0或1——0-1规划 单纯形法求得的解经过“舍入化整”不能保证是整数最优解，如下例 它和LP问题的区别仅在于最后的条件⑤。 不考虑这一条件⑤，①～④称为与原问题相应的LP问题 很容易求得最优解为:x1=4.8，x2=0，max z=96 非整数的最优解“化整”： 将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，不满足条件②，因而它不是可行解； 将(x1=4.8，x2=0)凑整为(x1=4，x2=0)，是可行解，但不是最优解，因为当x1=4，x2=0, 时z=80，但当x1=4，x2=1(这也是可行解)时，z=90。 由上例看出，将其相应的线性规划的最优解“化整”来解原整数规划，常常得不到整数规划的最优解，甚至不是可行解。因此有必要对整数线性规划的解法进行专门研究。 第2节 分支定界解法 求解整数规划时，如果可行域有界，容易想到穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的。 对于大型的问题，可行的整数组合数很大时，穷举法是不可取的 我们希望仅检查可行的整数组合的一部分，就能定出最优的整数解，如分支定界解法 设有最大化的整数线性规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，而A的任意可行解的目标函数值将是z*的一个下界。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小上界和增大下界，最终求到z*。 第4节 0-1型整数线性规划 0-1变量——变量只能取0或1：逻辑变量，二进制变量 4.1 引入0-1变量的实际问题 投资场所的选定——相互排斥的计划 例4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai (i=1，2，…，7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大? 为减少运算量，按目标函数中各变量系数大小重新排列各变量，以便最优解较早出现，对于最大化问题系数由小到大排列，对于最小化问题则相反 上例可改写为 目标函数 max z=-2x2+3x1+3x5 约束条件： 2x2+x1-x3≤2 ① 4x2+x1+x3≤4 ② x2+x1≤3 ③ 4x2+x3≤6 ④ x1，x2，x3=0或1 ⑤ 最优解z=8第四步出现，原方法第六步才出现 例 min z=3x1+7x2-x3+x4 2x1-x2+x3-x4≥1 x1-x2+6x3+4x4≥8 5x1+3x2 +x4≥5 x1,x2,x3,x4=0或1 将其改写为 min z=7x2+3x1+x4-x3 -x2+2x1-x4+x3≥1 -x2+x1+4x4+6x3≥8 +3x2+5x1+x4 ≥5 x1,x2,x3,x4=0或1 只需30次运算，否则36次运算 最优解为(x2,x1,x4,x3)T=(0,1,1,1)T，min z=3 (3) 由于是IP问题，化标准型前决策变量取值为非负整数，化标准型后，引入的松弛变量和剩余变量也均为非负整数，对于 等式左边是整数，右边是不超过fi的整数，因为0＜fi＜1，右边是不超过0的整数： 这就是一个切割方程。 ① 切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。非整数最优解为(5-4)中的基变量Xi，非基变量Xk取0，不满足切割方程(5-7) ② 没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。 注：实际解题时，经验表明若从最优单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。 解题时先引入0-1变量xi(=1,2，…，7) 于是问题可列成： 2. 相互排斥的约束