第六讲 线性规划与非线性规划.ppt

第六讲 线性规划与 非线性规划 线性规划与非线性规划 最优化是人们在工程技术、科学研究和经济管理等领域常见的问题。要表述一个最优化问题，一般需要确定三个要素：一是决策变量，通常是要求解的未知量 ；二是目标函数，通常是要优化(最小或最大)的那个目标的数学表达式，是决策变量的函数 ；三是约束条件，对决策变量的限制条件，即 允许取值的范围，称为可行域。 一般地，优化模型可表述为 只满足(2)的解 称为可行解，同满足(1)(2)的解 称最优解。 优化模型的分类 一、线性规划 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) 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： 例2： 例3：问题一的解答 改写为 结果： 例4：问题二的解答 改写为 结果： 即只需聘用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)