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

《线性规划问题的解法比较与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划问题的解法比较与分析【摘要】总结了线性规划问题数学模型各种解法的优势和局限性，结合具体实例介绍一种适用性强，便于理解和记忆的新解法—新两阶段的解题思想和步骤，并通过初等行变换对单纯形法进行了进一步的改进。关键词：新两阶段法；换基迭代；单纯形法；初等行变换1.问题的提出线性规划问题的数学模型的一般表示形式为：由于有的线性规划问题目标函数求“最大值”，有的求“最小值”；约束条件中数量约束部分有的为“等式”约束，有的为“不等式”约束，故在解线性规划问题数学模型时，除图解法外，通常先规定线性规划问题的标准形式，然后给出标准形式的解

2、法。在此我们规定，线性规划问题数学模型的标准形式为：且：2.新两阶段法以往，根据标准形式的不同形式的不同特点需要采用不同的解法。常用方法有：单纯形方法,大M法，两阶段法及对偶单纯形方法等等。在吕为的《线性规划数学模型的一种新解法》【1】一文中，给出了适用性强，便于理解和记忆的新解法——新两阶段法，下面我们结合例题介绍其解题方法和步骤：例1：求解线性规划问题：51.标准化新两阶段法标准化时必须引入m个松弛变量，若某约束条件在原始问题中为等式约束，引入松弛变量的系数为0.因而标准形中共有n+m个决策变量。例1标准化为：显然标准形中无现

3、成单位阵作初始可行基，可以采用大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，说明松弛变量系数恰为

4、单位阵，可取其作初始可行基；若有非0元素，需进行换基迭代；若无负虚拟检验数，且不全为0，说明该线性规划问题无可行解。取表1虚拟检验数行最小者-3<0，根据单纯形法选取主元，换基迭代的表2，表3：-2001001-210-0.5001[2]00-0.51010-20100035000000继续迭代得表3，因其虚拟检验数均为0，即出现单位阵作为可行基，去掉最后一行，继续换基迭代，得表4。表4：0000.51011010-11011100-0.250.505001-0.51013表4所有检验数均大于等于0，所以为最优单纯性表，即例1的最

5、优解为：最优值为：3.对单纯形法的改进通常我们用单纯形法解决线性规划问题时，往往计算过程复杂易出错，于是我们通过对系数增广矩阵的初等行变换来对单纯行法进行改进，以达到提高计算效率的目的。我们通过一个例题来讲述这个改进方法：例2：求解首先，对系数增广矩阵做保持可行性的初等行变换：然后，安排初始单纯形表如下：-31100b0[3]001-21210100-111-201001-100015-31001/3-2/3410100-1110012/3-4/390001/31/3于是，得到最优解及最优值而该例用书上的大M法进行了3次迭代才得到

6、最优解；用两阶段法进行了2次迭代才完成了第一阶段，然后进入了第二阶段，又进行了1次迭代才求得最优解。4.各解法的优势和局限性通常，根据标准形式的不同形式的不同特点需要采用不同的解法。教材中给出的方法有：图解法，单纯形方法,大M法，两阶段法及对偶单纯形方法等等。每种方法各有其优势和局限性。现对各方法的优缺点进行比较：i.图解法：优点：简单直观，有助于了解线性规划问题求解的基本原理缺点：当变量数多于三个以上时无法求解ii.单纯形法：优点：解法简单，易于掌握缺点：1.只适用于标准形约束方程组系数矩阵A中含有现成的m阶单位子阵为初始可行基

7、的情况，2.计算步骤繁杂；iii.对偶单纯形法：优点：解法简单，易于掌握缺点：只适用于一小部分无现成单位阵的情况；iv.大M法优点：适用于所有的线性规划模型，缺点：1.需引用人工变量，使计算量大幅度增加，2.使用大M法时事先无法确定M究竟多大才能保证人工变量出基，手算时工作量大3.上机计算时，选取过分大的M会使计算产生困难或误差；v.两阶段法优点：适用于所有的线性规划模型，缺点：当第一阶段完成进入第二阶段时，需重新计算检验数才行，使计算量和计算难度增加。vi.新两阶段法优点：1.通用性强，适用于所以线性规划问题数学模型。2.克服了

8、大M法中M无法确定，决策变量增加，检验数难于计算等弱点。3.两个阶段所用的换基迭代及判优的方法前后一致，连贯性强，便于理解，记忆和计算。51.方法简单统一，适用于计算机编程。缺点：计算过程还是比较繁杂，计算效率不是很高。i.单纯形法的改进方法优点：