9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 理学 >>

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

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


运 筹 学
整数线性规划

§1 整数规划问题
在前面的线性规划问题中,它的解都假设为可以取连续数值。 但是在许多实际问题中,决策变量仅仅取整数值时才有意义,比如 变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮 数等等。为了满足整数解的要求,比较自然的简便方法似乎就是把 用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾 取整”处理。当然,这样做有时确实也是有效的,可以取得与整数 最优解相近的可行整数解,因此它是实际工作中经常采用的方法。 但是实际问题中并不都是如此,有时这样处理得到的解可能不是原 问题的可行解,有的虽是原问题的可行解,但却不是整数最优解。 (详见后面例1)。因而有必要专门研究只取整数解的线性规划的 解法问题。 在一个线性规划问题中,如果它的所有决策变量都要求取整数 时,就称为纯整数规划;如果仅部分决策变量要求取整数则称为混 合整数规划,二者统称为整数规划。整数规划的一个特殊情形是0-1 规划,它的决策变量取值仅限于0或1两个逻辑值。整数规划是近几 年发展起来的规划论的一个分支。

下面我们举例说明对于整数规划问题,用“四舍五入”取 整,或“舍尾取整”方法,是行不通的。 例1 现有甲、乙两种货物拟用集装箱托运,每件货物的体 积、重量、可获利润,以及集装箱的托运限制如下表: 货物 体积(米3/件) 重量(万斤/件) 利润(万元/件) 5 2 20 甲 4 5 10 乙 24 13 托运限制 试确定集装箱中托运甲、乙货物的件数,使托运利润最大。 设x1,x2分别表示甲、乙货物托运的件数(整数),则该问题的 数学模型为: maxZ=20x1+10x2 ⑴ 5x1+4x2≤24 ⑵ 2x1+5x2≤13 ⑶ x1,x2≥0,整数 ⑷

这里货物的件数只能是整数,所以这是一个纯整数规划。若先不考 虑整数限制,可求得问题的最优解为: x1=4.8,x2=0, maxZ=96 由于x1=4.8不符合整数要求,所以该解不是整数规划的最优解。 是否可以将非整数解用“四舍五入”方法处理呢?事实上,如 果将x1=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。 由此例看出,简单的处理方法常常得不到整数规划的最优解, 甚至得不到可行解。 如何求得这类问题的整数最优解呢?到目前为止,整数规划还 没有一种很满意的和有效的解法。现在用以求解整数规划的方法基 本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种

§2 割平面法

割平面法是1958年美国学者R.E.Gomory提出的求解纯整数规 纯 划的一种比较简便的方法,其基本思想是:先不考虑变量的整数限 制求解线性规划,如果得到的解不是整数解,则不断增加适当的约 束,割掉原可行域不含整数解的一部分,最终得到一个具有若干整 数顶点的可行域,而这些顶点中恰有一个顶点是原问题的整数解。 割平面法的基本步骤: 步骤1 不考虑变量的整数限制,求解相应的线性规划问题,如 果该问题无解,或最优解已是整数解,则停止计算,否则转下一步。 步骤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 ⑶ 这里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≤1 3x1+x2≤4 x1,x2≥0,整数 解:将问题标准化得 maxZ=x1+x2 ⑴ -x1+x2+x3 =1 ⑵ 3x1+x2+x4=4 ⑶ x1,x2≥0 ⑷ x1,x2 整数 ⑸ 不考虑条件⑸,求解相应线性规划,结果见下表:

C CB 0 0 XB X3 X4 B-1b 1 4 0

1 X1 -1 3 1

1 X2 1 1 1

0 X3 1 0 0

0 X4 0 1 0

σ … …
1 1 X1 X2


3/4 7/4


1 0


0 1


-1/4 3/4


1/4 1/4

0 0 -1/2 -1/2 σ 表中x1=3/4,不是整数,将表中第一行还原成方程,即 x1-1/4x3+1/4x4=3/4 因为3/4=0+3/4,-1/4=-1+3/4,1/4=0+1/4 所以有 x1-x3=3/4-3/4x3-1/4x4 因而有切割方程: 3/4x3+1/4x4 ≥ 3/4 即 3x3+x4 ≥3 引入松弛变量x5,得方程 -3x3-x4+x5=-3 将新约束方程加到原最优表下面(切割),求得新的最优解如下 :

C CB 1 1 0 XB X1 X2 X5 B-1b 3/4 7/4 -3

1 X1 1 0 0 0

1 X2 0 1 0 0 0 1 0

0 X3 -1/4 3/4 -3 -1/2 0 0 1

0 X4 1/4 1/4 -1 -1/2

0 X5 0 0 1 0

σ
1 1 0 X1 X2 X3 1 1 1

1 0 0

1/3 -1/12 0 1/4 1/3 -1/3

0 0 0 -1/3 -1/6 σ 由于x1,x2的值已是整数,所以该题经一次切割已得最优解:

x1=1,x2=1,最优值:Z※=2

现在我们来看看切割方程 3x3+x4 ≥3 的几何意义。 例3对应的线性规划为 maxZ=x1+x2 -x1+x2≤1 3x1+x2≤4 x1,x2≥0 用图解法求得可行域D及最优解点A,见下图: x2 A(3/4,7/4) 由标准化的约束方程组可得 x3 =1+x1-x2 -x1+x2=1 D x4=4 -3x1-x2 B(1,1) 1 代入切割方程 得 3x1+x2=4 3(1+x1-x2)+(4-3x1-x2)≥3 即 x2≤1,将此切割方程 加入原约 x1 -1 0 1 束中,就等于切掉原可行域得 A1B部分,如图。 显然在A1B区域不含整数解点,对原可行域切割的结果是产生了一 个新顶点B,用图解法在新的可行域(黄色)中可求得整数最优解 恰是B(1,1)。

在求解实际问题中,割平面法经常会遇到收敛很慢的情 况,但若和其它方法,如分枝定界法,联合使用,一般能收 到比较好的效果。

§3 分枝定界法
分枝定界法是求解整数规划的常用算法,既可用来解全部变量 取值都要求为整数的纯整数规划,又可用以求解混合整数规划。 该算法的基本思路是:先不考虑整数限制,求出相应的线性规 划的最优解,若此解不符合整数要求,则去掉不包含整数解的部分 可行域,将可行域D分成D1、D2两部分(分枝) ,然后分别求解这 两部分可行域对应的线性规划,如果它们的解仍不是整数解,则继 续去掉不包含整数解的部分可行域,将可行域D1或D2分成D3与D4两 部分,再求解D3与D4对应的线性规划,……,在计算中若已得到一 个整数可行解X0,则以该解的目标函数值Z0作为分枝的界限,如果 某一线性规划的目标值Z≤ Z0 ,就没有必要继续分枝,因为分枝 (增加约束)的结果所得的最优解只能比Z0 更差。反之若Z> Z0 , 则该线性规划分枝后,有可能产生比Z0 更好的整数解,一旦真的产 生了一个更好的整数解,则以这个更好的整数解目标值作为新的界 限,继续进行分枝,直至产生不出更好的整数解为止。 下面以实例来说明算法的步骤。

例2 求解下面整数规划

x2 8

maxZ=40x1+90x2 ⑴ 9x1+ 7x2≤56 ⑵ 7x1+20x2≤70 ⑶ 4 x1,x2≥0 ⑷ x1,x2 整数 ⑸ 解:先不考虑条件⑸,求解相 0 应的线性规划问题L,得最优解 x1=4.81,x2=1.82,Z0=356(见图) 该解不是整数解。选择其中一个 非整数变量,如x1=4.81,对问题 L分别增加约束条件: x1≤4,x1≥5 将问题L分解为两个子问题L1,L2 (分枝),也就是去掉问题L不含 整数解的一部分可行域,将原可 行域D变为D1、D2两部分(如图)。

9x1+ 7x2=56 Z=40x1+90x2 D1
4

7x1+20x2=70
D2

6

10

x1

求解线性规划L1、L2 得最优解为: 问题L1: L+ x1≤4 x1=4.00 x2=2.10 Z1=349 问题L2: L+ x1≥5 x1=5.00 x2=1.57 Z2=341

因为没有得到整数解,所以继续对L1进行分解,增加约束: x2≤2,x2≥3将L1分解成问题L3与L4,并求得最优解如下: 问题L3: L1+ x2≤2 x1=4.00,x2=2.00 Z3=340 问题L4:L1+x2≥3 x1=1.42,x2=3.00 Z4=327

问题L3的解已是整数解,它的目标值Z3=340,大于问题L4的目标值, 所以问题L4已无必要再分枝。但由于问题L2的目标值Z2大于Z3,分解 L2还有可能产生更好的整数解,因此继续对L2分枝。增加约束 x2≤1,x2≥2 将L2分解成问题L5与L6,并求解,结果如下: 问题L5: L2+ x2≤1 问题L6:L2+x2≥2 x1=5.44,x2=1.00 Z5=308 无可行解

问题L5的Z5 =308< Z3=340 ,所以不必分解了;问题L6无可行解, 于是可以断定问题L3的解: x1=4.00,x2=2.00即为最优整数解。

整个分枝定界过程如下图所示:
问题L Z0=356 x1=4.81x2=1.82 x1≤4 问题L1 Z1=349 x1=4.00,x2=2.10 x2≤2 x2≥3 问题L3 问题L4 Z3=340 Z4=327 x1=4.00 x1=1.42 x2=2.00 x2=3.00 × Z※=340 x1≥5 问题L2 Z = 0, Z = 349 Z2=341 x1=5.00,x2=1.57 x2≤1 问题L5 Z5=308 x1=5.44,x2=1.00 ×
Z = 340, Z = 341 x2≥2

Z = 0, Z = 356

问题L6 无可行解 ×

用分枝定界法求解整数规划的步骤可总结如下: 步骤1:求解与整数规划相对应的线性规划L,若L无可行解, 则整数规划也没有可行解,计算停;若L的最优解是整数解,则该 解即为整数规划的最优解,计算停;若L的最优解不是整数解,则 转步骤2。 步骤2(分枝)在L的最优解中任选一个不符合整数条件的变量 XBi,其值为(B-1b)i,[(B-1b)i ]为小于(B-1b)i的最大整数,构造两 个约束条件 XBi ≤ [(B-1b)i ]和XBi≥ [(B-1b)i ] +1 将这两个约束条件分别加在问题L的约束条件上,形成两个子问题 L L1和L2,并求解L1和L2 。 步骤3(定界 )取整数解中最大目标值为界限值Z(下界),如果 计算中尚无整数解,则取Z=-∞。检查分枝Li,若它的最优解不是 整数解,且Zi>Z,则重复步骤2,若Zi≤Z,则Li不再分枝。 重复步骤2、步骤3,直至所有分枝都不能再分解为止,这时界 限值Z对应的整数解即为原问题的最优解。 用分枝定界法可解纯整数规划问题和混合整数规划问题。它比 穷举法优越,因为它仅在一部分可行的整数解中寻求最优解,计算 量比穷举法小。若变量数目很大,其计算工作量也是相当可观的。


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com