高一政治作业(5)

1/64Chapter5整数规划(IntegerProgramming)整数规划问题的提出分支定界法割平面法0-1整数规划指派问题本章主要内容：2/64第一节.整数规划问题的提出一、整数规划的一般形式1、实例：例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：货物体积每箱（米3）重量每箱（百斤）利润每箱（百元）甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？3/64A(4.8,0)0X1X2B(4,1)整数2121212121,0,135224451020maxxxxxxxxxxxz①②③④⑤设x1、x2为甲乙两种货物托运的箱数。(非负整数)不考虑x1、x2取整数的约束，线性规划的可行域如图中的阴影部分，最优解为*(4.8,0) ,*96TXz4/64若将（x1=4.8，x2=0）凑整为（x1=5，x2=0），显然已不满足约束条件，②25。若将（x1=4.8，x2=0）凑整为（x1=4，x2=0），是可行解，但是否最优呢？当（x1=4，x2=0），Z＝80。向原点平行移动目标函数的等值线，第一次遇到“＋”的B点，即为最优解。(“＋”的点表示可行的整数解。)当（x1=4，x2=1），Z＝90，更优。5/642、整数规划的数学模型一般形式且部分或全部为整数或n)1.2(j0)2.1()min(max11jnjijijnjjjxmibxaxcZZ依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。6/64纯整数规划(全整数规划)：所有变量要求取非负整数。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。7/643、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。8/64例：设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxZ首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。0,13651914max21212121xxxxxxxxZ9/64用解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图10/64因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：分支定界法割平面法对于特别的0－1规划问题采用隐枚举法和匈牙利法。11/64基本思想:第二节分枝定界解法首先，不考虑变量的整数约束，求解相应的线性规划，得到线性规划的最优解。如果线性规划的最优解恰好是整数解，则这个解就是整数规划的最优解。如果线性规划的最优解中至少有一个变量不是整数，选择其中一个将线性规划的可行域切割成两部分，分别求解两个线性规划的最优解。如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。这个过程，叫做“分枝”。分枝过程得到的整数解中，目标函数值最大的一个叫做整数规划目标函数值的“下界”。分枝过程中非整数的线性规划的最优解，如果目标函数值小于或等于这个“下界”，就停止继续分枝。这个过程，叫做“定界”。12/64取整数2121212121,0,3121451149maxxxxxxxxxxxz步骤1：用单纯形法求解线性规划问题，得到最优解及最优值。步骤2：分枝。例2解整数规划问题0,23121451149max:2112121211xxxxxxxxxzBTx310,23*0629*0z0,13121451149max:2112121212xxxxxxxxxzB941923,2**zx31037,1**zx41/910/3,优先选择B1分枝。13/640,23121451149max:2112121211xxxxxxxxxzB941923,2**zx0,323121451149max:212121212111xxxxxxxxxxzB0,223121451149max:212121212112xxxxxxxxxxzB无可行解14612,1433**ZX61/14(B12)10/3(B2),优先选择B12分枝。14/640,223121451149max:212121212112xxxxxxxxxxzB14612,1433**ZX0,3223121451149max:21121212121121xxxxxxxxxxxzB0,2223121451149max:21121212121122xxxxxxxxxxxzB4,1,3**ZX4,2,2**ZX410/3，所以B2无需分枝。15/64(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。分支定界法的步骤z(1)用观察法求整数规划原问题的一个可行解，其目标值便是R的最优目标值z*的一个下界z。(2)求解与R对应的线性规划问题R0，若R0无可行解，则R也无可行解，结束；若得到R0的最优解x0和最优值z0。若x0符合R的整数条件，则显然x0也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是R的最优目标值的一上界。16/64(4)定界。在各分枝中找出目标函数值最大者作为新的上界；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。z(5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。17/64解求相应的线性规划B0,702075679:9040max21212121xxxxxxBxxz例2求解A且均取整数,0,7020756799040max21212121xxxxxxxxz18/64567921xx7020721xx线性规划B的最优解X*=(4.81,1.82),z0=356B87654321012345678910x1x2z=40x1+90x2因(0,0)是问题A的一个整数可行解，故0≤z*≤35619/64x1得到两个线性规划及增加约束5411xxB187654321012345678910x2B2B2:X*=(5,1.57),z2=341B1:X*=(4,2.1),z1=349修改,0≤z*≤349349z20/6432221xxB及进行分枝，增加约束选择B387654321012345678910x1x2B2B4B3:X*=(4,2),z3=340B4:X*=(1.42,3),z5=327修改340≤z*≤341341,340zz×B2:X*=(5,1.57),z2=34121/64B2B521222xxB及进行分枝，增加约束选择87654321012345678910x1x2修改z=z*=340340zB5:X*=(5.44,1)z5=308×B3B4B6无可行解×B4:X*=(1.42,3),z5=327B3:X*=(4,2),z3=34022/64x1≤4x1≥5x2≤2x2≥2x2≥3x2≤1问题BX*=(4.81,1.82)Tz0=356问题B5X*=(5.44,1)Tz5=308问题B2X*=(5,1.57)Tz0=341问题B1X*=(4,2.10)Tz0=349问题B3X*=(4,2)Tz3=340问题B4X*=(1.42,3)Tz0=327问题B6无可行解×××356,0zz349,0zz341,340zz*340zz23/64算法思想•由相应的线性规划问题的可行域向整数规划的可行域逼近•方法—利用超平面切除•要求整数解保留不符合整数条件的线性规划问题的最优解被切除第三节割平面解法24/64是整数2121212121,0,431..maxxxxxxxxxtsxxz例1用割平面法求解整数规划问题0,,,431..max432142132121xxxxxxxxxxtsxxz步骤1：标准化其对应的线性规划问题B0Cj1100CBXBbx1x2x3x411x2x17/43/401103/4－1/41/41/4cj-zj00－1/2－1/2引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的任一个整数可行解。求得最优单纯形表25/64步骤2：求一个割平面方程（1）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1，则含x1的约束方程为)3(434141431xxx（2）将所选择的约束方程中非基变量的系数及常数项进行拆分处理。即：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（3）式变为：)4(430410431431xxx（3）将上述约束方程（4）重新组合。即：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得：)5(x41x4343xx4331很明显，（5）左端为整数，右端1，则有其右端0，即)6(43414343xx（4）将割平面方程加到松弛问题的约束方程中，构成新的松弛问题并求解（对偶单纯形法）。26/640,,,,434143431..00max543215434213214321xxxxxxxxxxxxxxtsxxxxz割平面方程Cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj000－1/3－1/327/64例2：用割平面法求解整数规划问题且为整数0,023623max2121212xxxxxxxZ解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/428/64此题的最优解为：X＊(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2所在行生成割平