第5章整数规划

1第五章整数规划2§1整数规划的数学模型一、整数规划的数学模型1.整数规划(IntegerProgramming简记IP)要求一部分或全部决策变量必须取整数的规划问题2.松驰问题(SlackProblem)不考虑整数约束，由余下的目标函数和约束条件构成的规划问题(也称伴随规划)3.整数线性规划(ILP)若松驰问题是一个线性规划问题3§1整数规划的数学模型一、整数规划的数学模型整数线性规划数学模型的一般形式为：jjinjjijnjjjxnjxmibxastxcz,,2,10,,2,1)(.max(min)11中部分或全部取整数4§1整数规划的数学模型一、整数规划的数学模型整数线性规划分为：纯整数LP——PureIntegerLinearProgramming混合整数LP——MixedIntegerLinearProgramming0-1型整数LP——Zero-OneIntegerLinearProgramming5§1整数规划的数学模型二、整数规划举例例1：某厂生产A1和A2两种产品，需要经过B1，B2，B3三道工序加工，单件工时和利润以及各工序每周工时限额见下表，问工厂应如何安排生产，才能使总利润最大？B1B2B3利润A10.30.20.325A20.70.10.540工时限制2501001506§1整数规划的数学模型二、整数规划举例解：设工厂每周生产A1产品x1件，A2产品x2件。则该问题的数学模型为：0,1505.03.01001.02.02507.03.0.4025max2121212121xxxxxxxxstxxz且取整数值7§1整数规划的数学模型二、整数规划举例例2：见书P130例18§1整数规划的数学模型三、整数规划解的特点1.整数规划问题的可行解集合是它的松驰问题可行解集合的一个。2.整数规划问题最优解的目标函数值松驰问题最优解的目标函数值。3.对松驰问题最优解中非零分量取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。子集不优于9例1:某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制见表.问每集装箱中两种货物各装多少箱,可使所获利润最大?货物/箱体积/米3重量/百斤利润/百元甲5220乙4510托运限制/集装箱241310解：设分别为甲、乙两种货物的托运箱数.则这是一个纯整数规划问题。其数学模型为:21,xx211020maxxxZ整数,0,13522445.212121xxxxxxts（1）11若暂且不考虑取整数这一条件。则(1)就变为下列线性规划:21,xx211020maxxxZ0,13522445.212121xxxxxxts（2）将式(2)称为(1)的松驰问题，解(2)得到最优解:,8.4*1x,0*2x96*Z（3）但它不满足(1)的整数要求。因此它不是(1)的最优解。12若取X1=(5,0)T，它不满足(1)中的约束条件1。若取X2=(4,0)T，X2是(1)的可行解,但它却不是(1)的最优解。因为当X2=(4,0)T时,Z=80,当X3=(4,1)T时,Z′=90Z,即松驰问题的最优解通过“舍零取整”得到的X1,X2都不是(1)的最优解。因此通过松驰问题最优解的“舍零取整”的办法,一般得不到原整数规划问题的最优解。13k0={(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l)}将C点“舍零取整”后得到的X1=(5,0)T不在K0中,而X2=(4,0)T在K0中,但不是(1)的最优解,最优解在B点。松驰问题(2)的可行域K如图,1123421x2xACBO(4.8,0)(4,0)5则原整数规划(1)的可行域K0应是K中有限个格点(整数点）的集合。图中“*”为整数点(格点)。例2：见书P132例414由于整数规划问题(1)可行解的个数较少，故可用“穷举法”来求解,即将K0中所有整数点的目标函数值都计算出来,然后逐一比较找出最优解。取=0,1,2,3,41x其组合最多为15个(其中有不可行的点)。2x=0,1,2但对大型问题，这种组合数的个数可能大得惊人!如在指派问题中，有n项任务指派n个人去完成，不同的指派方案共有n!种。当n=20时，这个数超过2×1018。如果用穷举法每一个方案都计算一遍，就是用每秒亿次的计算机，也要几十年。15显然“穷举法”并不是一种普遍有效的方法。因此研究求解整数规划的一般方法是有实际意义的。自20世纪60年代以来，已发展了一些常用的解整数规划的算法，如各种类型的割平面法、分枝定界法、解0-1规划的隐枚举法、分解方法、群论方法、动态规划方法等等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果。16§2解纯整数规划的割平面法割平面法在1958年由R.E.Gomory首先提出。一、割平面法的思想若松驰问题的最优解不满足整数约束，就设法在问题上增加一个约束，把包含这个非整数解的一部分可行域从原来的可行域中割掉，但不割掉任何一个整数可行解，这个新增加的约束条件就称为割平面约束或Gomory约束。170,431.max21212121xxxxxxstxxz且为整数p(3/4,7/4)****12xq(1,1)18二、割平面法步骤1.解松驰问题的最优解；2.若X*的所有分量均为整数，则满足整数约束，X*即为整数规划的最优解。若存在X*的某个分量为小数，则选取分数部分最大的分量，构造新的约束条件；3.将新的约束条件加入松驰问题中，形成一个新的线性规划，对这个新的线性规划求解；4.若新的解满足整数约束，则此解为整数规划的最优解，否则重复第2，3步，直到获得最优解为止。19三、新约束条件的构造在松驰问题的最优单纯形表中，m个约束方程可表示为：QibxaxiKjjiji其中Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。20三、新约束条件的构造若不是整数，其对应的约束方程：分解和成两部分，一部分是不超过该数的最大整数，另一部分是余下的正小数。即：000iKjjjiibxax0ibjia0)(00Qibi21三、新约束条件的构造0000000000iiiiijijijijijibNfNbaNfNa且为整数且为整数)(100Kjfji100if构造新的约束条件为：Kjijjifxf00)(割平面约束22四、新增约束条件的性质性质1：原松驰问题的非整数最优解不满足新增约束条件。性质2：原松驰问题的整数可行解均满足新增的约束条件，也就是说，整数可行解始终保留在每次形成的线性规划的可行域中。23Kjijjifxf00)(下面说明新增约束：能够“割掉”松驰问题中的非整数可行解。证明：设X*为松驰问题的最优解，将其代入新增约束有：，（因非基变量取值为0）00if这与矛盾，即X*不满足新增约束。100if注：经验表明若从最优单纯形表上选择具有最大小数部分的非整数分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。24例1：用割平面法求解整数规划0,431.max21212121xxxxxxstxxz且为整数解：引入松驰变量x3，x4，将问题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下：25cj1100CBXBbx1x2x3x411x2x17/43/401103/4-1/41/41/400-1/2-1/2j43414343xx割平面约束为：引入松驰变量x5，得割平面方程：x1,x2的最大分量均为3/4，不妨选取x2，得：434143543xxx26cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/400100-1/2-1/20j110x2x1x311101010000101/31/31-1/3-4/3000-1/3-2/3j27例2：用割平面法求解整数规划0,521045323.3max2121212121xxxxxxxxstxxz且为整数解：引入松驰变量x3，x4，x5，将问题化为标准形式，用单纯形法解其松驰问题，得最优单纯形表如下：28cj3-1000CBXBbx1x2x3x4x53-10x1x2x413/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/7j76727153xx割平面约束为：引入松驰变量x6，得割平面方程：767271653xxx29cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70j767271653xxx30cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x4x510-53100001000-1/2-21/20010000113/211-7/200-5/70-3/70j767271653xxx31cj3-10000CBXBbx1x2x3x4x5X63-100x1x2x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4000-1/40-17/4j43414164xx割平面约束为：引入松驰变量x7，得割平面方程：434141764xxx32cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x715/45/27/4-3/41000001000001000-1/4-1/21/4-1/4000101-5/4-11/2-3/4-1/400001000-1/40-17/40j33cj3-100000CBXBbx1x2x3x4x5x6x73-1000x1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-400000-4-1j上表中给出的最优解x=(1,2,4,3,1,0,0)已满足整数约束，因而，原整数规划问题的最优解为：x1=1,x2=2,maxz=134331xx11x*****35§3分枝定界法在20世纪60年代初LandDoig和Dakin等人提出了分枝定界法。由于该方法灵活且便于用计算机求解，所以目前已成为解整数规划的重要方法之一。分枝定界法既可用来解纯整数规划，也可用来解混合整数规划。分枝定界法的主要思路是首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则：•增加新约束——缩小可行域;•将原整数规划问题分枝——分为两个子规划,再解子规划的伴随规划；•通过求解一系列子规划的伴随规划及不断地定界。最后得到原整数规划问题的整数最优解。36例1：某公司计划建筑两种类型的宿舍。甲种每幢占地0.25×103m2,乙种每幢地0.4×103m2。该公司拥有土地3×103m2.计划甲种宿舍不超过8幢，乙种宿舍不超过4幢。甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元。问该公司应计划甲、乙两种类型宿舍各建多少幢时，能使公司获利最大?37解：设计划甲种宿舍建幢,乙种宿舍建幢,则本题数学模型为:2x1x212010maxxxZ取整数,0,4834.025.0.212121xxxxxxts这是一个纯整数规划问题,称为问题。将(1)中约束条件0A34.025.021xx的系数全化为整数,改为：608521xx（1）38然后去掉整数条件,得到问题的伴随规划(2),称之为问题0A0B21