单纯形法在线性规划中的应用

1、单纯形法在线性规划中的应用。1 / 9最大增加原则、换出变量的确定- 最小比值原则、表格单纯形法、大关键词：线性规划图解法单纯形法 基变量 基向量单纯形法在线性规划中的应用摘要求解线性规划问题， 就是在各项资源条件的限制下， 如何确定方 案，使预期的目标达到最优。 本文重点介绍了求解线性规划问题目前 最常见的两种方法， 图解法和单纯形法。 图解法适合于只含两个变量 的线性规划问题， 文中只做了简单的描述。 而单纯形法是求解线性规 划问题的通用方法， 适合于求解大规模的线性规划问题， 本文作了重 点描述，对单纯形法中的基本概念如基变量、非基变量、基向量、非 基向量、可行基以及基本可行解等概念作了

2、详细的陈述， 在此基础上， 介绍了线性规划问题的标准化、 单纯形法的基本原理、 确定初始可行解、最优性检验、解的判别、基本可行解的改进、换入变量的确定M法、两阶段法等。可行基 基本可行解单纯形法在线性规划中的应用。2 / 9正文引言在生产管理和经济活动中， 经常遇到这些问题， 如生产计划问题， 即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题， 即如何用最少的劳动力来满足工作的需要； 运输问题， 即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等

3、。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。解线性规划问题目前最常见的方法有两种， 图解法和单纯形法。 单纯形法是求解线性规划问题的通用方法。1 线性规划问题的求解方法1.1 图解法解线性规划问题只含两个变量的线性规划问题， 可以通过在平面上作图的方法求解， 步骤如下：(1)以变量 x1 为横坐标轴， x2 为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。(2)图示约束条件，找出可行域（所有约束条件共同构成的图形）(3)画出目标函数等值线，并确定函数增

4、大（或减小）的方向。（4）然而，图解法虽然直观、简便，但当变量数多于三个以上时，其实用意义不可行域中使目标函数达到最优的点即为最优解。大。单纯形法在线性规划中的应用。3 / 9单纯形法在线性规划中的应用。4 / 91.2 单纯形法解线性规划问题它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集, 其最优值如果存在必在该凸集的某顶点处达到。 顶点所对应的可行解称为基本可 行解。单纯形法的基本思想是： 先找出一个基本可行解, 对它进行鉴别, 看是否是 最优解；若不是，则按照一定法则转换到另一改进的基本可行解 , 再鉴别；若仍 不是,则再转换 , 按此重复进行。因基本可行解的个数有限

5、,故经有限次转换必 能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下： 把线性规划问题的约束方程组表达 成典范型方程组,找出基本可行解作为初始基本可行解。 若基本可行解不存在, 即约束条件有矛盾, 则问题无解。 若基本可行解存在, 从初始基本可行解作为 起点，根据最优性条件和可行性条件， 引入非基变量取代某一基变量， 找出目标 函数值更优的另一基本可行解。按步骤 3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中 发现问题的目标函数值无界,则终止迭代。1.3 线性规划问题的标准化使用单纯形法求解线性规划时，

6、首先要化问题为标准形式所谓标准形式是指下列形式：nmax zc j xjj1naij x jbi (i 1, ,m)s t j 1 xj 0 ( j 1,2, ,n)当实际模型非标准形式时，可以通过以下变换化为标准形式：n当目标函数为min zCjXj时，可令Z =-Z，而将其写成为j1nmin zCj X jj1单纯形法在线性规划中的应用。5 / 9当s t 中存在ai1x1ai2 x2ain xn bi 形式的约束条件时， 可引进变xn 1xn 1bi (ai1x1 ai2 x20ain xn)ai1x1ai2 x2xn 1 0ain xnxn 1bi其中的 xn+1 称为松驰变量，其作用

7、是化不等式约束为等式约束。同理，若该约束不是用“W”号连接，而是用连接，贝U可引进松驰变xn 1xn 1(ai1 x1 ai2 x20ain xn) biai1x1ain xnxn 1xn 1 0bi求得最终解时，再求逆变换 z=-z即可。便写原条件成为使原条件写成单纯形法2.1 单纯形法的基本原理单纯形法迭代原理：1) 确定初始可行解当线性规划问题的所有约束条件均为W号时，松弛变量对应的系数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。 对约束条件含号或=号时，可构造人工基，人为产生一个 m m单位矩阵用大M法或两阶段法获得初始基可行解。2) 最优性检验与解的判别(目标函数极大型) 当

8、所有变量对应的检验数均非正时， 现有的基可行解即为最优解。单纯形法在线性规划中的应用。6 / 9若存在某个非基变量的检验数为零时，线性规划问题有无穷多最单纯形法在线性规划中的应用。7 / 9xm+2 xn的系数列向=BXB+NXN=b若令所有非基变量XN=0 ,则基变量X B =B b由此可得初始的基本可行解X=B 1b0假如已求得一个基本可行解X=B 1b0，将这一基本可行解代入目标函数,其中 CB=(Cl ,C2,|Cm ), C N =(Cm+1 ,Cm+2 ,Cn )分别表示基变量和非基变量所对优解；当所有非基变量的检验数均严格小于零时，线性规划问题 具有唯一最优解。 若存在某个非基变

9、量的检验数大于零，而该非基变量对应的系数均非正，则该线性规划问题具有无界解(无最优解)当存在某些非基变量的检验数大于零， 需要找一个新的基可行解,基要进行基变换。2.1确定初始可行解确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定， 为了讨论方便，不妨假设在标准 型线性规划中，系数矩阵A中前m个系数列向量恰好构成一个可行基，即A =(BN)，其中B=(P 1，P 2,P m为基变量x1, x2，xm的系数列向量构成的可行基，N =( P m+1 Pm+2 Pn)为非基变量xm+1量构成的矩阵。X所以约束方程AX=b就可以表示为AX=(BN

10、) BX N用可行基B的逆阵B -1左乘等式两端，再通过移项可推得：XB二B-1b-B-1NXN2.2最优性检验B 1 b可求得相应的目标函数值Z=CX=(CBCN) B b =CBB1b0应的价值系数子向量。单纯形法在线性规划中的应用。8 / 9其中 N=CN-CBB N=(m+1 , m+1 ,n）称为非基变量X N的检验向量，它的各m+k0，但是 B-1Pm+k0，要判定Z=CBB-1b是否已经达到最大值，只需将 XB二B-1b-B-1NXN代入目标函数，使目标函数用非基变量表示，即:XBZ=CX=(CBCN) 乂X N=CBXB+CNXN=CB (B-1 b-B-1 NXN)+CNXN

11、Xm+1A -1-1X m+2_CBB b+ ONX N CBB b+( om+1, om+1on)* * * Xn个分量称为检验数。若C N的每一个检验数均小于等于 0,即C N0，则选 其中的c j最大者的非基变量为入基变量。从最优解判别定理知道，当某个c j 0时，非基变量Xj变为基变量不取零 值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中 去（称之为入基变量）。若有两个以上的c j 0,则为了使目标函数增加得更大 些，一般选其中的c j最大者的非基变量为入基变量。2.4.2换出变量的确定-最小比值原则把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中

12、的 常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。即若则应令Xl出基。其中bi是目前解的基变量取值，aik是进基变量Xk所在 列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik 0,则 对应的Xi不会因xk的增加减值而成为出基变量）。2.5表格单纯形法在单纯形法的求解过程中，有下列重要指标:单纯形法在线性规划中的应用。11 / 9(1)每一个基本可行解的检验向量ON二CN-CBB-1N，根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合 适的换入变量。(2)每一个基本可行解所对应的目标函数值Z=CBB 1b，通过目标函

13、数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目 标函数为止。在单纯形法求解过程中，每一个基本可行解X都以某个经过初等行变换的约 束方程组中的单位矩阵I为可行基。当B =1时，B -1= I,易知：（TN=CN-CBN，Z=CBb可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成:CCBCNCBXBbX X 2X mXm+IX m+2X n0CIXibi01C2X2b2IN0 2CmXmbm0 mZCBb0C-CBN2.6大M法大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位 矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边

14、加上若干个 非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构 成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基 变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-M。这样只要基变量中还存在人工变量，目标函数就不可能实现 极大化。以后的计算与单纯形表解法相同，M只需认定是一个很大的正数即可。假如 在单纯形最优表的基变量中还包含人工变量， 则说明原问题无可行解。 否则最优 解中剔除人工变量的剩余部分即为原问题的初始基本可行解。2.7 两阶段法用大M法求解含人工变量的LP时，用手工计算不会碰到麻烦，但用电子计 单纯形法在线性规划中的应用。12 / 9算机求解时，对M就只能在计算机内输入一个机器最大字长的数字， 这就可能造成一种计算上的误差，为克服这个困难，对添加人工变量后的LP分两个阶段