线性规划与非线性规划.pptx

《线性规划与非线性规划.pptx》由会员分享，可在线阅读，更多相关《线性规划与非线性规划.pptx（39页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、线性规划与非线性规划最优化是人们在工程技术、科学研究和经济管理等领域常见的问题。要表述一个最优化问题，一般需要确定三个要素：一是决策变量，通常是要求解的未知量 ；二是目标函数，通常是要优化(最小或最大)的那个目标的数学表达式，是决策变量的函数 ；三是约束条件，对决策变量的限制条件，即 允许取值的范围，称为可行域。一般地，优化模型可表述为只满足(2)的解 称为可行解，同满足(1)(2)的解 称最优解。第1页/共39页优化模型的分类 数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)0-1整数规划一般整数规划纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)连续规划第2页/共39

2、页一、线性规划1、引例问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？第3页/共39页模型 设在甲车床上加工工件1、2、3的数量分别为 在乙车床上加工工件1、2、3的数量分别为第4页/共39页问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元

3、/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？模型 设需要一级、二级检验员的人数分别为 人，应付检验员工资为 因检验员错检而造成的损失为第5页/共39页2、线性规划模型的标准形式 或矩阵形式 其中 是决策变量，是约束矩阵，3、线性规划模型的实用形式 (1)(2)注；当前MATLAB只支持第一种形式。第6页/共39页 4、用MATLAB优化工具箱解线性规划 (1)模型1：命令：x=linprog(c,A,b)(2)模型2：命令：x=linprog(c,A1,b1,A2,b2)

4、注：1若没有不等式 存在，则令 2 输出的x为最优解。第7页/共39页(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乘子。第8页/共39页例1：见MATLAB程序（x

5、ianxingguihua1）第9页/共39页例2：见MATLAB程序（xianxingguihua2）第10页/共39页例3：问题一的解答改写为见MATLAB程序（xianxingguihua3）第11页/共39页结果：即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.第12页/共39页例4：问题二的解答改写为见MATLAB程序（xianxingguihua4）第13页/共39页结果：即只需聘用9个一级检验员。注：本问题应还有一个约束条件：x1、x2取整数，故它属于一个整数线性规划问题，这里当成一个线性规划求解，求得

6、最优解刚好是整数x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.第14页/共39页二、非线性规划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);第15页/共39页例1：改写成标准形式：第16页/共39页编程(见MATLAB程序(e

7、rciguihua1)结果：第17页/共39页2、一般非线性规划标准形式：其中 为n维变元向量，均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同用MATLAB求解上述问题，基本步骤分三步。第18页/共39页(1)首先建立M文件,用来定义目标函数f(x)，形式为 function f=fun(x)f=f(x);(2)若有非线性约束条件：或 则建立M文件定义函数 一般形式为 function c1,c2=c(x)c1=c2=(3)建立主程序。求解非线性规划的函数是fmincon,调用格式为 x=fmincon(fun,x0,A1,b1);x,fv,ef,out,lag,grad,

8、hess=fmincon(fun,x0,A1,b1,A2,b2,v1,v2,c,opt,P1,P2,)第19页/共39页注意：(1)fmincon函数提供了大型优化算法和中型优化算法。当options参数的GradObj设置为on时必须给出fun函数的梯度，并且只有上下界约束或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。(2)fmincon函数的中型算法使用的是序列二次规划法(SQP方法)。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵。(3)fmincon函数可能会给出局部最优解，这与初值x0的选取有关。第20页/共

9、39页例2：改写成标准形式：建立M文件第21页/共39页建立主程序(见MATLAB程序(feixianxingguihua1)结果：第22页/共39页例3：建立M文件定义目标函数：建立M文件定义非线性约束条件：第23页/共39页编写主程序(见MATLBA程序(feixianxingguihua2)结果：第24页/共39页例4：建立M文件定义目标函数：建立M文件定义非线性约束条件：第25页/共39页编写主程序(见MATLBA程序(feixianxingguihua3)结果：第26页/共39页补充知识：用LINDO、LINGO优化工具箱解线性规划LINDO、LINGO能求解的优化模型优化模型连续优

10、化整数规划(IP)二次规划(QP)非线性规划(NLP)线性规划(LP)LINDOLINGO第27页/共39页一、LINDO软件包引例：加工奶制品的生产计划每天：50桶牛奶，时间：480小时，至多加工100千克 ，制定生产计划，使每天获利最大。35元可买到1桶牛奶，买吗？若买，每天最多买多少？可聘用临时工人，付出的工资最多是每小时几元?获利增加到 30元/千克，是否应改变生产计划？一桶牛奶3千克A14千克A2获利24元/千克获利16元/千克12小时8小时或第28页/共39页建立模型 桶牛奶生产 桶牛奶生产 获利 获利 决策变量决策变量 目标函数目标函数 约束条件约束条件线性规划模型(LP)每天获

11、利原料供应劳动时间加工能力非负约束第29页/共39页模型求解：20桶牛奶生产 ，30桶牛奶生产 ，利润为3360元。原料无剩余时间无剩余加工能力剩余40三种资源第30页/共39页基变量的reduced cost值为0；对于非基变量，reduced cost值表示该非基变量增加一个单位时（其他非基变量保持不变），目标函数减少量（对max型问题）。影子价格原料增1单位，利润增48时间增1单位，利润增2能力增减不影响利润35元可买到1桶牛奶，要买吗？35”（或“=”（或“=”）功能相同。变量与系数间可有空格(甚至回车),但无运算符。变量名以字母开头，不能超过8个字符。变量名不区分大小写(包括LIND

12、O中的关键字)。目标函数所在行是第一行，第二行起为约束条件。行号(行名)自动产生或人为定义.行名以“）”结束。行中注有“!”符号的后面部分为注释。如：!Its Comment。在模型的任何地方都可以用“TITLE”对模型命名(最多72个字符)，如：TITLE This Model is only an Example。第34页/共39页变量与系数间可有空格，但不能有任何运算符号(如乘号*)。变量不能出现在一个约束条件的右端。表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2。表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2。缺省假

13、定所有变量非负，可在模型的“END”语句后用“FREE name”将变量name的非负假定取消。可在“END”后用“SUB”或“SLB”设定变量上下界，例如：“sub x1 10”的作用等价于“x1=10”，但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。“END”后对0-1变量说明：INT n 或 INT name，前者指前n个变量标识为整型。“END”后对整数变量说明：GIN n 或 GIN name。第35页/共39页2、状态窗口(LINDO Solver Status)当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：分枝数：1所用时间：秒（太快了，还不到秒）刷新本界面的间隔:1(秒)第36页/共39页二、LINGO软件包1、LINGO软件简介LINGO模型的优点：(1)包含了LINDO的全部功能 (2)提供了灵活的编程语言（矩阵生成器）对简单的LINGO程序：LINGO和LINDO一样编程，但LINGO与LINDO语法有差异.第37页/共39页2、LINGO与LINDO的程序比较LINDO程序LINGO程序第38页/共39页感谢您的观看！第39页/共39页