数学建模整数规划课件.ppt

《数学建模整数规划课件.ppt》由会员分享，可在线阅读，更多相关《数学建模整数规划课件.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模整数规划2022/10/5第1页，此课件共78页哦数学建模2022/10/5第2页，此课件共78页哦第三部分 整数规划应用实例分析整数规划问题的几种求解方法分枝界定法隐枚举法匈牙利法蒙特卡洛法实验准备2022/10/5第3页，此课件共78页哦例例1 1 整数整数规划划问题 某厂某厂拟购进拟购进甲、乙两甲、乙两类类机床生机床生产产新新产产品。已知甲、乙机床品。已知甲、乙机床进进价分价分别为别为2万元和万元和3万元；安装占地面万元；安装占地面积积分分别为别为4m2和和2m2；投后的收益分；投后的收益分别为别为300元元/日和日和200元元/日。厂方目前日。厂方目前仅仅有有资资金金14万元，

2、安装面万元，安装面积积18m2。为为使收益最大，厂方使收益最大，厂方应购进应购进甲、乙机床各多少台？甲、乙机床各多少台？实例一 整数规划问题甲型乙型现有量进价（万元）2315占地面积（m2）4218利润（百元）32第4页，此课件共78页哦设设应购进甲、乙机床台数分别为x1和x2，工厂的收益为z。整数整数规规划划(IP)1.模型建立s.t.实例一 整数规划问题第5页，此课件共78页哦format short c=-3;-2;a=2,3;4,2;b=14;18;lb=0;0;x,Fval=linprog(c,a,b,lb)先不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，最优值：

3、z=14.75。2.模型求解设整数规划问题为A，与它相应的线性规划为问题B，先来求解问题B。1）舍去小数：取x1=3，x2=2，算出目标函数值z=13。2）试探：如取x1=4，x2=1时，z=14，如取x1=3，x2=3时，不满足约束条件，通过比较得到模型的最优整数解。解法一：实例一 整数规划问题第6页，此课件共78页哦1）不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，最优值：z=14.752.模型求解解法二：设整数规划问题为A，与它相应的线性规划为问题B实例一 整数规划问题第7页，此课件共78页哦2.模型求解 因为2与3之间无整数，故这两个子集的整数解必与原可行集合整数解

4、一致，这一步骤称为分枝。对问题A分枝构成两个子问题称为B1和B2。问题B1数学模型：s.t.问题B2数学模型：s.t.实例一 整数规划问题第8页，此课件共78页哦2.模型求解B2最优解：x1=4，x2=1，z2=14B1最优解：x1=3，x2=8/3，z1=43/3图解法（单纯形法）求得的最优解分别为：实例一 整数规划问题第9页，此课件共78页哦4）对问题B1在进行分枝，得问题B11和B122.模型求解问题B11数学模型：s.t.问题B12数学模型：s.t.实例一 整数规划问题第10页，此课件共78页哦 求解问题B11和B12 得到：2.模型求解5）此时由于所有子问题的目标值均小于或等于z2，

5、故问题A的目标函数最优值z*=z2=14，最优解为x1=4，x2=1。B11最优解：x1=3，x2=2，z11=13B12最优解：x1=2.5，x2=3，z12=13.5实例一 整数规划问题第11页，此课件共78页哦整数规划整数规划（Integer Programming）数学规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。整数规划分类：（1）变量全限制为整数时，称纯（完全）整数规划。（2）变量部分限制为整数的，称混合整数规划。2022/10/5第12页，此课件共78页哦整数规划整数规划特点（i）原线性规划有最优解，当自变量限制为整

6、数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值变差。（ii）整数规划最优解不能按照实数最优解简单取整而获得。2022/10/5第13页，此课件共78页哦整数规划整数规划求解方法分类（1）分枝定界法可求纯或混合整数线性规划。（2）割平面法可求纯或混合整数线性规划。（3）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。（4）匈牙利法解决指派问题（特殊“0-1”规划）。（5）蒙特卡洛法求解各种类型规划。2022/10/5第14页，此课件共78页哦分枝定界法（1）分枝：通常，把全部可

7、行解空间反复地分割为越来越小的子集，称为分枝；（2）定界：并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题。分枝定界法2022/10/5第15页，此课件共78页哦分枝定界法步骤（1）求解整数规划问题A对应的线性规划问题B（松弛问题）；（2）分枝，在松弛问题B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于bj的最大整数，构造两个约束条件将这两个约束条件，分别加入问题B，

8、求两个后继规划问题B1和B2。分枝定界法2022/10/5第16页，此课件共78页哦分枝定界法2022/10/5第17页，此课件共78页哦 1 2 3 4 5 6 7 松弛问题的可行域增加x13增加x14L1L2分枝定界法例例2 2第18页，此课件共78页哦x13x14父问题子问题结论 1：（IP）的最优解一定在某个子问题中父问题的最优值 3：子问题中的整数解都是（IP）的可行解子问题的最优解2：子问题的可行域父问题的可行域第19页，此课件共78页哦x13x14x22x23x12x13 1 2 3 4 5 6 7 4x1+x2=16.52x1+3x2=14.5z=30 x1+20 x2第20页

9、，此课件共78页哦某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai(i=1,2,7)可供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪些点可使年利润最大？0-10-1变量量例例3 3 投投资场所的所的选定定 0-1 0-1变量量第21页，此课件共78页哦s.t.1.模型建立目标函数：约束条件：v在东区，由A1，A2，A3三个点中至多选两个；v在西区，由A4，A5两个点中至少选一个；v在南区，由A6，A

10、7两个点中至少选一个。0-10-1变量量第22页，此课件共78页哦0-1 型整数规划0-1型整数规划决策变量只能取0或1的整数规划，叫做0-1整数规划。决策变量称为0-1变量(二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。在实际问题中引入0-1变量，可以把各种情况需要分别讨论的数学规划问题统一在一个问题中讨论了。2022/10/5第23页，此课件共78页哦 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表格所示。问两种货物各托运多少箱，可使获得利润为最大?货物甲乙托运限制体积每箱（米3）5424

11、重量每箱（百公斤）2513利润每箱（百元）20100-1 型整数规划例例44互相排斥的互相排斥的计划划第24页，此课件共78页哦0-1 型整数规划 1.模型建立+(1-y)M+yM 假设现在有车运和船运两种运输方式，但只能选择一种运输方式，如用车运时关于体积的限制条件为5x1+4x224(车)。如用船运时关于体积的限制条件为7x1+3x245(船)。（这两条件互相排斥）。设甲、乙两种货物的托运箱数分别为x1，x2，可获得的利润为z。设变设变量量y表示运表示运货货的方式，当的方式，当y为为1时时，用，用车车运，运，y为为0时时，用船运。，用船运。M是充分大的数是充分大的数2022/10/5第25

12、页，此课件共78页哦0-1 型整数规划 模型分析有多个相互排斥的约束条件2022/10/5第26页，此课件共78页哦相互排斥的约束条件如果有m个互相排斥的约束条件（0）若不生产第j种产品（即xj=0）j=1，2，3则问题的模型为s.t.如果生如果生产第第j种种产品，品，则其其产量量xj0，由，由xjMjyj知，知，yj1。因此，相。因此，相应的固定的固定费用在用在目目标函数中将被考函数中将被考虑。同理，如果不生同理，如果不生产第第j种种产品，品，则其其产量量xj=0，只有，只有yj为0才有意才有意义，因此，相，因此，相应的的固定固定费用不用不应在目在目标函数中被考函数中被考虑。0-1 型整数规

13、划2022/10/5第29页，此课件共78页哦0-1 型整数规划解法只检查变量取值的组合的一部分的方法。：求解下列问题隐枚举法(a)(b)(c)(d)例62022/10/5第30页，此课件共78页哦0-1 型整数规划解法解法一：隐枚举法(x1,x2,x3)z值abcd过滤条件过滤条件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3Z8(1,0,1)(1,1,0)81(1,1,1)6所以，最所以，最优解解(x1，x2，x3)T=(1，0，1)T，max z=8。2022/10/5第31页，此课件共78页哦0-1 型整数规划解法为了使最优解尽可能早出现，可

14、先将目标函数中各变量的顺序按其系数大小重新排列，这样可进一步减少计算量。隐枚举法按目按目标标函数中各函数中各变变量系数的大小重新排列各量系数的大小重新排列各变变量量最大化最大化问题问题：由小到大：由小到大最小化最小化问题问题：由大到小：由大到小2022/10/5第32页，此课件共78页哦解法二（优化）：重新排列xj的顺序(系数递减)0-1 型整数规划解法第33页，此课件共78页哦0-1型整数规划计算表目标函数z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是55x33x12x28 点(x3,x1,x2)约束条件满足条件?是否z值(1,1,0)8 8隐枚举法：共计算5次(

15、均满足约束条件)。（最优解为1，0，1，最优值8）可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大值的点是否满足约束条件)0-1 型整数规划解法过滤隐枚举法第34页，此课件共78页哦步步骤1：将将问题转化化为如下如下标准形式：准形式：其中其中cj0，且，且c1c2cn。例7求解0-1整数规划（选学-分枝隐枚举法）0-1 型整数规划解法第35页，此课件共78页哦 如约束条件为，两边同乘(-1)；如约束条件为等式，可令变量，代入目标函数和其它约束条件中，将xn消掉。按目标函数中系数由小到大的顺序重新排列变量，并将约束条件中的排列顺序

16、做相应改变。如目标函数为max z，令，可化为。如某个变量的系数为负，令，使系数变正。0-1 型整数规划解法步步骤1：将将问题转化化为标准形式：准形式：第36页，此课件共78页哦调整后的0-1规划问题变为：(a)(b)步步骤2：令所有令所有变量取量取0，求出目，求出目标函数函数值，并代入，并代入约束条件中束条件中检查是是否可行，如果可行即否可行，如果可行即为问题的最的最优解；否解；否则转下一步。下一步。令，得-10，但不满足两个约束条件。0-1 型整数规划解法第37页，此课件共78页哦 步步骤3：分支和定界。依次令各分支和定界。依次令各变量分量分别取取0或或1，将，将问题划划分分为两个子两个子

17、问题，分，分别检查解是否可行，如不可行解是否可行，如不可行继续对边界界值较小的子小的子问题分支，直到找出一个可行解分支，直到找出一个可行解为止，止，这时得到得到值的一个上界。的一个上界。分支过程见下图所示：0-1 型整数规划解法第38页，此课件共78页哦步步骤4：考察所有子考察所有子问题，有以下四种情况：，有以下四种情况：若某个子若某个子问题的的边界界值对应原原问题的可行解，的可行解，则将它的将它的边界界值与保留的与保留的值作比作比较，并取，并取较优的一个作的一个作为新的新的值。如。如所有子所有子问题都已考察完都已考察完毕，则保留下来的保留下来的值及其及其对应的解即的解即为0-1整数整数规划划

18、问题的最的最优解。解。若某个子若某个子问题的的边界界值大于保留下来的大于保留下来的值，不管其是否，不管其是否可行，可行，则将将这一分支剪掉。一分支剪掉。若某个子若某个子问题不可行（不可行（在该分支中的上级变量的值已经确定的情况下，其余变量不管取什么值都无法满足所有约束时，该枝的分枝已无可行解），），则将将这一分支剪掉。一分支剪掉。若某个子若某个子问题可行且可行且边界界值优于于值，但，但该边界界值对应的的解不是可行解，解不是可行解，则该问题待考察。如有多个待考察。如有多个问题待考察，待考察，优先先对其中最其中最优值最大的一个子最大的一个子问题进行考察，行考察，转步步骤3。0-1 型整数规划解法第

19、39页，此课件共78页哦 分支分支边界界值=-6-4，但相，但相应的解不可行，需的解不可行，需继续分支。分支。过程如上程如上图所示。所示。0-1 型整数规划解法第40页，此课件共78页哦上述求解上述求解过程也可用表格表示：程也可用表格表示：(0(0，1 1，0 0，1 1，0)0)(0(0，1 1，1 1，0 0，0)0)(0(0，0 0，1 1，0 0，0)0)(1(1，0 0，1 1，0 0，0)0)(1(1，1 1，0 0，0 0，0)0)(0(0，1 1，0 0，0 0，0)0)(1(1，0 0，0 0，0 0，0)0)(0(0，0 0，0 0，0 0，0)0)-4，剪枝1 -4，剪枝

20、-1不可行，剪枝-5 -4，剪枝-3可行 -4-4-6-8-10ba备注约束条件z 值序号0-1 型整数规划解法第41页，此课件共78页哦所以，最所以，最优解：解：即原即原问题的最的最优解解为：分枝隐枚举法0-1 型整数规划解法第42页，此课件共78页哦指派问题（0-1型）一、指派一、指派问题拟派n人去做n项工作，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高的问题，这类问题称为指派问题(分派问题、分配问题)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任任务务cij表示第表示第i个人完个人完成

21、第成第j项项任任务务的的效率。效率。第43页，此课件共78页哦二、指派二、指派问题问题的数学模型的数学模型=(Cij)指派指派问问题题系数系数矩矩阵阵B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任任务务解：解：设设指派问题（0-1型）第44页，此课件共78页哦某某单单位位现现在、四在、四项项工作需完成，工作需完成，现现在甲、乙、丙、在甲、乙、丙、丁四个人均可完成丁四个人均可完成这这四四项项任任务务。每人完成各每人完成各项项任任务务所用的所用的时间时间如如右表所示，右表所示，问应问应指派何人去完成指派何人去完成何何项项任任务务，使所需，使所需时间时间最少？最

22、少？甲甲215134乙乙1041415丙丙9141613丁丁78119ABCD任任务务人人员员满满足所有足所有约约束条件的可行解束条件的可行解xij也可也可写成表格或矩写成表格或矩阵阵形式，称形式，称为为解矩解矩阵阵(xij)=本例的一个可行解矩阵(cij)=例例8 8 指派指派问题指派问题（0-1型）第45页，此课件共78页哦指派指派问题问题数学模型的性数学模型的性质质：若从指派问题的系数的系数矩阵（cij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。独立的独立的0元素：元素：位于不同行不同列的

23、位于不同行不同列的0元素称元素称为为独立的独立的0元素。元素。结论：若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解，也就得到了问题的最优解。指派问题（0-1型）第46页，此课件共78页哦三、指派三、指派问题问题的解法（匈牙利法）的解法（匈牙利法）第一步第一步:使指派使指派问题问题的系数矩的系数矩阵经变换阵经变换，在各行各列都出，在各行各列都出现现元素。元素。（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素

24、中减去该列的最小元素。2497min24min指派问题（0-1型）第47页，此课件共78页哦经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，若能找出，就以这些独立的0元素对应解矩阵中的元素为1，其它作为0，这就得到最优解。找独立0元素的步骤如下：第二步：第二步：进进行行试试指派指派，以，以寻寻求最求最优优解。解。0（1）从只有一个从只有一个0元素的行开始，元素的行开始，给这给这个个0元素加圈，元素加圈，记记作作.然后再划去然后再划去所在列的其它所在列的其它0元素，元素，记记作作 。（2）给给只有一个只有一个0元素的列的元素的列的0元素加圈，元素加圈，记记作作；然后划

25、去；然后划去所在行的所在行的0元素，元素，记记作作 。0指派问题（0-1型）第48页，此课件共78页哦（3）反复反复(1),(2)两步，直到所有两步，直到所有0元素都被圈出和元素都被圈出和划掉划掉为为止。止。（4）若各行各列均有多于若各行各列均有多于2个的个的0元素未被圈出元素未被圈出或划掉，任或划掉，任选选其中任意一个其中任意一个0元素加圈。元素加圈。（5）若若元素的数目元素的数目m等于矩等于矩阵阵的的阶阶数数n，那，那么指派么指派问题问题的最的最优优解已得到，若解已得到，若m4）,x23又又M为为任意大任意大正数，正数，则问题则问题可表达可表达为为：指派问题（0-1型）第63页，此课件共7

26、8页哦4、用以表示固定、用以表示固定费费用的函数用的函数生生产费产费用函数：用函数：引入引入变变量量yj指派问题（0-1型）第64页，此课件共78页哦例10 东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表学生代号报酬（元/h)每天最多可安排的值班时间周一 周二 周三 周四 周五12345610109.99.810.811.36 0 6 0 70 6 0 6 04 8 3 0 55 5 6 0 43 0 4 8 00 6 0 6 3应用举例第65页，此课件共78页哦该实验室开放时间

27、是上午8点至晚上10点，开放时间内须有且仅需一名学生值班，规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人且其中必须有一名研究生，试为该实验室安排一张人员的值班表，使总支付的报酬最少解：设xij为学生i在周j的值班时间，安排学生i在周j值班否则用aij代表学生i在周j最多可安排的值班时间，ci为学生i的每h的报酬，则其数学模型为应用举例第66页，此课件共78页哦不超过可安排时间大学生每周值班不少于8h研究生每周值班不少于7h实验室每天开放14h每名学生一周值班不超过3次每天值班不超过3人每天有一名研究生值班应用举例

28、第67页，此课件共78页哦学生代号一 二 三 四 五1234566 6 6 7 6 7 4 6 4 6 8 5 8 55 5 6 63 3 2 2 2 2 2 6 3 2 6 3 最优结果为总支付报酬每周727.5元值班方案为：应用举例第68页，此课件共78页哦蒙特卡洛法整数规划蒙特卡洛法(MonteCarlomethod)也称为随机取样法，进行大统计量（N）的统计实验方法或计算机随机模拟方法。当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。大数定理：

29、均匀分布的算术平均收敛于真值中心极限定理：置信水平下的统计误差2022/10/5第69页，此课件共78页哦MonteCarlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用投针试验的方法来决定圆周率。本世纪40年代计算机的出现、特别是近年来高速计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。使用蒙特卡罗方法估算值.放置30000个随机点后,的估算值与真实值相差0.07%.蒙特卡洛法整数规划第70页，此课件共78页哦蒙特卡洛法整数规划求解问题可以分为两类:确定性问题和随机性问题。解题步骤：1.

30、根据提出的问题构造一个简单、适用的概率模型或随机模型，使问题的解对应于该模型中随机变量的某些特征（如概率、均值和方差等），所构造的模型在主要特征参量方面要与实际问题或系统相一致2.根据模型中各个随机变量的分布，在计算机上产生随机数，实现一次模拟过程所需的足够数量的随机数。通常先产生均匀分布的随机数，然后生成服从某一分布的随机数，方可进行随机模拟试验。2022/10/5第71页，此课件共78页哦蒙特卡洛法整数规划解题步骤：3.根据概率模型的特点和随机变量的分布特性，设计和选取合适的抽样方法，并对每个随机变量进行抽样（包括直接抽样、分层抽样、相关抽样、重要抽样等）。4.按照所建立的模型进行仿真试验

31、、计算，求出问题的随机解。5.统计分析模拟试验结果，给出问题的概率解以及解的精度估计。2022/10/5第72页，此课件共78页哦蒙特卡洛法整数规划例：随机变量x=0，1，2表示每分钟到达超市收款台的人数，有分布列模拟十分钟内顾客到达收款台的状况。xk012pk 0.40.30.3r=rand(1,10);for i=1:10;if r(i)0.4 n(i)=0;else if 0.4=r(i)&r(i)0.7 n(i)=1;else n(i)=2;end endendr,n2022/10/5第73页，此课件共78页哦如下图，正方形的面积A=1；1/4圆的面积B=/4。我们想象有一个容器在正方

32、形中夹有一个极薄的圆弧隔板。下小雨时搬至屋外，经一定时间后，称1/4圆的容器内的水重C，与作为一个整体的正方形中的水重D。C与D之比应该等于B与A之比，即可得例例10 10 求求的近似值蒙特卡洛法整数规划第74页，此课件共78页哦让计算机来模拟雨点落下：产生伪随机数x和y，让x的值的范围在01之间；让y的值的范围也在01之间，模拟雨点落在正方形中，当然会有的雨点落在1/4圆中。数以百万计雨点可以累计得到C和D，从而上述公式算出的近似值。关键点：落入扇形区的判据蒙特卡洛法整数规划第75页，此课件共78页哦蒙特卡洛法整数规划%随机模拟方法%c=0;x=0;y=0;pai;for i=1:20000

33、 x=rand(1,1);%雨点在x方向的位置y=rand(1,1);%雨点在y方向的位置if(x*x+y*y=1.0)c=(c+1);endendpai=(4*c/20000)模型求解2022/10/5第76页，此课件共78页哦实验准备问题习题2.3生产计划安排（P18）准备工作：1、matlab软件的熟悉2、矩阵的表示和基本操作3、随机数产生函数的用法实验要求独立完成实验报告写出完整的模型假设、模型建立、模型求解（源代码）、模型结果、模型分析（结果说明什么问题？达到建模目的？适用范围？模型是否合理？）2022/10/5第77页，此课件共78页哦谢谢！2022/10/5第78页，此课件共78页哦