数学实验之5线性规划2

1线性规划21．掌握用MATLAB优化工具箱求解线性规划的方法；2、了解线性规划模型中的灵敏度分析方法；掌握如何使用软件来实现分析；3．练习怎样由实际问题建立线性规划模型的全过程。实验目的返回3两个应用案例实验内容最优化问题简介引例:生产计划问题线性规划模型及方法概述用MATLAB软件进行计算主要内容4特点：从若干可能的计划（方案）中寻求某种意义下的最优方案，数学上将这种问题称为最优化问题（optimization).静态问题(没有考虑时间t的变化)1、生产计划问题；2、运输问题；最优化问题简介5单耗甲乙丙x1x2x3限额材料工时工人231321.5325343640利润(元/件)432在一定的条件下，问生产数量xi=？使利润达到最大？数据表生产计划问题123123123123123max4322334321.536..32540,,0Zxxxxxxxxxstxxxxxx规划模型利润材料工时人力6运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km）目标：运费达到最小网络图7某种原材料有M个产地，现在需要将原材料从产地运往N个工地，假定M个产地的产量为ai和N个工地的需求量为bj，单位产品的运费cij已知，那么如何安排运输方案可以使总运费最低？数学模型：NjbxMiaxtsxcjMiijiNjijijNjijMi,...,2,1,...,2,1,..min1111cij—单位运费；xij—运输量；ai—第i地产量；bj—第j地需要量；状态变量返回运输问题8建立最优化的数学模型应具备三个基本要素1、决策变量（decisionvariables);2、约束条件（constraints);3、目标函数（objectivefunction)最优化问题分类：①线性、非线性②静态、动态③整数、非整数④随机、非随机等返回9最优化数学模型的分类•线性规划(LP)目标和约束均为线性函数•非线性规划(NLP)目标和约束均为非线性函数•二次规划(QP)目标为二次函数、约束为线性函数•整数规划(IP)决策变量为整数•多目标规划目标函数至少两个以上•动态规划研究随时间变化的决策问题返回10典型的工程应用问题返回线性规划(LP)运输问题配料问题投资计划综合生产中转调用生产率比较整数规划(IP)投资选择生产计划指派问题下料问题50个决策变量以上的优化问题称为大规模的.11生产计划问题mincTxs.t.Ax≤bx≥0归纳：TT123c[4,3,2],[,,]23134A321.5,b3632540xxxx123123123123123max4322334321.536..32540,,0Zxxxxxxxxxstxxxxxx规划模型利润材料工时人力12min(max)cTxs.t.Ax≥b(Ax≤b,Ax=b)x≥0线性规划模型单纯形算法的标准形式：mincTxs.t.Ax=b(b≥0)x≥0(a≤x≤b)其中：x∈Rn，A∈Rm×n，b∈Rm，c∈Rn例：maxz=3x1+x2s.t.-x1+x2≤2x1-2x2≥2x1，x2≥0例：min-(3x1+x2)+0y1+0y2s.t.-x1+x2+y1=2x1-2x2-y2=2x1，x2,y1,y2≥0其中y1,y2表示松弛变量.13有关线性规划解的若干概念1、可行解（可行点）2、可行域3、最优解例：Maxz=3x1+x2s.t.-x1+x2≤2L1x1-2x2≤2L23x1+2x2≤14L3x1，x2≥0图解:起作用约束：L2，L3最优解（4，1）最优值zmax=13L3L2L114求解LP的特殊情形Maxz=3x1+x2s.t.-x1+x2≤2----L1x1-2x2≤2----L23x1+2x2≤14----L3x1，x2≥0x1x2L2L1L30x1x2L2L1L30x1x2L2L10x1x2L2L1L30z=c②无最优解3x1+2x2≤-1①无可行解③最优解不唯一15线性规划的基本性质可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点LP的基本性质：可行域存在时，必是凸多面体；可行解对应于可行域中的点；最优解存在时，必在可行域的顶点取得。LP的通常解法是单纯形法。超平面组成的凸多面体等值线是超平面凸多面体的某个顶点2维n维16线性规划的基本性质求解LP的基本思想：从可行域的某一个顶点开始，只需在有限多个顶点中一个一个找下去，一定能找到最优解。单纯形算法：从一个顶点转换到另一个顶点，使目标函数下降（上升）最多。17单纯形算法的思路判断Pk最优？寻找下一个顶点Pk+1endnoyesk=0初始顶点P0k+1→k算法实现需要解决以下问题：1、顶点如何表示？2、如何判断顶点的最优？3、如果某顶点非最优，如何转移到下一个顶点？4、算法的效率如何体现？18Maxz=3x1+x2s.t.-x1+x2≤2x1-2x2≤23x1+2x2≤14x1，x2≥0单纯形算法的思路Minz=-3x1-x2+0·x3+0·x4+0·x5s.t.-x1+x2+x3=2x1-2x2+x4=23x1+2x2+x5=14x1,x2,x3,x4,x5≥0加松弛变量将不等式变为等式minz=cTxs.t.Ax=bx≥0,A∈Rm×n,m≤n标准形19对标准形求解的第一步:先求可行解单纯形算法的思路s.t.-x1+x2+x3=2x1-2x2+x4=23x1+2x2+x5=14x1，x2,x3,x4,x5≥011100A1201032001P1P2P3P4P5A=[B,N],xT=[xB,xN]Ax=BxB+NxN=bxN=0→xB=B-1bx1x2Q0PRM345135235123[](0,0,2,2,4)[](2,0,4,0,8)[](0,1,3,0,16)[](4,1,5,0,0)TTTTBPPPxBPPPxBPPPxBPPPx最优解O点Q点R点P点120线性规划的灵敏度分析灵敏度分析也称变动分析(ranginganalysis)，主要指参数如何变化而不影响解的结果。maxcTxs.t.Ax=b(b≥0)x≥0标准形式：参数变动有以下三种情况：1、c→c+△c；△c影响目标平面的方向；2、A→A+△A；△A影响约束平面的方向；3、b→b+△b；△b使约束平面平移；参数：c,A,b决策变量：x21解释情况1新最优解c→c+△cmaxz=3x1+x2c=[3,1];c+△c=[3,3]maxz=3x1+3x2线性规划的灵敏度分析22情况2A→A+△A情况3b→b+△b3x1+x2=1423Z实际问题中，为什么要进行灵敏度分析？线性规划的结构灵敏度分析1、变量的增加或减少；2、约束的增加或减少；返回24Matlab解决的线性规划的标准格式为：mincTxx∈Rns.t.A·x=bAeq·x=beqL≤x≤U其中，A,b,c,x,Aeq,beq,L,U等均表示矩阵向量。1、函数变化，lp→linprog；2、输入、输出格式简化，易懂；3、规模增大，上千个变量以及几百个等式或不等式约束；MATLAB6.0语句格式1.X=linprog(c,A,b)用于求解模型：minz=cTxs.t.Ax≤b用MATLAB工具箱解线性规划模型2.X=linprog(c,A,b,Aeq,beq)用于求解模型：minz=cTxs.t.Ax≤bAeq.x=beq3.X=linprog(c,A,b,Aeq,beq,VLB,VUB)也用于求解在2中增加约束VLB≤x≤VUB的模型。用MATLAB工具箱解线性规划模型4.x=linprog(c,A,b,Aeq,beq,VLB,VUB,x0，options)用于求解模型:minz=cTxs.t.Ax=bAeq.x≤beqVLB≤x≤VUB其中x0表示解向量x的初值,由options规定算法中的参数，参数结构options由命令optimset来定义或修改。用MATLAB工具箱解线性规划模型options=optimset(‘param1’,value1,‘param2’,value2,...)依次设定参数param1,param2，…的值分别为value1,value2,…。参数有：MaxIter，允许的最大迭代数。LargeScale：当被置为‘on’时，表示用大规模算法；当被置为‘off’时，表示用中等规模算法。Display：当被置为‘off’时，不显示输出；当被置为‘iter’时，显示每次迭代的输出；当被置为‘final’或缺省时，显示最终的输出。TolFun：函数值终止的允许误差。MATLAB6.0软件求解x=linprog(c,A,b,Aeq,beq,VLB,VUB,x0，options)[x,fval,exitflag,output]=linprog(c,A,b,Aeq,beq…）等式约束初始值解的上下界不等式约束算法中的参数目标函数值0：收敛=0:到最大迭代次数时都还未收敛0：infeasible或方法失败迭代次数和算法类型29格式；mincTxx∈Rns.t.A·x=b2Aeq·x=beqL≤x≤U[x,fval,exitflag,output,lambda]=linprog(c,A,b,Aeq,beq,L,U,x0)若没有这些项，则可以省略。MATLAB6.0语句格式Lagrange乘子,维数等于约束个数,非零分量对应于起作用约束.lower下界Upper上界ineqlin不等式约束eqlin等式约束0,算法收敛；=0，达到最大步骤而停止；0，算法不收敛;算法结束状态iterations,迭代次数algorithm,使用的优化方法cgiterations,CG迭代次数若没有等式约束，则Aeq=[]；beq=[];或A=[];b=[];30归纳：MATLAB语句格式√minfTxs.t.Ax=bAeqx≤beqL≤x≤U310,,40653025..325max321321321321xxxxxxxxxtsxxxZ例1编程计算：(li1.m)c=[-5,-2,-3]';A1=[1,-5,-6];A2=[1,5,2];b1=40;b2=30;L=zeros(3,1);[]U=[inf,inf,inf]';[]x0=[1,1,1]';[x,fval]=linprog(c,A1,b1,A2,b2,L,U,x0)计算结果：x=30.00000.00000fval=-150.0000思考：灵敏度分析(li4.m)[a=?,b=?]32forc3=0:0.05:15(li4.m)c=[-5,-2,-c3]';A=[1,-5,-6];b=40;Aeq=[1,5,2];beq=30;L=[0,0,0]';x,=linprog(c,A,b,Aeq,beq,L);z=-c'*x;plot(c3,z,'.')holdonendholdonforc2=0:0.05:15c=[-5,-c2,-3]';x=linprog(c,A,b,Aeq,beq,L);z=-c'*x;plot(c2,z,'r')holdonend灵敏度分析c3c233121212112max10965601020150..8,0Zxxxxxxstxxx例2某厂生产两种口味的饮料,条件如上.问应如何安排生产计划?单耗甲(百箱)乙(百箱)x1x2限额原料(kg)工人(名)6510206