《数学规划模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学规划模型ppt课件.ppt（49页珍藏版）》请在三一办公上搜索。
1、第六章数学规划模型,数学规划模型,线性规划模型整数规划模型0-1整数规划模型(指派问题)无约束规划模型非线性规划模型(NP)专题 钢管下料,数学规划模型,实际问题中的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,多元函数条件极值,决策变量个数n和约束条件个数m较大,最优解在可行域的边界上取得,数学规划,线性规划非线性规划整数规划,重点在模型的建立和结果的分析,一、线性规划模型(Linear Programming 简记LP),所谓线性规划问题，是求一组满足一个线性方程组（或线性不等式）的非负变量的值，使一个关于这组变量的线性目标函数达到最大值或最小值问题，这类问题的数学表达式就
2、称为线性规划问题的数学模型。线性规划（LP）的三大基本特征：目标函数，函数约束和符号约束（详见单纯形法部分）,引 例任务分配问题：,某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,一 图解法：对于只有两变量的线性规划问题，
3、可以在直角坐标平面上，用图解法求解此类线性规划问题。例（数模）P83 例1；结论：最优解会在约束条件所界定的一个凸多面体（可行域）的某个顶点取得。二 代数方法：因为线性规划问题的最优解总是在边界或顶点处取得，求最优解时可只考虑边界和顶点部分的值，此方法即为代数法。缺点：计算量大导致工作量大。三 单纯形法：求解线性规划问题的最常用、最有效的算法之一 四 软件求解法：Matlab优化工具箱、Lingo软件,线性规划的求解方法：,Lingo程序:min=6*x1+3*x2+4*x3;x1+x2+x3=120;x1=30;x2=20;,可以转化为线性规划的问题,很多看起来不是线性规划的问题也可以通过变
4、换变成线性规划问题来解决。如：其中，A和b为相应维数的矩阵和向量。,要把上面的问题变换成线性规划问题，只要注意到事实：对任意的xi，存在ui,vi0，满足 xi=ui-vi,|xi|=ui+vi。事实上，我们只要取 就可以满足上面的条件。这样，记，从而我们可以把上面的问题变成,作业：求解引例任务分配问题,二、整数规划模型(Integer Programming,简记IP),定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。2.整
5、数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：(1)变量全限制为整数时，称纯（完全）整数规划。(2)变量部分限制为整数的，称混合整数规划。(3)变量只能取0或1时，称之为0-1整数规划。,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,例 汽车厂生产计划,模型建立,整数规划模型(IP),整数规划特点:,（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。（ii）整数规划最优
6、解不能按照实数最优解简单取整而获得。,整数规划(IP)求解方法分类：,（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划。,整数规划(IP)的计算机解法,IP问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用Matlab的函数li
7、nprog。,汽车厂生产计划Lingo程序,max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3=600;280*x1+250*x2+400*x3=60000;gin(x1);gin(x2);gin(x3);,三、0-1整数规划模型(指派问题),0-1整数规划是整数规划中的特殊情形，它的变量仅取值0或1。这时称xi为0-1变量，或称二进制变量。xi仅取值0或1,丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,例1 混合泳接力队的选拔,5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=1
8、20种。,目标函数,若选择队员j参加泳姿i 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员j 第i 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,模型求解,model:sets:row/1.4/:;col/1.5/:;matrix(row,col):c,x;endsets min=sum(matrix:c*x);for(matrix:bin(x);for(col(j):sum(row(i):x(i,j)=1);for(row(i):sum(col(j):x(i,j)=1);data:c=66.8,57.2,78,70,67.4,75.6,66
9、,67.8,74.2,71,87,66.4,84.6,69.6,83.8,58.6,53,59.4,57.2,62.4;enddataend,输入LINGO求解,最优解：x12=x23=x34=x41=1,其它变量为0;成绩为253.2(秒)=413”2,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,丁蛙泳c34=69.675.2，戊自由泳c45=62.4 57.5,方案是否调整？,讨论,敏感性分析？,IP规划一般没有与LP规划相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的。,乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,最优解：x12=x23=x34=x45=1,成绩为417”7,c
10、34,c45 的新数据重新输入模型，用LINGO求解,指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.,四、无约束规划模型,标准形式：,求解无约束最优化问题的基本思想,求解的基本思想(以二元函数为例),5,3,1,连续可微,多局部极小,唯一极小(全局极小),无约束规划的求解方法:,一维搜索方法 即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：(1)试探法（“成功失败”，Fibonacci斐波那契法，0.618法等）；(2)插值法（抛物线插值法，三次插值法等）；(3)微积分中的求根法（切线法，二分法等）。无约束极值问
11、题方法 一是用到函数的一阶导数或二阶导数，称为解析法,包括:(1)共轭梯度法（最速下降法）(2)Newton法(3)拟Newton法(变尺度法,包括DFP和 BFGS)另一是仅用到函数值，称为直接法。遇到问题的目标函数不可导或导函数的解析式难以表示时，人们一般需要使用直接搜索方法。例如Powell方法,Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,无约束的多元函数最小值,函数 fminsearch格式 x=fminsearch(fun,x0)%x0为初始点，fun为目标函数的表达式字符串或Matlab自定义函数的函数句柄。x=fminsearch(fun,x0,optio
12、ns)x,fval=fminsearch()x,fval,exitflag=fminsearch()x,fval,exitflag,output=fminsearch()注意：fminsearch采用了Nelder-Mead型简单搜寻法。,实验作业,五、非线性规划模型(NP),定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式:（1）其中，是定义在 En 上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,非线性规划的基本解法,一般说来，解非线性规划要比解线性规划问题困难得多。而且，也
13、不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。线性规划与非线性规划的区别 如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点 出发，按照某一特定的迭代规则产生一个点列，使得 当是有穷点列时，其最后一个点是(NP)的最优解；当是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。,非线性规划的基本解法,SUTM外点法,SU
14、TM内点法（障碍罚函数法）,1、罚函数法,2、近似规划法,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法 其一为SUMT外点法，其二为SUMT内点法,近似规划法,近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似,近似规划法,每得到一个近似解后，都从这点出发，重复以上步骤,这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序
15、列，经验表明，这样的序列往往收敛于非线性规划问题的解。,Matlab解法,二次规划(quadprog)一般非线性规划(fmincon),生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,专题 钢管下料,原料下料问题,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,问题1.如何下料最节省?,例1 钢管下料,问题2.客户增加需求：,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢管下料,为满足客户需要，按照哪些
16、种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12,x5=15,其余为0；最优值：27。,整数约束：xi 为整数,当余料没有用处时，通常以总根数最少为目标,目标2（总根数）,钢管下料问题1,约束条件不变,最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。,xi 为整数,按模式2切割15根，按模式5切割5根，按模式7
17、切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米”相比,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。,决策变量,xi 按第i 种模式切割的原料钢管根数(i=1,2,3),r1i,r2i,r3i,r4i 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整
18、数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=31,模式排列顺序可任定,钢管下料问题2,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,LINGO求解整数非线性规划模型,Local optimal solution found at iteration:12211 Objective value:28.00
19、000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。,下料问题的建模,确定下料模式,构造优化模型,规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用缩小可行域的方法进行化简，但要保证最优解的存在。,一维问题（如钢管下料）,二维问题（如易拉罐下料）,具体问题具体分析（比较复杂）,
