西安电子科技大学数学建模讲义第六讲.ppt

主讲人:,Email:mxw1334,数学建模讲义,数学建模专题讲座,最优化模型-线性整数规划,整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。,整数规划简介,线性整数规划,1、建模引例。2、线性整数规划模型3、线性整数规划的主要算法。4、0-1规划选讲,1、建模引例,是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？,它和线性规划问题的区别在于条件(5)。,此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z80，而对x1=4,x2=1（也是可行解）有z90。因此要专门研究整数规划的解法。,整数规划(IP)的一般数学模型:max(min)z=cjxjs.t.aijxjbi(i=1,2,m)xj0且部分或全部是整数,2.线性整数规划模型,解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。,先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。,例2求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值,O12345678910,54321,x1,x2,I(2,4),B(9.2,2.4),A,D,可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,3线性整数规划的解法,枚举法仅仅对极小规模的问题有效分支定界法应用比较广泛，对中小规模问题割平面法应用比较广泛，对中小规模问题,分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。,3.1分枝定界法,分枝定界法步骤原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xlxl或xlxl+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,R0:z0=356x1=4.81x2=1.82,R1:z1=349x1=4.00 x2=2.10,R2:z2=341x1=5.00 x2=1.57,R12:z12=327x1=1.42x2=3.00,x23,R11:z11=340 x1=4.00 x2=2.00,R21:z21=308x1=5.44x2=1.00,R22:无可行解,x14,x11,x15,x12,问题R0为:Maxz=40 x1+90 x29x1+7x2567x1+20 x270 x1,x20,问题R2为:Maxz=40 x1+90 x29x1+7x2567x1+20 x270 x15x1,x20,问题R1为:Maxz=40 x1+90 x29x1+7x2567x1+20 x270 x14x1,x20,x22,问题R11为:Maxz=40 x1+90 x29x1+7x2567x1+20 x270 x14x22x1,x20,问题R12为:Maxz=40 x1+90 x29x1+7x2567x1+20 x270 x14x23x1,x20,割平面法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑变量为整数这一条件，但增加线性约束条件（几何术语，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。切除的结果使整数解可能成为顶点,分枝定解法是对原问题可行解域进行了切割，切割方法是对取非整数解相邻的整数作附加约束，约束方程简单，但子问题由于分枝的增多而成指数增长。,关键：如何找到割平面约束方程，使切割后最终得到这样的可行解域，它的一个整数坐标的顶点恰好是问题的最优解。,3.2割平面法,割平面法步骤：（1）去掉整数约束，用单纯形法求解。若最优解是整数，停止计算，否则转第（2）步。,（2）寻求附加条件（割平面方程），其方法后述。,（3）将割平面方程标准化后加到约束方程组中求解，如所得最优解仍为非整数，则转到第（2）步继续进行，直到找到最优整数解为止。,决策变量仅取为0或1的整数规划问题。xi是0-1变量的表示：xi1，xi0,40-1规划,把上约束加到约束方程组中就和一般整数规划的约束条件一致了。故0-1型整数可用一般求整数规划的方法求解，但0-1型整数规划是整数规划的特殊情形，因此，有特殊解法。,4.1隐枚举法,【例4】某厂拟在A、B、C、D、E五个城市中建立若干个产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供的利润各处不同，有些点也可能亏本，但却能获得贷款和人力等。设数据已知（在下面建模中给出），为使总收益最大，问厂方应作出何种最优选点决策？,上述各城市是否被选，可用决策变量xi表示，xi=1表示被选，否则xi=0，根据已知数据可建数模如下:,解题分析：仅从目标函数看，为使总收益最大，应取x1=x2=x3=1，x4=x5=0即选A、B、C三城建联营点不选D、E，这时总收益为Z=17.8（十万元）；但从约束条件来看，这个决策不可行。如果哪个城市都不设点，即xj=0(j=1,2,3,4,5)，从约束条件看都满足，但Z=0，这显然不是一种最优决策，究竟应选那些城市建点呢?,每个城市都有可能入选和不入选，即xj取值有0和1两种状态；有5个变量，这样的0，1组合就有25=32个。把每种组合列出，代入约束条件检验是否可行，可行解代入目标函数比较大小得出最优解-枚举法，繁琐!,实际不需要列出所有的可行组合。兴趣-使目标函数最优的变量的可行组合。按目标函数值从优到劣（本例，从大到小），顺序列出变量的组合；,过滤性条件,2.逐个检验变量组合的可行性，最先满足所有约束条件的变量组合就是最优解；,3.而劣于最优解的组合即使可行，也不用列出和检验；,4.相当于把枚举法得出的所有非优组合隐去不算了，故称为隐枚举法。,本例变换结果如下：,（2）用目标函数值探索法求最优解由公式，当时，Z=Z0=17.8为上限。如果这个组合又满足全部约束条件，则它为最优解;否则，按劣于Z0的组合解方向探索可行解。按由小到大逐项计算组合解的值及其相应的Z值，代入约束条件检查可行性，如全部满足，即为最优解。,最大值,目标探索法计算过程示于下表：,最优解为：x1=1,x2=0,x3=1,x4=0,x5=1,即在A,C,E三个城市设联营点，可获最大收益12.5（十万元）。,4.2分派问题和匈牙利法,AssignmentProblem,有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij，如何分派使总花费最省？,第j项工作由一个人做,第i人做一项工作,分派第i人做第j项工作不分派第i人做第j项工作,【例5】有四项任务需分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，但完成各项任务所需时间如下表所示。问应如何分派任务可使完成任务的总工时最少？,问题分析：引入决策变量xij,分派问题是0-1规划问题。,因每个人仅能承担一项任务，每项任务也只能分派给一个人，因此上述问题的线性规划模型为：,满足该约束条件的可行解可写成矩阵形式,分派问题是线性规划，又是运输问题。,匈牙利算法的步骤：（1）变换系数矩阵，使其每行每列都出现0元素。首先每行减去该行最小数，再每列减去该列最小数。,-7-7-8-7,-4,(cij),(2)进行试分派，寻求最优解。经第（1）步变换后，系数矩阵每行每列都已有了0元素，但需找出n个独立的0元素，为此，按下列的步骤进行。,从只有一个0元素的行（列）的0元素开始，给这个0元素加圈，即作，这表示对这行所代表的人，只有一种任务可分派。然后划去所在列（行）的其它0元素，记作，这表示这列所代表的任务已分派完，不必再考虑别人了。,给只有一个0元素的列(行)的元素加圈，记作；然后划去所在的行的其它0元素，即作。,反复进行、两步，直到所有0元素都被圈出或划掉为止。转第步。,若仍有没有圈出或划掉的0元素，且同行（列）的0元素至少有2个，则找出0元素的闭回路，任选一个0元素加圈，破闭回路，直到所有0元素都已圈出和划掉为止。,若元素的数目等于矩阵的阶数，那末，这分派问题的最优解已经得到，否则转第（3）步。,（3）作最少的直线覆盖所有的0元素，已确定该系数矩阵能找到最多的独立0元素。为此按以下步骤进行：对没有的行打号；对已打的行中所有0元素所对应的列打号；再对打有的列中元素所对应的行打号；重复、，直到得不出新的打号的行、列为止。对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有的0元素的最少直线数。,（4）在未被直线覆盖的部分中找出最小元素，然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。这样得到新的系数矩阵（它的最优解和原问题相同）。,【例5】,4.3背包问题(KnapsackProblem)和贪心算法,一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有