06-整数规划1.ppt

1、管理运筹学,整数规划,第三讲,10/14/2020,3,先看一个例子：,例 现有甲乙两种货物拟用集装箱托运，每件货物的体积、重量、获利、以及集装箱的总托运限制如下，求托运方案。,设甲乙的托运数量分别为x1, x2：,10/14/2020,4,1. 从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。 2. 但实际上两者却有很大的不同，通过舍入得到的解(整数)也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解； 2. 常用的求解整数规划的方法有： 分支定界法和割平面法； 3. 对于特别的0-1规划问题采用隐枚举法和匈牙利

2、法,一、整数规划与线性规划的关系,10/14/2020,5,例1：,设整数规划问题如下:,10/14/2020,6,用图解法求出最优解x13/2, x2 = 10/3 且有z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解(最优解)： 如用“舍入取整法”可得到4个点，即 (1,3) (2,3) (1,4) (2,4)。 显然，它们都不可能是整数规划的最优解。,10/14/2020,7,思路:,1. 先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一: a.若(LP)没有可行解，则(IP)也没有可行解，停止计算。 b.若(LP)有最优解，并符合(IP)的整数

3、条件，则(LP)的最优解即为(IP)的最优解，停止计算。 c.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。 为讨论方便，设(LP)的最优解为:,二、分支定界法,10/14/2020,8,2. 定界: 记(IP)的目标函数最优值为Z* ,以Z(0)作为Z*的上界，记为 再用观察法找一个整数可行解 ,并以其相应的目标函数值Z作为Z*的下界，记为 也可以令 ，则有:,10/14/2020,9,3. 分枝: 在(LP)的最优解中，任选一个不符合整数条件的变量，例如 (不为整数)，以 表示不超过 的最大整数。 构造两个约束条件,将这两个约束条件分别加入问题(IP) ，形成两个子问题(IP

4、1)和(IP2) ，再解这两个问题的松弛问题(LP1)和(LP2) 。,10/14/2020,10,4. 修改上、下界: 按照以下两点规则进行,a.在各分枝问题中，找出目标函数值最大者作为新的上界； b.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。,10/14/2020,11,5. 比较与剪枝 : 各分枝的目标函数值中，若有小于 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了; 否则继续分枝。,如此反复进行，直到得到 为止，即得最优解X* 。,10/14/2020,12,说明:,分支定界法是一种隐枚举方法(implicit enumeration)或部分枚举方法，它不是一种

5、有效的算法，是枚举方法基础上的改进。其关键是分支和定界。,10/14/2020,13,例,Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整数,s.t.,松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,该整数规划松弛问题的解为： （X1 ，X2 ）= （3/2 ，10/3） Z0 = 29/6,松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,（3/2 ，10/3） Z0 = 29

6、/6,LP1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,LP2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0,LP2：解 （1，7/3 ）Z2 = 10/3,LP1：解 （2，23/9 ） Z1 = 41/9,（3/2 ，10/3） Z0 = 29/6,LP1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,LP2：解 （1，7/3 ） Z2 = 10/3,LP1：解 （2，23

7、/9 ） Z1 = 41/9,LP11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0,LP12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,LP12：解 （33/14，2 ） Z12 = 61/14,（3/2 ，10/3） Z0 = 29/6,LP2：解 （1，7/3 ） Z2 = 10/3,LP12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,L

8、P12：解 （33/14，2 ） Z12 = 61/14,LP121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0,LP122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,LP121：解 （3，1 ） Z121 = 4,LP122：解 （2，2 ） Z122 = 4,LP1：解 （2，23/9 ） Z1 = 41/9,分支搜索法流程,分支定界法流程,10/14/2020,20,用单纯形法解对应的(LP)问题, 获得最优解:,例:

9、用分支定界法求解整数规划问题（单纯形法）,10/14/2020,21,x1=13/4 x2=5/2 Z(0) =59/414.75 选 x2 进行分枝，即增加两个约束，2 x2 3 有下式：,10/14/2020,22,分别在(LP1)和(LP2)中引入松弛变量x5和x6 ， x2+x5= 2 , -x2+x6=-3,x1=7/2, x2=2 Z(1) =14.5 继续分枝，加入约束 4 x1 3,LP1,LP2,x1=5/2, x2=3 Z(2) =13.5 Z(2) Z(1) 先不分枝,10/14/2020,25,(LP1)继续分枝，加入约束 3x14，有下式：,分别引入松弛变量x7 和

10、x8 ，然后进行计算。,x1=3, x2=2 Z(3) =13 找到整数解，该枝LP11问题已探明。,LP11,x1=4 x2=1 Z(4) =14 该枝LP12问题已探明。,LP12,10/14/2020,28,树形图如下：,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,LP11 x1=3, x2=2 Z(3) 13,LP12 x1=4, x2=1 Z(4) 14,x22,x23,x13,x14,10/14/2020,29,0-1整数规划,10/

11、14/2020,30,1.隐枚举法： 对于0-1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。 但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。,一、0-1规划的解法,10/14/2020,31,例 求解下列0-1 规划问题,10/14/2020,32,10/14/2020,33,10/14/2020,34,为了进一步减少运算，可按目标函数中个变量系数顺序重新排列各变量，以使最优解较早出现。(一般情况) 一般地，对于Max问题，可降序排；对于Min问题，反之。,10

12、/14/2020,35,例 求解下列0-1 规划问题,10/14/2020,37,例 求解下列0-1规划问题,由于目标函数中变量x1, x2 , x4 的系数均为负数，可作如下变换：,令 x1 1-x1 , x2 =1- x2, x3= x3, x4 =1- x4带入原题中，重新调整变量编号。,10/14/2020,38,10/14/2020,40,一般形式的0-1规划化为标准形式：,10/14/2020,41,2.0-1分支定界法： 与整数规划的分支定界法类似，但要求化为标准型。,一、0-1规划的解法,其中要求cj非正！,10/14/2020,42,例 求解下列0-1规划问题,10/14/2

13、020,43,0-1,Branch 1 x2=0,other=0,Branch 2 x2=1,other=0,10/14/2020,44,0-1变量作为逻辑变量(Logical Variable), 常用于表示系统是否处于某个状态，或者决策时是否取某个方案。例如：,二、0-1变量以及应用,10/14/2020,45,例： 某银行用资金a对A，B，C三个行业放款，对行业A(企业Ai=1,2,3,4）至多选择2个企业；对行业B(企业Bj=1,2,3,4,5)至多选择3个企业；对行业C(企业Ck=1,2,3,4)至多选择2个企业。如企业Xi得到放款后，银行可获利bi，应如何安排放款计划？,令：,10

14、/14/2020,46,对本讲开始第一个例子修改如下：,例 现有甲乙两种货物拟用集装箱托运，每件货物的体积、重量、获利、以及运输方式的总托运限制如下，求托运方案。,10/14/2020,47,指派问题,10/14/2020,48,见p173，指派问题的解：,系数矩阵：,10/14/2020,49,10/14/2020,50,重要性质：,如从矩阵C中的任何一行/列中的各元素，加上一个实数a，从而得到一个新的矩阵B，那么以B为效益矩阵的指派问题与原问题同解。,10/14/2020,51,证明：,不失一般性，假定从C中的第k行加上实数a，则：,那么，新矩阵的目标函数为：,10/14/2020,52,

15、解题步骤：,指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不经济的。 利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,10/14/2020,53,第1步： 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从(cij)的每行元素都减去该行的最小元素； (2)再从所得新系数矩阵的每列元素中减去该列的最小元素。,10/14/2020,54,第2步： 进行试指派，以寻求最优解。 在(bij)中

16、找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 否则，转下一步；,10/14/2020,55,第3步： 最少直线覆盖所有0元素。,10/14/2020,56,第4步 变换矩阵(bij)以增加0元素： 没有被直线覆盖的所有元素中的最小元素为1，然后打各行都减去1；打各列都加上1，得如下矩阵，并转第二步进行试指派：,10/14/2020,57,例 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使

17、总时间最少？,10/14/2020,58,第1步 变换系数矩阵：,-5,10/14/2020,59,第2步 试指派：,找到3个独立零元素 但m=3n=4,10/14/2020,60,第3步 作最少的直线覆盖所有0元素：,独立零元素的个数m等于最少直线数l，即lm=3n=4；,10/14/2020,61,第4步-变换矩阵(bij)以增加0元素：,-1,-1,10/14/2020,62,非标准形式的指派问题 参见p179,10/14/2020,63,指派问题应用,10/14/2020,64,例 分配甲、乙、丙、丁去完成五项任务，每人完成各项任务的时间如下表。由于任务多，规定其中有一人可兼完成两项任

18、务，试确定总花费时间最少的分配方案。,10/14/2020,65,10/14/2020,66,例 从甲、乙、丙、丁、戊5人中选4人去完成4项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。,10/14/2020,67,10/14/2020,68,整数规划的一些典型应用,10/14/2020,69,1. 投资场所选择问题,某公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 1.在东区由A

19、1,A2,A3三个点至多选择2个； 2.在西区由A4,A5两个点中至少选1个； 3.在南区由A6,A7两个点中至少选1个； 4.在北区由A8,A9,A10三个点中至少选2个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见右表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,10/14/2020,70,设0-1变量xi=1(Ai 被选用)或0(否则)；设pi为Ai的利润；Ii为Ai的投资,x1+x2+x32 x4+x51 x6+x71 x8+x9+x102,10/14/2020,71,2.固定成本问题,高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,10/14/2020,72,设x1,x2, x3分别为小中大号的生产数量。各种容器的固定费用只有在生产该种容器时才投入。引入约束yi,10/14/2