西安电子科技大学数学建模讲义第六讲专题省名师优质课赛课获奖课件市赛课一等奖课件

主讲人:穆学文西安电子科技大学数学系Email:mxw1334@126.com数学建模讲义第1页数学建模专题讲座最优化模型---线性整数规划

第2页整数规划是一类要求变量取整数值数学规划，可分成线性和非线性两类。依据变量取值性质，又能够分为全整数规划，混合整数规划，0-1整数规划等。整数规划是数学规划中一个较弱分支，当前只能解中等规模线性整数规划问题，而非线性整数规划问题，还没有好方法。整数规划介绍第3页线性整数规划1、建模引例。2、线性整数规划模型3、线性整数规划主要算法。4、0-1规划选讲第4页

1、建模引例例1:某厂拟用火车装运甲、乙两种货物集装箱，每箱体积、重量、可赢利润以及装运所受限制以下：

货物集装箱体积(米3)重量(百斤)利润(百元) 甲5220乙 4510托运限制24 13 问两种货物各装运多少箱，可使取得利润最大？第5页

设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型以下：Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)x1,x2≥0(4)x1,x2为整数(5)第6页

是不是可经过把不考虑整数要求求得最优解经过“化整”得到满足整数要求最优解呢？它和线性规划问题区分在于条件(5)。

此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足全部约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。所以要专门研究整数规划解法。第7页整数规划(IP)普通数学模型:max(min)z=Σcjxjs.t.Σaijxj

bi(i=1,2,…m)

xj

0且部分或全部是整数2.线性整数规划模型第8页解法概述当人们开始接触整数规划问题时，常会有以下两种初始想法：因为可行方案数目有限，所以经过一一比较后，总能求出最好方案，比如，背包问题充其量有2n-1种方式；连线问题充其量有n!种方式；实际上这种方法是不可行。构想计算机每秒能比较1000000个方式，那么要比较完20!（大于2*1018）种方式，大约需要800年。比较完260种方式，大约需要360世纪。第9页先放弃变量整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量取值很大时，才有成功可能性，而当变量取值较小时，尤其是0-1规划时，往往不能成功。例2求以下问题：MaxZ=3x1+13x2s.t.2x1+9x2

4011x1-8x2

82x1,x2

0,且取整数值第10页O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。第11页3线性整数规划解法枚举法仅仅对极小规模问题有效分支定界法应用比较广泛，对中小规模问题割平面法应用比较广泛，对中小规模问题第12页

分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划最主要方法。3.1分枝定界法第13页

分枝定界法步骤原问题松驰问题：任何整数规划（IP），凡放弃一些约束条件（如整数要求）后，所得到问题（P）都称为（IP）松驰问题。普通求解对应松驰问题，可能会出现下面几个情况：若所得最优解各分量恰好是整数，则这个解也是原整数规划最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划最优解，转下一步。第14页从不满足整数条件基变量中任选一个xl进行分枝，它必须满足xl

[xl]或xl

[xl]+1中一个，把这两个约束条件加进原问题中，形成两个互不相容子问题（两分法）。定界：把满足整数条件各分枝最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题最优值与界值比较，凡不优或不能更优分枝全剪掉，直到每个分枝都查清为止。第15页例3求解问题Maxz=40x1+90x29x1+7x2≤

567x1+20x2≤70x1,x2≥0,整数R0:z0=356x1=4.81x2=1.82R1:z1=349x1=4.00x2=2.10R2:z2=341x1=5.00x2=1.57R12:z12=327x1=1.42x2=3.00x2≥3R11:z11=340x1=4.00x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可行解x1≤4x1≤1x1≥5x1≥2问题R0为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0问题R2为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

0问题R1为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0x2≤2问题R11为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0问题R12为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1,x2≥

0第16页割平面法基础依然是用解线性规划方法去解整数规划问题。首先不考虑变量为整数这一条件，但增加线性约束条件（几何术语，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。切除结果使整数解可能成为顶点分枝定解法是对原问题可行解域进行了切割，切割方法是对取非整数解相邻整数作附加约束，约束方程简单，但子问题因为分枝增多而成指数增加。关键：怎样找到割平面约束方程，使切割后最终得到这么可行解域，它一个整数坐标顶点恰好是问题最优解。3.2割平面法第17页割平面法步骤：（1）去掉整数约束，用单纯形法求解。若最优解是整数，停顿计算，不然转第（2）步。（2）寻求附加条件（割平面方程），其方法后述。（3）将割平面方程标准化后加到约束方程组中求解，如所得最优解仍为非整数，则转到第（2）步继续进行，直到找到最优整数解为止。第18页

决议变量仅取为0或1整数规划问题。xi

是0-1变量表示：xi

≤1，xi≥040-1规划把上约束加到约束方程组中就和普通整数规划约束条件一致了。故0-1型整数可用普通求整数规划方法求解，但0-1型整数规划是整数规划特殊情形，所以，有特殊解法。4.1隐枚举法第19页【例4】某厂拟在A、B、C、D、E五个城市中建立若干个产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供利润各处不一样，有些点也可能赔本，但却能取得贷款和人力等。设数据已知（在下面建模中给出），为使总收益最大，问厂方应作出何种最优选点决议？上述各城市是否被选，可用决议变量xi表示，xi=1表示被选，不然xi=0，依据已知数据可建数模以下:第20页解题分析：仅从目标函数看，为使总收益最大，应取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个。把每种组合列出，代入约束条件检验是否可行，可行解代入目标函数比较大小得出最优解----枚举法，繁琐!第21页实际不需要列出全部可行组合。兴趣----使目标函数最优变量可行组合。按目标函数值从优到劣（本例，从大到小），次序列出变量组合；过滤性条件2.逐一检验变量组合可行性，最先满足全部约束条件变量组合就是最优解；3.而劣于最优解组合即使可行，也不用列出和检验；4.相当于把枚举法得出全部非优组合隐去不算了，故称为隐枚举法。第22页隐枚举法解题步骤：（1）变换目标函数和约束条件①价值系数cj前符号统一在目标函数求极大时，统一带负号；求极小值时，统一带正号。在不满足上述要求时，用代入目标函数。本例求极大值，x1,x2,x3前符号不满足，用代入目标函数和约束条件；②按值从小到大排列决议变量项本例变换结果以下：第23页本例变换结果以下：（2）用目标函数值探索法求最优解由公式，当时，Z=Z0=17.8为上限。假如这个组合又满足全部约束条件，则它为最优解;不然，按劣于Z0组合解方向探索可行解。按由小到大逐项计算组合解值及其对应Z值，代入约束条件检验可行性，如全部满足，即为最优解。最大值第24页目标探索法计算过程示于下表：Z值组合解是否满足约束是否可行解x5x4017.800000×否1.516.310000×否2.015.801000√×否3.514.311000√×否3.814.000100√×否4.513.300010√×否5.312.510100√√√是最优解为：x1=1,x2=0,x3=1,x4=0,x5=1,即在A,C,E三个城市设联营点，可获最大收益12.5（十万元）。第25页4.2分配问题和匈牙利法AssignmentProblem有n项任务，恰好n个人负担，第i人完成第j项任务花费(时间或费用等)为cij，怎样分配使总花费最省？第j项工作由一个人做第i人做一项工作分配第i人做第j项工作不分配第i人做第j项工作第26页【例5】有四项任务需分配给甲、乙、丙、丁四个人去做，这四个人都能负担上述四项任务，但完成各项任务所需时间以下表所表示。问应怎样分配任务可使完成任务总工时最少？

任务人员ABCD甲917167乙1271416丙8171417丁79119问题分析：引入决议变量xij,第27页分配问题是0-1规划问题。因每个人仅能负担一项任务，每项任务也只能分配给一个人，所以上述问题线性规划模型为：满足该约束条件可行解可写成矩阵形式分配问题是线性规划，又是运输问题。第28页匈牙利算法步骤：（1）变换系数矩阵，使其每行每列都出现0元素。首先每行减去该行最小数，再每列减去该列最小数。-7-7-8-7-4(cij’)(2)进行试分配，寻求最优解。经第（1）步变换后，系数矩阵每行每列都已经有了0元素，但需找出n个独立0元素，为此，按以下步骤进行。第29页①从只有一个0元素行（列）0元素开始，给这个0元素加圈，即作◎，这表示对这行所代表人，只有一个任务可分配。然后划去◎所在列（行）其它0元素，记作

，这表示这列所代表任务已分配完，无须再考虑他人了。②给只有一个0元素列(行)元素加圈，记作◎；然后划去◎所在行其它0元素，即作。③重复进行①、②两步，直到全部0元素都被圈出或划掉为止。转第⑤步。④若仍有没有圈出或划掉0元素，且同行（列）0元素最少有2个，则找出0元素闭回路，任选一个0元素加圈，破闭回路，直到全部0元素都已圈出和划掉为止。第30页⑤若◎元素数目等于矩阵阶数，那末，这分配问题最优解已经得到，不然转第（3）步。（3）作最少直线覆盖全部0元素，已确定该系数矩阵能找到最多独立0元素。为此按以下步骤进行