西安电子科技大学数学建模讲义第6讲.pptVIP

主讲人:穆学文;数学建模专题讲座;整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 根据变量的取值性质，又可以分为全整数规划，混合整数规划，0-1整数规划等。 整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。;线性整数规划; 1、建模引例; 设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下： Max z＝20x1+10x2 (1) 5x1+4x2≤24 (2) 2x1+5x2≤13 (3) x1,x2≥0 (4) x1,x2为整数 (5); 是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？;整数规划(IP)的一般数学模型: max (min) z= Σcjxj s.t. Σaijxj ? bi(i=1,2,…m) xj ? 0 且部分或全部是整数;解法概述 当人们开始接触整数规划问题时，常会有如下两种初始想法： 因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。设想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。;;;3 线性整数规划的解法; 分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。; 分枝定界法步骤 原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P） 都称为（IP）的松驰问题。一般求解对应的松驰问题，可能会出现下面几种情况： 若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。 若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。 若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。;从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl ?[xl ] 或xl ?[xl ] +1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。 定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。 剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。;例3 求解问题 Max z=40x1+90x2 9x1+7x2 ≤ 56 7x1+20x2≤70 x1,x2≥0, 整数; 割平面法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑变量为整数这一条件，但增加线性约束条件（几何术语，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。切除的结果使整数解可能成为顶点 ;割平面法步骤： （1）去掉整数约束，用单纯形法求解。若最优解是整数，停止计算，否则转第（2）步。; 决策变量仅取为0或1的整数规划问题。 xi 是0-1变量的表示： xi ≤1， xi≥ 0 ; 【例4】某厂拟在A、B、C、D、E五个城市中建立若干个产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供的利润各处不同，有些点也可能亏本，但却能获得贷款和人力等。设数据已知（在下面建模中给出），为使总收益最大，问厂方应作出何种最优选点决策？;解题分析： 仅从目标函数看，为使总收益最大，应取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，这显然不是一种最优决策，究竟应选那些城市建点呢?; 实际不需要列出所有的可行组合。 兴趣----使目标函数最优的变量的可行组合。 按目标函数值从优到劣（本例，从大到小），顺序列出变量的组合；;隐枚举法解题步骤：; 本例变换结果如下：;目标探索法计算过程示于下表：;4.2 分派问题和匈牙利法; 【例5 】 有四项任务需分派给甲、乙、丙、丁四个人去做，这四个人都能