第1节  整数线性规划问题的提出

       (1)用分支定界法求解整数线性规划(最大化)问题的步骤为：

       将要求解的整数线性规划问题称为问题A，

       将与它相应的线性规划问题称为问题B。

       (1) 解问题B，可能得到以下情况之一。

       ① B没有可行解，这时A也没有可行解，则停止。

       ② B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。

       ③ B有最优解，但不符合问题A的整数条件，记它的目标函数值为

       (2) 用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，…，n，试探，求得其目标函数值，以z*表示问题A的最优目标函数值；这时有进行迭代

       第一步：分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构造两个约束条件：xj≤［bj］和xj≥［bj］+1。将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，

       第二步：比较与剪支，各分支的最优目标函数中若有小于   者，则剪掉这支(用打×表示)，即以后不再考虑了。若大于   ，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，…，n。用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。

       第3节  割平面解法

       整数线性规划问题的可行域是整数点集（或称格点集），割平面解法的思路是：首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线性规划问题，若得到非整数的最优解，然后增加能割去非整数解的线性约束条件(或称为割平面)使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。这个方法是R.E.Gomory提出来的，所以又称为Gomory的割平面法。

       现把求一个切割方程的步骤归纳为：

      (1) 令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到

      (2) 将bi和αik都分解成整数部分N与非负真分数f之和，即：bi=Ni+fi，其中0＜fi＜1，αik=Nik+fik，其中0≤fik＜1，而N表示不超过b的最大整数。

      (3) 现在提出变量(包括松弛变量，参阅例3的注)为整数的条件(当然还有非负的条件).

      第4节   0-1型整数线性规划

      4.1 引入0-1变量的实际问题

      1. 投资场所的选定——相互排斥的计划

      2. 相互排斥的约束条件

      3. 关于固定费用的问题

      4.2  0-1型整数线性规划的解法

下载需要: 0 积分

附件：  第5章 整数线性规划-第1-4节.ppt