下载文档原格式
整数规划的求解方法有哪些在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。
例如，当变量代表的是机器的台数，工作的人数或装货的车数等。
为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。
实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。
在整数规划中，如果所有变量都限制为整数，则称为纯整数规划;如果仅一部分变量限制为整数，则称为混合整数规划。
整数规划的一种特殊情形是01规划，它的变数仅限于0或1。
不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。
组合最优化通常都可表述为整数规划问题。
两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。
有许多典型的问题反映整数规划的广泛背景。
例如，背袋(或装载)问题、固定费用问题、和睦探险队问题(组合学的对集问题)、有效探险队问题(组合学的覆盖问题)、旅行推销员问题, 车辆路径问题等。
因此整数规划的应用范围也是极其广泛的。
它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。
解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。
对每个衍生问题又伴随一个比它更易于求解的松弛问题(衍生问题称为松弛问题的源问题)。
通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。
随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。
目前比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。
0-1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。
整数规划的数学模型及解的特点整数规划IP (integer programming ）:在许多规划问题中,如果要求一部分或全部决策变量必须取整数。
例如,所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。
松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。
一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划（pure integer linear programming ）:指全部决策变量都必须取整数值的整数线性规划。
有时,也称为全整数规划.2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划（zero —one integer liner programming ）：指决策变量只能取值0或1的整数线性规划。
1 解整数规划问题0—1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi 称为0-1变量，或称为二进制变量.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z0—1型整数规划中0—1变量作为逻辑变量(logical variable ），常被用来表示系统是否处于某一特定状态,或者决策时是否取某个方案。
求解整数规划的方法整数规划是一种最优化问题，其解决方案限制了决策变量必须取整数值。
整数规划的应用非常广泛，涉及到许多实际问题，如制造业生产调度、物流优化、资源分配等。
在本文中，我们将介绍几种常用的整数规划方法。
一、分支定界法分支定界法是一种常用的整数规划求解方法，它通过不断将解空间分割为子问题并求解这些子问题，最终找到整数规划的最优解。
具体步骤如下：1. 初始时，将整数规划问题转化为一个线性规划问题，并求解线性规划问题的松弛解。
2. 如果松弛解满足整数约束条件，则找到一个整数解，更新当前最优解。
3. 如果松弛解不满足整数约束条件，则选择一个变量将其分割为两个子问题，并分别求解这两个子问题。
4. 对每个子问题，递归地应用上述步骤，直到找到一个整数解或者确定当前子问题的上界小于当前最优解。
5. 最终，得到整数规划的最优解。
分支定界法的优点是能够保证找到最优解，但其缺点是计算复杂度较高，特别是在问题规模较大时，会导致计算时间过长。
二、整数规划的近似算法当整数规划问题规模较大时，找到精确解的计算复杂度可能变得非常高，此时可以考虑使用近似算法来求解。
近似算法的思想是通过放松整数约束条件，将整数规划问题转化为一个线性规划问题，并对线性规划问题进行求解。
然后，根据线性规划问题的解，对整数规划问题进行修正，得到整数规划问题的一个近似解。
三、割平面法割平面法是一种常用的整数规划求解方法，它通过添加一系列线性不等式（割平面）来逐步减小可行解空间，最终找到整数规划的最优解。
具体步骤如下：1. 初始时，将整数规划问题转化为一个线性规划问题，并求解线性规划问题的松弛解。
2. 如果松弛解满足整数约束条件，则找到一个整数解，更新当前最优解。
3. 如果松弛解不满足整数约束条件，则根据当前松弛解所对应的目标函数值，添加一系列线性不等式（割平面）来限制可行解空间。
4. 对添加了割平面约束的线性规划问题，继续求解，并更新最优解。
5. 重复以上步骤，直到找到一个整数解或者确定当前问题的上界小于当前最优解。
第十一章整数规划方法整数规划的一般模型；整数规划解的求解方法；整数规划的软件求解方法；0-1规划的模型与求解方法；整数规划的应用案例分析。
一、整数规划的一般模型1. 问题的提出:固定资源分配问题设某企业有n 个生产车间需要m 种资源，对于第i 个生产车间分别利用第j 种资源ij x 进行生产，单位资源可以获得利润为ij r (1,2,,;1,2,,)i n j m == ．若第j 种资源的单位价格为(1,2,,)j a j m = ，该企业现有资金M 元.试问该企业应购买多少第j 种资源(总量为j X ），又如何分配给所属的n 个生产车间，使得总利润最大？固定资源分配问题解 设决策变量为(1,2,,;1,2,,)ij x i n j m == 表示分配给第i 个生产车间的第j 种资源的资源量，均为非负整数，第j 种资源的需求总量(1,2,,)j X j m = 也都为整数． 问题的目标函数为总利润求11n mij iji j z r x ===∑∑的最大值． 1111max ,(1,2,,),,s.t.0(1,2,,),0(1,2,,).n mij ij i j nij j i m j j j ij j z r x x X j m a X M x i n X j m =====⎧==⎪⎪⎪≤⎨⎪≥=⎪≥=⎪⎩∑∑∑∑ 且为整数且为整数2. 整数规划模型的一般形式一、整数规划的一般模型(A) ⎪⎩⎪⎨⎧⋅⋅⋅=≥⋅⋅⋅=≥=≤=∑∑==),,2,1(,0),,2,1(),(max(min)11n j x x m i b x a x c z j j i nj j ij nj jj 为整数 •问题是如何求解整数规划问题呢？•能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？•实际上，可借鉴这种思想来解决整数规划问题．1 .整数规划求解的总基本思想•松弛问题(A)中的约束条件,使构成易于求解的新问题---松弛问题(B)；•如果问题(B)的最优解是原问题(A)的可行解,则就是原问题(A)的最优解；•否则,在保证不改变松弛问题(B)的可行解的条件下,修正松弛问题(B)的可行域(增加新的约束),得到新问题(C)，再求问题（C)的解.•重复这一过程直到修正问题的最优解在原问题(A)的可行域内为止,即得到了原问题的最优解。
1 .整数规划求解的总基本思想(A) ⎪⎩⎪⎨⎧⋅⋅⋅=≥⋅⋅⋅=≥=≤=∑∑==),,2,1(,0),,2,1(),(max(min)11n j x x m i b x a x c z j j i n j j ij n j jj 为整数 (B) 11max(min)(,)(1,2,,)0(1,2,,)nj j j nij j i j j z c x a x b i m x j n ===⎧≤=≥=⋅⋅⋅⎪⎨⎪≥=⋅⋅⋅⎩∑∑ ！！注意：如果每个松弛问题的最优解不是原问题的可行解,则这个解对应的目标函数值z 一定是原问题最优值*z 的上界(最大化),即z z ≤*，或下界(最小化),即z z ≥*．（1）分枝定界法的思想2 .整数规划分枝定界法● 将原问题（Ａ）中整数约束去掉变为问题（Ｂ）,求出（Ｂ）的最优解.● 如果不是原问题（Ａ）的可行解，则通过附加线性不等式约束(整数)，将问题(B)分枝变为若干子问题),,2,1)((I i B i ⋅⋅⋅=，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，就得两个子问题. ●继续求解定界，重复下去，直到得到最优解为止。
2、整数规划的分枝定界法（2）分枝定界法一般步骤1)将原整数规划问题（A）去掉所有的整数约束变为线性规划问题（B），用线性规划的方法求解问题（B）:•问题(B)无可行解，则(A)也无可行解，停止；X，并是(A)的可行解，则此●问题(B)有最优解*解就是(A)的最优解，计算结束；●问题(B)有最优解*X，但不是(A)的可行解，转下一步。
2）将*X 代入目标函数，其值记为z ，并用观察法找出（A ）的一个可行解（整数解，不妨可取),,2,1(0n j x j ⋅⋅⋅==），求得目标函数值（下界值），记为z ，则（A ）的最优值记为*z ，即有z z z ≤≤*，转下一步； （2）分枝定界法一般步骤3) 分枝：在问题(B)的最优解中任选一个不满足整数约束的变量j j b x =，附加两个整数不等式约束：][j j b x ≤和1][+≥j j b x 到问题(B)中，构成两个新的子问题)(1B 和)(2B ，求)(1B 和)(2B 的解。
定界：对每一子问题的求解结果，找出最优值最小者为新的上界z ，从所有符合整数约束条件的分枝中找出目标函数值最大的为新下界z（2）分枝定界法一般步骤（2）分枝定界法一般步骤4）比较与剪枝：各分枝问题的最优值同z 比较，如果其值小于z ，则这个分枝可以剪掉，以后不再考虑。
如果其值大于z ，且又不是（A ）的可行解，则继续分枝，返回（3），直到最后得到最优解使z z =*，即),,2,1(*n j x j⋅⋅⋅=为最优解。
（1）割平面法的思想将原整数规划问题(A)去掉整数约束变为线性规划问题(B)，引入线性约束条件(称为Gomory约束，几何术语割平面)使问题(B)的可行域逐步缩小.每次切割掉的是问题非整数解的一部分，不切掉任何整数解，直到最后使目标函数达到最优的整数解成为可行域的一个顶点时，即问题最优解。
利用线性规划的求解方法逐步缩小可行域，最后找到整数规划的最优解。
（2）割平面法的一般步骤设原问题中有n 个决策变量，m 个松弛变量，共m n +个变量，略去整数约束求解线性规划问题. 设),,2,1(m i x i ⋅⋅⋅=表示基变量，),,2,1(n j y j ⋅⋅⋅=表示非基变量.1)在最优解中任取一个具有分数值的基变量，不妨是)1(m i x i ≤≤,则有i n j j ij i b y a x =+∑=1，即∑=-=n j j ij i i y a b x 1 （a ）2）将i b和ij a（为假分数）分为整数部分和非负的真分数，即),,2,1(,njfNafNbijijijiii⋅⋅⋅=+=+=，其中iN和ijN表示整数，而)10(<<iiff和)10(<≤ijijff表示真分数，代入（a）式，并将整数放在一边，分数放在一边，即∑∑==-=-+njjijijnjjijiyffNyNx11（b）3）要使ix和jy都有为整数，（b）式的左端必为整数，右端也是整数，而且由jijyf,0≥是非负整数，故此01≥∑=njjijy f，又因0>if是真分数，于是有11<≤-∑=injjijify ff，则必有1≤-∑=njjijiy ff（c）这就是所要求的切割方程（Gomory约束条件）。
４）对（c）引入一个松弛变量iS，则（c）变为injjijifyfS-=-∑=1将其加入原问题中去，求解新的线性规划问题.5）应用单纯形法求解，直到最优解为整数解为止，否则继续构造Gomory约束条件。
3、整数规划的LINGO 解法二、整数规划的求解方法MODEL: sets: row/1..m/:b; arrange/1..n/:c,x; link(row,arrange):a; endsets data:b=b(1),b(2),…,b(m); c=c(1),c(2),…,c(n); a=a(1,1),a(1,2),…,a(1,n),... ... ... ...a(m,1),a(m,2),…,a(m,n);enddata[OBJ] min=@sum(arrange(j):c(j)*x(j));@for(row(i):@sum(arrange(j):a(i,j)*x(j))>=b(i);); @for(arrange(j):x(j)>=0;);@for(arrange(j):@GIN(x(j)););END11min (1,2,,)0,(1,2,,)n j j j n ij j i j j j z c x a x b i m x x j n ===⎧≥=⋅⋅⋅⎪⎨⎪≥=⋅⋅⋅⎩∑∑为整数1、0-1整数规划的模型三、0-1 整数规划0-1规划一般模型: ∑==nj j j x c z 1max(min)⎪⎩⎪⎨⎧⋅⋅⋅==⋅⋅⋅=≥=≤∑=),,2,1(,10),,2,1(),(1n j x m i b x a ji n j j ij 或 如果整数线性规划问题的所有决策变量i x 仅限于取0或1两个值，则称此问题为0-1线性规划，简称为0-1规划。
三、0-1 整数规划2、指派（或分配）问题在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。
例如：某部门有n项任务，正好需要n个人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。
如何分派使完成n项任务的总效益为最高（效益量化），这是典型的分配问题。
现在不妨设有4个人，各有能力去完成4项科研任务中的任一项，由于4个人的能力和经验不同，所需完成各项任务的时间如右表：项目人员A B C D甲乙丙丁2109715414813141611415139问如何分配何人去完成何项目使完成4项任务所需总时间最少？建立模型：设ij x 表示第i 个人去完成第j 项任务，则⎩⎨⎧=项任务时个人不去完成第当第项任务时个人去完成第当第j i j i x ij ,0,1 每个人去完成一项任务的约束为 ⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++=+++111144434241343332312423222114131211x x x x x x x x x x x x x x x x 每一项任务必有一人完成的约束：⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++=+++111144342414433323134232221241312111x x x x x x x x x x x x x x x x目标函数：444342413433323124232221141312119118713161491514410413152min x x x x x x x x x x x x x x x x z +++++++++++++++=记系数矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=9118713161491514410411152ij c 称其为效益（价值）矩阵.ij c 表示第i 个人去完成第j 项任务时有关的效益（时间、费用、价值等）。
则目标函数可表示为ij i j ij x c z ∑∑===4141min⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧======∑∑==)4,3,2,1,(1034,2,1,14,3,2,1,14141j i or x j x i x ij ij i ij j故模型为：ij i j ijx cz ∑∑===4141min设指派问题有相应的系数矩阵()nn ijc ⨯，其元素ijc 表示分配第i 个人去完成第j 项任务时的效益（0≥），或者说：以ij c 表示给定的第i 单位资源分配用于第j 项活动时的有关效益。
