[经济学]第五章 整数规划1.ppt

例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。 * . 用图解法求出最优解 x1＝3/2, x2 = 10/3 且有Z = 29/6 x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)、 (2，3)、(1，4)、(2，4)。 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。 显然，它们都不可能是整数规划的最优解。 * . 因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（2，2）（3，1）点为最大值，Z=4。 目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的0－1规划问题采用隐枚举法 和匈牙利法。 * . （一）基本思路 考虑纯整数 问题： 整数问题的 松弛问题： 二、分枝定界法 * . maxZ=CX AX=b X?0 (A) IP maxZ=CX AX=b X?0 X为整数 (B) LP (B)为(A)的松弛问题。 * . 分枝定界法一般步骤： (1) 先解(A)的松弛问题(B) (2) ① (B)无可行解→(A)无可行解。 ② (B)最优解符合(A)要求，停。 ③ (B)最优解不符合(A)要求，转(3)。 (3) 估整数解S0 ，定界（上界、下界） (4) 选(B)解中不符合整数条件的分量Xj (Xj = bj ) 分枝，作(B)的后续问题(C)、(D)。 (C)：(B) 加约束Xj ?[bj]+1 (D)：(B) 加约束Xj? [bj] * . (6) 全部枝剪完，停 (5) 解(C)、(D) 剪枝条件: ① (C)，[(D)]无可行解 ② (C)（(D)）对应的目标值Sc (Sd) ? S0 （极大化） ③ (C)（(D)）对应的目标值Sc (Sd) S0 （极小化） 且解为整数解，令Sc (Sd) ? S0 且解为非整数解，令(C)，[(D)]取代 (B) 返回(4) * . 例1：用分枝定界法求解整数规划问题（用图解法计算） 记为（IP） 解：首先去掉整数约束，变成一般线性规划问题 记为（LP） 例题 * . 用图解法求（LP）的最优解，如图所示。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 对于x1＝18/11≈1.64， 取值x1 ≤1， x1 ≥2 对于x2 =40/11 ≈3.64，取值x2 ≤3 ，x2 ≥4 先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2 x1＝18/11, x2 =40/11 Z(0) =－218/11≈(－19.8) 即Z 也是（IP）最小值的下限。 * . 有下式： 现在只要求出（LP1）和（LP2）的最优解即可。 * . x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 先求（LP1）,如图所示。此时在B 点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此枝停止计算。 1 1 同理求（LP2） ,如图所示。 在C 点取得最优解。 即x1＝2, x2 =10/3, 　Z(2) ＝－56/3≈－18.7 B A C ∵Ｚ(2) Z(１)＝－16 ∴原问题有比（－16）更小的最优解，但 x2 不是整数，故利用 3 ≤10/3≤4 加入条件。 * . 加入条件： x2≤3, 　x2≥4 有下式： 只要求出（LP3）和（LP4）的最优解即可。 * . x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C 先求（LP3）,如图所示。此时在D 点取得最优解。 即 x1＝12/5≈2.4, x2 =3, Z(3)＝-87/5 ≈-17.4 Z(1)≈-16 但x1＝12/5不是整数，可 继续分枝。即 3≤x1≤2。 D 求（LP4），如图所示。 无可行解，不再分枝。 * . 在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式： 只要求出（LP5）和（LP6）的最优解即可。 * . x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求（LP5）,如图所示。此时在E 点取得最优解。