运筹学-4、整数规划

1、1,第 5 章 整 数 规 划,第 一 节 整 数 规 划 问 题 的 数 学 模 型,2,例1：某集装箱运输公司，箱型标准体积24m3，重量13吨，现有两种货物可以装运，甲货物体积5m3、重量2吨、每件利润200元；乙货物体积4m3、重量5吨、每件利润100元，如何装运获利最多？,问题举例,解：设x1， x2分别为甲、乙两种货物的装运件数(当然是非负整数)，则建立该问题的整数线性规划(IP)模型如下：,3,（IP）：,此(IP)问题相应的线性规划问题(LP)为：,（LP）:,4,解此LP问题得解为： x1 =4.8， x2=0，maxz=960 显然它不是IP问题的可行解。,是不是可以把所得

2、的非整数的最优解经过“化整”就可得到符合整数条件的IP的最优解呢？,如将(x1 =4.8， x2=0)四舍五入凑整为(x1 =5， x2=0)，这样就不满足第一个约束条件，因而它不是可行解。,如将(x1 =4.8， x2=0)舍去小数凑整为(x1 =4， x2=0，Z0=800)，这当然满足各约束条件，因而是可行解，但不是最优解，因为 x1 =4， x2=1 (这也是可行解)的Z1=900。,5,整数规划图解法,Z=900,Z=960,A(4.8,0),B(4,1),6,图解法的启示,纯整数规划的可行解就是相应LP的可行域中的整数点。,非整数点不是IP的可行解，对于求解没有意义，故切割掉相应L

3、P的可行域中的非整数点，不妨碍整数规划问题的求解。,IP问题的最优解不优于相应LP问题的最优解。,A(4.8,0)点是相应LP问题的最优解，但不是IP问题的可行解，B(4,1)才是IP的最优解。,7,思路：设有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件按，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作 ；而A的任意可行解的目标函数值将是Z*的一个下界 。分支定界法就是将B的可行域分成子区域（分支）的方法。逐步减小 和增加 （定界），最终得到Z*。 也就是切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解。 方法灵活

4、且便于计算机求解。,第二节 分枝定界法,8,例2：求解整数规划,解：先求问题0相应的线性规划问题，,得最优解：,9,则 是问题0的一个上界，且,显然是问题0的一个下界，,即有 0 Z* 110/10,10,11,12,13,问题0 x1=6/5 x2=21/10 z0=111/10,=0 =111/10,x2 2,x2 3,问题1 x1=5/4 x2=2 z1=11,问题2 x1=1 x2=3 z2=9,=9 =11,x1 1,x1 2,问题3 x1=1 x2=2 z3=10,问题4 x1=2 x2=1/2 z4=19/2,=10 =11,Z*=10,分枝定界法的步骤：,1. 求整数规划的松弛

5、问题最优解； 2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步； 3.任意选一个非整数解的变量xi，在松弛问题中加上约束xixi及xixi+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； 4. 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。,【例3.5 】用分枝定界法求解例5.1,【解】先求对应的松弛问

6、题（记为LP0）：,用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。,8.33,10,松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,10,10,10,x1,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,LP1:X=(3,7.6),Z1=34.8,10,10,x1,x2,o,A,C,LP1,3,4,6,LP4:X=(4,6)

7、,Z4=34,LP5:X=(5,5),Z5=35,5,LP1:X=(3,7.6),Z1=34.8,LP3,LP5,尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。,上述分枝过程可用下图表示,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z1=34.8,LP2:X=(4,6.5) Z2=35.5,x13,x14,LP3:X=(4.33,6) Z3=35.33,x26,LP4:X=(4,6) Z4=34,LP5:X=(5,5) Z5=35,x14,x15,无可行解,x27,设纯整数规划,松弛问题,的最优解,3.2.2 求解IP的割平

8、面法,若 满足整数要求，则X就是IP问题的最优解；若 不全为整数，则X不是IP问题的可行解，自然就不是最优解。 用割平面法求解整数规划时，若其松弛LP问题的最优解X不满足整数要求，则从X的非整数分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则，重复上述步骤，直到获得整数最优解为止。,为最终获得整数最优解，每次增加的线性约束条件应当具备两个基本性质：其一是已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，从而不可能在以后的解中再出现；其二为凡整数可行解均满足该线性约束条件，因而整数

9、最优解始终被保留在每次形成的线性规划可行域中。,将 分离成一个整数与一个非负真分数之和：,则有,等式两边都为整数并且有,设xi不为整数，,加入松弛变量si得,此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。,将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。,则,（加入的线性约束满足两基本性质）,例如，,x1行：,移项：,令,加入松弛变量s1得,同理，对于x2行有：,【例3.6】 用割平面法求解下列IP问题,【解】 放宽变量约束，对应的松弛问题是,加入松弛变量x3及x4后，用单

10、纯形法求解，得到最优表3-3。,最优解X(0)(5/2，15/4),不是IP的最优解。选择表3-3的第一行(也可以选第二行)为源行,表3-3,分离系数后改写成,加入松弛变量x5得到高莫雷约束方程,将式(3.8)作为约束条件添加到表33中，用对偶单纯形法计算，如表34所示,最优解X(1)(3，3)，最优值Z21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。,表34,如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。,32,第三节 01规划问题,一、引入01变量的实际问题,1、投资场所的选定

11、相互排斥的计划,例3：某公司拟在城市的东、西、南三区建立门市部。拟议中有7个位置(点)Ai(i1,2,7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个; 在南区，由A6，A7两个点中至少选一个。,33,解: 先引于01变量xi(i1，2，7),令：,如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？,34,于是问题可表示为 ：,35,2、相互排斥的约束条件,在本章开始的例1中，关于运货的体积限制为：,今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用

12、船运时体积的限制条件为：,这两条件是互相排斥的。为了统一在一个问题中，引入01变量y，,（1）,（2）,36,于是上述问题可用下述条件来表示：,其中M是充分大的数，当y0时，上述条件(3)就是条件(1)，条件(4)自然成立，因而是多余的；当y1时，上述条件(4)就是条件(2)，条件(3)自然成立，因而是多余的。,令：,37,解01型整数规划最容易想到的方法就是穷举法。但一般穷举法计算量太大，下面介绍隐枚举法。,二、01型整数规划的解法,例4：求解01型整数规划：,38,解：先通过试探的方法找一个可行解，容易看出(x1, x2,x3)=(1,0,0)就是满足(1) (5)条件的，算出相应的目标函

13、数值 z3。,我们求最优解，对于极大化问题，当然希望z*3，于是增加一个约束条件(称为过滤条件):,这样，原问题的约束条件就变成5个。依次验证约束条件(0)(4)即可求出最优解。求解过程如下表：,39,于是求得最优解： (x1, x2,x3)=(1,0,1) ， max Z8,40,在计算过程中，若遇到Z值己超过条件(0)右边的值，应改变条件(0)，使右边为迄今为止最大者，然后继续做。例如，当检查点(0,0,1)时因Z5(3)，所以应将条件(0)换成：,这种对过滤条件的改进，可以减少计算量。,41,第四节 指派问题,我们经常遇到这样的问题，有n项任务要完成，恰好有n个人可以承担这些任务，但由于

14、任务性质和各人专长不同，各人完成各种任务的效率(或所费时间等)就有差别。因此提出下述问题：应当指派哪个人去完成哪项任务使总的效率为最高(或花费的总时间为最小)?这类问题称为指派问题(或称分派问题)。,42,例5：有一份说明书，要分别译成英、日、德、俄四种文字(分别称为任务E、J、G、R)，交由甲、乙、丙、丁四人去完成，每人完成一种，因各人专长不同，他们翻译成不同文字所需时间(小时数)如下表，问应指派哪个人去完成哪项任务可使总的花费时间为最小?,43,一般地，设第i个人完成第j项任务的时间(或效率、成本等)为cij0(i,j=1,2, n), 问应指派哪个人去完成哪项任务可使总的花费时间为最小?

15、,设：,则原问题的数学模型可表示为：,44,45,约束条件（1）说明第i人只能完成1项任务,约束条件(2)说明第j项任务只能由1个人来完成。,满足约束条件的可行解xi j也可写成表格或矩阵形式，例如例5的一个可行解就是:,记： 称为效率(系数)矩阵。,这个解矩阵(xij )中各行各列的元素素之和都是1，即各行各列都只有元素是1，其余都是0。当然，它不一定是最优解。,46,指派问题最优解的性质：如果从效率(系数)矩阵C=(cij)的一行(列)各元素分别减去(或加上)一个常数,最优解不变。,我们利用这性质，并结合例题，研究指派问题的一般解法。,第一步：使效率(系数)矩阵每行每列都有出现0元素，为此

16、，,(1)从系数矩阵的每一行都减去该行的最小元素， (2)再从所得矩阵的每一列减去该列的最小元素。,第二步：试求最优解。为此，按下述步骤进行。,47,经过第一步变换后，矩阵的每行每列都有了0元素，但我们希望能找出n个位于不同行不同列的0元素。如果能找到，则可得到最优解。,每一行都减去该行的最小元素后得：,对例5进行求解，先得到效率矩阵。,2,4,9,7,48,再从所得矩阵的每一列减去该列的最小元素后得：,试求最优解：寻找不同行不同列的0元素,4 2,由此得最优解：甲R、乙J、丙 E、丁 G。使总的花费时间最小为28。,49,例6： 甲乙丙丁四个人要完成A、B、C、D四项任务，不同的人做不同的工

17、作效率不同，问如何指派四个人去做四项工作使效率最高？,指派问题的一般解法匈牙利法,50,第一步 造0各行各列减其最小元素,51,第三步 打无 0 的行打，打行上 0 列打 ，打列上 0 行打，打行上 0 列打 ,52,第四步 划线无行、打列划线,第五步 造 0 直线未覆盖的元素，找 出最小值，未被直线覆盖的行减去这个最小值，被直线覆盖的列加上这个最小值，得到新的矩阵，返回第二步。,53,最优解:,最优目标值为15:,54,有关问题,非标准型的转化,M是足够大的常数， 新问题的最优解就是原问题的最优解。,55,应用举例,例8：(航班分派问题) 某航空公司经营A、B、C三个城市之间的航线，这些航线每天航班次起飞与到达时间如下表所示。设飞机在机场停留的损失费用大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需2小时准备时间，试决定一个使停留费用损失为最小的分派飞行方案。,56,57,解： 如果把从A、B、C城市起飞当作要完成的“任务”，那么到达的飞机可看作待分派去完成任务的“人”只要飞机到达后两小时，即可分派去完成起飞的任务，于是可以分别对城市A、B、C各列出一个指派问题的效率矩