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

第六讲线性规划与非线性规划线性规划与非线性规划最优化是人们在工程技术、科学研究和经济管理等领域常见的问题。要表述一个最优化问题，一般需要确定三个要素：一是决策变量，通常是要求解的未知量；二是目标函数，通常是要优化(最小或最大)的那个目标的数学表达式，是决策变量的函数；三是约束条件，对决策变量的限制条件，即允许取值的范围，称为可行域。一般地，优化模型可表述为只满足(2)的解称为可行解，同满足(1)(2)的解称最优解。xx()fxmin()(1)..()0,1,2,(2)xizfxstgximx*xx优化模型的分类数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)0-1整数规划一般整数规划纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)连续规划一、线性规划1、引例问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900模型设在甲车床上加工工件1、2、3的数量分别为在乙车床上加工工件1、2、3的数量分别为123,,,xxx456,,.xxx123456142536123456min1391011128..4006005000.41.18000.51.21.39000,1,2,6izxxxxxxstxxxxxxxxxxxxxi问题二：某厂每日8小时的产量不低于1800件.为了进行质量控制，计划聘请两种不同水平的检验员.一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检验员每错检一次，工厂要损失2元.为使总检验费用最省，该工厂应聘一级、二级检验员各几名？模型设需要一级、二级检验员的人数分别为人，应付检验员工资为因检验员错检而造成的损失为12,xx121284833224,xxxx1212(8252%8155%)2812xxxx121212121211221212min(3224)(812)4036..82581518005345825180098151800150,00,0zxxxxxxstxxxxxxxxxxxx2、线性规划模型的标准形式或矩阵形式其中是决策变量，是约束矩阵，，3、线性规划模型的实用形式(1)(2)11min..,1,2,0,1,2,niiinikkikizcxstaxbinxinmin..0TzcxstAxbx12()Tnxxxx12().TnccccijmnAamn12()Tmbbbb112212min..TzcxstAxbAxbvxv1122312min..TzcxstAxbbAxbvxv注；当前MATLAB只支持第一种形式。4、用MATLAB优化工具箱解线性规划(1)模型1：命令：x=linprog(c,A,b)(2)模型2：命令：x=linprog(c,A1,b1,A2,b2)注：[1]若没有不等式存在，则令[2]输出的x为最优解。min..TzcxstAxb1122min..TzcxstAxbAxb11Axb11[],[].Ab(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乘子。112212min..TzcxstAxbAxbvxv22[],[].Ab22Axb例1：123456123456142536max0.40.280.320.720.640.6..0.010.010.010.030.030.038500.020.057000.020.051000.030.089000,1,2,6jzxxxxxxstxxxxxxxxxxxxxj见MATLAB程序（xianxingguihua1）例2：112323121233121323min634min(634)111120....12001050300503020020xzxxxzxxxstxstxxxxxxxxxx见MATLAB程序（xianxingguihua2）例3：问题一的解答改写为123456min(1391011128)0.41.11000800..0000.51.21.3900100100400010010600,0001001500zxstxxxxxxxxx见MATLAB程序（xianxingguihua3）结果：即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.例4：问题二的解答改写为12121122min(4036)..5345109,00115xzxxstxxxxx见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);1122121min2..TTzxHxcxstAxbAxbvxv例1：改写成标准形式：221211221212121212min(,)2333..2323342,0fxxxxxxxxstxxxxxxxx1112221212124331min()3612213..13412320Txxzxxxxxstxxxxx编程(见MATLAB程序(erciguihua1))结果：2、一般非线性规划标准形式：其中为n维变元向量，均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同．用MATLAB求解上述问题，基本步骤分三步。12112212min()..00zfxstcxcxAxbAxbvxv12(),cxcxx(1)首先建立M文件fun.m,用来定义目标函数f(x)，形式为functionf=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,…)10cx20,cx12,,cxcx注意：(1)fmincon函数提供了大型优化算法和中型优化算法。当options参数的GradObj设置为’on’时必须给出fun函数的梯度，并且只有上下界约束或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。(2)fmincon函数的中型算法使用的是序列二次规划法(SQP方法)。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵。(3)fmincon函数可能会给出局部最优解，这与初值x0的选取有关。例2：改写成标准形式：建立M文件fun1.m22121212121211min222..23645,0zxxxxstxxxxx22121212121211min2222360..45000zxxxxxxstxxxx建立主程序(见MATLAB程序(feixianxingguihua1))结果：例3：建立M文件fun2.m定义目标函数：建立M文件c.m定义非线性约束条件：1221212212121212min42421..01.50100xzexxxxxstxxxxxxxx编写主程序(见MATLBA程序(feixianxingguihua2))结果：例4：建立M文件fun3.m定义目标函数：建立M文件c1.m定义非线性约束条件：12221122221212min2..()2507005,010zxxstcxxxcxxxxx编写主程序(见MATLBA程序(feixianxingguihua3))结果：补充知识：用LINDO、LINGO优化工具箱解线性规划LINDO、LINGO能求解的优化模型优化模型连续优化整数规划(IP)二次规划(QP)非线性规划(NLP)线性规划(LP)LINDOLINGO一、LINDO软件包引例：加工奶制品的生产计划每天：50桶牛奶，时间：480小时，至多加工100千克，制定生产计划，使每天获利最大。35元可买到1桶牛奶，买吗？若买，每天最多买多少？可聘用临时工人，付出的工资最多是每小时几元?获利增加到30元/千克，是否应改变生产计划？一桶牛奶3千克A14千克A2获利24元/千克获利16元/千克12小时8小时或1A1A建立模型桶牛奶生产桶牛奶生产获利获利5021xx48081221xx10031x决策变量目标函数12max7264zxx约束条件0,21xx线性规划模型(LP)1x1A2x2A每天获利原料供应劳动时间加工能力非负约束1243x2164x模型求解：1A2A20桶牛奶生产，30桶牛奶生产，利润为3360元。原料无剩余时间无剩余加工能力剩余40三种资源基变量的reducedcost值为0；对于非基变量，reducedcost值表示该非基变量增加一个单位时（其他非基变量保持不变），目标函数减少量（对max型问题）。影子价格原料增1单位，利润增48时间增1单位，利润增2能力增减不影响利润35元可买到1桶牛奶，要买吗？35