生产计划优化模型在生产计划管理软件中起重要作用-永凯软件技术（上海）有限公司

生产计划管理知识

返回列表

生产计划优化模型在生产计划管理软件中起重要作用

时间：2013年5月24日来源：永凯软件技术（上海）有限公司

生产计划优化模型在生产计划管理软件中起重要作用

1、线性规划
　　建立生产计划优化模型并进行求解，运用的最主要的数学方法是线性规划，它是应用最广泛的优化技术之一。线性规划这个术语最早由1947年提出，所解决的问题中目标函数和约束条件都是线性的。
　　线性规划的一个重要特性是：极值一般总是发生在可行域的顶点上。这构成了求解LP问题单纯形法的基础。单纯形法的基本思想是，将全部变量分成两部分：基变量和非基变量。令非基变量的值为0，而得到的一组解称为基解，如果这组基解又满足非负的条件，就称为基可行解。有如下定理：线性规划问题如果有最优解，则最优解一定可以在基可行解中找到。基于这个定理，LP的最优解只需在基可行解中去搜索。单纯形法就是基于这一思想而形成的有效搜索方法，它从一个基可行解索到另外一个基可行解，直到最优解。在此基础上又形成对偶单纯形的求解方法。
　　求解LP问题还可以应用阻挡层法。阻挡层法于1980年被首次提出。这种方法的基本原理及操作方式跟单纯形法完全不同。它产生一系列的点，在该方法收敛时，这些点才能满足所有约束条件，并且这些点不一定是顶点。它们可以穿过可行域，而不像单纯形法那样从一个顶点移动到另一个顶点。
2、非线性规划
　　如果在计划优化问题中出现的目标函数是非线性的，约束条件是线性的或非线性的，这类问题可以称为非线性规划问题。主要有以下求解方法：
　　（1）通过求解一阶必须条件达到优化的解析方法，这种方法只适用于含变量较少的小问题；
　　（2）罚函数和障碍法，这两种方法到基本原理都是将有约束的优化问题变为一组无约束优化问题再进行求解；
　　（3）序贯线性规划法，在实际中应用广泛。当最优值在顶点时，快速收敛。在每次迭代中并不需要满足等式约束，但是对于非顶点最优化问题，可能收敛的比较慢，而且会经常大量违反非线性约束，直到收敛至最优；
　　（4）序贯二次规划法。二次规划问题是指对服从m个线性不等式或等式约束，含n个变量的二次目标函数进行最小化的优化问题。序贯二次规划法所需函数及梯度值往往最少，在每次迭代中，并不需要满足每一个等式约束。但是也会经常大量地违反非线性约束，直到收敛至最优；
　　（5）广义简约梯度法。适合于线性约束和非线性约束，一旦达到一个可行解，那么它将保持可行。可以在任何一步都停止。并得到一个改进解，缺点就是每一步都需要满足算法中的等式约束条件。
3、混合整数规划
　　在工厂生产计划的制订过程中，很多问题涉及的变量是整型的，而不是连续的。例如：求解完成某项工作的人数，最优调度的人数等；还有更为重要的决策问题，可以用0和1表示，这类决策变量称为0-1变量，生产计划中包含许多此类决策问题。我们将这类问题称为混合整数规划问题。许多MIP问题的目标函数和约束条件都是线性的，称这类数学规划问题为混合整数线性规划问题，而称约束条件或目标函数包含非线性规划。
　　求解MILP问题最常用的方法是分支界限法，简要介绍一下求解原理：分支界限算法中所有的整列变量都是二进制的，即0或1。通过将0或1的二进制约束松驰为“0或1之间的任意值”，如果解出的解中所有的离散变量都为整型值，那么这个方法即可求解MILP；相反，如果一个或多个离散变量含有小数值，选择其中一个变量，针该变量的值固定为0或1，创建两个子问题。如果这些子问题中的任何一个有整形解，则求解到此结束，如果其目标函数值优于迄今为止找到的最优值，即用该值代替原最优值。如果所有的子问题都是不可行的，则终止此问题的求解，寻找另外一个小数变量。重复以上步骤。分支界限法可以算是一种枚举法。
　　求解MILP问题还有其他的方法，如割平面法。这个方法的基础的是用解线性规划的方法去求解整数规划问题，首先不考虑变量是整数的条件，但增加线性约束条件将原可行域切割掉一部分，这部分只包含非整数解，没有切割任何整数可行解。这个方法就是指出怎样找到合适的割平面，使得切割后最终得到这样的可行域；它的一个有整数坐标的极点恰好是原问题的最优解。