线性规划问题的解法比较与分析

线性规划问题的解法比较与分析【摘要】总结了线性规划问题数学模型各种解法的优势和局限性，结合具体实例介绍一种适用性强，便于理解和记忆的新解法一新两阶段的解题思想和步骤，并通过初等行变换对单纯形法进行了进一步的改进。关键词：新两阶段法；换基迭代；单纯形法；初等行变换1.问题的提出线性规划问题的数学模型的一般表示形式为：22nn+ax<(=,>)b+ax<(=,>)b2nn2+ax<(=,>)bmnnm,x>0max(min)z=cx+cx++cxax+ax+111122ax+ax+211222--ax+22nn+ax<(=,>)b+ax<(=,>)b2nn2+ax<(=,>)bmnnm,x>0由于有的线性规划问题目标函数求“最大值”，有的求“最小值”；约束条件中数量约束部分有的为“等式”约束，有的为“不等式”约束，故在解线性规划问题数学模型时，除图解法外，通常先规定线性规划问题的标准形式，然后给出标准形式的解法。在此我们规定，线性规划问题数学模型的标准形式为：maxz=cx+cx++cx1122nnax+ax++ax=b111122•・1nn1ax+ax++ax=b211222-•-2nn2彳:.•♦ax+ax++ax=bm11m22mnnmx,x,x>0、12,•••n且：七>0(i=1,2,m)2.新两阶段法…以往，根据标准形式的不同形式的不同特点需要采用不同的解法。常用方法有：单纯形方法,大M法，两阶段法及对偶单纯形方法等等。在吕为的《线性规划数学模型的一种新解法》【1】一文中，给出了适用性强，便于理解和记忆的新解法一一新两阶段法，下面我们结合例题介绍其解题方法和步骤：例1：求解线性规划问题：maxz=4x-2x+x'-8x+2x+2x>82x1-x+x<31223x—x——3xj>0(j—1,2,3)标准化新两阶段法标准化时必须引入m个松弛变量，若某约束条件在原始问题中为等式约束，引入松弛变量的系数为0.因而标准形中共有n+m个决策变量。例1标准化为：maxz—4x—2x+x—8x+2x+2x—x—82x—x+x+x=12St<1235—2x+x+0x—3x>0(j—1,2,6,6)j显然标准形中无现成单位阵作初始可行基，可以采用大M法或两阶段法先找出第一个单位阵作可行基，而用新两阶段法相对简单一些。2.列表表1：-42-10000-822-10082-1101012-20[1]000310-2-3100其中第一行为标准形式目标函数中各决策变量系数的相反数和常数，最后一行为虚拟检验数行，即是松弛变量系数不等于1的各约束条件决策变量系数不等于1的各约束条件决策变量系数的相反数之和。表2：-6200003-4[2]0-10024-100109-20100034-20100若表1得到的虚拟检验数行所有元素均为0，说明松弛变量系数恰为单位阵，可取其作初始可行基；若有非0元素，需进行换基迭代；若无负虚拟检验数，且不全为0，说明该线性规划问题无可行解。取表1虚拟检验数行最小者-3<0，根据单纯形法选取主元，换基迭代的表2，表3：-2001001-210-0.5001[2]00-0.51010-2010003

000000继续迭代得表3,因其虚拟检验数均为0,即出现单位阵作为可行基，去掉最后一行，继续换基迭代，得表4。表4：0000.51011010-11011100-0.250.505001-0.51013表4所有检验数均大于等于0，所以为最优单纯性表，即例1的最优解为:x=5,x=11,x=13最优值为：maxz=11对单纯形法的改进通常我们用单纯形法解决线性规划问题时，往往计算过程复杂易出错，于是我们通过对系数增广矩阵的初等行变换来对单纯行法进行改进，以达到提高计算效率的目的。我们通过一个例题来讲述这个改进方法：例2：求解minz=-3x+x+xx-2x+x+x=11-4x+x+2x-x=3st<1235-2x1+x3=1、x>0(i=1,2,,5)首先，对系数增广矩阵做保持可行性的初等行变换：「1-21101「「3-201010-「3001-212--4120-130100-110100-11-201001-201001-201001然后，安排初始单纯形表如下:cj-31100bcXxxxxx0x[3]001-2121x0100-111x-201001bj-10001-3x1001/3-2/341x20100-111x0012/3-4/39bJ0001/31/3于是，得到最优解尤*=(4,1,9,0,0)『及最优值z*=—2而该例用书上的大M法进行了3次迭代才得到最优解；用两阶段法进行了2次迭代才完成了第一阶段，然后进入了第二阶段，又进行了1次迭代才求得最优解。各解法的优势和局限性通常，根据标准形式的不同形式的不同特点需要采用不同的解法。教材中给出的方法有：图解法，单纯形方法，大M法，两阶段法及对偶单纯形方法等等。每种方法各有其优势和局限性。现对各方法的优缺点进行比较：图解法：优点：简单直观，有助于了解线性规划问题求解的基本原理缺点：当变量数多于三个以上时无法求解单纯形法：优点：解法简单，易于掌握缺点：1.只适用于标准形约束方程组系数矩阵A中含有现成的m阶单位子阵为初始可行基的情况，计算步骤繁杂；对偶单纯形法：优点：解法简单，易于掌握缺点：只适用于一小部分无现成单位阵的情况；大M法优点：适用于所有的线性规划模型，缺点：1.需引用人工变量，使计算量大幅度增加，使用大M法时事先无法确定M究竟多大才能保证人工变量出基，手算时工作量大上机计算时，选取过分大的M会使计算产生困难或误差；两阶段法优点：适用于所有的线性规划模型，缺点：当第一阶段完成进入第二阶段时，需重新计算检验数才行，使计算量和计算难度增加。新两阶段法优点：通用性强，适用于所以线性规划问题数学模型。克服了大M法中M无法确定，决策变量增加，检验数难于计算等弱点。两个阶段所用的换基迭代及判优的方法前后一致，连贯性强，便于理解，记忆和计方法简单统一，适用于计算机编程。缺点：计算过程还是比较繁杂，计算效率不是很高。单纯形法的改进方法优点：在于寻求初始可行基时，思路清晰，不需要引用人工变量，方法简明。借助于线性代数的初等行变换。在进行主元选取时，通过改进入基变量的选取准则明显提高了单纯行法的计算效率。缺点：不易寻找对系数增广矩阵做保持可行性的初等行变换参考文献【1】吕为，赵佳因，线性规划数学模型的一种新解法，北京市经济管理干部学院学报，2000,15（1）【2】申卯兴，许进，求解线性规划的单纯形法的直接方法，计算机工程与应用，2007,43（30）：【