最优化理论与方法2(2014-简版)

̀《最优化理论与方法》讲义(下)第三章整数规划线性规划问题的最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。这样的问题称为整数线性规划(integerlinearprogramming)，简称ILP。一、整数规划(IP)(1)要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。若松弛问题是一个线性规划，则称整数规划为整数线性规划。(2)整数线性规划的一般形式njjixcff1)max(min或且部分或全部为整数njxmibxajnjijij,,10,,11(3)整数线性规划问题的种类·纯整数线性规划它指全部决策变量都必须取整数值的整数线性规划。njxxbAXtsXCjjT,,1,0..min为整数·0-1型整数线性规划决策变量只能取值0或1的整数线性规划。njxbAXtsXCjT,,11,0..min·混合整数线性规划决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。pjxxbAXtsXCjjT,,10..min为整数(4)举例例1：工厂1A和2A生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有3A和4A两个。这种物资的需求地有1B、2B、3B、4B四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费ijC，见下表：工厂3A或4A开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂3A还是4A，才能使今后每年的总费用最少。解：这是一个物资运输问题，特点是事先不能确定应该建3A还是4A中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：2,101iyi若不建工厂若建工厂再设ijx为由iA运往jB的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为ja和jcnj,,1，此外由于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定；项目3和4中至少选择一个；项目5、6、7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令jx表示第j个项目的决策选择，记为：njjjxj,,101不投资对项目投资对项目投资问题可以表示为：njxxxxxxxxBxatsxczjnjjjnjjj,,11021..max76543121或者二、整数规划的求解线性规划问题的最优解可能是分数或小数，为满足整数解的要求，似乎可以把已得到的带有分数或小数的解“舍入化整”。这种方法可行吗？例设整数规划问题如下：用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6。现求整数解(最优解)：如用舍入取整法可得到4个点，即(1,3),(2,3),(1,4),(2,4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集。由上例看出，将线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至且为整数0,13651914max21212121xxxxxxxxZ0,13651914max21212121xxxxxxxxZ根本不是可行解。1、整数规划问题解的特征最优点不一定在顶点处取得；最优解不一定是松弛问题最优解的邻近整数解；整数可行解远多余于顶点，枚举法不可取；可行解是其松弛问题的可行解，反之不一定，但如果松弛问题的最优解还满足整数约束条件，是整数规划的最优解。2、整数规划问题的求解方法2.1割平面法1、基本思想：由松弛问题的可行域向整数规划的可行域逼近。2、方法：利用超平面切除要求：(1)整数解保留；(2)松驰问题最优值增加。具体为：即首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解松弛问题。若得到非整数的最优解，则增加线性约束条件(或称为割平面)，割去非整数解，切割掉原可行域的一部分，使得只切割掉非整数解，没有切割掉任何整数可行解。以下仅讨论纯整数线性规划的情形。例求解目标函数21maxxxZ①约束条件：1-21xx②4321xx③0,21xx④为整数21,xx⑤先不考虑条件⑤的整数约束条件，求得相应的松弛线性规划的最优解为：4/7,4/321xx，最优值为4/10*z。最优解是图中域R的极点A，但A不符合整数约束条件。现设想，如能找到像CD那样的直线去切割域R，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域'R的一个极点。如在域'R上求解原来的松弛问题①～④，而得到的最优解又恰巧在C点，就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。首先，将松弛规划化为标准型，即在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束：1-321xxx⑥43421xxx⑦用单纯形表求解，见下表。由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。然后，可从最终计算表中得到非整数变量对应的关系式：474143434141432431xxxxxx为了得到整数最优解，将上式变量的系数和常数项都分解成整数和非负真分数两部分之和4314104300143041043101432431xxxxxx然后将整数部分与分数部分分开，移到等式左右两边，得到43243314143431414343xxxxxxx现考虑整数约束条件⑤要求21xx、都是非负整数，于是由条件⑥、⑦可知43xx、也都是非负整数，这一点对以下推导是必要的，如不都是整数，则应在引入43xx、之前乘以适当常数，使之都是整数。上式中，从等式左边看是整数；等式右边也应是整数，即则整数条件⑤可由下式所代替：041434343xx即3343xx⑧这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例题。引入松弛变量x5，得到等式33543xxx将这新的约束方程加到上述的最终计算表，得下表。这从表的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。选择5x为换出变量，计算将3x做为换入变量，再按原单纯形法进行迭代，得表。由于21xx、的值已都是整数，解题已完成。注意：新得到的约束条件3343xx⑧61121,321min0minljljjjjaazc如用21xx、表示，由⑥、⑦式得334132121xxxx12x这就是21,xx平面内形成的新的可行域，即包括平行于1x轴的直线12x和这直线下的可行区域，整数点也在其中，没有切割掉，见图。求一个切割方程的步骤为：Step1令ix是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到：kikikibxax(3-4)其中Qi，Q指构成基变量的指标集合；Kk，K指构成非基变量的指标集合。Step2将ib和ika都分解成整数部分N与非负真分数f之和，即1010ikikikikiiiffNaffNb其中其中(3-5)而N表示不超过b的最大整数。例如：若b=2.35，则N=2，f=0.35若b=−0.45，则N=−1，f=0.55代入(3-4)式得kkkikiikikixffNxNx(3-6)Step3现在提出变量(包括松弛变量)为整数的条件。kkkikiikikixffNxNx(3-6)这时，上式由左边看必须是整数，但由右边看，因为10if，所以不能为正，即kkikixff0(3-7)这就是一个切割方程。由(3-4)式，(3-6)式，(3-7)式可知：①切割方程(3-7)式真正进行了切割，至少把非整数最优解这一点割掉了。②没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(3-7)式的缘故。2.2分枝定界法对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。但对于大型问题，可行的整数组合数会很大。例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20时，超过2×1018。显然，穷举法是不可取的。(1)分枝定界法的简介20世纪60年代初由LandDoig和Dakin等提出，是解整数线性规划的重要方法之一。基本思想：将要求解的整数规划问题逐步通过设置某些决策变量的范围，把问题分解成若干子问题，对每个子问题再利用去掉整数约束得到松弛的子问题，使用线性规划方法求解松弛子问题，得到原问题最优值的上界。考虑最大化整数线性规划问题A，与它相应的线性规划记为问题B若B无可行解，则A无可行解；若B有最优解，且满足整数约束，则它也是A的最优解；若B有最优解，但不满足整数约束条件，这时B的最优值是A的最优值*z的上界；分枝定界法可用于解纯整数或混合整数线性规划问题，考虑如下问题njjixcXf1max且部分或全部为整数njxmibxajnjijij,,10,,112、解题步骤(以极大化问题为例)(1)确定整数规划最优解的上下界若B无可行解，则A无可行解，停机；若B有最优解且为整数解，则此解为A的最优解，停机；若B有最优解但不是整数解，记目标函数值是Z；用观察法找A的一个可行整数解，其函数值记为Z。若观察不到，则可令Z，即得ZZZ(2)分枝、求解(增加约束条件将问题分枝)任意选一个非整数解的变量ix，在松弛问题中加上约束：iixx和1iixx组成两个新的松弛问题，称为分枝，并求解这两个问题。举例：为整数2121212121,0,05.1645.1432..2030maxxxxxxxxxtsxxz松弛问题0L：0,05.1645.1432..2030max212121210xxxxxxtsxxzL松弛问题0L的最优解：5.2,5.321xx则分解为二个子问题1L和2L：0,035.1645.1432..2030max2112121211xxxxxxxtsxxzL0,045.1645.1432..2030max2112121212xxxxxxxtsxxzL(3)定界、剪枝定界：①修改上界Z：每解完一对分枝后，都要修改上界，在所有未被分枝的问题中找出最优目标函数值的最大者作为新的上界。在分枝定界法的整个过程中上界的值不断减少。②修改下界Z：每求出一次已符合整数条件的可行解时，都要修改下界。在所有符合条件的各分枝中，找出目标函数值最大者作为新的下界。在分枝定界法的整个过程中，下界的值不断增大。剪枝①若分枝无可行解—树叶，则剪掉该分枝；②分枝的最优目标函数值Z，剪掉该分枝(枯枝)；③若分枝的最优目标函数值Z，则继续分枝，转②，直到ZZ，则ZZZ*。注：继续分枝时，先对目标函数值较大的那枝进行分枝求解。对目标函数值较差的那一枝暂且放下，待目标函数值较优的那枝全部分解到不能再分解，再考虑目标函数值较差的那枝。例