《20100420 第七讲：线性规划与非线性规划方法(2次课)》由会员分享，可在线阅读，更多相关《20100420 第七讲：线性规划与非线性规划方法(2次课)（28页珍藏版）》请在金锄头文库上搜索。
1、1第七讲 线性规划与 非线性规划方法第七讲 线性规划与非线性规划内容: 本讲主要介绍线性规划问题的求解 目的: 接触最优化问题,学习线性规划算法的MATLAB实现(基于单纯型法变种) 要求: 能够直接对小规模线性规划问题进行求 解了解线性规划问题的基本概念、形式和算法掌握线性规划问题的图解法(2维)和lp算法通过范例,掌握线性规划问题求解一般过程2第七讲 线性规划与 非线性规划方法关于线性规划的引入和概述线性规划隶属于运筹学中的约束优化，简单说 就是目标函数(希望进行最优化的指标)和约束条件( 决策变量受到的限制)均为线性函数的约束优化(否 则称为非线性规划)线性规划问题是企业运作、科技研发和
2、工程设计 的常见问题，应用十分广泛。具有代表性的算法有 单纯型法、椭球法和Karmarkar算法。随着计算机 硬件和软件技术发展，几十万变量和约束的线性规 划问题已经很普通。 MATLAB优化工具箱 Optimization Toolbox 采用 投影法(单纯型法变种)，由函数linprog实现求解。3第七讲 线性规划与 非线性规划方法解决规划问题的基本流程第1步：问题的分析理解及描述（数学建模）第2步：解决问题的整体目标（目标函数）第3步：影响目标的各种限制条件（约束条件）第4步：应用相关函数获得求解（算法实现）4第七讲 线性规划与 非线性规划方法哪样一些问题可以描述成为线性规划问题？线性规
3、划模型的一般形式当 均为线性函数，上述优化模型称为线 性规划，否则称为非线性规划。 关于线性规划的形式，有诸如标准形式、规范 形式等之分，在这里我们只关心MATLAB能够 接受的形式：一般来说不同形式之间可以转换(YCXp14)z目标函数/c价值向量/A约束矩阵/b右端向量 一个满足约束的x-可行解/可行解集合-可行域5第七讲 线性规划与 非线性规划方法线性规划的图解法(2维情形)1通过一个简单的实例,巩固对线性规划的若干概念的理解： exp.1 图解法求解线性规划问题: 将前三个约束条件的不等号改为等号,就是如上 三条直线,下面考察直线L1, L2, L3及坐标轴围成 的可行域:6第七讲 线
4、性规划与 非线性规划方法线性规划的图解法(2维情形)2如图所示:五边形OQ1Q2Q4Q3构成可行域x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1 Z2 Z3 Z4 Z5 当目标函数z=3x1+x2取不同值时，表示一组平行 直线，如图中虚线，最优解在Q4点，Zmax=137第七讲 线性规划与 非线性规划方法线性规划的图解法(2维情形)3一些直观结论和定理：在2维情形下，可行域为直线组成的凸多边 形，目标函数的等值线为直线，最优解在凸多边 形的 某个顶点处取得。 可行域空集，如改例中第3个约束为-3x1+2x214 ，则无最优解； 可行域无界，如去掉例中第3个约束-3x1+2x214 ，则可
5、能无最优解； 无穷多最优解，如改例中第3个约束为3x1+x2 14 ，则最优解在凸多边形一条边上取得； 推广到n维欧氏空间，线性规划问题若有最优 解，则最优解必是作为可行域的凸多面体的某个 顶点。8第七讲 线性规划与 非线性规划方法线性规划的LP解法相关函数介绍：lpx=lp(c,A,b) x=lp(c,A,b,v1,v2) % 即有约束v1x v2 x=lp(c,A,b,v1,v2,x0) % x0为初始解，缺省为0 x,lag=lp() % lag为拉格朗日乘子，非零分量对应于起作用的约束条件 x,lag,how=lp() % how给出求解信息，无 可行解infeasible,无有界解u
6、nbounded,成功ok不过在高版本中lp已被linprog取代！9第七讲 线性规划与 非线性规划方法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.0000 1.0000 z = 13.0000c=-3;1;a=-1,1;1,- 2;3,2;b=2;2;14;v1=0,0;x=lp(c,a,b,v1)z=-c*x10第七讲 线性规划与 非线性规划方法线性规划的LP解法相关函数介绍：linprogx=linprog(f,A,b) x=linprog(
7、f,A,b,Aeq,beq) % 增加约束Aeq*x=beq x=linprog(f,A,b,Aeq,beq,lb,ub) % 设计变量下上界 x,fval,exitflag,output,lambda=linprog() % fval返回 目标函数值/exitflag返回退出条件/output返回优化信息 /lambda返回显示哪些主动约束（参数繁杂会用即可）11第七讲 线性规划与 非线性规划方法linprog函数求解示例：exp.2求解下列线性规划问题：f=-5;-4;-6;A=1,-1,1;3,2,4;3,2,0; b=20;42;30;lb=zeros(3,1); x,fval,exi
8、tflag,output,lambda=linprog(f,A,b, ,lb);x,fval,lambda.ineqlin, lambda.lower12第七讲 线性规划与 非线性规划方法范例-化工公司产品生产计划1.问题：略 2.建模：3.求解：13第七讲 线性规划与 非线性规划方法范例-化工公司产品生产计划f=-400;-1000;-300;200;A=0,-2,1,1;2,3,0,0;3,4,0,0;b=0;16;24;Aeq=0,-2,1,1;beq=0;lb=zeros(4,1);ub=inf*ones(4,1);ub(3)=5;x0=zeros(4,1);x,fval,exitfl
9、ag,output,lambda=linprog(f,A,b,Aeq,b eq,lb,ub,x0)x=lp(f,A,b,lb,ub,x0,1)14第七讲 线性规划与 非线性规划方法Thats all3Q!15第七讲 线性规划与 非线性规划方法第七讲 线性规划与非线性规划内容：本讲主要介绍非线性规划问题的求解 目的：学习非 线性规划算法的 MATLAB实现 要求：能够运用软件直接对小规模非线性规划问题进行求解了解非线性规划问题区别于线性规划问题的基 本概念、形式和算法掌握约束和无约束优化函数constr和fminu通过范例,掌握非线性规划问题求解一般过程16第七讲 线性规划与 非线性规划方法关于
10、非线性规划的引入和概述非线性规划同时涵盖运筹学中的约束优化和无 约束优化两种类型，简单说就是目标函数或约束条 件(可以不带constraint)均为非线性函数的优化模 型，称为非线性规划。非线性规划问题同样是企业运作、科技研发和 工程设计的常见问题，甚至在某种意义上应用面比 线性规划更广。因为非线性本身就意味着混沌和无 序，这与现实世界一致。 MATLAB优化工具箱(Optim)针对约束和非约束分 别由函数constr和fminu进行求解。constr升级为fmincon，fminu升级为fminunc17第七讲 线性规划与 非线性规划方法在后继版本中不再提供支持？熟悉新函数版本更新带来的函数
11、升级18第七讲 线性规划与 非线性规划方法非线性规划模型的一般形式1下面分别给出约束和非约束优化的一般形式， 以及各自简单的例子: 19第七讲 线性规划与 非线性规划方法非线性规划模型的一般形式2无约束优化只有一个目标函数，这个目标函数 必须是非线性的，实际问题真正无约束并不多: 20第七讲 线性规划与 非线性规划方法非线性规划方法概要由于本身的复杂性，非线性规划远不如线性 规划问题那样具备很高效率的求解方法。相对而言无约束优化更容易求解一些，一个 基本的思路就是，化约束优化为一系列无约束优 化问题，例如：序列无约束极小化技术、可变容 差法，等等对于具体算法细节，我们虽然不会本课程中 深入探究
12、，但能够从算法本身的着手改进将会是 很有价值的工作，比如本章作者开发的逼近精确 罚函数法，感兴趣可以仔细研读21第七讲 线性规划与 非线性规划方法MATLAB非线性规划函数约束优化函数介绍：constr调用语法：constr (fmincon) X,OPTIONS = constr(FUN,x0,OPTIONS,VLB,VUB) 具体含义请参见联机help22第七讲 线性规划与 非线性规划方法MATLAB非线性规划函数无约束优化函数介绍：fminu (fminunc)调用语法： fminu X,OPTIONS = fminu(FUN,x0,) 具体含义请参见tbp154求解非线性规划问题，需要
13、首先编制一个m文件 ，描述需要求解的问题，也即求解需以“被调” 的形式进行23第七讲 线性规划与 非线性规划方法非线性规划问题的范例-圈地1某旅游发展有限公司计划开发度假村，公司要 求先用一批旧砖建一圈矩形围墙，以便存放建筑材 料旧砖的数量是固定的，围墙的高度不能低于两 米，围墙围住的面积越大越好要你来设计。24第七讲 线性规划与 非线性规划方法非线性规划问题的范例-圈地225第七讲 线性规划与 非线性规划方法非线性规划问题的范例-圈地3具体非线性规划模型：tbp172.m function F,G= tbp172(x) F=-x(1)*x(2); G(1)=(x(1)+x(2)*x(3)-1
14、20;26第七讲 线性规划与 非线性规划方法非线性规划问题的范例-圈地4loadtbp172.mx=10;10;2; options(13)=0 %等式约束的个数为0 xl=0;0;2; xu=inf;inf;inf; x,options=constr(tbp172,x,options,xl,xu); x,fmin=options(8)关于constr的升级函数 fmincon，请参考联机 帮助系统范例27第七讲 线性规划与 非线性规划方法非线性规划问题的范例-无约束3补充范例:求解： fun.m function y=fun(x) a=2;b=2; y=x(1)2/a+x(2)2/b;x0=1,1; x=fminu(fun,x0) 精确解为0，028第七讲 线性规划与 非线性规划方法预习第11章 图的模型及矩阵表示
