线性规划与非线性规划.ppt
《线性规划与非线性规划.ppt》由会员分享,可在线阅读,更多相关《线性规划与非线性规划.ppt(39页珍藏版)》请在三一办公上搜索。
1、第六讲,线性规划与非线性规划,线性规划与非线性规划,最优化是人们在工程技术、科学研究和经济管理等领域常见的问题。要表述一个最优化问题,一般需要确定三个要素:一是决策变量,通常是要求解的未知量;二是目标函数,通常是要优化(最小或最大)的那个目标的数学表达式,是决策变量的函数;三是约束条件,对决策变量的限制条件,即 允许取值的范围,称为可行域。一般地,优化模型可表述为只满足(2)的解 称为可行解,同满足(1)(2)的解 称最优解。,优化模型的分类,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),0-1整数规划一般整数规划,纯整数规划(PIP)混合整数规划(MIP),整数规划(IP)
2、,连续规划,一、线性规划,1、引例问题一:任务分配问题:某车间有甲、乙两台机床,可用于加工三种工件.假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?,模型 设在甲车床上加工工件1、2、3的数量分别为 在乙车床上加工工件1、2、3的数量分别为,问题二:某厂每日8小时的产量不低于1800件.为了进行质量控制,计划聘请两种不同水平的检验员.一级检验员的标准为:速度25件/小时,正确率98%,计时工资4元/小时;二级检验
3、员的标准为:速度15件/小时,正确率95%,计时工资3元/小时.检验员每错检一次,工厂要损失2元.为使总检验费用最省,该工厂应聘一级、二级检验员各几名?模型 设需要一级、二级检验员的人数分别为 人,应付检验员工资为 因检验员错检而造成的损失为,2、线性规划模型的标准形式 或矩阵形式 其中 是决策变量,是约束矩阵,3、线性规划模型的实用形式(1)(2),注;当前MATLAB只支持第一种形式。,4、用MATLAB优化工具箱解线性规划(1)模型1:命令:x=linprog(c,A,b)(2)模型2:命令:x=linprog(c,A1,b1,A2,b2)注:1若没有不等式 存在,则令 2 输出的x为最
4、优解。,(3)模型3:命令:1 x=linprog(c,A1,b1,A2,b2,v1,v2)2 x=linprog(c,A1,b1,A2,b2,v1,v2,x0)注:1 若没有等式约束:,令 2 x0表示初始解。(4)命令:x,fval,ef,out,lambda=linprog(c,A1,b1,A2,b2,v1,v2,x0)输出x为最优解,fval为最优值,ef为程序停止的标志,out为个结构变量,包括程序运行的有关信息,lambda也是结构变量,对应于相应的约束的Lagrange乘子。,例1:,见MATLAB程序(xianxingguihua1),例2:,见MATLAB程序(xianxin
5、gguihua2),例3:问题一的解答改写为,见MATLAB程序(xianxingguihua3),结果:,即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3,可在满足条件的情况下使总加工费最小为13800.,例4:问题二的解答改写为,见MATLAB程序(xianxingguihua4),结果:即只需聘用9个一级检验员。注:本问题应还有一个约束条件:x1、x2取整数,故它属于一个整数线性规划问题,这里当成一个线性规划求解,求得最优解刚好是整数x1=9,x2=0,故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数,将其取整后不一定是相应整数规划的最优解,这
6、样的整数规划应用专门的方法求解.,二、非线性规划,1、二次规划标准形式:MATLAB调用格式:(1)x=quadprog(H,C,A1,b1);(2)x=quadprog(H,C,A1,b1,A2,b2,v1,v2);(3)x,fval,exitflag,output=quadprog(H,C,A1,b1,A2,b2,v1,v2,x0,options);,例1:改写成标准形式:,编程(见MATLAB程序(erciguihua1)结果:,2、一般非线性规划标准形式:其中 为n维变元向量,均为非线性函数组成的向量,其他变量的含义与线性规划、二次规划中相同用MATLAB求解上述问题,基本步骤分三步。
7、,(1)首先建立M文件fun.m,用来定义目标函数f(x),形式为 function f=fun(x)f=f(x);(2)若有非线性约束条件:或 则建立M文件c.m定义函数 一般形式为 function c1,c2=c(x)c1=c2=(3)建立主程序。求解非线性规划的函数是fmincon,调用格式为 x=fmincon(fun,x0,A1,b1);x,fv,ef,out,lag,grad,hess=fmincon(fun,x0,A1,b1,A2,b2,v1,v2,c,opt,P1,P2,),注意:(1)fmincon函数提供了大型优化算法和中型优化算法。当options参数的GradObj设
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 非线性 规划
链接地址:https://www.31ppt.com/p-4936303.html