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

整数规划及其数学模型分枝定界法割平面法0-1整数规划指派问题WinQSB软件应用第五章整数规划(IntegerProgramming)第一节整数规划及其数学模型在很多实际问题中，有些变量的取值必须是整数在一个规划问题中，如果它的某些变量（或全部变量）要求取整数，这个规划问题就称为整数规划问题，其中如果所有变量都取整数，就称为纯整数规划或全整数规划如果仅有一部分变量取整数，则称为混合整数规划若变量值仅限于0或1，则称为0-1规划一、问题的提出在整数规划问题中，不考虑整数要求，由其他约束条件和目标函数构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规划问题，则其对应的整数规划问题称为整数线性规划（ILP）。本章所讨论的整数规划都是指整数线性规划。（一）下料问题【例5-1】某工地需要长度不同、直径相同的成套钢筋，每套钢筋由两根7米长和七根2米长的钢筋组成。现有15米的圆钢毛坯150根，应如何下料使废料最少？下料方式7米长的钢筋（根）2米长的钢筋（根）废料120121403071(二)工厂选址问题【例5-3】工厂A1和A2生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这种物资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（j=1,2,3,4）如下表所示B1B2B3B4生产能力（千吨/年）A12934400A28357600A37612200A44525200需求量（千吨/年）350400300150工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设A3还是A4，才能使今后每年的总费用最少。(三)投资问题【5-2】某投资公司可用于投资的资金是B，可供投资的项目有n个，项目j所需投资额和预期收益分别aj和cj。同时，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2，反之则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？整数规划数学模型的一般形式且部分或全部为整数，，，，，，或n)21(j0)21()min(max11jnjijijnjjjxmibxaxcZZ依照决策变量取整要求的不同，整数规划可分为纯整数规划/全整数规划、混合整数规划、0－1整数规划二、整数规划模型的一般形式及解的特点且为整数0,143292)(23max21212121xxxxxxIPxxZ求解整数规划问题分析：考虑对应的线性规划问题(LP)0,143292)(23max21212121xxxxxxLPxxZ整数规划解的性质3200CBXBbx1x2x3x40x3921109/20x414230114/2σj32003200CBXBbx1x2x3x43x113/4103/4-1/42x25/201-1/21/2σj00-5/4-1/4用单纯形法解（如表所示），获得最优解初始表最终表可见，最优解为x1=3.25x2=2.5z(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规划的隐枚举法0x2x1(a)(b)(5/3,5/2)第二节整数规划的解法—分枝定界法且均为整数0,521023max2122121xxxxxxxz【例5-7】求解整数规划问题【思考】（IP）的可行域与（LP）可行域的关系如何？（IP）的最优解是否会优于（LP）的最优解？若（LP）有最优解，且其最优解为整数，则它是否也是（IP）的最优解？若（LP）有最优解，但其最优解不是整数，怎么办？假设已知（IP）的一个整数可行解，则（IP）的最优解与该解有怎样的关系？适用范围全整数规划问题或混合整数规划问题本世纪60年代初由LandDoig和Dakin等人提出基本思路设有最大化的整数规划问题(IP)，与它相应的线性规划问题为(LP)——松弛问题。从解(LP)开始，若其最优解不符合整数条件，那么(LP)的最优目标函数必是(IP)最优解z*的一个上界，记作z;而(IP)的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就是将(LP)的可行域分成子区域（分枝），逐步减小z和增大z，最终求得z*的方法。【例5-7】且为整数)2.1(,0)2.1()(max11mjxmibxaIPxcZjnjijijnjjj考虑全整数规划问题：)2.1(,0)2.1()(max11mjxmibxaLPxcZjnjijijnjjj整数规划的松弛问题：步骤：1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴(LP)没有最优解，则(IP)也没有最优解，停止计算；⑵若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算；⑶若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：不全为整数其中目标函数最优值为),,2,1(.Z)0,,0,,,,,,((0)21)0(mibbbbbXiTmr2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为＝Z(0)。再用观察法找到一个整数可行解X′，并以其相应的目标函数值Z′作为Z*的下界，记为Z＝Z′（取xj=0），则有：Z≤Z*≤。ZZ将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。3、分枝：在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以表示不超过的最大整数。构造两个约束条件xr≤和xr≥＋1rbrbrbrbrb4、修改上、下界：(按照以下两点规则进行)⑴在各分枝问题中，找出目标函数值最大者作为新的上界；⑵从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。如此反复进行，直到得到Z＝Z*＝为止，即得最优解X*Z3200CBXBbx1x2x3x40x3921109/20x414230114/232003200CBXBbx1x2x3x43x113/4103/4-1/42x25/201-1/21/200-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解初始表最终表可见，最优解为x1=3.25x2=2.5z(0)=59/4=14.75且为整数0,143292)(23max21212121xxxxxxIPxxZ例1、用分枝定界法求解整数规划问题选x2进行分枝，即增加两个约束x2≤2和x2≥3，则且为整数0,2143292)1(23max212212121xxxxxxxIPxxZ且为整数0,3143292)2(23max212212121xxxxxxxIPxxZ分别在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算，即x2+x5=2,－x2+x6=－3得下表:32000CBXBbx1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x520100100-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/2100-5/4-1/403x17/2101/20-1/22x22010010x4100-11-200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5继续分枝，加入约束x1≤3,x1≥4LP132000CBXBbx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3Z(2)=27/2=13.5∵Z(2)Z(1)∴先不考虑分枝接(LP1)继续分枝，加入约束x1≤3和x1≥4，则且为整数0,32143292)3(23max2112212121xxxxxxxxIPxxZ且为整数0,42143292)4(23max2112212121xxxxxxxxIPxxZ分别引入松弛变量x7和x8，然后进行计算CBXBbx1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算LP3CBXBbx1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4,x2=1Z(4)=14找到整数解，问题已探明，停止计算因为z(4)z(3),故x1=4,x2=1为最优解LP4树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4＃＃＃例2、用分枝定界法求解整数规划问题（图解法计算）且全为整数0,4306525min211212121xxxxxxxxxZ记为（IP）解：首先去掉整数约束，变成一般线性规划问题0,4306525min211212121xxxxxxxxxZ记为（LP）用图解法求（LP）的最优解，如图所示x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，取值x2≤3，x2≥4先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限有下式：且为整数0,1430652)1(5min2111212121xxxxxxxxIPxxZ