整数规划--.pptVIP

第4章 整数规划 第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*。 这从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。 选择x5为换出变量，计算 第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+5x3 约束条件： 2x2+x1-x3≤2 ① 4x2+x1+x3≤4 ② x2+x1≤3 ③ 4x2+x3≤6 ④ x1，x2，x3=0或1 ⑤ 因为? 2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，…， 这样，最优解容易比较早的发现。 再结合过滤条件的改进，更可使计算简化。 现在增加了过滤条件◎，如按下述方法进行，就可减少运算次数。将5个约束条件按◎～④顺序排好(表5-5)。对每个可能的解，依次代入约束条件左侧，求出数值，看是否适合不等式条件。如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。 求得最优解为： (x1，x2，x3)=(1，0，1), max 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 (2)