《运筹学》第5章 整数规划(割平面法)

整数规划的割平面法计算流程与举例下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。

文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor.I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!整数规划中的割平面法计算流程与实例解析整数规划是运筹学中的一个重要分支，它涉及到在满足一系列线性约束条件下，寻找整数变量的最大值或最小值。

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020max x x z += ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96max ,0,8.421===z x x 。

50用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z；而A 的任意可行解的目标函数值是*z的一个下界z，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040max x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82, =0z 356（见下图）。

割平面法求解整数规划技巧割平面法是一种经典的求解整数规划问题的方法，它可以通过不断添加约束来逼近整数解，并最终找到最优解。

下面将介绍一些割平面法求解整数规划问题的技巧。

1. 初始化问题：割平面法的第一步是用线性松弛来求解相应的线性规划问题。

线性松弛问题忽略了约束条件中的整数要求，将其转化为一个线性函数的最优化问题。

通过求解线性松弛问题，可以获得一个最优解，并作为整数规划问题的一个可行解。

2. 添加割平面约束：如果线性松弛问题的最优解不是整数解，割平面法会添加一个新的约束条件来限制解的空间。

这个新的约束条件可以通过不等式来表示，例如 x1 + x2 ≤ 3。

通过添加这个不等式，割平面法将整数规划问题的可行区域缩小，从而更有可能得到一个整数解。

3. 求解线性松弛更新问题：添加割平面约束后，需要重新求解线性松弛问题，得到新的最优解。

如果新的最优解是整数解，则整数规划问题得到解决。

如果新的最优解不是整数解，则继续添加割平面约束，并重复这个步骤，直到找到整数解为止。

4. 割平面生成技巧：割平面法的关键在于如何选择适当的割平面约束。

以下是一些常用的割平面生成技巧：- Gomory割割平面：Gomory割是一种经典的割平面约束生成方法。

它利用线性规划的单纯形表达式中的非整数系数生成新的约束。

对于每个非整数系数cij，可以将其转化为一个新的不等式约束 cij xj ≤∑(cij - xi), 其中 xi 表示已经确定的整数变量的取值。

- 0-1割平面：0-1割平面方式适用于含有0-1变量（即只能取0或1值）的整数规划问题。

它可以通过适当选择0-1变量的线性组合来生成割平面约束。

- 最小割边集生成割平面：对于某些特殊问题，可以使用图论中的最小割边集生成割平面约束。

这种方法适用于有图结构的整数规划问题，通过找到图中的最小割边集，可以生成割平面约束来缩小解的空间。

5. 割平面法的终止条件：割平面法在每次迭代中都会找到一个更好的整数解并更新线性松弛问题。