整数规划培训讲学.ppt

《整数规划培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情况。第一节整数规划问题的提出2要求一部分或全部决策变量必须取整数值的线性规划问题称为整数线性规划（IntegerlinearProgramming，简称IP）。一、整数线性规划数学模型的一般形式3整数线性规划数学模型的一般形式为：4整数线性规划问题可以分为下列几种类型：1.纯整数（全整数）线性规划（pureintegerlinearprogramming）：指全部决策变量都必须取整数值的整数线性规划。52.混合整数线性规划（mixedintegerli

2、nearprogramming）：指决策变量中有一部分必须取整数值，另一部份可以不取整数值的整数线性规划。3.0-1型整数线性规划（zero-oneintegerlinearprogramming）：指决策变量只能取值0或1的整数线性规划。6二、整数线性规划的松弛问题松弛问题（slackproblem）：不考虑整数条件，由余下的目标函数和约束条件构成的线性规划问题称为该整数规划问题的松弛问题（slackproblem）。7整数线性规划松弛问题8maxz=2x1+3x2maxz=2x1+3x2整数规划松弛问题91.整数线性规划的可行解集合是其松弛问题可

3、行解集合的一个子集，即：三、整数线性规划的解和其松弛问题的解之间的关系整数规划可行域松弛问题可行域10整数线性规划的可行解集合其松弛问题可行解集合从而可得出：整数线性规划的可行解一定也是其松弛问题的可行解。松弛问题的可行解不一定是整数线性规划的可行解。整数线性规划最优解的目标函数值≤松弛问题最优解的目标函数值（极大化问题）。112.松弛问题的可行解集合：凸集（任意两个可行解的凸组合仍为可行解）整数线性规划的可行解集合：不是凸集（任意两个可行解的凸组合不一定满足整数要求，因而不一定仍为可行解）。12产生问题：利用对松弛问题的最优解中不符合整数要求的分量

4、简单地取整，是否能得出整数规划问题的最优解呢？133.对松弛问题的最优解中不符合整数要求的分量简单地取整，所得到的问题解：不一定是整数线性规划问题的最优解。甚至也不一定是整数线性规划问题的可行解。14例：15解：问题的最优解为：x1=4.8，x2=0其中分量x1不满足整数要求，从而对分量x1进行“化整”：16为可行解，但不是最优解（x1=4,x2=1更优）17不满足约束条件1，从而为不可行解。18结论：利用求解整数线性规划的松弛问题的最优解，再化整的方法无法得出整数线性规划的最优解。19纯整数规划问题：可行解的数量是有限的。小型纯整数规划问题：可通过

5、全枚举法，从中筛选最优解。大型纯整数规划问题：可行解的数量很大，无法使用全枚举法。混合整数规划问题：可行解的数量是无限的，无法使用全枚举法。第2节分支定界法2020世纪60年代由LandDoig和Dakin等人提出了一种仅检查可行域内可行的整数组合的一部分，就能定出最优整数解的方法，称为分支定界法（branchandboundmethod）。一、分支定界法的提出21它是在枚举法基础上的改进，是一种隐枚举法（implicitenumeration）或部分枚举法，不是一种有效算法。22特点：它比枚举法优越，因为它仅在一部分可行解的整数解中寻找最优解，计算

6、量比枚举法要小。但若变量数目很大，则其工作量也相当可观。23步骤1求解整数线性规划问题A的松弛问题B：B没有可行解，A也没有可行解，停止；B有最优解，且符合整数条件，B的最优解就是A的最优解，停止；B有最优解，但不符合整数条件，转步骤2。二、分支定界法的步骤24步骤2分支和定界分支在B的最优解中任选一个不符合整数条件的变量xj=bj，并构造两个约束条件，并将这两个约束条件加入问题B，得到两个分支问题B1和B2，并求解这两个分支问题B1和B2。25A的下界=max{，max{符合整数条件的分支的目标函数值}}。令初始=0。定界26步骤3比较和剪枝：比较

7、比较多个目标函数值大于且不满足整数要求的分支，选择目标函数值最大的分支继续分支，返回步骤2。27剪枝目标函数值小于且不满足整数要求的分支：停止继续分支，即剪掉该枝。无可行解的分支：停止继续分支，即剪枝。满足整数要求的分支：停止分支，即剪枝。28例：求解29解：（1）利用单纯型法求解原问题的松弛问题B：cj2300θiCBXBbx1x2x3x40x3403[8]1050x42443018cj–zj560030cj2300θiCBXBbx1x2x3x46x253/811/8040/30x49[23/8]0-3/8172/23cj–zj11/40-3/40

8、31最优解为：（2）x1和x2均为分数，任选x1进行分支。cj2300θiCBXBbx1x2x3x46x28