线性规划与非线性规划.ppt

第六讲,线性规划与非线性规划,线性规划与非线性规划,最优化是人们在工程技术、科学研究和经济管理等领域常见的问题。要表述一个最优化问题，一般需要确定三个要素：一是决策变量，通常是要求解的未知量；二是目标函数，通常是要优化(最小或最大)的那个目标的数学表达式，是决策变量的函数；三是约束条件，对决策变量的限制条件，即 允许取值的范围，称为可行域。一般地，优化模型可表述为只满足(2)的解 称为可行解，同满足(1)(2)的解 称最优解。,优化模型的分类,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),0-1整数规划一般整数规划,纯整数规划(PIP)混合整数规划(MIP),整数规划(IP),连续规划,一、线性规划,1、引例问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,模型 设在甲车床上加工工件1、2、3的数量分别为 在乙车床上加工工件1、2、3的数量分别为,问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度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为最优解。,(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程序（xianxingguihua2）,例3：问题一的解答改写为,见MATLAB程序（xianxingguihua3）,结果：,即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.,例4：问题二的解答改写为,见MATLAB程序（xianxingguihua4）,结果：即只需聘用9个一级检验员。注：本问题应还有一个约束条件：x1、x2取整数，故它属于一个整数线性规划问题，这里当成一个线性规划求解，求得最优解刚好是整数x1=9，x2=0，故它就是该整数规划的最优解.若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解.,二、非线性规划,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求解上述问题，基本步骤分三步。,(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设置为on时必须给出fun函数的梯度，并且只有上下界约束或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。(2)fmincon函数的中型算法使用的是序列二次规划法(SQP方法)。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵。(3)fmincon函数可能会给出局部最优解，这与初值x0的选取有关。,例2：改写成标准形式：建立M文件fun1.m,建立主程序(见MATLAB程序(feixianxingguihua1)结果：,例3：建立M文件fun2.m定义目标函数：建立M文件c.m定义非线性约束条件：,编写主程序(见MATLBA程序(feixianxingguihua2)结果：,例4：建立M文件fun3.m定义目标函数：建立M文件c1.m定义非线性约束条件：,编写主程序(见MATLBA程序(feixianxingguihua3)结果：,补充知识：用LINDO、LINGO优化工具箱解线性规划,LINDO、LINGO能求解的优化模型,优化模型,连续优化,整数规划(IP),二次规划(QP),非线性规划(NLP),线性规划(LP),LINDO,LINGO,一、LINDO软件包,引例：加工奶制品的生产计划每天：50桶牛奶，时间：480小时，至多加工100千克，制定生产计划，使每天获利最大。35元可买到1桶牛奶，买吗？若买，每天最多买多少？可聘用临时工人，付出的工资最多是每小时几元?获利增加到 30元/千克，是否应改变生产计划？,一桶牛奶,3千克A1,4千克A2,获利24元/千克,获利16元/千克,12小时,8小时,或,建立模型,桶牛奶生产,桶牛奶生产,获利,获利,决策变量,目标函数,约束条件,线性规划模型(LP),每天获利原料供应劳动时间加工能力非负约束,模型求解：,20桶牛奶生产，30桶牛奶生产，利润为3360元。,原料无剩余时间无剩余加工能力剩余40,三种资源,基变量的reduced cost值为0；对于非基变量，reduced cost值表示该非基变量增加一个单位时（其他非基变量保持不变），目标函数减少量（对max型问题）。,影子价格原料增1单位，利润增48时间增1单位，利润增2能力增减不影响利润,35元可买到1桶牛奶，要买吗？35 48,应该买！聘用临时工人付出的工资最多每小时几元？2元,给出松弛变量的值，表示约束是否起作用约束,“资源”剩余为零的约束为紧约束（有效约束）。,灵敏性分析,最优解不变时目标系数允许变化范围(约束条件不变),系数范围，系数范围。,获利增加到 30元/千克，应否改变生产计划？不变！因为 系数由 增加到，在允许范围之内。,影子价格有意义时约束右端的允许变化范围(目标函数不变),原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？最多买10桶,1、使用Lindo的注意事项模型以MAX或MIN定义目标函数，约束条件前一定要有ST或S.T.,END表示约束条件输入结束。“”（或“=”（或“=”）功能相同。变量与系数间可有空格(甚至回车),但无运算符。变量名以字母开头，不能超过8个字符。变量名不区分大小写(包括LINDO中的关键字)。目标函数所在行是第一行，第二行起为约束条件。行号(行名)自动产生或人为定义.行名以“）”结束。行中注有“!”符号的后面部分为注释。如：!Its Comment。在模型的任何地方都可以用“TITLE”对模型命名(最多72个字符)，如：TITLE This Model is only an Example。,变量与系数间可有空格，但不能有任何运算符号(如乘号*)。变量不能出现在一个约束条件的右端。表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2。表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2。缺省假定所有变量非负，可在模型的“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。,2、状态窗口(LINDO Solver Status),当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒),二、LINGO软件包,1、LINGO软件简介LINGO模型的优点：(1)包含了LINDO的全部功能(2)提供了灵活的编程语言（矩阵生成器）对简单的LINGO程序：LINGO和LINDO一样编程，但LINGO与LINDO语法有差异.,2、LINGO与LINDO的程序比较,LINDO程序,LINGO程序,