系统工程第8章-系统优化

系统工程

第八章系统优化

November20,2023PPT

12023最新整理收集do

something本章学习目标1.了解最优化问题的基本概念2.学会建立最优化问题的数学模型3.掌握线性规划及单纯形法4.掌握动态规划及逆序解法5.了解非线性规划November20,2023PPT

2章节框架

8.1最优化问题概述

8.2线性规划

8.3动态规划

8.4非线性规划

本章小结

思考与练习题

参考答案November20,2023PPT

38.1最优化问题概述最优化理论与方法最优化理论是一个重要的数学分支，它所研究的问题是在众多的方案中什么样的方案最优以及怎样找出最优方案。最优化理论与方法在第二次世界大战后迅速发展，成为一门新兴学科，并且随着科学技术的进步和现代化生产的发展，越来越受到人们的重视，其发展日趋成熟。

November20,2023PPT

4

在满足约束条件的解中确定使目标函数达到最大或最小值的问题就是最优化问题，最优化问题的一般数学模型为：

目标函数约束条件8.1最优化问题概述November20,2023PPT

5

模型由三个要素组成：

(1)变量,又称为决策变量，是问题中要确定的未知量，用以表明最优化问题中的用数量表示的方案、措施，可以由决策者决定和控制。

(2)目标函数,它是决策变量的函数，按优化目标的不同分别在这个函数前加上max或min。

(3)约束条件,指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。8.1最优化问题概述November20,2023PPT

68.2

线性规划

8.2.1线性规划模型

8.2.2单纯形法November20,2023PPT

78.2.1线性规划模型

约束条件和目标函数都是呈线性关系的就叫线性规划。线性规划是最优化理论的一个重要分支，它是研究如何在多项互相竞争的活动中间最优地分配各项有限的资源的一种数学方法。线性规划研究的问题主要有两类：一类是已经给定可用的资源的数量，如何运用这些资源来完成最大量的任务；另一类是已经给定一项任务，研究如何统筹安排，才能以最少量的资源去完成这项任务。November20,2023PPT

88.2.1线性规划模型

对于一类最优化问题，如果同时满足如下条件：（1）按问题的不同，要求实现决策变量的线性函数（即目标函数）最大化或最小化。（2）存在一组用线性等式或线性不等式表示的约束条件。（3）每一个问题都用一组决策变量表示某一方案，一般这些变量取值是非负的。我们将满足上述条件的问题称为线性规划问题，简称为LP。November20,2023PPT

98.2.1线性规划模型

一般线性规划的数学模型具有如下形式:

November20,2023PPT

10用矩阵和向量形式来描述时，上述模型可写为：其中8.2.1线性规划模型November20,2023PPT

118.2.1线性规划模型

为了求解问题的方便，常将多种线性规划问题统一变换为标准形式:November20,2023PPT

128.2.2单纯形法

单纯形法是应用最早也是最广泛的一种求解线性规划问题的行之有效的方法。其基本思想是：从可行域中某个基可行解出发，每次用一个非基变量来取代一个基变量，也就是把一个非基变量从0增加到某一个正数，而把相应的一个基变量从一个正数变成0，使得每一个新的解有可能改进目标函数值，经过一次次迭代，目标函数值一步步改进，当使目标函数达到最大值时，线性规划就得到了最优解。November20,2023PPT

138.2.2单纯形法单纯形法的基本步骤(1)找出初始可行基，确定初始基可行解，建立初始单纯形表，一般先取松弛变量为基变量。(2)检验各非基变量的检验数，若

,则可得到最优解，停止计算；否则转入步骤3。(3)在中，若有某个对应的系数列向量

0，则此问题无界，停止计算；否则，转入步骤4。(4)根据，确定为调入变量，按最小比值规则计算确定为调出变量。转入步骤5。November20,2023PPT

14(5)用加减消元法化主元为１，同列其他系数为０，把所对应的列向量变为：将列中的换为，得到新的单纯形表，重复步骤2-5，直到终止。

8.2.2单纯形法November20,2023PPT

15解决线性规划问题的一般步骤如下：(1)明确问题的目标，划定决策实施的范围，建立线性目标函数；(2)选定决策变量，一组决策变量就是一个决策方案；(3)建立约束条件，每个约束条件均为决策变量的线性函数；(4)线性规划模型求解；(5)线性规划模型及其解的特性分析，如灵敏度分析等。8.2.2单纯形法November20,2023PPT

168.3动态规划

8.3.1动态规划概述

8.3.2多阶段决策问题

8.3.3动态规划模型November20,2023PPT

17

动态规划是美国数学家贝尔曼（R.Bellman）等人于20世纪50年代提出的解决多阶段决策过程最优化问题的一种数学方法，并根据多阶段决策问题的特点提出了解决这类问题的“最优化原理”，研究了许多实际问题，最终建立了数学规划的一个新分支——动态规划(Dynamicprogramming)，简称为DP。可以根据时间变量是离散的还是连续的，把动态规划问题分为离散决策过程和连续决策过程；根据决策过程的演变是确定性的还是随机性的，动态规划问题又可分为确定性的决策过程和随机性的决策过程，即离散确定性，离散随机性，连续确定性，连续随机性四种决策过程模型。8.3.1动态规划概述November20,2023PPT

188.3.2多阶段决策问题

把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，这种解决多阶段决策最优化的过程为动态规划方法。November20,2023PPT

198.3.3动态规划模型动态规划的概念(1)阶段(Stage)(2)状态(State)(3)决策(Policy)(4)策略(Strategy)(5)状态转移方程(Statetransformequation)(6)指标函数(Indexfunction)November20,2023PPT

20常见的指标函数形式：(a)求和型指标函数(b)乘积型指标函数8.3.3动态规划模型November20,2023PPT

218.3.3动态规划模型

动态规划的基本思想：对最优策略来说，无论过去的状态和决策如何，由前面诸决策所形成的状态出发，相应的剩余决策序列必构成最优子策略。也就是说，最优策略后部的子策略总是最优的。逆序解法：根据动态规划的基本思想可知，寻求最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到点的最短路线。最后求出由点到点的最短路线，这种解法称为逆序解法。November20,2023PPT

228.3.3动态规划模型建立动态规划模型的过程中必须注意：（1）要解决的实际问题应由几个相互联系的阶段组成，而每个阶段始点往往存在几个可供选择的不同状态，对每一阶段都必须进行决策，同时要求能写出状态移动方程，有些实际问题阶段的组成并不明显，需要仔细地观察和人为地划分，对每一种状态可根据决策变量取值所对应的成本大小做出决策，进而找出最优策略(最低成本)；（2）在动态规划求解中不可避免的需要确定问题的策略，子策略和指标函数。一般来说，要解决的问题不同，策略和子策略的内容也不同，而指标函数的含义也随问题的改变而改变；November20,2023PPT

238.4非线性规划

8.4.1非线性规划概念

8.4.2二次规划November20,2023PPT

248.4.1非线性规划概念

在实际问题中存在一类特殊的最优化问题，他们的目标函数或约束条件中包含有自变量的非线性函数，则将这一类特殊的规划问题称为非线性规划，简记为（NP）。非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。非线性规划是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的如凸分析、数值分析等也得到了发展。

November20,2023PPT

25

非线性规划问题模型的一般形式：一般将不带有约束的极小化问题称为无约束极小化问题；根据约束条件是否是等式，还可以将非线性规划问题分为等式约束下的极小化问题和不等式约束下的极小化问题。8.4.1非线性规划概念November20,2023PPT

26Kuhn-Tucher条件：若是问题(8-12)的局部最优解，且为正则点，则存在向量，使下述条件成立：8.4.1非线性规划概念November20,2023PPT

278.4.1非线性规划概念

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意：（1）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（2）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（3）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（4）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。November20,2023PPT

288.4.1非线性规划概念非线性规划的Matlab解法

Matlab中非线性规划的数学模型写成以下形式

November20,2023PPT

298.4.2二次规划

求解约束极值问题比求解无约束极值困难得多，为了简化工作，常采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及将复杂问题变换为简单问题等方法。在下面主要介绍约束极值问题中的一类特殊问题：二次规划问题。所谓二次规划问题，就是非线性规划的目标函数为自变量的二次函数，同时约束条件又全是线性的。二次规划问题是非线性规划问题中比较简单的一类，较容易求解，同时它和线性规划问题也有直接联系，因此在实际中常将很多方面的问题抽象成二次规划的模型来求解。November20,2023PPT

30

二次规划的数学模型常可以表述如下

8.4.2二次规划November20,2023PPT

318.4.2二次规划

求解二次规划的方法的步骤：

(1)将库恩-塔克条件中的第一个条件应用于二次规划，并用代替库恩-塔克条件中的即可得到

(2)若在式中引入松弛变量,则得到如下等式：

(3)将库恩-塔克条件中第二个条件应用于二次规划，与上式联立，November20,2023PPT

32(4)联立求解式和，若求得的解也满足式和，则此时得到的解就为二次规划问题的解。得到初始基本可行解8.4.2二次规划November20,2023PPT

33将上述问题修正后得到如下线性规划问题：

8.4.2二次规划November20,2023PPT

34本章小结

本章首先通过几个例子介绍了什么是最优化问题，提出了最优化问题数学模型的一般形式并解释了模型的各个组成要素。其次介绍了最优化问题的几个重要分支，包括线性规划、动态规划和非线性规划。内容包括线性规划的定义、线性规划模型、线性规划模型的标准形式、单纯形法；多阶段决策问题的定义、动态规划的概念、动态规划模型、基本思想和逆序解法求解动态规划问题；非线性规划的定义、凸函数的概念和判断条件、Kuhn-Tucher条件、二次规划问题的模型及其解法。通过本章的学习，要求了解最优化问题的基本概念，学会如何分析实际问题建立最优化问题的数学模型，并且选择适当的方法求解最优化问题。重点包括如何把一般形式的线性规划模型转变为标准形式、如何运用单纯形法求解线性规划问题、建立动态规划方程、逆序法求解动态规划问题、非线性规划问题中比较简单的二次规划问题的模型的建立及求解。November20,2023PPT

35思考与练习题试述最优化问题的数学模型的结构及各要素的特征。什么是线性规划问题的标准形式，如何将一个非标准型的线性规划问题转化为标准形式。试述单纯形法的基本思想和计算步骤。试述动态规划的最优化原理，动态规划方法的基本思想和动态规划基本方程的结构。如何判断一个函数是否为凸函数。November20,2023PPT

36思考与练习题

6.某工厂生产甲、乙两种产品，单位产品的销售价格和所需要的原料的数量、原料的供应量及单价如表8-1所示，问：工厂应如何安排生产，才能使所获利润最大？建立该线性规划问题的数学模型。表8-1原料的供应量及单价甲乙日供应量原料单价（百元/kg）原料A(kg)621801原料B(kg)4104002原料C(kg)3521014销售价格(百