整理整数规划与matlab吴颖丹.ppt

在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式： 只要求出（LP5）和（LP6）的最优解即可。 分枝定界法 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求（LP5）,如图所示。此时E 在点取得最优解。 即 x1＝2, x2 =3, Z(5)＝－17 找到整数解，问题已探明，此枝停止计算。 E 求（LP6），如图所示。此时 F在点取得最优解。 x1＝3, x2 =2.5, Z(6)＝－31/2≈－15.5 Z(5) F 如对 Z(6) 继续分解，其最小值也不会低于－15.5 ，问题探明,剪枝。 分枝定界法 至此，原问题（IP）的最优解为： x1=2， x2 =3, Z* = Z(5) ＝－17 以上的求解过程可以用一个树形图表示如右： LP1 x1=1, x2=3 Z(1) ＝－16 LP x1=18/11, x2=40/11 Z(0) ＝－19.8 LP2 x1=2, x2=10/3 Z(2) ＝－18.5 LP3 x1=12/5, x2=3 Z(3) ＝－17.4 LP4 无可 行解 LP5 x1=2, x2=3 Z(5) ＝－17 LP6 x1=3, x2=5/2 Z(6) ＝－15.5 x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ＃ ＃ ＃ ＃ 分枝定界法 （一）、计算步骤： 1、用单纯形法求解( IP )对应的松弛问题( LP )： ⑴.若( LP )没有可行解，则( IP )也没有可行解，停止计算。 ⑵.若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 ⑶.若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 割平面法 2、从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程： 3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。 的小数部分 的小数部分 割平面法 例一：用割平面法求解整数规划问题 解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表： Cj 0 1 0 0 CB XB b x1 x2 x3 x4 0 x3 6 3 2 1 0 0 x4 0 -3 2 0 1 －Z 0 0 1 0 0 Cj 0 1 0 0 CB XB b x1 x2 x3 x4 0 x1 1 1 0 1/6 -1/6 1 x2 3/2 0 1 1/4 1/4 －Z -3/2 0 0 -1/4 -1/4 割平面法 此题的最优解为：X*= (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为: 也即： 割平面法 将 x3=6-3x1-2x2 , x4=3x1-2x2 ,带入 x1 x2 ⑴ ⑵ 3 3 第一个割平面 得到等价的割平面条件： x2≤ 1,见下图。 割平面法 Cj 0 1 0 0 0 CB XB b x1 x2 x3 x4 s1 0 x1 1 1 0 1/6 -1/6 0 1 x2 3/2 0 1 1/4 1/4 0 0 s1 -1/2 0 0 -1/4 -1/4 1 －Z -3/2 0 0 -1/4 -1/4 0 现将生成的割平面条件加入松弛变量，然后加到表中： CB XB b x1 x2 X3 X4 s1 0 x1 2/3 1 0 0 -1/3 2/3 1 x2 1 0 1 0 0 1 0 x3 2 0 0 1 1 -4 －Z -1 0 0 0 0 -1 割平面法 此时，X1 ＝(2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为： 用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 ≥ x2 ，见图： x1 x2 ⑴ ⑵ 3 3 第一个割平面 第二个割平面 割平面法 将生成的割平面条件加入松弛变量，然后加到表中： CB XB b x1 x2 x3 x4 s1 s2 0 x1 2/3 1 0 0 -1/3 2/3 0 1 x2 1 0 1 0 0 1 0 0 x3 2 0 0 1 1 -4 0 0 s2 -2/3 0 0 0 -2/3 -2/3 1 －Z -1 0 0 0 0 -1 0 CB XB b x1 x2 x3 x4 s1 s2 0