资源描述：
《算法大全第02章 整数规划.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章整数规划§1概论1.1定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。1.2整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：o1变量全限制为整数时，称纯（完全）整数规划。o2变量部分限制为整数的，称混合整数规划。1.2整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性
2、规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。例1原线性规划为minz=x+x122x+4x=5,x≥0,x≥0121255其最优实数解为：x=0,x=,minz=。1244③有可行解（当然就存在最优解），但最优解值变差。例2原线性规划为minz=x+x122x+4x=6,x≥0,x≥0121233其最优实数解为：x=0,x=,minz=。1222若限制整数得：x=1,x=1,minz=2。12（ii）整数规划最优解不能按照实数最优解简单取整而获得。1.3求解方法分类：（i）分枝定界法—
3、可求纯或混合整数线性规划。（ii）割平面法—可求纯或混合整数线性规划。（iii）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法—求解各种类型规划。下面将简要介绍常用的几种求解整数规划的方法。§2分枝定界法对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为
4、定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，-16-这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由LandDoig和Dakin等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，*若其最优解不符合A的整数条件，那么B的
5、最优目标函数必是A的最优目标函数z的*上界，记作z；而A的任意可行解的目标函数值将是z的一个下界z。分枝定界法就*是将B的可行域分成子区域的方法。逐步减小z和增大z，最终求到z。现用下例来说明：例3求解下述整数规划Maxz=40x+90x12⎧9x1+7x2≤56⎪⎨7x1+20x2≤70⎪x,x≥0且为整数⎩12解（i）先不考虑整数限制，即解相应的线性规划B，得最优解为：x=4.8092,x=1.8168,z=355.877912*可见它不符合整数条件。这时z是问题A的最优目标函数值z的上界，记作z。而*x=0,x=
6、0显然是问题A的一个整数可行解，这时z=0，是z的一个下界，记作z，12*即0≤z≤356。（ii）因为x,x当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x121进行分枝，把可行集分成2个子集：x≤[4.8092]=4，x≥[4.8092]+1=511因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：问题B：Maxz=40x+90x112⎧9x1+7x2≤56⎪⎨7x1+20x2≤70⎪0≤x≤4,x≥0⎩12最优解为：x=4.0,x=2.1,z
7、=349。121问题B：Maxz=40x+90x212⎧9x1+7x2≤56⎪⎨7x1+20x2≤70⎪x≥5,x≥0⎩12最优解为：x=5.0,x=1.57,z=341.4。121*再定界：0≤z≤349。（iii）对问题B再进行分枝得问题B和B，它们的最优解为11112-17-B:x=4,x=2,z=340111211B:x=1.43,x=3.00,z=327.14121212*再定界：340≤z≤341，并将B剪枝。12（iv）对问题B再进行分枝得问题B和B，它们的最优解为22122B:x=5.44,x=1.00
8、,z=308211222B无可行解。22将B,B剪枝。2122于是可以断定原问题的最优解为：*x=4,x=2,z=34012从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。（i）解问题B可能得到以下情况之一：（a）B没有可行解，这时A也没
