2.1　最优化算法

最优化算法是通过对混流装配线中不同的生产计划状况进行具体分析，建立问题的数学函数模型，并结合收集的时间数据进行数理化分析，求解装配线在理论上达到最优平衡状态。它主要运用了运筹学中的分支定界法和数学规划法。其中，分支定界法是求解组合优化问题的通用方法，通过对分支定界的规则制定、设计出更强大、效率更高的排除规则，求得优化问题的最优解；数学规划法主要包括整数规划法、线性规划法、混合整数规划、拉格朗日松弛法、动态规划法等，其中的线性规划法和动态规划法是较为常用的优化方法。下面对其进行具体描述。

1. 线性规划法

线性规划（Linear Programing，LP）模型是由约束条件和目标函数组成的，研究在满足线性约束条件下找出目标函数的最优解。作为运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面，是合理地利用有限的人力、物力、财力等资源做出的最优决策，提供科学的依据。它是最早应用于装配线优化问题的研究方法，其在混流装配线应用中的主要优点是模型建立相对简单、易于理解，但由于受到约束条件的限制，模型难以准确地表达混流装配线的实际情况，同时优化的运算量会随着变量和约束条件的变化而增多。尤其是混流装配线中又引入了品种维度，使得线性规划模型的整体求解规模增大。线性规划的一般流程如图2-1所示。

2. 动态规划法

动态规划（Dynamic Programing，DP）法是用以解决多阶段决策最优的一种方法。它将实际中复杂的混流装配线优化问题划分为多个互相联系的子阶段，逐个解决每个子阶段的优化问题，以此实现整个生产系统最优化的目的。混流装配线中的简单生产计划优化问题包含最优化原理、无后效性和有重叠子问题3种性质，适合动态规划法的求解范围，因而对小规模、简单环境的混流装配线生产计划优化问题可以利用动态规划法进行优化分析。动态规划法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或分治）的方式去解决。其基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划法解决的问题多数有重叠子问题这个特点，为减少重复计算，对每个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。能采用动态规划法求解的问题的一般具有以下3个性质。

（1）最优化原理。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

（2）无后效性。某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题。子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划法同其他方法相比就不具备优势了）。

动态规划法所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线），如图2-2所示。动态规划法的设计都有一定的模式，一般要经历以下几个步骤。

（1）划分阶段。按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段中，注意划分后的阶段一定是有序的或是可排序的；否则问题就无法求解。

（2）确定状态和状态变量。将问题发展到各阶段时，所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程。因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果确定了决策，状态转移方程也就可以写出了。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

（4）寻找边界条件。给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般来说，只要确定问题的阶段、状态和状态转移决策，就可以写出状态转移方程（包括边界条件）。在实际应用中，可以按以下几个简化的步骤进行设计。

① 分析最优解的性质，并刻画其结构特征。

② 递归的定义最优解。

③ 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。

④ 根据计算最优值时得到的信息，构造问题的最优解。

3. 分支定界法

分支定界（Branch and Bound）法是一种求解整数规划问题最常用的方法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。对于两个变量的整数规划问题，使用网格的方法有时更为简单。通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；对每个子集内的解集计算一个目标下界（对于最小值问题），称为定界。在每次分支后，凡是界限超出已知可行解集目标值的那些子集不再进一步分支。这样，许多子集可不予考虑，称之为剪枝。这就是分支定界法的主要思路。

分支定界法是组合优化问题的有效求解方法，其步骤如下。

（1）如果问题的目标为最小化，那么设定目前最优解的值Z=∞。

（2）根据分支法则（Branching Rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。

（3）计算每个新分支出来的节点的下限值（Lower Bound，LB）。

（4）对每一节点进行洞悉条件测试，若节点满足以下任一条件，则此节点可洞悉而不再被考虑，此节点的下限值大于或等于Z值。已找到在此节点中，具有最小下限值的可行解。若此条件成立，则需比较此可行解与Z值；若前者较小，则需更新Z值，以此为可行解的值。此节点不可能包含可行解。

（5）判断是否仍有尚未被洞悉的节点，若有，则进行步骤（2），若已无尚未被洞悉的节点，则演算停止，并得到最优解。

分支定界法的优缺点如下。

优点：可以求得最优解、平均速度快。

因为从最小下界分支，所以每次算完限界后，把搜索树上当前所有的叶子节点的限界进行比较，找出限界最小的节点，此节点即为下次分支的节点。这种决策的优点是检查子问题较少，能较快地求得最佳解。

缺点：要存储很多叶子节点的限界和对应的耗费矩阵，花费很多内存空间。

分支定界法可应用于大量组合优化问题。其关键技术在于各节点权值如何估计，可以说一个分支定界法的效率基本上由值界方法决定。如果界估计不好，那么在极端情况下将与穷举搜索没多大区别。

分支定界法或数学规划法等优化方法只适用于求解规模较小、环境简单的优化问题；而当面对复杂多变的实际优化环境则是难以应对的。因此，对于更大规模及更复杂环境的混流装配线优化问题需要采取更有效的优化方法进行优化分析。