求解最优化问题的方法(经典组合优化问题的一般求解方法)

1.经典组合优化问题的一般求解方法有哪些

组合最优化方法（combinatorial optimizationmethod ）求解组合最优化问题的方法一般地，对于不同类的组合最优化问题，对应着不同的求解方法.判定一个组合最优化方法好坏的主要标准是运算次数.用n表示某一组合最优化问题的规模p(n)表示在对方法影响最坏的情况下所需的运算次数.若p(n)是n的多项式函数，则称该方法是多项式算法.凡能用多项式算法求解的问题都称为P问题.有一类问题称为NP完全问题，若这类组合最优化问题具有如下特点：1.它们都未找到多项式算法.2.如果对其中某一问题存在多项式算法，那么此类中的所有问题也都有多项式算法.已发现有成千的组合最优化问题属于NP完成问题.为求解该类中的问题，人们往往采用“启发式”方法.这些方法一般地，不能保证求得问题的最优解，但常能得到较好的近似解。

2.解决经济分析的最优化问题的基本步骤是什么

从数学角度看，最优化问题可以分为无约束最优化和约束最优化。所谓无约束最优化问题是比较简单的微分问题，可用微分求解。

管理决策问题往往也就是最优化问题，而比较常用和方便的方法就是边际分析法。

所谓“无约束”，即产品产量、资源投入量、价格和广告费的支出等都不受限制。在这种情况下，最优化的原则是：边际收入等于边际成本，也就是边际利润为零时，利润最大，此时的业务量为最优业务量。管理决策中的诸多最优化问题，比如投入要素之间如何组合才能使成本最低；企业的产量多大，才能实现利润最大，当因变量为自变量的连续函数时，经济学与数学意义是统一的，可用边际分析法解决；而在处理离散数列的最优化问题时则可以用统计的方法先将离散数列拟合成连续函数，求得最优点，然后在原离散数列中找到离拟合曲线最优点最近的前后两点，比较其值及其投入量，既而求得最优点。

有约束条件的最优化包括一个或几个货币、时间、生产能力或其他方面的限制，当存在不等式约束条件时，可以采用线性规划。大多数情况下，管理者知道某些约束是连在一起的，即它们是同样的约束条件，可以采用拉格朗日乘数法解决这些问题。

从数学上比较一般的观点来看，所谓最优化问题可以概括为一种数学模型：结合一个函数F(x)以及自变量 应满足一定的条件，求X 为怎样的值时，F(x)取得其最大值或最小值。通常，称F(x)为目标函数，X 应满足的条件为约束条件。求目标函数F(x)

在约束条件X 下的最大值或最小值问题，就是一般最优问题的数学模型，可以用数学符号简洁地表示为MinF(x)或MaxF(x)。解决最优化问题地关键步骤是如何把实际问题，抽象成数学模型，也就是构造出目标函数与约束条件，一旦这一步完成，对于简单问题，可借助图形或微积分来解决，遇到比较复杂地课题，可利用现有地数学软件或最优化软件，比如Matlab, Mathematica, Lindo,Lingo 等来计算。下面举例说明如何计算有约束条件地最优化问题。

例 设某种产品的产量是劳动力x和原料y(t)的函数，f(x),y=60X 3y 2，假定每单位劳动力费用100元，每单位原料费用200元，现有2万元资金用于生产，为了得到最多的产品，应如何安排劳动力和原料。

解：依题意，可归结为求函数f(x,y)=60x 3y 2在约束条件100x+200y=20000下的最大值，故可用拉格朗日乘数法求解。

3.目前对于优化控制问题有哪些求解方法

最优控制理论（optimal control theory），是现代控制理论的一个主要分支，着重于研究使控制系统的性能指标实现最优化的基本条件和综合方法。 最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。它是现代控制理论的重要组成部分。

为了解决最优控制问题，必须建立描述受控运动过程的运动方程，给出控制变量的允许取值范围，指定运动过程的初始状态和目标状态，并且规定一个评价运动过程品质优劣的性能指标。通常，性能指标的好坏取决于所选择的控制函数和相应的运动状态。系统的运动状态受到运动方程的约束，而控制函数只能在允许的范围内选取。因此，从数学上看，确定最优控制问题可以表述为：在运动方程和允许控制范围的约束下，对以控制函数和运动状态为变量的性能指标函数（称为泛函）求取极值（极大值或极小值）。解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。