基于单纯形法的线性规划模型研究

基于单纯形法的线性规划模型研究

线性平面问题是在一定的约束条件下计算目标函数的最佳（最大或最小）值的问题。求解线性规划问题有图解法,单纯形法,椭球法及投影尺度法。其中以单纯性法最常用,应用范围也更广泛。一、可行解和实际效果函数的确定单纯形法是从一个初始解开始,不断地改进现有的解,直到所要求的目标函数值被满足为止。即是进行反复的迭代,直到得到需要的最优解。这即是单纯形法的基本思想。它的主要步骤我们通过一个例子说明。例1:解线性规划问题:x2≤3解:(1)先将线性规划问题化为标准形式。须在约束方程中加入松弛变量x2,x3,x4,得到标准形式如下(2)选择一个初始可行解。由约束方程组的系数矩阵,选择x3,x4,x5为基变量,x1,x2为非基变量。将基变量由非基变量表示,同时令非基变量x1,x2为0,便得到一个基本可行解(0,0,4,3,8)T,此时目标函数值为z=0(3)检验是否是最有解。检验的方法是非基变量在目标函数中的系数是否有正值。本例求出的基本可行解(0,0,4,3,8)不是最优解。因为从目标函数表达式2x1+5x2中可以看出,当可行解中非基变量x1=x2=0,目标函数值为0,但只要x1或x2之一取正值,则目标函数值应增加,所以它不是最优解。从一般情况而言,当目标函数表达式中还存在正系数的非基变量时,就表示目标函数值还有可能增加,此时将非基变量与基变量进行对换,就可以使目标函数值继续增加。对于本例,就是将x3,x4或x5之一置成0,而x1或x2之一的值可以取为大于0,目标函数值不再是0,而是大于0。欲置0的基变量被称为离基变量。而允许目标函数中系数大于0非基变量被称为进基变量。那么如何选择进基与离基变量呢?(4)进基变量的选择。进基变量的选择方法是取非基变量在目标函数的正系数中的最大的数所对应的变量为进基变量。在目标函数方程中选取正系数最大的非基变量作为进基变量。非基变量的正系数意味着相应变量的增加,这种增加将使目标值增大,所以只有使具有正系数的非基变量进基才有可能使目标函数值得到改善。在本例中目标函数方程中x2的系数具有最大值5,因此,x2将进入下一个基本可行解的基。(5)离基变量的选择。离基变量的选择的原则是,求出每一个约束方程中的右端常数与进基变量在约束方程中的系数的比值,最小非负比值所在方程中的基变量应是离基变量。本例中考虑每一个约束方程右边的常数与该方程中进基变量x2的系数的比值,找出最小非负比值,把这个方程中的基作为离基变量。本例记其中“-”表示进基变量约束条件的系数为0或为负数。下面求以x2,x3,x4为进基变量时的基本可行解。(6)转轴计算。先选主元,令进基变量所在列为主元列,离基变量所在的行为主元行,主元行与主元列交叉位置的元素为主元。然后用高斯消元法进行消元运算,即将主元位置的数变为1,主元列中其余元素变为0。本例中x2进基,x4离基,所以第2行为主元行,第2列为主元列,其主元为第2列与第2行交叉的元素,将该位置的数变为1,该列的其余系数变为0。即可得到从而得到目标函数z=2x1-5x4+15。(7)确定新的基本可行解。由上一步得到的等价约束条件方程组和等价的目标函数式,可得到本例另一基本可行解(0,3,4,0,2)T。此时得到目标函数值z=15。(8)求出最优解。经过这一系列运算,我们从一个基本可行解(0,0,4,3,8)T达到另一基本可行解,目标函数值也从0增加到15。因此第二个基本可行解是改进的基本可行解。下面再从基本可行解(0,3,4,0,2)T出发,寻找最优解。仍须重复(4)——(7)的步骤,直至找到最优解:目标函数值z=19。以上就是单纯形法的基本思路及运算过程。这些运算可简写成矩阵,行列式的形式,这便是下面要介绍的求解一般线性规划问题的单纯形法。二、一般单纯度法的原理1、约束方程的增广矩阵的确定(1)先找出一个初始可行解。(2)进行最优性检验。就是尽兴迭代运算,首先应建立一个判别准则。如最优解判别定理:若x(0)=(b1′,b2′,bm′,0,…,0)T为对应于基矩阵B的基本可行解,且对于一切j=m+1,m+2,…,n,有σ≤0,则x(0)为最优解(3)进基变量(主元列)的确定。为使目标函数值增加得快,一般选σj大于0的非基变量中的最大者为进基变量。即σk=max[σjσj≥0],所对应的xk为进基变量。(4)离基变量(主元行)的确定。按最小比值原则或θ原则取约束方程组的右端项和进基变量的对应约束条件的比值的最小值所在行的基变量x1作为离基变量。(5)转轴计算。假设约束方程组有x1,x2,…,xm个基变量,其系数列向量构成一个m阶单位矩阵是可行基,令非基变量xm+1,…,xk,…,xn为零,便可得一个基本可行解。若它不是最优解,则要找另一个基本可行解。即可假定xk为进基变量,x1为离基变量,对主元αlk作转轴运算,即以αlk为主元的增广矩阵作Gauss-Jordan消元法。(6)重复上述过程,直至找到最优解。三、基变量对应关系对于标准的线性规划问题,用单纯形表方法求解最优解一般分为两个步骤:1、找出基变量,确定初始基本可行解,列初始的单纯形表。2、从初始单纯形表开始,逐步求出最优解。(1)基变量对应的列经过适当的位置变换后能变成一个单位矩阵。(2)在检验数这一行中,对应的基变量的检验数要全为0。(3)表格中常数b这一列(除去最后一行)的元素应全为非负数。如果上述3个条件都被满足,则所得到的表格就是问题的初始单纯形表。以下通过例1说明单纯形法求解最优解。(方法同三中所述各步)解:(1)列初始单纯形表(2)利用单纯形表求最优解:列第二张单纯形表从上表中可看到,得到一组新的基本可行解x(2)=(2,3,2,0,2)T,此时z=19。在最后的检验数行中已无正值,说明已求出最优解。四、关于单纯度法的进一步讨论1、线性规划的最优解只有当矩阵A中存在单位矩阵或约束条件为Ax≤b时,加上松驰变量生成单位矩阵,即Ax+Ixs=b。如果约束条件非上述两种情况,又将如何处理呢?有两种方法处理:一——大法;二——两阶段法。所谓大M法,就是在确定离基变量时,即如何是基变量xa=0,就是采用惩罚的方法:在xa的前面乘上一个很大的数M,一旦xa的某个分量大于0,目标函数值就会下降。这样就得到一个与M有关的问题,简记为P(M),即记原线性规划问题为P,相应的大M问题为P(M)。设x=0,xa=b是P(M)的一个基本可行解,从基本可行解出发,对P(M)求解,分以下情况进行讨论。(1)P(M)有最优解,其解为(x*,xa*,且xa*=0,则x*是P的最优解。若x是p的可行解,则(x,0)是P(M)的可行解,因此有cTx-0≤cTx*-0,所以x*是P的最优解。(2)P(M)有最优解,其解为(x*,xa*),且xa*≠0(某些分量大于0),则p无可行解。若p存在可行解x,则(x.0)是P(M)的可行解,则有cTx*-MeTxa*≥cTx,这与M可以充分大矛盾。(3)P(M)无有限最优解。若存在并且σk>0,B-1Pk≤0,并且人工变量xa*≠0,则P无有限最优解。(4)P(M)无有限最优解。若存在σk>0,B-1Pk≤0并且人工变量xa*≠0(某些分量大于0),则P无可行解。下面以(2)为例,说明大M法的迭代过程。例2:用大M法求解线性规划问题列出单纯形表,并进行迭代,具体迭代过程如下表所示:从表中的检验数可看出:检验数已符合最优解的要求,得到唯一最优解x=(0,2,0,0,4)T,最优解为4-4M。但现在的最优解包含人工变量,说明该解对于原问题而言是不可行的。因此原问题无解。2、两阶段法算法用大M法手工计算时很实用。但用计算机求解时,对M就要附一个机器最大字长的数,因此在迭代过程中很容易溢出。有可能使计算结果产生错误。为了解决这个问题,可以对增加人工变量后的规划问题分两个阶段来计算,称为两阶段法。下面通过例子来说明两阶段法的算法。例3:解线性规划问题解:第一阶段要增加新的人工变量x6,x7,x8,所得辅助问题为由原问题及辅助问题作单纯形表:将表中第一行,第二行,第三行加到关于g的检验行中,使基变量的x6,x7,x8检验数为0,得到辅助问题的第一张单纯形表:按单纯形法迭代,得关于目标函数g的检验数都是负数,所以辅助线性规划问题的最优解是其最优解,所以原问题无解。从迭代过程可以发现,无论是大M法还是两阶段法,目的都是尽快地使人工变量离基,从而得到原问题的初始基本可行解,再由此进行迭代,得到原问题的最优解。五、线性规划问题的算法需要改良单纯形法是解线性规划问题的一种有效的方法,它需要一个已知的基本可行解,并需把原始线性规划问题化为标准式,而在一般情况下线性规划问题并无明显的基本可行解,则需增加人工变量以获得基本可行解,这样可能增加计算量,因而需要改进算法;同时,实际生活中的线性规划问题规模较大,即变量个数和约束条件都多,当用计算机进行计算时会占据大量的内存空间,在迭代过程中,实际上有很多计算是多余的,当迭代次数增多时,累计误差就会增加,进而会影响计算精度。针对这一问题,算法也需改进。因此,单纯形法解线性规划问题的算法仍需更进一步的探究与改良,这将对解决线性规划问题非常有意义。其中,