运筹学第五章整数规划

第５章整数规划（割平面法）求解整数规划问题：Max Z=3x1+2x22x1+3x2≤144x1+2x2≤18x1,x2≥0，且为整数解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。

从而有：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9x1,x2≥0，且为整数利用单纯形法求解，得到最优单纯形表，见表1：表1最优解为：x1=13/4, x2=5/2, Z=59/4根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1)将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。

又因为x3,x4 0，所以必有：1/2-(1/2x3+1/2x4)<1由于(2)式右端必为整数，于是有：1/2-(1/2x3+1/2x4)≤0 (3)或x3+x4≥1 (4)这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：2x1+2x2≤11 (5)从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。

图1在(3)式中加入松弛变量x5，得：-1/2x3-1/2x4+x5=-1/2 (6)将(6)式增添到问题的约束条件中，得到新的整数规划问题：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9-1/2x3-1/2x4+x5=-1/2x i≥0，且为整数，i=1,2,…,5该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020max x x z += ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96max ,0,8.421===z x x 。

50用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z；而A 的任意可行解的目标函数值是*z的一个下界z，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040max x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82, =0z 356（见下图）。

运筹学5 整数规划* 用匈牙利法求解：最优解：即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项。

总分为：Z＝92＋95＋90＋80＝357 * 本章介绍了整数规划的数学模型的特征及其应用； 1．整数规划的最优解是先求相应的线性规划的最优解然后取整得到. 2．部分变量要求是整数的规划问题称为纯整数规划. 3．求最大值问题的目标函数值是各分枝函数值的上界. 4．求最小值问题的目标函数值是各分枝函数值的下界. 5．变量取0或1的规划是整数规划. 求解方法有：解一般整数规划用分枝定界法、割平面法；解0－1规划用隐枚举法；解指派问题用匈牙利法。

试一试，下例结论是否正确： * 6．整数规划的可行解集合是离散型集合. 7．将指派（分配）问题的效率矩阵每行分别加上一个数后最优解不变. 8．匈牙利法求解指派问题的条件是效率矩阵的元素非负. 9．匈牙利法可直接求解极大化的指派问题. 10．高莫雷（R..E.Gomory）约束是将可行域中一部分非整数解切割掉. 11．指派问题也是一个特殊的运输问题. 12．指派问题也可用运输问题求其最优解. 13．在用隐枚举求解具有n 个变量的0-1规划时需枚举2的n次幂个可能. The End of Chapter 5 下一章：图与网络 Exit 进入练习第*页 * 整数规划 Integer Programming 可分性假设?divisibility assumption 可加性假设 ?additivity assumption 比例性假设?proportionality assumption 0－1变量 binary variable BIP 0－1整数规划纯整数规划 pure Integer Programming 混合整数规划 mixed Integer Programming LP放宽 LP relaxation 分枝定界法 brabch and boundmethod 高莫雷 R．E．Gomory 过滤条件 filtering constraint 隐枚举法implicit enumeration 指派问题 assignment problem 边际收益递减decreasing marginal returns 第*页 * 作业：教材P135 T5.7 The End of Chapter 5 下一章：图与网络是非决策 yes－or－no decision 二选一约束either－or－constraints 互斥的选择 mutually exclusive alternative 相依决策 contingent decision * 分枝定界法的步骤： 1. 求整数规划的松弛问题最优解； 2. 若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步； 3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[[]xi]及xi≥[[]xi]+1组成两个新的松弛问题，称为分枝。

第五章整数规划1．整数规划的特点（1）整数规划：决策变量要求取整数的线性规划。

(2)整数规划可分为纯整数规划和混合整数规划.(3)整数规划的可行域为离散点集。

2．整数规划的建模步骤整数规划模型的建立几乎与线性规划模型的建立完全一致，只是变量的部分或全体必须限制为整数。

3．求解整数规划的常用方法1）分支定界法没有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作，而A的任意可行解的目标函数值将是z*的一个下界 ,分支定界法就是将B的可行域分成子区域的方法,逐步减小和增大，最终求得z*。

将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。

(1）解与整数规划问题A相应的线性规划问题B,可能得到以下几种情况之一：①B没有可行解，A也没有可行解，停止计算。

②B有最优解，并符合问题A的整数条件，则此最优解即为A的最优解，停止计算.③B有最优解，但不符合A的整数条件，记它的目标函数值为。

(2）用观察法找问题A的一个整数可行解，求得其目标函数值，并记作。

以z*表示问题A的最优目标数值，则≤z*≤。

下面进行迭代。

分支，在B的最优解中任选一个不符合整数条件的变量xi ，其值为bi。

构造两个约束条件xj ≤［bj] ①和xj ≥[bj]+1 ②其中[bj ]为不超过bj的最大整数。

将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。

不考虑整数约束条件求解这两个后继问题。

定界，以每个后继问题为一分支标明求解的结果。

第一步：先不考虑整数约束，变成一般的线性规划问题,用图解法或单纯形法求其最优解，记为）；第二步：若求得的最优解，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步;第三步:对原问题进行分支寻求整数最优解。

第四步：对上面两个子问题按照线性规划方法求最优解.若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍;否则,对该子问题继续进行分支。