matlab在运筹学中的应用.ppt

MATLAB 在运筹学中的应用,绪 论,优化求解工作中常用的软件： 1、Matlab 2、Mathematica 3、Maple 4、SAS 5、SPSS 6、Lindo/Lingo 7、GAMS 8、WinQSB 9、Excel 10、其他，如SQP、DPS、ORS、Visual Decision、Decision Explore、AIMMS、Crystal Ball、TreeAge等。,Matlab （Matrix Laboratory ） 专业级的数值计算和符号计算、 强大的绘图功能、 可视化建模仿真和实时控制,从事理论研究的数学工作者和其他科学工作者 强大的符号计算能力 输入格式有严格的规定,SAS（Statistical Analysis System) 誉为统计分析的标准软件，统计方法齐、全、新 集数据存取、管理、分析和展现于一体 政府行政管理、科研、教育、生产和金融等领域,SPSS（Statistical Package for the Social Sciences) 2000 （Statistical Product and Service Solutions) 最早的统计分析软件 类似Execl表格的方式输入和管理数据 应用最广泛的专业统计软件,Lindo/Lingo 求解最优化问题的软件包 线性规划、二次规划、整数规划、非线性规划 解算器寻最佳模型进行求解，公式表示 Lingo优化问题的建模语言，可与文本、Excel、数据库对接,GAMS（General Algebraic Modeling System） 针对大型、复杂系统的建模 建模迅速、易修改，丰富的模型求解引擎,WinQSB（Quantitative Systems for Business） 基于模块化设计的专业运筹规划和决策辅助软件 规划问题、计划编制、抽样分析、MRP、质量控制、马尔可夫过程、决策分析等,通过加载宏功能 扩展为一个优化求解的工具,Matlab简介,概述 Matlab是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，和Mathematica、Maple并称为三大数学软件。 用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括Matlab和Simulink两大部分。 主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。 具有广泛应用前景的全新的计算机高级编程语言 产生与发展 70年代后期，基于特征计算的程序库EISPACK和线性代数程序库LINPACK （FORTRAN语言） 1984年，MathWorks公司正式推出的商业化版本，C语言； 1992年，基于Windows平台的Matlab4.0，6.5 2004年，7.x 2006a，2006b，2011a，2011b。,优势 强大易用的科学计算语言 全面的图形功能 独立开放的平台 实用的程序接口 Simulink动态仿真功能 Matlab是一个交互式开发系统，其基本数据单元是矩阵。 MathWorks公司的描述：计算、可视化及编程一体 常用网址： ,MATLAB 产品族可以用来进行以下各种工作： 数值分析 数值和符号计算 工程与科学绘图 控制系统的设计与仿真 数字图像处理 技术 数字信号处理 技术 通讯系统设计与仿真 财务与金融工程 MATLAB 的应用范围非常广，包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱（单独提供的专用MATLAB 函数集）扩展了MATLAB 环境，以解决这些应用领域内特定类型的问题。,Matlab Main Toolboxmatlab主工具箱 Control System Toolbox控制系统工具箱 Communication Toolbox通讯工具箱 Financial Toolbox财政金融工具箱 System Identification Toolbox系统辨识工具箱 Fuzzy Logic Toolbox模糊逻辑工具箱 Higher-Order Spectral Analysis Toolbox高阶谱分析工具箱 Image Processing Toolbox图象处理工具箱 computer vision system toolbox-计算机视觉工具箱 LMI Control Toolbox线性矩阵不等式工具箱 Model predictive Control Toolbox模型预测控制工具箱 -Analysis and Synthesis Toolbox分析工具箱 Neural Network Toolbox神经网络工具箱 Optimization Toolbox优化工具箱 Partial Differential Toolbox偏微分方程工具箱 Robust Control Toolbox鲁棒控制工具箱 Signal Processing Toolbox信号处理工具箱 Spline Toolbox样条工具箱 Statistics Toolbox统计工具箱 Symbolic Math Toolbox符号数学工具箱 Simulink Toolbox动态仿真工具箱 Wavele Toolbox小波工具箱 DSP system toolbox-DSP处理工具箱,Matlab界面窗口,MATLAB界面窗口,MATLAB中变量区别于其他编程语言的特点 MATLAB表达式中可以使用矩阵形式； MATLAB中不需要预先声明变量的类型和维数，MATLAB会根据对新变量的操作创建该变量，确定其类型并为其分配存储空间； 对已经存在的变量的赋值操作，MATLAB会以新值代替旧值。如果需要的话，MATLAB可以改变该变量的类型或者为其分配新的存储空间; MATLAB中的变量名是大小写敏感的，即A和a代表不同的变量；,矩阵特征值参数运算,一、矩阵的行列式 函数：det(A) 二、矩阵的迹 函数：trace(A) 三、矩阵的秩 函数：rank(A) 四、矩阵的范数 函数：norm（A，选项） 五、矩阵的特征值 函数：eig(A) 六、矩阵的分解-三角形分解（LU或LR分解）函数：L, U=lu(A) 七、矩阵的分解-正交分解（QR分解） 函数：Q, R=qr(A),MATLAB中的控制结构,循环结构 for循环 while循环 选择结构 if结构 switch结构 try/catch结构 其他流程控制 break语句 continue语句 return语句,try 语句组1 catch 语句组2 end,【例】解Lorenz方程-大气对流模型,function xdot=lorenzeq(t,x) xdot=-8/3*x(1)+x(2)*x(3); -10*x(2)+10*x(3); -x(1)*x(2)+28*x(2)-x(3);,线性规划问题的数学模型,线性规划问题的数学描述 或 其中 C 为n维行向量 A 为mn维矩阵 b 为m维列向量 X 为n维列向量,线性规划问题的MATLAB求解,MATLAB中求解 线性规划问题的 标准形式 MATLAB标准型和教科书中讲解有所不同， 极小化的目标函数z 线性规划问题具有不等式约束m1个，等式约束m2个 f、x、lb 和ub 均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1n维矩阵，Aeq为m2n维矩阵,注意事项 MATLAB标准型是对目标函数求极小，如果遇到是对目标函数求极大的问题，在使用MATLAB求解时，需要在函数前面加一个负号转化为对目标函数求极小的问题； MATLAB标准型中的不等式约束形式为“”，如果在线性规划问题中出现“”形式的不等式约束，则我们需要在两边乘以(-1)使其转化为MATLAB中的“”形式。如果在线性规划问题中出现了“”的约束形式，则我们需要通过添加松弛变量使得不等式约束变为等式约束,将问题转化为MATLAB标准型 原问题是对目标函数求极大，故添加负号使目标变为：min z=-4x1+2x2-x3 原问题中存在“”的约束条件，故添加负号使其变为 : 8x1-2x2+2x3 -8 将约束整理为矩阵形式 用MATLAB表达则为,f=-4; 2; -1; %将目标函数转化为求极小 A=2 -1 1; 8 -2 2; b=12; -8; %不等式约束系数矩阵 Aeq=-2 0 1; 1 1 0;beq=3; 7; %等式约束系数矩阵 lb=0; 0; 0;ub=Inf; Inf; Inf %边界约束,函数调用格式 MATLAB优化工具箱中求解线性规划问题的函数为 linprog() x = linprog(f, A, b) x = linprog(f, A, b, Aeq, beq) x = linprog(f, A, b, Aeq, beq, lb, ub) x = linprog(f, A, b, Aeq, beq, lb, ub, x0) x = linprog(f, A, b, Aeq, beq, lb, ub, x0, options) x = linprog(problem) x, fval = linprog(.) x, fval, exitflag = linprog(.) x, fval, exitflag, output = linprog(.) x, fval, exitflag, output, lambda = linprog(.),输入参数 MATLAB工具箱中的linprog函数在求解线性规划问题时，提供的参数为：模型参数、初始解参数和算法控制参数。 模型参数x、c、lb、ub、b、beq、A和Aeq在MATLAB标准型中已经介绍了其具体物理意义和获得方法 x0为线性规划问题的初始解，该设置仅在中型规模算法中有效，而在默认的大型规模算法和单纯形算法中，MATLAB将忽略一切初始解。 options为包含算法控制参数的结构变量，我们可以通过optimset命令对这些具体的控制参数进行设置，例如下述格式 options = optimset(param1,value1,param2,value2,.) 该命令格式创建一组控制参数结构变量options，将参数的具体值赋给单引号之间的参数，任何未被指定的参数将被赋值为，参数值为的具体的含义是将该组控制参数传递给优化函数时将使用MATLAB提供的默认值 在线性规划问题中可以用到的设置参数如下一页的表所示,输出参数 linprog函数返回的输出参数有x、fval、exitflag、lambda和output。 输出参数x为线性规划问题的最优解 输出参数fval为线性规划问题在最优解x处的函数值 输出参数exitflag返回的是优化函数计算终止时的状态指示，说明算法终止的原因，其取值和其代表的具体原因如表所示,输出参数 输出参数output是一个返回优化过程中相关信息的结构变量，其属性如表所示 输出参数lambda是返回线性规划问题最优解x处的拉格朗日乘子的一个结构变量,其总维数等于约束条件的个数，其非零分量对应于起作用的约束条件，其属性如表所示。,函数命令详解 x = linprog(f, A, b) 该函数调用格式求解线性规划问题 x = linprog(f, A, b, Aeq, beq) 该函数调用格式求解线性规划问题 即该函数调用格式解决的是既含有线性等式约束，又含有线性不等式约束的线性规划问题，如果在线性规划问题中无线性不等式约束，则可以设A=以及b=,函数命令详解 x = linprog(f, A, b, Aeq, beq, lb, ub) 该函数调用格式求解线性规划问题 即在线性规划问题的求解过程中进一步考虑了对决策变量的约束，其中lb和ub均是和决策变量维数相同的列向量，如果对决策变量没有上界约束，可以设置ub(i) = Inf，如果没有下界约束则可以设置lb(i) = -Inf，和(2)类似，如果问题中没有等式约束，则可以设Aeq=以及beq=,命令详解 x = linprog(c,A,b,Aeq,beq,lb,ub,x0) 在前面调用方法的基础上设置线性规划问题求解的初始解为x0，该参数仅在使用有效集算法时生效，否则当使用默认的内点算法时，将忽略任何初始点，即参数无效。 x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) 用options指定的优化参数进行最小化。可以使用optimset来设置这些参数 x,fval = linprog(.) 在优化计算结束之时返回线性规划问题在解x处的目标函数值fval。 x,fval,exitflag = linprog(.) 在优化计算结束之时返回exitflag值，描述函数计算的退出条件。 x,fval,exitflag,output = linprog(.) 在优化计算结束之时返回返回结构变量output x,fval,exitflag,output,lambda = linprog(.) 在优化计算结束之时返回线性规划问题最优解x处的拉格朗日乘子lambda,例题1,用MATLAB求解线性规划问题,f=-1; -1; %目标函数，为转化为极小，故取目标函数中设计变量的相反数 A=1 -2; 1 2; %线性不等式约束 b=4; 8; lb=0; 0; %边界约束，由于无上界，故设置ub=Inf;Inf; ub=Inf; Inf; x, fval=linprog(f, A, b, , , lb, ub) Optimization terminated. x = 6.0000 1.0000 fval = -7.0000,例题2,用MATLAB求解线性规划问题,f=-1; -3; 1; %目标函数，为转化为极小，故取目标函数中设计变量的相反数 Aeq=1 1 2; -1 2 1; %线性等式约束 beq=4; 4; lb=0; 0; 0; %设计变量的边界约束，由于无上界，故设置ub=Inf;Inf;Inf ub=Inf; Inf; Inf; x, fval, exitflag=linprog(f, , , Aeq, beq, lb, ub) Optimization terminated. x = 1.3333 2.6667 0.0000 fval = -9.3333 exitflag = 1,例题3,用MATLAB求解线性规划问题,f=-3; 1; 1; A=1 -2 1; 4 -1 -2; %线性不等式约束 b=11; -3; Aeq=-2 0 1; %线性等式约束 beq=1; lb=0; 0; 0; %变量的边界约束，由于无上界，故设置ub=Inf;Inf;Inf ub=Inf; Inf; Inf; x, fval, exitflag, output, lambda=linprog(f, A, b, Aeq, beq, lb, ub) Optimization terminated. x = 4.0000 1.0000 9.0000 fval = -2.0000output = exitflag = 1,output = iterations: 6 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated. lambda = ineqlin: 2x1 double eqlin: -0.6667 upper: 3x1 double lower: 3x1 double,0-1规划问题,MATLAB中求解 0-1规划问题的 标准形式 bintprog的调用格式 x = bintprog(f) x = bintprog(f, A, b) x = bintprog(f, A, b, Aeq, beq) x = bintprog(f, A, b, Aeq, beq, x0) x = bintprog(f, A, b, Aeq, beq, x0, options) x, fval = bintprog(.) x, fval, exitflag = bintprog(.) x, fval, exitflag, output = bintprog(.),线性二次规划问题,MATLAB中求解 线性二次规划问 题的标准形式 函数调用格式： x = quadprog(H, f, A, b) x = quadprog(H, f, A, b, Aeq, beq) x = quadprog(H, f, A, b, Aeq, beq, lb, ub) x = quadprog(H, f, A, b, Aeq, beq, lb, ub, x0) x = quadprog(H, f, A, b, Aeq, beq, lb, ub, x0, options) x, fval = quadprog(.) x, fval, exitflag = quadprog(.) x, fval, exitflag, output = quadprog(.) x, fval, exitflag, output, lambda = quadprog(.),线性目标规划问题,线性目标规划的MATLAB求解,输入输出参数,输入参数中，fun为目标函数，x0是求解的初始值，goal是目标函数的期 望值，nonlcon是非线性约束函数，weight是目标权重。 fun：最小化的目标函数，fun可以是一个在M函数中定义的函数句柄； Weight：可以控制低于或超过fgoalattain函数指定目标的相对程度。需要注意的是，如果将weight向量中的任一元素设置为0时，则算法将把对应的目标约束当做是硬约束来处理；当设置weight为不同的数值时，fgoalattain将对目标函数采取不同的处理方式： (1) 当权重weight设置为正时，fgoalattain函数则试图使目标函数值小于期望值； (2) 当权重weight设置为负时；fgoalattain函数则试图使目标函数值大于期望值； (3) 当需要目标函数值尽可能等于期望值时，则应设置控制参数GoalsExactAc