数学规划模型

第六章数学规划模型数学规划模型•线性规划模型•整数规划模型•0-1整数规划模型(指派问题)•无约束规划模型•非线性规划模型(NP)•专题钢管下料数学规划模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析一、线性规划模型(LinearProgramming简记LP)•所谓线性规划问题，是求一组满足一个线性方程组（或线性不等式）的非负变量的值，使一个关于这组变量的线性目标函数达到最大值或最小值问题，这类问题的数学表达式就称为线性规划问题的数学模型。•线性规划（LP）的三大基本特征：目标函数，函数约束和符号约束（详见单纯形法部分）引例——任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：6543218121110913minxxxxxxz6,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi•一图解法：对于只有两变量的线性规划问题，可以在直角坐标平面上，用图解法求解此类线性规划问题。例（数模）P83例1；结论：最优解会在约束条件所界定的一个凸多面体（可行域）的某个顶点取得。•二代数方法：因为线性规划问题的最优解总是在边界或顶点处取得，求最优解时可只考虑边界和顶点部分的值，此方法即为代数法。缺点：计算量大导致工作量大。•三单纯形法：求解线性规划问题的最常用、最有效的算法之一•四软件求解法：Matlab优化工具箱、Lingo软件线性规划的求解方法：例321436minxxxz120..321xxxts301x5002x203xLingo程序:min=6*x1+3*x2+4*x3;x1+x2+x3=120;x1=30;x2=50;x3=20;可以转化为线性规划的问题很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如：其中，A和b为相应维数的矩阵和向量。bAxxxxnt.s.||||||min21Tnxxx][1要把上面的问题变换成线性规划问题，只要注意到事实：对任意的xi，存在ui,vi0，满足xi=ui-vi,|xi|=ui+vi。事实上，我们只要取就可以满足上面的条件。这样，记，从而我们可以把上面的问题变成||||,22iiiiiixxxxuv11[],[]TTnnuuuvvv1min()()s.t.,0niiiuvAuvbuv作业：求解引例——任务分配问题6543218121110913minxxxxxxz6,,2,1,09003.12.15.08001.14.0500600400x..654321635241ixxxxxxxxxxxxtsi二、整数规划模型(IntegerProgramming,简记IP)1.定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。2.整数规划的分类如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：•(1)变量全限制为整数时，称纯（完全）整数规划。•(2)变量部分限制为整数的，称混合整数规划。•(3)变量只能取0或1时，称之为0-1整数规划。设每月生产小、中、大型汽车的数量分别为x1,x2,x3321432xxxzMax600535.1..321xxxts60000400250280321xxx123,,xxx为非负整数例汽车厂生产计划模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234整数规划模型(IP)整数规划特点:（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：•①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。•②整数规划无可行解。•③有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。（ii）整数规划最优解不能按照实数最优解简单取整而获得。整数规划(IP)求解方法分类：（i）分枝定界法—可求纯或混合整数线性规划。（ii）割平面法—可求纯或混合整数线性规划。（iii）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法—求解各种类型规划。整数规划(IP)的计算机解法IP问题的求解可以使用Lingo等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用Matlab的函数linprog。汽车厂生产计划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丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1混合泳接力队的选拔甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员j参加泳姿i的比赛，记xij=1,否则记xij=00-1规划模型cij(秒)~队员j第i种泳姿的百米成绩约束条件每人最多入选泳姿之一cijj=1j=2j=3j=4j=5i=166.857.2787067.4i=275.66667.874.271i=38766.484.669.683.8i=458.65359.457.262.45411ijijjiMinZcx每种泳姿有且只有1人411,1,5ijixj511,1,4ijjxi模型求解model:sets:row/1..4/:;col/1..5/:;matrix(row,col):c,x;endsetsmin=@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,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(秒)=4’13”2甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4丁蛙泳c34=69.675.2，戊自由泳c45=62.457.5,方案是否调整？讨论敏感性分析？IP规划一般没有与LP规划相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的。乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳最优解：x12=x23=x34=x45=1,成绩为4’17”7c34,c45的新数据重新输入模型，用LINGO求解指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案四、无约束规划模型XfnEXmin其中1:EEfn标准形式：XfnEXmax=][minXfnEX求解无约束最优化问题的基本思想求解的基本思想(以二元函数为例)1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf连续可微多局部极小298.0f0f298.0f唯一极小(全局极小)2122212121322)(xxxxxxxxf无约束规划的求解方法:•一维搜索方法即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：(1)试探法（“成功—失败”，Fibonacci斐波那契法，0.618法等）；(2)插值法（抛物线插值法，三次插值法等）；(3)微积分中的求根法（切线法，二分法等）。•无约束极值问题方法一是用到函数的一阶导数或二阶导数，称为解析法,包括:(1)共轭梯度法（最速下降法）(2)Newton法(3)拟Newton法(变尺度法,包括DFP和BFGS)另一是仅用到函数值，称为直接法。遇到问题的目标函数不可导或导函数的解析式难以表示时，人们一般需要使用直接搜索方法。例如Powell方法Matlab优化工具箱简介1.MATLAB求解优化问题的主要函数类型模型基本函数名一元函数极小MinF（x）s.t.x1xx2x=fminbnd(‘F’,x1,x2)无约束极小MinF(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)线性规划MinXcTs.t.AX=bX=linprog(c,A,b)二次规划Min21xTHx+cTxs.t.Ax=bX=quadprog(H,c,A,b)约束极小（非线性规划）MinF(X)s.t.G(X)=0X=fmincon(‘FG’,X0)达到目标问题Minrs.t.F(x)-wr=goalX=fgoalattain(‘F’,x,goal,w)极小极大问题Minmax{Fi(x)}X{Fi(x)}s.t.G(x)=0X=fminimax(‘FG’,x0)无约束的多元函数最小值•函数fminsearch•格式1.x=fminsearch(fun,x0)%x0为初始点，fun为目标函数的表达式字符串或Matlab自定义函数的函数句柄。2.x=fminsearch(fun,x0,options)3.[x,fval]=fminsearch(…)4.[x,fval,exitflag]=fminsearch(…)5.[x,fval,exitflag,output]=fminsearch(…)•注意：fminsearch采用了Nelder-Mead型简单搜寻法。实验作业1.求下列函数的极小点：1)2123222118294xxxxxXf；2)2