整数规划方法ppt课件.ppt

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

1、第十一章整数规划方法第十一整数规划方法整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；0-1规划的模型与求解方法；整数规划的应用案例分析。1一、整数规划的一般模型21.问题的提出:固定资源分配问题3固定资源分配问题一、整数规划的一般模型在这个问题中，所求解均是整数，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了，实际上这常常是不行的，因为化整后不见得是可行解，或虽是可行解但不一定是最优解。这种求最优整数解的问题就是整数规划。整数规划中如果所有的变量都限制为（非负）整数，称为纯整数规划；如果仅一部分变量限制为整数

2、，称为混合整数规划；整数规划一种特殊的情形是0-1规划，它的变量取值仅限于0和1。452.整数规划模型的一般形式一、整数规划的一般模型问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题．61.分枝定界法的基本思想二、整数规划求解方法71.分枝定界法的基本思想继续求解定界，重复下去，直到得到最优解为止。二、整数规划求解方法82.分枝定界法一般步骤问题(B)无可行解，则(A)也无可行解，停止；二、整数规划求解方法92.分枝定界法一般步骤二、整数规划求解方

3、法102.分枝定界法一般步骤二、整数规划求解方法112.分枝定界法一般步骤二、整数规划求解方法分枝定界法.ppt123.割平面法的思想将原整数规划问题(A)去掉整数约束变为线性规划问题(B)，引入线性约束条件(称为Gomory约束，几何术语割平面)使问题(B)的可行域逐步缩小.每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即问题最优解。利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。二、整数规划求解方法考虑纯整数规划问题：设其中aij和bi皆为整数（若不为整数时，可乘上一

4、个倍数化为整数）。割平面法是R.E.Gomory于1958年提出的一种方法，它主要用于求解纯ILP。割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其基本思路为：若其松弛问题的最优解X*不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。为最终获得整数最优解，每次增加的线性约束条件应当两个基本性质：（1）已获得的不符合整数要求的LP最优解不满足该线性约束条件

5、，从而不可能在以后的解中出现；（2）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。例1用割平面法求解整数规划问题步骤1：标准化其松弛问题B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/4－1/41/41/4cj-zj00－1/2－1/2引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。步骤2：求一个割平面方程（1）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1，则含x1的约束方程为（2）将所选择的约束方程中非基变量

6、的系数及常数项进行拆分处理。具体规则是：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（3）式变为：很明显，（5）左端为整数，右端<1，则有其右端0，即（3）将上述约束方程（4）重新组合。组合的原则是：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得：等式左端实际上由三部分组成，常数项的整数部分，基变量及非基变量（含松弛变量或剩余变量），前两部分都是整数或应取整数，而松弛变量x3、x4由松弛问题标准型知，也应取非负整数（对于这一点，当原问题的约束方程组中的系数或常数项中有非整数时，要求将约束方程

7、先化为成整数系数及整数常数项，然后再标准化，就可满足）。（4）将割平面方程加到松弛问题的约束方程中，构成新的松弛问题并求解（对偶单纯形法）。割平面方程Cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj00－1/3－2/3注释：（1）本题注只用一次割平面就求得了最优解，但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数

8、最优解，则按步骤2中的4个步骤，在松弛问题的最终单纯形表中找出第二个割平面方程，将此割平面方程