最优化问题的三要素是决策变量、目标函数和约束条件。

　　 线性规划（Linear programming），是研究线性约束条件下线性目标函数的极值问题的优化方法，常用于解决利用现有的资源得到最优决策的问题。

　　简单的线性规划问题可以用 Lingo软件求解，Matlab、Python 中也有求解线性规划问题的库函数或求解器，很容易学习和使用，并不需要用模拟退火算法。但是，由一般线性规划问题所衍生的整数规划、混合规划、0/1规划、二次规划、非线性规划、组合优化问题，则并不是调用某个库函数都能处理的。而模拟退火算法在很多复杂问题中具有较好的适应性，可以作为一种入门的通用智能算法来学习。

　　也就是说，如果只是处理线性规划问题，就不要用模拟退火算法了。但如果是现有方法无法处理的复杂优化问题，或者对某类、某个优化问题你不知道用什么方法处理了，这时用模拟退火算法还是能解决的。

　　本文使用惩罚函数法，分析模拟退火算法处理线性规划问题，相关内容也适用于非线性规划问题。

　　 线性规划问题是约束优化问题，而模拟退火算法则更适合处理无约束优化问题。对于优化问题中的约束条件，模拟退火算法有几种常用的处理方法：

　　1. 决策变量取值的上下限约束。此类约束条件比较容易处理，只要设定初始解、新解在决策变量取值的上下限之间就可以解决。例如，（1）设置产生新解的随机数的上下限为决策变量的上下限，即 [Xmin, Xmax]；（2）设置产生新解的随机数的上下限为当前解与决策变量的上下限，即 [Xnow, Xmax]；（3）通过条件判断，当新解超出决策变量上下限，则令其取上下限，即 xNew = max(min(xNew, xMax), xMin)。当然，这些处理方式，都会影响随机数的概率分布，因而也影响模拟退火算法的优化性能，在此不做深入讨论。

　　2. 检验法处理不等式约束问题。在模拟退火算法的迭代过程中，将每次产生的新解代入每个不等式约束函数，判断是否满足约束条件；如果新解不满足约束条件，则舍弃这个新解，返回重新产生一个新解进行检验，直到产生的新解满足全部约束条件为止。这个方法的思路简单，每次迭代都在可行域内进行，但是对于约束条件众多、苛刻的复杂问题，多次产生的新解都不能满足约束条件，会使计算时间很长，甚至停滞不前。

　　3. 消元法处理等式约束问题。对于等式约束，很难通过随机产生的新解满足约束条件，通常不能使用检验法处理。消元法是通过解方程将等式约束中的某个决策变量表示为其它决策变量的线性关系后，代入目标函数和不等式约束条件中，从而消去该约束条件。消元法不仅解决了等式约束问题，而且减少了决策变量的数量，从而有效简化了优化问题的复杂度，是一举两得的处理方法。但是，对于非线性等式约束，求解非线性方程组也是非常困难的，消元法并不是普遍都能适用的。

　　4. 更为通用的处理约束条件的方法是惩罚函数法，以下进行介绍。

　　惩罚函数法是一类常用的处理约束条件的技术，在模拟退火算法中处理约束条件非常有效。方法的思想是将约束条件转化为惩罚函数，附加在原有的目标函数上构造新的目标函数；当不满足约束条件时，通过惩罚函数使新的目标函数变差而被舍弃。

　　惩罚函数法有外点法和内点法。外点法对可行域外的点（即不满足约束的点）施加惩罚，对可行域内部的点不惩罚，从而使迭代点向可行域D逼近。 内点法是在可行域内部进行搜索，约束边界起到类似围墙的作用，使目标函数无法穿过，就把搜索点限制在可行域内了，因此只适用于不等式约束。

　　考虑约束优化问题：　　 min: f(X) 满足限制 ci(X) 惩罚函数法将问题转化成如下无约束问题 min: Lk(X)=f(X)+sigma(k)*g(ci(X)) 其中 g(c_i(X))=max(0,c_i(X))^2

在上述方程，g(ci(X)) 称为外部罚函数，sigma(k) 称为惩罚因子。在每一次迭代中，sigma(k) 都增大，然后求解该无约束问题。将每一次迭代的结果将组成一个序列，此序列的极限即为原约束问题的解。

　　虽然对于线性规划问题并不推荐使用模拟退火算法求解。但为了便于理解，本文仍使用之前的线性规划问题作为处理约束条件的案例。对于非线性规划问题，以及非线性约束问题，处理方法都是类似的，将在后续进行介绍。

　　某厂生产甲乙两种饮料，每百箱甲饮料需用原料6千克、工人10名，获利10万元；每百箱乙饮料需用原料5千克、工人20名，获利9万元。 　　今工厂共有原料60千克、工人150名，又由于其他条件所限甲饮料产量不超过8百箱。 　　（1）问如何安排生产计划，即两种饮料各生产多少使获利最大？

　　决策变量： 　　　　x1：甲饮料产量（单位：百箱） 　　　　x2：乙饮料产量（单位：百箱） 　　目标函数： 　　　　max fx = 10x1 + 9x2 　　约束条件： 　　　　6x1 + 5x2