整数规划 割平面法 分枝定界法

《整数规划 割平面法 分枝定界法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学整数线性规划§1整数规划问题在前面的线性规划问题中，它的解都假设为可以取连续数值。但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮数等等。为了满足整数解的要求，比较自然的简便方法似乎就是把用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾取整”处理。当然，这样做有时确实也是有效的，可以取得与整数最优解相近的可行整数解，因此它是实际工作中经常采用的方法。但是实际问题中并不都是如此，有时这样处理得到的解可能不是原问题的可行解，有的虽是原问题的可行解，但却不是整数

2、最优解。（详见后面例1）。因而有必要专门研究只取整数解的线性规划的解法问题。在一个线性规划问题中，如果它的所有决策变量都要求取整数时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混合整数规划，二者统称为整数规划。整数规划的一个特殊情形是0-1规划，它的决策变量取值仅限于0或1两个逻辑值。整数规划是近几年发展起来的规划论的一个分支。下面我们举例说明对于整数规划问题，用“四舍五入”取整，或“舍尾取整”方法，是行不通的。例1现有甲、乙两种货物拟用集装箱托运，每件货物的体积、重量、可获利润，以及集装箱的托运限制如下表：货物体积（米3/件）

3、重量（万斤/件）利润（万元/件）甲乙54252010托运限制2413试确定集装箱中托运甲、乙货物的件数，使托运利润最大。设x1,x2分别表示甲、乙货物托运的件数（整数），则该问题的数学模型为：maxZ=20x1+10x2⑴5x1+4x2≤24　⑵2x1+5x2≤13　⑶x1,x2≥0，整数⑷这里货物的件数只能是整数，所以这是一个纯整数规划。若先不考虑整数限制，可求得问题的最优解为：x1=4.8，x2=0，maxZ=96由于x1=4.8不符合整数要求，所以该解不是整数规划的最优解。是否可以将非整数解用“四舍五入”方法处理呢？事实上，如果将x

4、1=4.8，x2=0近似为x1=5，x2=0，则该解不符合体积限制条件⑵：5x1+4x2≤24因而它不是最优解；那么用“舍尾取整”方法处理又如何呢？将x1=4.8，x2=0“舍尾取整”为x1=4，x2=0，显然满足各约束条件，因而它是整数规划问题的可行解，但它不是整数最优解。因为它对应的目标函数值Z=80，而x1=4，x2=1这个解亦是可行解，但它对应的目标函数值Z=90。由此例看出，简单的处理方法常常得不到整数规划的最优解，甚至得不到可行解。如何求得这类问题的整数最优解呢？到目前为止，整数规划还没有一种很满意的和有效的解法。现在用以求解

5、整数规划的方法基本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种方法——割平面法和分枝定界法。§2割平面法割平面法是1958年美国学者R.E.Gomory提出的求解纯整数规划的一种比较简便的方法，其基本思想是：先不考虑变量的整数限制求解线性规划，如果得到的解不是整数解，则不断增加适当的约束，割掉原可行域不含整数解的一部分，最终得到一个具有若干整数顶点的可行域，而这些顶点中恰有一个顶点是原问题的整数解。割平面法的基本步骤：步骤1不考虑变量的整数限制，求解相应的线性规划问题，如果该问题无解，或最优解已是整数解，则停止计算，否则转下一

6、步。步骤2对上述线性规划的可行域进行“切割”，去掉不含整数解的一部分可行域，即增加适当的线性约束，然后转步骤1。割平面法的关键在于如何确定切割方程，使之能对可行域进行真正的切割，而且切去部分不含有整数解点。下面讨论切割方程的求法。设与整数规划相对应的线性规划最优解中基变量XBi=（B-1b)i不是整数，将最优单纯形表中该基变量对应的行还原成约束方程，即XBi+ΣaijXj=（B-1b)i⑴将（B-1b)i，aij都分解成整数与非负真分数之和的形式，即（B-1b)i=Ni+fi其中0＜fi＜1⑵aij=Nij+fij其中0≤fij＜1⑶这里

7、Ni、Nij是整数，将⑵、⑶代入⑴，得XBi+Σ（Nij+fij）Xj=Ni+fi即XBi+ΣNijXj-Ni=fi-ΣfijXj⑷当诸Xi都是整数时，⑷式左端是整数，所以右端亦应是整数，但右端是两个正数之差，且∵0＜fi＜1，∴fi-ΣfijXj是小于1的整数，从从而fi-ΣfijXj≤0⑸取⑸式作为切割方程。因为任何整数可行解都满足这个方程，所以把它加到原问题的约束中，它能够对原可行域进行切割，而不会切割掉整数解。例3用割平面法求解maxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0，整数解：将问题标准化得maxZ=x1

8、+x2⑴-x1+x2+x3=1　⑵3x1+x2+x4=4　⑶x1,x2≥0⑷x1,x2整数⑸不考虑条件⑸，求解相应线性规划，结果见下表：C1100CBXBB-1bX1X2X3X400X3X41