第7讲：线性规划与非线性规划方法(第1次课)

《第7讲：线性规划与非线性规划方法(第1次课)》由会员分享，可在线阅读，更多相关《第7讲：线性规划与非线性规划方法(第1次课)（14页珍藏版）》请在文档大全上搜索。

1、1第七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用第七讲 线性规划与非线性规划内容内容: 本讲主要介绍线性规划问题的求解本讲主要介绍线性规划问题的求解目的目的: 接触最优化问题接触最优化问题,学习线性规划算法的学习线性规划算法的 MATLAB实现实现(基于单纯型法变种基于单纯型法变种)要求要求: 能够直接对小规模线性规划问题进行求解能够直接对小规模线性规划问题进行求解了解线性规划问题的基本概念、形式和算法了解线性规划问题的基本概念、形式和算法掌握线性规划问题的图解法掌握线性规划问题的图解法(2维维)和和lp算法算法通过范例通过范例,掌握线性规划问题求解一般过程掌握线性规划问题求解

2、一般过程2第七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用关于线性规划的引入和概述 线性规划线性规划隶属于运筹学中的隶属于运筹学中的约束优化约束优化，简单说，简单说就是就是目标函数目标函数(希望进行最优化的指标希望进行最优化的指标)和和约束条件约束条件(决策变量受到的限制决策变量受到的限制)均为线性函数的约束优化均为线性函数的约束优化(否则称为否则称为非线性规划非线性规划) 线性规划问题是企业运作、科技研发和工程设计线性规划问题是企业运作、科技研发和工程设计的常见问题，应用十分广泛。具有代表性的算法的常见问题，应用十分广泛。具有代表性的算法有有单纯型法、椭球法和单纯型法、椭球法和

3、Karmarkar算法算法。随着计。随着计算机硬件和软件技术发展，几十万变量和约束的算机硬件和软件技术发展，几十万变量和约束的线性规划问题已经很普通。线性规划问题已经很普通。 MATLAB优化工具箱优化工具箱 Optimization Toolbox 采用采用投影法投影法(单纯型法变种单纯型法变种)，由函数，由函数linprog实现求解。实现求解。3第七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用解决规划问题的基本流程第1步：问题的分析理解及描述（数学建模）第2步：解决问题的整体目标（目标函数）第3步：影响目标的各种限制条件（约束条件）第4步：应用相关函数获得求解（算法实现）4第

4、七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用哪样一些问题可以描述成为线性规划问题？哪样一些问题可以描述成为线性规划问题？线性规划模型的一般形式12min( ),( ,.,). .( )0,1,2,.,Tnxizf x xx xxst g xim当当 均为线性函数，上述优化模型称为均为线性函数，上述优化模型称为线线性规划性规划，否则称为，否则称为非线性规划非线性规划。关于线性规划的形式，有诸如标准形式、规范关于线性规划的形式，有诸如标准形式、规范形式等形式等之分之分，在这里我们只关心在这里我们只关心MATLAB能能够接受的形式：够接受的形式：,ifgmin. .Tzc xs t

5、Axb一般来说不同形式之间可以转换一般来说不同形式之间可以转换(YCXp14)z目标函数目标函数/c价值向量价值向量/A约束矩阵约束矩阵/b右端向量右端向量一个满足约束的一个满足约束的x-可行解可行解/可行解集合可行解集合-可行域可行域5第七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用线性规划的图解法(2维情形)1通过一个简单的实例通过一个简单的实例,巩固对线性规划的若干巩固对线性规划的若干概念的理解：概念的理解：exp.1 图解法求解线性规划问题图解法求解线性规划问题: 1212112122121231212m ax3. .2 .:222 .:22321 4 .: 321 4,

6、0zxxs txxLxxxxLxxxxLxxxx将前三个约束条件的不等号改为等号将前三个约束条件的不等号改为等号,就是如上就是如上三条直线三条直线,下面考察直线下面考察直线L1, L2, L3及坐标轴围成及坐标轴围成的可行域的可行域:6第七讲第七讲 线性规划与线性规划与非线性规划应用非线性规划应用线性规划的图解法(2维情形)2如图所示如图所示:五边形五边形OQ1Q2Q4Q3构成可行域构成可行域x1x2oL1L2L3Q1Q2Q4(4,1)Q3Z1 Z2 Z3 Z4 Z5 当目标函数当目标函数z=3x1+x2取不同值时，表示一组平行取不同值时，表示一组平行直线，如图中虚线，最优解在直线，如图中虚线