生产作业计划单纯形矩阵优化算法研究.docVIP

生产作业计划单纯形矩阵优化算法研究 　　 摘 要：利用单纯形矩阵进行生产作业计划的优化，可使运算过程更为简易和高效。单纯形矩阵优化算法的关键是在建模后，编制出初始单纯形矩阵。对单纯形矩阵的换基迭代，变成了简单的矩阵初等变换运算，提高了运算速度和效率。算例的计算过程表明，单纯形矩阵优化算法是生产作业计划的一种很好的简易算法。 　　 关键词：生产作业计划；单纯形矩阵；优化算法；基变量 　　 中图分类号：F22 文献标志码：A 文章编号：1673-291X（2012）09-0191-02 　　 　　 引言 　　 在生产作业计划中，图解法是寻求最优解的一种有效方法。不过，对于三种以上产品的生产作业计划问题，图解法无能为力。这时，通常采用单纯形法确定最优解。单纯形法是从一个基本可行解出发，经过有限次的换基运算，逐渐改善直至获得最优的目标函数值或判明问题无解为止。利用单纯形法进行生产作业计划十分高效。然而，单纯形法多采用表格形式进行运算，求解过程较为烦琐。其实，利用单纯形矩阵进行生产作业计划的优化，运算过程更为简易。本文试图通过一个算例，说明生产作业计划的单纯形矩阵优化算法的原理和过程。 　　 一、生产作业计划建模 　　 1.数据来源。调查一家机械制造企业，获取生产作业计划数据。该企业使用A、B两种设备，生产甲、乙、丙三种产品，生产每件产品需要的设备台时、设备有效台时及单位产品产值（如表1所示）。 　　表1 生产作业计划的基本数据 　　 2.建模。现要安排生产作业计划，设法充分发挥设备生产能力，使企业获得最大的产品总产值。假定甲、乙、丙的产量分别为x1、x2、x3，利润为z。生产作业计划的线性规划模型为： 　　 maxz=3x1+2x2+x3 　　 s.t.z-3x1-2x2-x3=0x1+2x2+x3≤4002x1+x2+2x3≤500x1，x2，x3≥0 　　 加入松驰变量，将生产作业计划线性规划模型化为标准形， 　　 maxz=3x1+2x2+x3 　　 s.t.z-3x1-2x2-x3-0·x4-0·x5=0 （0）x1+2x2+x3+x4+0·x5=400 （1）2x1+x2+2x3+0·x4+x5=500 （2）x1，x2，x3，x4，x5≥0 （3） 　　 二、初始单纯形矩阵的构建 　　 1.初始单纯形矩阵的写法。依据标准形，按照约束方程（1）、（2）和目标方程（0）中变量系数和??数项的顺序，写出初始单纯形矩阵： 　　 x1 x2 x3 x4 x5 bix4 1 2 1 1 0 400x5 2 1 2 0 1 500σj -3 -2 -1 0 0 0 　　 2.初始单纯形矩阵的结构。初始单纯形矩阵的一般形式为： 　　 （4） 　　 矩阵（4）包括4个分块矩阵。 　　 左上角的分块矩阵为标准形的变量系数，x1，x2，…，xm为基变量。 　　 右上角的bi为基解，即基变量的取值。 　　 右下角的z0为目标函数值，初始单纯形矩阵的目标函数值为0，z0的计算方法为： 　　 z0=cTBb （5） 　　 其中，cB为目标函数的价值系数cj构成的列向量，b为基解构成的列向量。 　　 左下角为检验数σj，基变量的检验数为0。检验数是检验当前的基本可行解是否最优的一个标志。在单纯形矩阵中，只要存在负检验数，就意味着目标值还能增加，就需要把它所对应的非基变量变为基变量。因此，检验数成为是否进行换基迭代的决策依据。检验数的计算方法为： 　　 σj=cTBaj-cj，j=1，2，…，n （6） 　　 其中，aj为变量xj的系数列向量。 　　 三、单纯形矩阵的换基迭代 　　 1.确定进基变量、出基变量和主元。在初始单纯形矩阵中，由于minσj=min（-3，-2，-1，0，0）=-3，根据最小检验数规则，确定x1为进基变量，x1列为主列。 　　 由于minmin（，）=250，根据最小比值规则，确定x5为出基变量，即x1取代 x5为新的基变量，基变量仍为2个。 　　 处于进基变量所在列和出基变量所在行的元素2为主元。标记后的初始单纯形矩阵为： 　　 2.通过初等变换进行换基迭代。进行初等变换，将初始单纯形矩阵中的主元2化为1，主列其余元素化为0，实现换基迭代。进行初等变换时，要对检验数行、基解列和目标函数值一并处理。此时，x1、x4成为新的基变量组合，目标函数值由0增大到750。调换进基变量和出基主量，写出一次改进的单纯形矩阵： 　　 x1 x2 x3 x4 x5 bix4 1 1.5 0 1 0.5 150x1 2 0.5 1 0 0.5 250σj 0 -0.5 2 0 1.5 750 　　 3.检查检验数确定最优解。检查检验数，若σj≥0，则停止运算，得到最优解。否则