090403线性和非线性规划算法及其实现.ppt

数学实验第九章线性规划内容: 本讲主要介绍线性规划问题的求解目的: 接触最优化问题,学习线性规划算法的 MATLAB 实现(基于单纯型法变种) 要求: 能够运用软件直接对小规模线性规划问题进行求解?了解线性规划问题的基本概念、形式和算法?掌握线性规划问题的图解法(2维)和 lp算法?通过范例,掌握线性规划问题求解一般过程第 节引入与导言 01 数学实验关于线性规划的引入和概述~ 线性规划隶属于运筹学中的约束优化,简单说就是目标函数(希望进行最优化的指标)和约束条件(决策变量受到的限制)均为线性函数的约束优化(否则称为非线性规划)。线性规划问题是企业运作、科技研发和工程设计的常见问题,应用十分广泛。具有代表性的算法有单纯型法、椭球法和 Karmarkar 算法。随着计算机硬件和软件技术发展,几十万变量和约束的线性规划问题已经很普通。 MATLAB 优化工具箱(Optimization Toolbox )采用投影法(单纯型法变种),由函数 linprog 实现求解。第 节引入与导言 02 数学实验解决规划问题的基本流程~ 第 节引入与导言 03 第1步:问题的分析理解及描述(数学建模) 第2步:解决问题的整体目标(目标函数) 第3步:影响目标的各种限制条件(约束条件) 第4步:应用相关函数获得求解(算法实现) 数学实验哪样一些问题可以描述成为线性规划问题? 线性规划模型的一般形式第 节线性规划一般形式 04 1 2 min ( ), ( , ,..., ) . . ( ) 0, 1, 2,..., Tn xi z f x x x x x s t g x i m ? ?? ?当均为线性函数,上述优化模型称为线性规划,否则称为非线性规划。关于线性规划的形式,有诸如标准形式、规范形式等~之分,在这里我们只关心 MATLAB 能够接受的形式: , i f g min . . T z c x s t Ax b ??一般来说不同形式之间可以转换( YCXp14) z目标函数/c价值向量/A约束矩阵/b右端向量一个满足约束的 x-可行解/可行解集合-可行域数学实验线性规划的图解法(2维情形)1 通过一个简单的实例,巩固对线性规划的若干概念的理解: 图解法求解线性规划问题: 第 节线性规划图解法 05 1 2 1 2 1 1 2 1 2 2 1 2 1 2 3 1 2 1 2 m a x 3 . . 2 . . . . . . . . . . : 2 2 2 . . . . . . . . . . . . . . . . : 2 2 3 2 1 4 . . . . . . . . . . . . . : 3 2 1 4 , 0 z x x s t x x L x x x x L x x x x L x x x x ? ?? ?? ???? ? ??? ? ???将前三个约束条件的不等号改为等号,就是如上三条直线,下面考察直线 L1, L2, L3 及坐标轴围成的可行域: 数学实验线性规划的图解法(2维情形)2 第 节线性规划图解法如图所示:五边形 OQ1Q2Q4Q3 构成可行域 06x1 x2o L1 L2 L3 Q1 Q2 Q4(4,1) Q3 Z1 Z2 Z3 Z4 Z5 当目标函数 z=3x1+x2 取不同值时,表示一组平行直线,如图中虚线,最优解在 Q4 点, Zmax=13 数学实验线性规划的图解法(2维情形)3 一些直观结论和定理: 在2维情形下,可行域为直线组成的凸多边形,目标函数的等值线为直线,最优解在凸多边形的某个顶点处取得。可行域空集,如改例中第 3个约束为-3 x1+2x2 ?14 ,则无最优解; 可行域无界,如去掉例中第 3个约束-3 x1+2x2 ?14 ,则可能无最优解; 无穷多最优解,如改例中第 3个约束为 3 x1+x2 ? 14 ,则最优解在凸多边形一条边上取得; 推广到 n维欧氏空间,线性规划问题若有最优解,则最优解必是作为可行域的凸多面体的某个顶点。第 节线性规划图解法 07 数学实验线性规划的 LP 解法相关函数介绍: lp 第 节线性规划 LP 解法 08 min . . z cx s t Ax b ?? x=lp(c,A,b) x=lp(c,A,b,v1,v