最优化问题及线性规划问题

最优化问题的提出

• 生产计划中，在各种资源有限的前提下，如何安排生产，使生产成本达到最低？
• 工程施工中，要铺设一条从A地到B地输油管道，中间要经过n个中间站，而对于每个中间站又有mi个可选方案，如果各个方案在不同两点间的所需经费已知，如何选择一条最佳路线，使得总费用最低？
• 金融投资中，如何选择和设计证券组合或者投资项目组合，以便在可以接受的风险限度内获得尽可能大的投资回报？
• 机械设计中，如何在满足工作条件、裁荷和工艺要求，并在强度、刚度、寿命、尺寸范围及其他一些技术要求的限制条件下，寻找一组参数，以获得设计指标达到最优的设计方案？
• 针对化学过程如何设计控制方案，才能既优化其性能，又能保证其鲁棒性？
• 在电力分配中，由N个火力发电厂组成一个供电网，要求输出总负荷为S，该如何分配每个发电厂的发电量，在满足各电厂发电量约束的条件下使得总的生产消耗为最小？

最优化问题的数学描述

上述各类问题资源的最优利用问题，所有类似的这种课题统称为最优化问题，研究解决这些问题的科学一般就总称之为最优化理论和方法，用数学语言描述的话，最优化方法就是在给定的约束条件下，如何在某种范围内选取一些决策变量的取值，使得一个或者多个既定目标达到最优状态（极大、极小或者某种妥协状态）的一门学科。

最优化理论和方法的产生和发展

一些古老的方法
黄金分割法
阿基米德证明：如果给定平面几何图形的周长，则在各种图形中，圆所包围的面积为最大

古典最优化方法——精确的分析方法
理论基础的建立——牛顿和莱布尼茨在他们所创建的微积分理论
有约束的最优化问题
变分法

最优化理论和方法
由于军事上的需要产生了运筹学
线性规划，非线性规划 ，动态规划

现代优化方法
遗传算法
神经网络
模拟退火

最优化问题的数学模型

由各例子可以看出，最优化问题涉及的领域非常广泛，形式也千变万化，但是它们却可以用统一的数学形式表达，简单的 说，均可以转化为最小（或最大）化一个n维变量x的实函数f(x)，其中对变量
含有多种约束。一般情况下，最优化问题的数学模型可以表达如下：

最优化问题分类

根据设计变量的特征分类
• 按照设计变量的维数进行分类——一维优化问题，n维优化问题
• 根据设计变量的取值进行分类——离散最优化和连续最优化
根据目标函数的类型分类
• 只有一个目标的优化问题称为单目标优化问题
• 存在两个或者两个以上目标函数的优化问题，称为多目标优化问题
根据约束条件的类型分类
• 有无约束——无约束优化问题和约束优化问题
• 约束类型——线性规划、二次规划、整数规划、0-1规划、非线性规划等
根据最优化问题的解分类
• 如果最优化问题的解不随时间变化，则称其为静态最优化问题或参数最优化问题
• 如果最优化问题的解随时间而变，则称其为动态最优化问题

最优化问题的典型实例

资源利用问题：

数学模型：

分派问题：



数学模型：

投资决策问题：


数学模型：

什么是线性规划

最优化问题中有三个要素：决策变量、目标函数、约束条件，如果其中的目标函数和约束条件都是线性的，则该最优化问题称为线性规划问题。

线性规划问题的特征

1、均可以用一组设计变量来表示一种实施方案
2、每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式表达
3、在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或者最小值

线性规划的典型实例

运输问题

设决策变量xij代表建材厂Ci运往建筑工地Wj的数量（万吨），则各建材厂和工地之间的运量可以用下表来表示：

目标函数即为总运费：

约束条件：
建材厂C1、 C2的输出量应分别为建材厂C1、 C2的产量：

各工地的沙石需求量应当为从各建材厂接收到沙石的总量：

运输量xij为一非负值：

用计算机求解线性规划详见
[线性规划(LP)问题的Matlab求解](https://blog.csdn.net/zhangkaikai36/article/details/126997190?