第三章整数规划运筹学讲义.ppt

第三章 整 数 规 划 用单纯形法求解线性规划问题，其最优解往往是分数或小数．但对于某些实际问题，常要求全部或部分变量的最优解必须是整数．例如，所求的解是人数，机器台数或工厂个数等，若用分数或小数表示答案就显得不够合理． 在一个线性规划问题中，若要求全部变量取整数值，称为纯整数规划问题．若要求部分变量取整数值，称为混合整数规划问题．这两类问题简称为整数规划． 求解整数规划问题，初看起来好像很简单，比如把带有分数或小数的解进行“收尾”或“去尾”处理就可以了．事实上，这样处理有时行得通，有时却行不通．例如，某公司根据市场需要，用线性规划的方法得到一个方案是；增加甲产品的工厂3.7个，乙产品的工厂1.5个．如果用凑整方法求其解，则有四个近似方案：（4，1），（4，2），（3，1），（3，2），显然，这四个方案相互差别很大．对原线性规划问题来说，它们有的是可行解，有的则不是可行解；或虽是可行解，但不一定是最优解．因此，对求最优整数解的问题，有必要另行研究．然而时至今日，求解整数规划还没有一个很满意的有效的解法．下面介绍几种较为常用的方法 §3.1 分枝定界法 设有整数规划问题（A）为： 显然，问题（A）的可行解集是问题（B）的可行解集的子集．因而，（A）的最优值?（B）的最优值． 第一步 对线性规划（B）求解，其结果有下列三种情形： （1）（B）无可行解，这时（A）也无可行解，停止计算； （2）（B）有整数最优解，且符合（A）的整数条件，这时（B）的最优解就是（A）的最优解，停止计算； （3）（B）有最优解，而其解不全为整数．这时（B）的最优解不是（A）的可行解．但是，（B）的目标函数最优值（设为 ），是（A）的最优目标函数值S*的上界（求最小值时，为其下界）． 第二步 分枝与定界． 设线性规划问题（B）的最优解为 第三步 剪枝．在继续分枝的过程中，各分枝的最优目标函数值如果有小于S，则称这个分枝已被“查清”，将该枝剪掉，不再计算．因为再算下去不会得到更好的目标函数值． 若有目标函数值大于下界S，且不符合整数条件，则重复第二步骤，直到找到S*． 例 求解问题（A）： （2）分枝与定界 因x 1，x 2都是小数，可任选一个进行分枝．今选x 2=3.75，对问题（B0）增加约束条件： x 2?[3.75]=3和x 2?[3.75]+1=4, 则问题（B0）分解为两个子问题（B1）和（B2）（即两枝）． 求解线性规划问题（B1）和（B2），得到如下最优解： 问题（B1） x 1=3，x 2=3且s1=39． 问题（B2） x 1=1.8，x 2=4且s2=41． 问题（B1）都是整数解，该问题已经查清．然而（B1）虽都是整数解，但s1s2．这里s1=39可作为新的下界，s2=41可作为新的上界． 值得指出的是，增加了约束条件x 2≤3和x 2≥4之后，虽然缩小了可行解的范围，但原问题（A）的整数可行解没有变，这是因为在 3x 24内没有整数解，见2图． (3)重复步骤（2），继续对问题（B2）进行分解．因为在（B2）中x 1=1.8，对问题（B2）增加约束条件： x 1?[1.8]=1和x 1?[1.8]+1=2, 将问题（B2）再分解为两个子问题（B3）和（B4）： 求解线性规划问题（B5）和（B6），得到如下最优解： 问题（B5 ） x 1=1，x 2=4且S5=37； 问题（B6）x 1=0，x 2=5且S6=40． 问题（B5）和（B6）都是整数解，均属查清．但S5S1（下界），故将该枝剪去；又S1S6S3（上界），所以S6为原问题（A）的最优值，它对应的解为其最优解．计算终止． 综上所述，求解的全过程可用如下图所示的树形图表示． §3.2 割 平 面 法 割平面法是求解整数规划问题最早提出的一种方法．它的基本思想是：首先不考虑变量是整数的条件，但增加特定的约束条件（称为割平面），使得在原凸可行域中切掉一部分，被切割掉的这部分不包含任何的整数可行解．这样经过有限次的切割，最终可得到某个顶点的坐标恰好是整数，并且是问题的最优解． 割平面算法的基本类型有纯整数型和混合型．本节仅讨论纯整数型的割平面算法，它的基本要求是：每一个约束条件的所有系数及右端常数项都必须是整数．下面先讨论线性规划问题存在整数解的必要条件． §3.3 0一1规划 在整数规划中，如果所有决策变量xi只限于取0和1两个值，则称它为0一1规划问题．0一1规划的一个典型例子就是所谓“背包问题”： 一个旅行者，为了准备旅行的必备物品，要在背包里装一些最有用的东西．但他最多只能携带b公斤的物品．而每件物品都只能整件携带，于是他给每件物品规定了一定的“价值”，以表示其有用程度．如果共有m件物品，第i件物