大学精品课件：第六章 整数规划（3-4节）.ppt

1、第第1页页割平面法是由高莫瑞（割平面法是由高莫瑞（Gomory）于）于 1958 年提出的，年提出的，所以该方法又称为所以该方法又称为 Gomory 法。法。第第2页页思路：暂时不考虑整数规划的整数条件，思路：暂时不考虑整数规划的整数条件，而有规律而有规律地增加线性约束条件（在几何上称为割平面），使地增加线性约束条件（在几何上称为割平面），使得原可行域被切割掉一部分，但被切割掉的这部分得原可行域被切割掉一部分，但被切割掉的这部分不包含任何整数可行解。同时缩减后的可行域凸性不包含任何整数可行解。同时缩减后的可行域凸性不变。采取这样的方法，一直到获得整数规划的最不变。采取这样的方法，一直到获得整数

2、规划的最优解为止。优解为止。第第3页页通过举例来阐述割平面的概念通过举例来阐述割平面的概念。，整整数数、03576397max21212121xxxxxxxxz例：例：第第4页页25ADCB73x1x24可行域：可行域：ABCD 最优解：最优解：C点，其坐标为点，其坐标为)213,214(),(21 xx第第5页页在图中增加两个线性约束条件：在图中增加两个线性约束条件：PQ 和和 MN。增加割平面的目的：将原凸可行域增加割平面的目的：将原凸可行域 ABCD 缩减，变缩减，变成新的凸可行域成新的凸可行域 ABEFGD。使得新可行域的。使得新可行域的ABEFGD 顶点顶点 F（x1=4，x2=3）

3、对应着原整数线性）对应着原整数线性规划问题的最优解。规划问题的最优解。第第6页页25ADCB73MNPQx1x24GFE割去的部分割去的部分 EFGCE 中不包含任何整数解。中不包含任何整数解。第第7页页新增加的线性约束条件切割掉了原问题可行域的一新增加的线性约束条件切割掉了原问题可行域的一部分，但该可行域内不包含任何整数可行解，所有部分，但该可行域内不包含任何整数可行解，所有整数可行解全部都保留在被切割之后的可行域内。整数可行解全部都保留在被切割之后的可行域内。第第8页页故该约束条件具备如下两个基本性质：故该约束条件具备如下两个基本性质：已获得的不符合整数要求的松弛问题的最优解，已获得的不符

4、合整数要求的松弛问题的最优解，不满足该约束条件。不满足该约束条件。所有整数可行解都满足该约束条件。所有整数可行解都满足该约束条件。第第9页页具备上述两个基本性质的线性约束条件称为割平面具备上述两个基本性质的线性约束条件称为割平面约束或高莫瑞约束。约束或高莫瑞约束。现在面对的问题就是如何产生这样的割平面约束条现在面对的问题就是如何产生这样的割平面约束条件或高莫瑞约束。件或高莫瑞约束。第第10页页整数规划问题的模型：整数规划问题的模型：为为整整数数jjnjijijnjjjxnjxmibxaxcz,.,1,0,.,1,max11第第11页页 njxmibxaxczjnjijijnjjj,.,1,0,

5、.,1,max11松弛问题的模型：松弛问题的模型：松弛问题可以用单纯形法求解，在最优单纯形表中可松弛问题可以用单纯形法求解，在最优单纯形表中可得到：得到：第第12页页ikkikibxax 其中其中（Q 指构成基变量的号码集合）；指构成基变量的号码集合）；Kk （K 指构成非基变量的号码集合）指构成非基变量的号码集合）Qi（1）基变量基变量非基变量非基变量第第13页页将将 aik 和和 bi 都分解成整数部分都分解成整数部分 N 和非负真分数和非负真分数 f 之和：之和：aik=Nik+fik，其中，其中 Nik aik 且为整数，且为整数，0fik 1（2）bi=Ni+fi，其中，其中Ni b

6、i 且为整数，且为整数，0 fi 1 （3）可以为负整数可以为负整数 或或 0第第14页页ikkikibxax Nik+fikNi+fi第第15页页将式（将式（2）和式（）和式（3）代入式（）代入式（1）可得：）可得：iikkikkkikifNxfxNx （4）第第16页页将式（将式（4）的整数项移到等式左端，分数项移到）的整数项移到等式左端，分数项移到等式右端可得：等式右端可得：kkikiikkikixffNxNx（5）第第17页页对式（对式（5）进行分析：）进行分析：如果如果 xi 和和 xk 为整数解：为整数解：因为因为 Nik、Ni 均为整数，所以均为整数，所以为整数；为整数；ikki

7、kiNxNx 第第18页页因为因为 ，所以所以又因为又因为 必须为整数，必须为整数，所以所以 1 ikkikifxff kkikixff0 kkikixff0 ikf0 kx第第19页页由此可以得出整数解的必要条件为：由此可以得出整数解的必要条件为：0 kkikixff（6）第第20页页将式（将式（6）做如下变化：）做如下变化：ikkikfxf （7）约束条件（约束条件（7）就是割平面约束方程（或高莫瑞约）就是割平面约束方程（或高莫瑞约束方程）。束方程）。第第21页页下面来验证式（下面来验证式（7）是否满足割平面约束的两个性）是否满足割平面约束的两个性质：质：（1）设整数线性规划问题）设整数线

8、性规划问题 A 的松弛问题的松弛问题 B 的最优的最优解为解为 X*=（x1,xm,0,0）T，且，且 x1、xm中中有分数，则有分数，则 f1、fm 不全为不全为 0，代入式（，代入式（7）：）：第第22页页即已获得的不符合整数要求的松弛问题的最优解，即已获得的不符合整数要求的松弛问题的最优解，不满足该约束条件。不满足该约束条件。式（式（7）左端：）左端：0 kkikxf式（式（7）右端：）右端：ix 故式（故式（7）不满足。）不满足。10 if为分数为分数01 if第第23页页即所有整数可行解都满足该约束条件。即所有整数可行解都满足该约束条件。（2）设整数线性规划问题）设整数线性规划问题

9、A 的松弛问题的松弛问题 B 的最优的最优解为解为 X*=（x1,xm,0,0）T，且，且 x1、xm全全为整数，则为整数，则 f1、fm 全为全为 0，代入式（，代入式（7）：）：式（式（7）左端：）左端：0 kkikxf式（式（7）右端：）右端：0 if故式（故式（7）满足。）满足。第第24页页步骤步骤 1 求解整数线性规划问题求解整数线性规划问题 A 的松弛问题的松弛问题 B：B 没有可行解，没有可行解，A 也没有可行解，停止；也没有可行解，停止；B 有最优解，且符合整数条件，有最优解，且符合整数条件，B 的最优解就是的最优解就是 A 的最优解，停止；的最优解，停止；B 有最优解，但不符合整数条件，转步骤有最优解，但不符合整数条件，转步骤 2。第第25页页步骤步骤 2 构造割平面约束构造割平面约束 在在 B 的最优解中，比较不符合整数条件的各基变量的最优解中，比较不符合整数条件的各基变量值值 xi=bi=Ni+fi，其中，其中 Ni bi 且为整数，且为整数，0 fi 0 时：时：yi=1 约束才成立。约束才成立。xi=0 时：时：yi=0 约束才成立。约束才成立。