运筹学11-整数规划I-11.pptVIP

第11讲 整数规划I 本讲提纲 1. 整数规划的数学模型及解的特点 2. 割平面法 3. 分枝定界法 1. 整数规划的数学模型及解的特点 在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。 整数规划的分类： 变量全限制为整数时，称纯(完全)整数规划 部分变量限制为整数的，称混合整数规划 变量只能取0或1时，称之为0-1(整数)规划 部分变量要求为0或1，称为0-1混合规划 解： 设x1, x2分别为甲、乙两种集装箱数量，z为可获得的总利润。显然x1, x2都须是非负整数，因此它是一个(纯)整数规划问题，其数学模型为： [例2](投资决策模型) 某公司有四个项目可供投资，由于该公司的资金和人员有限，需要从中作出选择。下表列出了各个项目对于资金、人员的需求以及将会产生的净现值情况。该公司计划总投资额为1100万元，可调用的工作人员一共有22人。关于投资的项目，还有一个附加条件，即项目1和项目4由于某些原因不得同时投资。请问，该公司应该如何制定投资决策？ 解：首先定义0-1变量： 投资的目的是使净现值最大，因此目标函数为 被选择项目所需的投资总额必须不超过总投资额，所以 人员约束： 其他约束：项目1和项目4不能同时选择 该投资问题的整数规划模型为 整数规划的解 2.割平面法 这个方法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑变量是整数这一条件，求解该整数规划的松弛问题。若得到的最优解不满足整数条件，则通过增加线性约束条件（用几何术语，称为割平面）将原可行域切割掉一部分，及改变可行解空间，直到问题的最优解满足整数条件。 注意：通过增加割平面对原问题的可行域进行切割，必须保证不会删除任何一个原始问题的整数可行解。 这个方法就是指出怎样构造适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是原整数规划问题的最优解。这个方法是R.E. Gomory提出来的，所以又称为Gomory割平面法。 下面，我们通过求解上面这个例题，来说明割平面是如何构造和使用的。 Gomory的割平面法自1958年被提出后，即引起人们广泛地注意。但至今完全用它解题的仍是少数，原因就是经常遇到收敛很慢的情形。但若和其它方法（如分枝定界法）配合使用，也是有效的。 3. 分枝定界法(BB法) 分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。 例6：求解下列整数线性规划问题 (ILP) 分枝 分枝定界法的基本步骤 求解问题B，可能会出现下列三种情况之一： ① B无可行解，则A亦无可行解，停止对此问题的计算； ② B有最优解，并满足整数约束，B的最优解即为A的最优解，计算完毕； ③ B有最优解，但不满足整数条件，记它的目标函数值为z，z 即为原问题A目标函数值的上界。 分枝定界法的计算过程： 1、对原问题A，求解其松弛问题B。根据上面分析，若出现情况①，②则停止计算。若情况③发生，得到A问题目标函数最优值的上界z。我们任找A问题的一个可行解，那么对应的目标函数值可以作为A目标函数最优值的一个下界z 。即得到 z ＜ z* ＜z 将生成的割平面条件加入松弛变量，然后加到单纯形表中： 0 2/3 -1/3 0 0 1 2/3 x1 0 0 1 0 0 1 0 1 x2 1 0 -4 1 1 0 0 2 x3 0 -1 -2/3 s1 0 -2/3 x4 0 1 s2 0 0 0 检验数 0 0 0 -2/3 s2 0 x3 x2 x1 b XB CB 1 0 -1 0 0 1 0 x1 0 3/2 0 -1 0 1 0 0 x2 1 -6 0 5 1 0 0 6 x3 0 0 1 s1 1 1 x4 -3/2 -3/2 s2 0 0 0 0 检验数 0 0 0 1 s1 0 x3 x2 x1 b XB CB -1/2 1 0 0 0 1 1 x1 0 0 1 0 0 1 0 1 x2 1 3/2 -5 0 1 0 0 1 x3 0 -1 1 s1 0 1 x4 0 -3/2 s2 0 0 0 检验数 0 0 0 1 x4 0 x3 x2 x1 b XB CB 至此得到最优表，其最优解为 x1=1, x2=1 这也是原整数规划问题的最优解。 解：(1) 首先求解该ILP问题的松弛问题LP