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

线性规划问题的解法比较与分析【摘要】总结了线性规划问题数学模型各种解法的优势和局限性，结合具体实 例介绍一种适用性强，便于理解和记忆的新解法一新两阶段的解题思想和步骤， 并通过初等行变换对单纯形法进行了进一步的改进关键词：新两阶段法；换基迭代；单纯形法；初等行变换1.问题的提出线性规划问题的数学模型的一般表示形式为：22nn+ a x < (=, >)b + a x < (=, >)b2 n n 2+a x < (=, >)b mn n m,x > 0max(min)z = cx + c x + + c xa x + a x +1 1 1 1 2 2a x + a x +21 1 22 2 --a x + a x +m1 1 m2 2x「x2由于有的线性规划问题目标函数求“最大值”，有的求“最小值”；约束条件中数量约束部分 有的为“等式”约束，有的为“不等式”约束，故在解线性规划问题数学模型时，除图解法外， 通常先规定线性规划问题的标准形式，然后给出标准形式的解法在此我们规定，线性规划问题 数学模型的标准形式为：max z = c x + c x + + c x1122nna x+a x+ + a x=b11 112 2•・1n n1ax+a x+ +a x=b21 122 2-• - 2 n n2彳:. • ♦a x+a x+ + a x=bm1 1m2 2mn nmx , x,x >0、1 2,• • • n且：七 > 0(i = 1,2, m)2.新两阶段法 …以往，根据标准形式的不同形式的不同特点需要采用不同的解法。

常用方法有：单纯形方法, 大M法，两阶段法及对偶单纯形方法等等在吕为的《线性规划数学模型的一种新解法》【1】一文中，给出了适用性强，便于理解和记忆 的新解法一一新两阶段法，下面我们结合例题介绍其解题方法和步骤：例1：求解线性规划问题：max z = 4x - 2x + x '-8x + 2x + 2x > 82 x1 - x + x <3121 2 32 x — x — —3xj > 0( j — 1,2,3)1. 标准化新两阶段法标准化时必须引入m个松弛变量，若某约束条件在原始问题中为等式约束，引入 松弛变量的系数为0.因而标准形中共有n+m个决策变量例1标准化为：max z — 4 x — 2 x + x—8 x + 2 x + 2 x — x — 82 x — x + x + x =12St < 1 2 3 5—2 x + x + 0 x — 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-2010003000000继续迭代得表3,因其虚拟检验数均为0,即出现单位阵作为可行基，去掉最后一行，继 续换基迭代，得表4表4：0000.51011010-11011100-0.250.505001-0.51013表4所有检验数均大于等于0，所以为最优单纯性表，即例1的最优解为:x = 5, x = 11, x = 13最优值为：max z = 113. 对单纯形法的改进通常我们用单纯形法解决线性规划问题时，往往计算过程复杂易出错，于是我们通过对系 数增广矩阵的初等行变换来对单纯行法进行改进，以达到提高计算效率的目的我们通过一 个例题来讲述这个改进方法：例2：求解min z = -3x + x + xx - 2 x + x + x = 11-4 x + x + 2 x - x = 3st < 1 2 3 5-2 x1 + 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/341x 20100-111x0012/3-4/39bJ0001/31/3于是，得到最优解尤* = (4,1,9,0,0)『及最优值z* = —2而该例用书上的大M法进行了 3次迭代才得到最优解；用两阶段法进行了 2次迭代才完成了 第一阶段，然后进入了第二阶段，又进行了 1次迭代才求得最优解。

4. 各解法的优势和局限性通常，根据标准形式的不同形式的不同特点需要采用不同的解法教材中给出的方法有： 图解法，单纯形方法，大M法，两阶段法及对偶单纯形方法等等每种方法各有其优势和局限性 现对各方法的优缺点进行比较：i. 图解法：优点：简单直观，有助于了解线性规划问题求解的基本原理缺点：当变量数多于三个以上时无法求解ii. 单纯形法：优点：解法简单，易于掌握缺点：1.只适用于标准形约束方程组系数矩阵A中含有现成的m阶单位子阵为初始可行 基的情况，2. 计算步骤繁杂；iii. 对偶单纯形法：优点：解法简单，易于掌握缺点：只适用于一小部分无现成单位阵的情况；iv. 大M法优点：适用于所有的线性规划模型，缺点：1.需引用人工变量，使计算量大幅度增加，2. 使用大M法时事先无法确定M究竟多大才能保证人工变量出基，手算时工作量 大3. 上机计算时，选取过分大的M会使计算产生困难或误差；v. 两阶段法优点：适用于所有的线性规划模型，缺点：当第一阶段完成进入第二阶段时，需重新计算检验数才行，使计算量和计算难度 增加vi. 新两阶段法优点：1. 通用性强，适用于所以线性规划问题数学模型2. 克服了大M法中M无法确定，决策变量增加，检验数难于计算等弱点。

3. 两个阶段所用的换基迭代及判优的方法前后一致，连贯性强，便于理解，记忆和计4. 方法简单统一，适用于计算机编程缺点：计算过程还是比较繁杂，计算效率不是很高vii. 单纯形法的改进方法优点：1. 在于寻求初始可行基时，思路清晰，不需要引用人工变量，方法简明2. 借助于线性代数的初等行变换在进行主元选取时，通过改进入基变量的选取准 则明显提高了单纯行法的计算效率缺点：不易寻找对系数增广矩阵做保持可行性的初等行变换5. 参考文献【1】吕为，赵佳因，线性规划数学模型的一种新解法，北京市经济管理干部学院学报，2000,15（1）【2】申卯兴，许进，求解线性规划的单纯形法的直接方法，计算机工程与应用，2007,43（30）：【3】申卯兴，宁振民，郝彩丽，线性规划单纯形法的改进与教学，中国企业运筹学第三届学 术年会论文集，2008.4.26【4】李阳，熊令纯等，求解线性规划的一种单纯形矩阵法，数学的实践与认识，2003，43（17）【5】《运筹学》教材编写组，运筹学（第四版）［M］，北京，清华大学出版社，2005。