《优化与策略教学课件作者李卫国第2章优化方法之建模实验篇》由会员分享，可在线阅读，更多相关《优化与策略教学课件作者李卫国第2章优化方法之建模实验篇（82页珍藏版）》请在金锄头文库上搜索。
1、第2章 优化方法之建模实验篇,2. 1什么是数学模型和数学建模 2. 2数学建模的初级战法线性规划问题 2. 3数学建模的中级战法非线性规划问题 2. 4数学建模的终级战法实战规划问题,返回,2. 1 什么是数学模型和数学建模,数学模型(Mathematical Model)是用数学符号对一类实际问题或实际系统发生的现象的(近似的)描述。它不仅是了解基本规律，而且从应用的观点来看更重要的是预测和控制所建模的系统行为的强有力工具。而数学建模(Mathematical Modeling)则是获得该模型、求解该模型并得到结论以及验证结论是否正确的全过程，而且从应用的观点来看更重要的是预测和控制所建模
2、系统的行为的强有力工具。 数学建模的全过程大体上可归纳为以下步骤： (1)对某个实际问题进行观察、分析(是否抓住主要方面)。 (2)对实际问题进行必要的抽象、简化，做出合理的假设(往往是很不容易的)。 (3)确定要建立的模型中的变量和参数。,下一页,返回,2. 1 什么是数学模型和数学建模,(4)根据某种“规律”(已知的各学科中的定律，甚至是经验的规律)建立变量和参数间确定的数学关系(明确的数学问题或在这个层次上的一个数学模型)，这可能是一个非常具有挑战性的数学问题。 (5)解析或近似地求解该数学问题。这往往涉及复杂的数学理论和方法，近似方法和算法。 (6)数学的结论能否展示、解释甚至预测实际
3、问题中出现的现象，或用某种方法(例如，历史数据、实验数据或现场测试数据等)来验证结论是否合理、正确，这也是很不容易的。 (7)如果第(6)步的结果是肯定的，那么就可以付之试用;如果是否定的，那就要回到第(1)(6)步进行仔细分析，重复上述建模过程。 因此，如果要对数学建模下定义，那就是:数学建模就是上述7个步骤的多次重复执行的过程。如果用框图来表示，则如图2.1.1所示。,上一页,下一页,返回,2. 1 什么是数学模型和数学建模,由此可见，数学建模过程中最重要的3个要素，也是3个最大的难点是: (1)怎样从实际情况出发做出合理的假设，从而得到可以执行的合理的数学模型。 (2)怎样求解模型中出现
4、的数学问题，它可能是非常困难的问题。 (3)怎样验证模型的结论是否合理、正确、可行的。 数学建模中的优化问题，是比较典型的一类题目，主要特点是实现某种过程或达到某个结果的方法不唯一，但是不同方法的代价是不同的，优化问题就是寻找代价最小的方法。所以简单地说，优化问题的日的就是找到最佳实现方法。 人们解决这些优化问题的手段大致有以下几种: (1)依赖过去的经验判断面临的问题。 (2)做大量的试验反复比较。,上一页,返回,2.2数学建模的初级战法-线性规划问题,2. 2. 1线性规划的基本原理和解法 一、线性规划的图解法 作图如图2. 2. 1所示。 求解线性规划的基本思路为:从可行域的某一顶点开始
5、，只需在有限多个顶点中一个一个找下去，一定能得到最优解。于是问题化为怎样从一顶点转到下一顶点，使尽快找到最优解。 从二维例子的几何意义可以看出，还会有下列情形出现: (1)若可行域为空集，则无最优解。 (2)若可行域无界，则可能无最优解。 (3)最优解在凸多边形的一条边上取得，则有无穷多个最优解。,下一页,返回,2.2数学建模的初级战法-线性规划问题,二、单纯形法的基本思路 对于二维空间有图解法，但三维空间或更高维的空间就无法用图解法了，单纯形法正是用于解决高维伞间的最有效的算法，且具有一般性。其基本思路是:用迭代法从一个顶点转换到另一个顶点，每一个转换应使目标函数下降较多。单纯形法的具体步骤
6、可参阅线性规划书籍。由于计算机的普及和时间关系，我们对工科学生更强调用数学软件包Matlab优化工具箱、Lingo等软件计算模型。 图解法简单直观，有助于了解线性规划问题求解的基本原理。如图2. 2. 2所示. 从上面的图解过程可以看出，并不难证明以下断言: (1)可行域R可能会出现多种情况。R可能是空集一也可能是非空集合，当R非空时，它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域，也可能是无界区域。,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,(2)在R非空时，线性规划既可以存在有限最优解，一也可以不存在有限最优解(其目标函数值无界)。 (3) R
7、非空且LP有有限最优解时，最优解可以唯一或有无穷多个。 (4)若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。 2. 2. 2用Matlab优化工具箱解线性规划 Matlab语言是由美国的Clever Mole:博士于1980年开发的，它集科学计算、图像处理、声音处理于一身，并提供了丰富的% inflow*图形界面设计方法。Matlab语言提供了一套功能强大的绘图命令，这些命令可以根据输入的数据自动完成图形的绘制，为计算过程和结果的可视化提供了极佳的手段。,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,一、线性规划的Matlab标准形式 线性规划的目
8、标函数可以是求最大值，一也可以是求最小值，约束条件的不等号可以是小于号一也可以是大于号。 二、线性规划问题的解的概念 一般线性规划问题的标准型为: 定义2. 2. 1满足约束条件(2)的解x=(x1，x2，xn ),称为线性规划问题的可行解，而使目标函数(1达到最小值的可行解叫做最优解。 定义2. 2. 2所有可行解构成的集合称为问题的可行域，记为R。 定义2.2.3称n维空间中的区域R为一凸集，若 有,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,定义2. 2. 4设R为n维空间中的一个凸集，R中的点二被称为R的一个极点，若不存在 三、求解线性规划的Matlab解法 用Mat
9、lab优化工具箱求解线性规划时必须先化为如下形式: 有如下程序:,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,其中，输入矩阵参数c,A, b，输出x为最优解;，v1，v2给出x的下界和上界，即有约束v1 x v2 ， v1或v2的维数k可以小于x的维数n，这时， v1或v2仅表示x前k个分量的下界或上界; x0为初始值，缺省时程序自动取x0=0; ne为等式约束的个数，且需将等式约束置于不等式约束前面;dis给出警告信息，如解无界或不可行。当中间某个参数缺省时，需用 占据其位置。输出参数lag是拉格朗日乘子，维数等于约束条件的个数，其非零分量对应于起作用的约束条件;b给出错误
10、信息:无可行解(infeasible，无有界解(unbounded)或问题顺利解决(ok) 。 Matlab 7. 0中线性规划的标准型为: 四、可以转化为线性规划的问题 很多看起来不是线性规划的问题一也可以通过变换变成线性规划问题来解决。,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,2.2.3用Lingo解线性规划和整数规划 Lingo(Linear Interactive and Discrete Optimizer)和Lingo(Linear Interactive and Generai Optimizer)是由美国芝加哥大学的Linus Schragc于1986年开
11、发的优化计算软件包，Lingo可以用来求解线性规划、线性整数规划、二次规划和整数二次规划，而Lingo除此之外还可以解非线性规划和非线性整数规划。 一、Lingo解线性规划 用Lingo求解线性规划(LP)时，首先在Lingo软件的模型窗口输入一个LP模型，模型以MAX或MIN开始，按线性规划问题的自然形式输入(见下面例子所示)。输入结束时只需键入END。,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,显然，目标函数和约束条件都是线性的，这是一个线性规划(linear programming , LP ) ,求出的最优解将给出使净利润最大的生产计划，要讨论的问题需要考虑参数的变
12、化对最优解的影响，一般称为敏感性(或灵敏度)分析。 二、Lingo解整数规划 Lingo可用于求解单纯的或混合型的整数规划。Lingo求解IP问题用的是分支定界法。但目前尚无完善的敏感性分析理论，因此敏感性分析在整数规划中没有意义。,上一页,下一页,返回,2.2数学建模的初级战法-线性规划问题,三、用Lingo求解整数规划 Lingo软件用于线性或非线性规划(无论是连续规划还是整数规划)，因此包含了Lingo的功能。在Lingo中，输入总是以“model:”开始，以“end”结束;中间的语句之间必须以“;”分开;目标函数用“MAX=;”或“MIN=；”给出(注意有等号“=”)。在Lingo中所
13、有的函数均以“”符号开始，如约束中gin ( x1)表示x1为整数，用bin(x1)表示x1为01整数。在现在的Lingo中，默认设置假定所有变量非负。,上一页,返回,2. 3数学建模的中级战法-非线性规划问题,2. 3. 1非线性规划的基本原理和解法 非线性规划(NLP)有很多解法，如一般教科书上介绍的最速下降法、可行方向法、罚函数法、梯度投影法、步长加速法等，其共性均是逐步迭代法的形式，找出的最优点通常只是局部最优，这里我们先论述一下简单且好编程的步长加速法和仿真方法解非线性规划，其后叙述Matlab优化工具箱中用的逐步二次规划法(Sequential Quadratic Programm
14、ing，记作SQP)，它被认为是解NLP很有效的方法，通过它们来感受一下非线性规划解法特性。 一、步长加速法 步长加速法的思想很简单、易编程，可用于求解有约束和无约束非线性规划问题，先通过二维的例子来说明无约束非线性规划极小化min问题:,下一页,返回,2. 3数学建模的中级战法-非线性规划问题,首先在可行域中找一初始点A，坐标x0，从x0出发，沿x轴正向，按固定步长“试跨出一步到A1点，计算函数值.f (A1) ，若函数值下降了(若没下降则反向后退一步试算，若还不下降则在原地)，则从此点出发沿)轴正向按固定步长u试跨出一步到B点，计算函数值f (B)，若函数值下降了(若没下降则反向后退一步试
15、算，若还不下降则在原地)，则说明沿方向A到B是下降方向，真正跨出的一步，应该是从x0出发，沿A到B方向，加倍跨出到点x1。重复以上过程到走不动为止，走不动则说明最优点离此地不远了，缩短步长，令新的步长=u/10，如此下去到步长符合要求精度为止。,上一页,下一页,返回,2. 3数学建模的中级战法-非线性规划问题,二、仿真方法解非线性规划 仿真方法只能用于可行域有限的非线性规划问题，其思想很简单，通过二维的例子来说明:找一较小的矩形区域覆盖住可行域，在此矩形区域内随机找一点，若此点是可行域内的点，则计算函数值，如此重复上万次，从中选出最优值作为原最优化问题的近似解。显然，解的精度随重复次数的上升而
16、上升，若维数较高可行域较大，则此法效率就较差。此法的优点是好编程，不用求导数。 三、SQP方法的基本原理 SQP解LNP (1)的基本原理是:构造拉格朗日函数:,上一页,下一页,返回,2. 3数学建模的中级战法-非线性规划问题,SQP包括以下3个主要部分: (1)求解QP子问题; (2)用线性搜索计算步长ak; (3)确定矩阵Gk的迭代公式。 2. 3. 2用Matlab优化工具箱解非线性规划 一、Matlab优化工具箱 优化工具箱(Optimization toolbox)在Matlab中其主要功能列入表2. 3. 1 。 g和dg的表达形式请看下面的例子: 计算结果见表2. 3. 2。,上一页,下一页,返回,2. 3数学建模的中级战法-非线性规划问题,二、控制参数options的设置 在大多数优化程序中有一个向量控制参数options，由18个元素组成，供使用者在计算时控制精度要求、输出形式、算法选择、迭代次序等，options的18个元素的功能极其缺省值列入表2. 3. 3中。 三
