线性与非线性规划算法及实现.pptxVIP

第九章线性规划内容：本讲主要介绍线性规划问题的求解目的：接触最优化问题,学习线性规划算法的MATLAB实现(基于单纯型法变种)要求：能够运用软件直接对小规模线性规划问题进行求解了解线性规划问题的基本概念、形式和算法掌握线性规划问题的图解法(2维)和lp算法通过范例,掌握线性规划问题求解一般过程第9.1节引入与导言01

关于线性规划的引入和概述~线性规划隶属于运筹学中的约束优化，简单说就是目标函数(希望进行最优化的指标)和约束条件(决策变量受到的限制)均为线性函数的约束优化（否则称为非线性规划）。线性规划问题是企业运作、科技研发和工程设计的常见问题，应用十分广泛。具有代表性的算法有单纯型法、椭球法和Karmarkar算法。随着计算机硬件和软件技术发展，几十万变量和约束的线性规划问题已经很普通。MATLAB优化工具箱(OptimizationToolbox)采用投影法(单纯型法变种)，由函数linprog实现求解。第9.1节引入与导言02

解决规划问题的基本流程~01添加标题第9.1节引入与导言02添加标题0303添加标题问题的分析理解及描述（数学建模）04添加标题解决问题的整体目标（目标函数）05添加标题影响目标的各种限制条件（约束条件）06添加标题应用相关函数获得求解（算法实现）

哪样一些问题可以描述成为线性规划问题？线性规划模型的一般形式第9.31节线性规划一般形式04当均为线性函数，上述优化模型称为线性规划，否则称为非线性规划。关于线性规划的形式，有诸如标准形式、规范形式等~之分，在这里我们只关心MATLAB能够接受的形式：一般来说不同形式之间可以转换(YCXp14)z目标函数/c价值向量/A约束矩阵/b右端向量一个满足约束的x-可行解/可行解集合-可行域

线性规划的图解法(2维情形)1添加标题通过一个简单的实例,巩固对线性规划的若干概念的理解：exp.1图解法求解线性规划问题:01添加标题第9.34节线性规划图解法02添加标题0503添加标题将前三个约束条件的不等号改为等号,就是如上三条直线,下面考察直线L1,L2,L3及坐标轴围成的可行域:04

线性规划的图解法(2维情形)2第9.34节线性规划图解法如图所示:五边形OQ1Q2Q4Q3构成可行域06x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1Z2Z3Z4Z5当目标函数z=3x1+x2取不同值时，表示一组平行直线，如图中虚线，最优解在Q4点，Zmax=13

线性规划的图解法(2维情形)3一些直观结论和定理：在2维情形下，可行域为直线组成的凸多边形，目标函数的等值线为直线，最优解在凸多边形的某个顶点处取得。可行域空集，如改例中第3个约束为-3x1+2x2?14，则无最优解；可行域无界，如去掉例中第3个约束-3x1+2x2?14，则可能无最优解；无穷多最优解，如改例中第3个约束为3x1+x2?14，则最优解在凸多边形一条边上取得；推广到n维欧氏空间，线性规划问题若有最优解，则最优解必是作为可行域的凸多面体的某个顶点。第9.34节线性规划图解法07

线性规划的LP解法相关函数介绍：lp第9.2节线性规划LP解法08x=lp(c,A,b)x=lp(c,A,b,v1,v2)%即有约束v1?x?v2x=lp(c,A,b,v1,v2,x0)%x0为初始解，缺省为0[x,lag]=lp(…)%lag为拉格朗日乘子，非零分量对应于起作用的约束条件[x,lag,how]=lp(…)%how给出求解信息，无可行解infeasible,无有界解unbounded,成功ok不过在高版本中lp已被linprog取代！

lp函数求解示例：第9.2节线性规划LP解法针对前述exp.1可如下计算：c=-[3,1];a=[-1,1;1,-2;3,2];b=[2,2,14];v1=[0,0];x=lp(c,a,b,v1)z=-c*xx=4.00001.0000z=13.000009c=-[3;1];a=[-1,1;1,-2;3,2];b=[2;2;14];v1=[0,0];x=lp(c,a,b,v1)z=-c*x

线性规划的LP解法相关函数介绍：linprog第9.2节线性规划LP解法10x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)%增加约束Aeq*x=beqx=li