整数规划ppt课件 (2).ppt

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

1、整数规划第1页第一节整数规划问题的提出第二节分支定界法第三节割平面法第四节0-1整数规划第五节指派问题第2页在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情况。第一节整数规划问题的提出第3页要求一部分或全部决策变量必须取整数值的线性规划问题称为整数线性规划（IntegerlinearProgramming，简称IP）。一、整数线性规划数学模型的一般形式第4页整数线性规划数学模型的一般形式为：第5页整数线性规划问题可以分为下列几种类型：1.纯整数（全整数）线性规划（pureint

2、egerlinearprogramming）：指全部决策变量都必须取整数值的整数线性规划。第6页2.混合整数线性规划（mixedintegerlinearprogramming）：指决策变量中有一部分必须取整数值，另一部份可以不取整数值的整数线性规划。3.0-1型整数线性规划（zero-oneintegerlinearprogramming）：指决策变量只能取值0或1的整数线性规划。第7页二、整数线性规划的松弛问题松弛问题（slackproblem）：不考虑整数条件，由余下的目标函数和约束条件构成的线性规划问题称为该整数

3、规划问题的松弛问题（slackproblem）。第8页整数线性规划松弛问题第9页maxz=2x1+3x2maxz=2x1+3x2整数规划松弛问题第10页1.整数线性规划的可行解集合是其松弛问题可行解集合的一个子集，即：三、整数线性规划的解和其松弛问题的解之间的关系整数规划可行域松弛问题可行域第11页整数线性规划的可行解集合其松弛问题可行解集合从而可得出：整数线性规划的可行解一定也是其松弛问题的可行解。松弛问题的可行解不一定是整数线性规划的可行解。整数线性规划最优解的目标函数值≤松弛问题最优解的目标函数值（极大化问题）。第

4、12页2.松弛问题的可行解集合：凸集（任意两个可行解的凸组合仍为可行解）整数线性规划的可行解集合：不是凸集（任意两个可行解的凸组合不一定满足整数要求，因而不一定仍为可行解）。第13页产生问题：利用对松弛问题的最优解中不符合整数要求的分量简单地取整，是否能得出整数规划问题的最优解呢？第14页3.对松弛问题的最优解中不符合整数要求的分量简单地取整，所得到的问题解：不一定是整数线性规划问题的最优解。甚至也不一定是整数线性规划问题的可行解。第15页例：第16页解：问题的最优解为：x1=4.8，x2=0其中分量x1不满足整数要求，

5、从而对分量x1进行“化整”：第17页为可行解，但不是最优解（x1=4,x2=1更优）第18页不满足约束条件1，从而为不可行解。第19页结论：利用求解整数线性规划的松弛问题的最优解，再化整的方法无法得出整数线性规划的最优解。第20页纯整数规划问题：可行解的数量是有限的。小型纯整数规划问题：可通过全枚举法，从中筛选最优解。大型纯整数规划问题：可行解的数量很大，无法使用全枚举法。混合整数规划问题：可行解的数量是无限的，无法使用全枚举法。第2节分支定界法第21页20世纪60年代由LandDoig和Dakin等人提出了一种仅检查可

6、行域内可行的整数组合的一部分，就能定出最优整数解的方法，称为分支定界法（branchandboundmethod）。一、分支定界法的提出第22页它是在枚举法基础上的改进，是一种隐枚举法（implicitenumeration）或部分枚举法，不是一种有效算法。第23页特点：它比枚举法优越，因为它仅在一部分可行解的整数解中寻找最优解，计算量比枚举法要小。但若变量数目很大，则其工作量也相当可观。第24页步骤1求解整数线性规划问题A的松弛问题B：B没有可行解，A也没有可行解，停止；B有最优解，且符合整数条件，B的最优解就是A的最

7、优解，停止；B有最优解，但不符合整数条件，转步骤2。二、分支定界法的步骤第25页步骤2分支和定界分支在B的最优解中任选一个不符合整数条件的变量xj=bj，并构造两个约束条件，并将这两个约束条件加入问题B，得到两个分支问题B1和B2，并求解这两个分支问题B1和B2。第26页A的下界=max{，max{符合整数条件的分支的目标函数值}}。令初始=0。定界第27页步骤3比较和剪枝：比较比较多个目标函数值大于且不满足整数要求的分支，选择目标函数值最大的分支继续分支，返回步骤2。第28页剪枝目标函数值小于且不满足整数要求的分支：停

8、止继续分支，即剪掉该枝。无可行解的分支：停止继续分支，即剪枝。满足整数要求的分支：停止分支，即剪枝。第29页例：求解第30页解：（1）利用单纯型法求解原问题的松弛问题B：cj2300θiCBXBbx1x2x3x40x3403[8]1050x42443018cj–zj5600第31页cj2300θiCBXBbx1x2x