运筹学课件 第5章：整数规划

1、整数规划及其数学模型 分枝定界法 割平面法 0-1整数规划 指派问题 WinQSB软件应用,第五章 整数规划 (Integer Programming),第一节 整数规划及其数学模型,在很多实际问题中，有些变量的取值必须是整数 在一个规划问题中，如果它的某些变量（或全部变量）要求取整数，这个规划问题就称为整数规划问题，其中,如果所有变量都取整数，就称为纯整数规划或全整数规划 如果仅有一部分变量取整数，则称为混合整数规划 若变量值仅限于0或1，则称为0-1规划,一、问题的提出,在整数规划问题中，不考虑整数要求，由其他 约束条件和目标函数构成的规划问题称为该整 数规划问题的松弛问题。 若松弛问题是

2、一个线性规划问题，则其对应的 整数规划问题称为整数线性规划（ILP）。 本章所讨论的整数规划都是指整数线性规划。,（一）下料问题,【例5-1】某工地需要长度不同、直径相同的成套钢筋，每套钢筋由两根7米长和七根2米长的钢筋组成。现有15米的圆钢毛坯150根，应如何下料使废料最少？,(二)工厂选址问题,【例5-3】工厂A1和A2生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这种物资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（j=1,2,3,4）如下表所示,工厂A3或A4开工后，每年的生产费用估计

3、分别为1200万元或1500万元。现要决定应该建设A3还是A4，才能使今后每年的总费用最少。,(三)投资问题,【5-2】某投资公司可用于投资的资金是B，可供投资的项目有n个，项目j所需投资额和预期收益分别aj和cj。同时，由于种种原因，有三个附加条件： 第一，若选择项目1，就必须同时选择项目2，反之则不一定； 第二，项目3和项目4中至少选择一个； 第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,二、整数规划模型的一般形式及解的特点,求解整数规划问题,分析：考虑对应的线性规划问题(LP),整数规划解的性质,用单纯形法解（如表所示），获得最优解,初始表,最

4、终表,可见，最优解为x1=3.25 x2=2.5 z(0) =59/4=14.75,变量不为整数，显然（LP）的最优解不是（IP）的最优解,怎么办？,凑整：(4, 3), (4, 2), (3, 3), (3, 2) (4, 3), (4, 2), (3, 3)均不可行 (3, 2)对应的目标函数值 z=13 但(4, 1)对应的目标函数值 z=14 可见，直接凑整得到的解不见得是可行解；或者虽是可行解，但不一定是最优解 故需要对整数规划问题发展新的解法 分枝定界法 割平面法 分配问题的匈牙利法 0-1规划的隐枚举法,(a),(b),(5/3,5/2),第二节 整数规划的解法 分枝定界法,【例

5、5-7】求解整数规划问题,【思考】 （IP）的可行域与（LP）可行域的关系如何？ （IP）的最优解是否会优于（LP）的最优解？ 若（LP）有最优解，且其最优解为整数，则它是否也是（IP）的最优解？ 若（LP）有最优解，但其最优解不是整数，怎么办？ 假设已知（IP）的一个整数可行解，则（IP）的最优解与该解有怎样的关系？,适用范围 全整数规划问题或混合整数规划问题 本世纪60年代初由Land Doig和Dakin等人提出 基本思路 设有最大化的整数规划问题(IP)，与它相应的线性规划问题为(LP)松弛问题。从解(LP)开始，若其最优解不符合整数条件，那么(LP)的最优目标函数必是(IP)最优解z

6、*的一个上界，记作z ;而(IP)的任意可行解的目标函数值将是z*的一个下界z 。分枝定界法就是将(LP)的可行域分成子区域（分枝），逐步减小z 和增大z ，最终求得z*的方法。,【例5-7】,考虑全整数规划问题：,整数规划的松弛问题：,步骤：,1、先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： ( LP )没有最优解，则( IP )也没有最优解，停止计算； 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算； 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。为讨论方便，设( LP

7、)的最优解为：,2、定界： 记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上界，记为 Z(0) 。再用观察法找到一个整数可行解 X，并以其相应的目标函数值 Z作为Z* 的下界，记为Z Z（取xj = 0），则有： Z Z* 。,4、修改上、下界：(按照以下两点规则进行) 在各分枝问题中，找出目标函数值最大者作为新 的上界； 从已符合整数条件的分枝中，找出目标函数值最 大者作为新的下界。,5、比较与剪枝 ： 各分枝的目标函数值中，若有小于Z 者，则剪掉此枝， 表明此子问题已经探清，不必再分枝了;否则继续分枝 。,如此反复进行，直到得到ZZ* 为止，即得最优解 X*,解:用单纯形

8、法解对应的(LP)问题,如表所示,获得最优解,初始表,最终表,可见，最优解为x1=3.25 x2=2.5 z(0) =59/4=14.75,例1、用分枝定界法求解整数规划问题,选 x2 进行分枝，即增加两个约束x22 和x2 3 ，则,分别在(LP1)和(LP2)中引入松弛变量x5和x6 ，将新加约束条件加入上表计算，即 x2+ x5= 2 , x2+x6=3 得下表:,x1=7/2, x2=2 Z(1) =29/2=14.5 继续分枝， 加入约束 x1 3, x1 4,LP1,LP2,x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝,接(LP1)继续

9、分枝，加入约束 x1 3和x1 4 ，则,分别引入松弛变量x7 和 x8 ，然后进行计算,x1=3, x2=2 Z(3) =13 找到整数解，问题已探明，停止计算,LP3,x1=4, x2=1 Z(4) =14 找到整数解，问题已探明，停止计算 因为z(4)z(3), 故x1=4, x2=1 为最优解,LP4,树形图如下：,LP1 x1=7/2, x2=2 Z(1)29/2=14.5,LP x1=13/4, x2=5/2 Z(0) 59/4=14.75,LP2 x1=5/2, x2=3 Z(2)27/2=13.5,LP3 x1=3, x2=2 Z(3) 13,LP4 x1=4, x2=1 Z(

10、4) 14,x22,x23,x13,x14,例2、用分枝定界法求解整数规划问题（图解法计算）,记为（IP）,解：首先去掉整数约束，变成一般线性规划问题,记为（LP）,用图解法求（LP）的最优解，如图所示,x1,x2,3,3,(18/11,40/11),对于x118/111.64， 取值x1 1， x1 2 对于x2 =40/11 3.64，取值x2 3 ，x2 4 先将（LP）划分为（LP1）和（LP2）,取x1 1, x1 2,x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是（IP）最小值的下限,有下式：,现在只要求出（LP1）和（LP2）的最优解即可,

11、同理求（LP2） ,如图所示 在C 点取得最优解 即x12, x2 =10/3, Z(2) 56/318.7 Z(2) Z(0) 原问题目标函数值的下界为-18.7 x2 不是整数，故利用3 10/34 加入条件,x1,x2,3,3,(18/11,40/11),先求（LP1）,如图所示。此时，在B 点取得最优解 x11, x2 =3, Z(1)16 找到整数解，问题已探明，此枝停止计算。且由此可知目标函数最优值的上界为-16,1,1,B,A,C,加入条件： x23, x24 有下式：,只要求出（LP3）和（LP4）的最优解即可,x1,x2,3,3,(18/11,40/11),1,1,B,A,C

12、,先求（LP3）,如图所示。此时D 在点取得最优解 即 x112/5=2.4, x2 =3, Z(3)-87/5=-17.4-18.7 但x112/5不是整数，可继续分枝。即 3x12,D,求（LP4），如图所示 无可行解，不再分枝,在（LP3）的基础上继续分枝。加入条件3x12有下式：,只要求出（LP5）和（LP6）的最优解即可,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求（LP5）,如图所示。此时E 在点取得最优解 即 x12, x2 =3, Z(5)17 找到整数解，问题已探明，此枝停止计算。,E,求（LP6），如图所示。此时 F在点取得最优解 x13,

13、x2 =2.5, Z(6)31/2=15.5 Z(5),F,如对Z(6) 继续分解，其最小值也不会低于15.5，问题探明,剪枝,至此，原问题(IP)的最优解为： x1=2， x2 =3, Z* = Z(5) 17 以上的求解过程可以用一个树形图表示如右：,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP3 x1=12/5, x2=3 Z(3) 17.4,LP4 无可 行解,LP5 x1=2, x2=3 Z(5) 17,LP6 x1=3, x2=5/2 Z(6) 15.5,x

14、11,x12,x23,x24,x12,x13,练习：用分枝定界法求解整数规划问题,x11,x12,x22,x23,x12,x13,一、计算步骤 1、用单纯形法求解( IP )对应的松弛问题( LP ) 若( LP )没有最优解，则( IP )也没有最优解，停止计算； 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算； 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。,第三节 整数规划的解法 割平面法,2、从(LP)的最优解中，任选不为整数的分量xi ,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，

15、并以该行为源行，作割平面方程,割平面方程,3、将由割平面方程得到的约束条件作为一个新的约束条件置于最优单纯形表中，用对偶单纯形法求出新的最优解，返回1。,例1 、用割平面法求解整数规划问题,解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：,此题的最优解为：X =(13/4 ,5/2) 。但不是整数最优解，引入割平面。可以使用的割平面的条件有:,为加快割平面的速度，一般选择较大的 fi 作为割平面方程进行计算,现将生成的割平面条件加入松弛变量，然后加到表中,割平面方程为:,【例5-7】求解整数规划问题,【练习】求解整数规划问题,01整数规划是一种特殊形式的整数规划，这时的

16、决策变量xi 只取两个值0或1，一般的解法为隐枚举法,【例5-11】求解下列01规划问题,第四节 0-1整数规划,由上表可知，问题的最优解为 X*=( x1=1， x2=0， x3=1 ),解：对于01规划问题，由于每个变量只取0、1两个值，一般会用穷举法来求解，即将所有的0、1组合找出，使目标函数达到极值要求就可求得最优解。,由上表可知： x1 =0，x2=0，x3=1是一个可行解，为尽快找到最优解，可将3x12x25x35作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。,问题的最优解为 X*=( x1 =1，x2=0，x3=1 ),隐枚举法,如果重新排列变量的顺序可使问题更快地求

17、得最优解，如：,问题的最优解为 X*=( x1=1，x2=0，x3=1 ),【例】求解下列01规划问题,解：令 x11x1, x2=1- x2, x4=1- x4，则目标函数变为,此时，x*=(1, 0, 1, 0)，z*=-2,练习：求解下列01规划问题,所以， 原问题的最优解为： X*(0, 0, 1, 0, 0)，Z*=8,第五节 指派问题,在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，指派哪个人去完成哪项任务，可使完成 n 项任务的总效

18、率最高（或所需时间最少）？这类问题称为指派问题或分配问题。,每一项工作只能分配给一个人； 每一个人只能并且必须接受一项工作,一、指派问题的一般提法,【5-13】某工厂要生产四种产品，该工厂有四个车间都可以生产这四种产品。但由于设备情况与技术情况不同，所以生产成本不同，其单位产品的生产成本如表所示。问应当如何分配这四种产品到各车间，才能使总的生产成本最小？试建立该问题的数学模型。,解 引入0-1变量xij (i, j1,2,3,4,5)，令：,这个问题的约束条件如下：,(1)一个车间只生产一种产品，即,(2)一种产品只由一个车间生产，即,(3)变量工xij 必须等于0或1，即xij =0或1。,

19、目标函数为：Min,其数学模型为：,设n个人被分配去做n件工作，规定每个人只做一件工作,每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（ 时间或费用）为cij (i =1, 2, , n; j =1, 2, , n)并假设cij 0。问应如何分配才能使总效率（ 时间或费用）最高？,效率矩阵（成本矩阵）:(cij )nn,二、匈牙利法,分配问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，但这些方法却没有充分利用指派问题的特点。,库恩(W.W.Kuhn)于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格(D.Konig)的关于矩

20、阵中独立零元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有零元素的最小直线数，习惯上称之为匈牙利解法。,分配问题最优解的以下性质：若从系数矩阵(cij )的某行(或某列)各元素分别减去该行（列）的最小元素，得到新矩阵(cij),那么以(cij)为系数矩阵求得的最优解和利用原系数矩阵求得的最优解相同。,证明,设成本矩阵第一行各元素均减去同一个数k，得到的新矩阵记为(cij ),第一步：变换成本矩阵，使每行每列中至少出现一个0元素 (1) 令(cij) nn的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。,匈牙利法的步骤（以例5-13为例）,第二

21、步：试求最优解 在新矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1) 从只有一个0元素的行(列)开始，给这个0元素加，记作 。然后划去 所在列(行)的其它0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了； (2) 给只有一个0元素的列(行)中的0元素加，记作 ；然后划去 所在行的0元素，记作 ； (3) 反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止；,0,0,0,0,(4) 若仍有没有划的0元素，且同行(列)的0元素至少有两个，则从剩有

22、0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加(表示选择性多的要“礼让”选择性少的)，然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止； (5) 若 元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到;若m n, 则转入下一步。,0,例、有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,求解过程如下： 第一步，变换系数矩阵：,5,第二步，试指派：,找到 3 个独立零元素 但 m = 3 n = 4,第三步：作最少的直线覆盖所有0元素 (1)