单纯形算法.ppt

,,信息系刘康泽,单纯形算法,,单纯形算法是1947年由丹齐克（G．B．Dantzig）等建立的一种解决线性规划问题的种最有效的方法，它解决了在诸多的基可行解之中迅速地求出最优解的方法。,单纯形方法的基本思路是在线性规划问题数学模型的标准型基础上，从可行解集中先求出一个基可行解，并用一种检验的方法断判这个解是否为最优解。如果是最优解，则到此结束；若不是最优解，则在该解的基础之上去求出另一个使得目标函数变得更小的基可行解；若还不是最优解，就再去求下一个使得目标函数进一步改善的基可行解。依此下去，一步步地走向最优解。,换句话说，单纯形方法是从可行解集的某一个顶点出发，迭代到另一个顶点，并使目标函数值逐步减小，直到使目标函数值达到最小为止。,一、基本思路,由于基可行解实际上是将非基变量令为零的解，因此我们可以首先将基变量通过代换而由非基变量表达出来，这样就极易得到关于某个基阵的基可行解。,二、基变量的非基变量表示,例设,此模型不易看出一个明显的基与基解以及基解对应的目标值。,将非基变量令为零x1x2x30，极易得到关于这个基的基可行解x0，0，0，8，6，1T,上述模型经过变形可以变成如下形式,此模型就有一个明显的基{x4,x5,x6}，,同时得到目标函数f在这个基的取值－3。,一般地，设LP问题,记,由于,即,故,这就是用非基变量来表示基变量的矩阵表达式。,（1）约束条件中基变量的非基变量表示,其中,于是令所有的非基变量等于0，立即得到关于基B的基解,即,由于,而,即,（2）目标函数的非基变量表示,就是目标函数的非基变量表示。,记,则,的第k个分量，,令所有的非基变量等于0，立即得到关于基B的目标值,例,则得到一个基可行解,相应的目标函数值为,称,为LP问题关于基的典式。,【注1】有时将典式中的目标函数写成下述形式更为方便。,其目的是为了将目标函数也理解成一个与约束条件同形式的方程，而在使用初等变换时一次性的将约束条件与目标函数中的基变量同时用非基变量表示出来，从而快速得到基解与目标值。,或写成,（3）典式,【注2】用初等行变换化典式不影响线性方程的同解性，而单纯形方法正是利用同解性这个特点，在典式之间通过初等行变换进行转换，对每个典式进行最优性判别，若不是最优解，则继续化成另一个典式。,注意到一个基对应一个典式，而基的个数有限，从而通过有限次典式之间的转换，便可得到问题的最优解，或判定问题无解。,例,此问题明显有一个关于基{x4,x5,x6}的基解,x0，0，0，8，6，1T,显然当且仅当x1x2x30时,目标函数f取到最小值9，因此这个基解就是问题的最优解.,三、最优性判别,将目标函数改写为f－3x1－2x2－5x39,再将它与约束条件联立,并写出系数矩阵用表格形式写出,,,常称首行的中间部分为检验数，首行右上方的数为目标值，,检验数,,,目标值,基变量,,因此若检验数都小于或等于0,则对应的基解为最优解.,基解,,或,一般地设LP问题,典式,,由于,即,其中λk是目标函数中非基变量前的系数的相反数，称为检验数。,【注4】基变量的检验数一定等于0。,这是因为,对应基变量,对应非基变量,我们可将基阵B对应的典式的有关数据列成一张表，,设,更一般地有,称此表为对应基B的单纯形表。,四、单纯形表,基变量的检验数,非基变量的检验数,目标值,基变量对应的单位列向量,基变量,0,0,1,0,,基解,非基变量对应的列向量,,1o基变量对应的检验数；,2o基变量对应的列构成一个单位阵I;,3o是在非基变量取0时的目标函数值。,4o是在非基变量取0时基变量的取值（基可行解）。,【注】单纯形表的特点,例,基可行解,相应的目标函数值为,相应地单纯形表为,1,,,对应的单纯形表为,由于检验数都小于0，,,,则此表已是最优表，相应基解为最优解。,,例,此问题已是典式，单纯形表如下,由于检验数λ2＝2＞0，此表不是最优表，,注意到P2≤0，,,,,,五、无最优解的判定,若令x2a＞0，仍取x10，x30，则有,而,因此LP问题无下界.不存在最优解.,这说明在单纯形表中,只要某个检验数＞0,且该检验数下方的系数列向量≤0,则问题无下界.,检验数＞0,对应系数列向量≤0,,一般地,若出现下表情形,则LP问题无界.,,例,注意到目标函数中x2前的系数是－4，即检验数λ2＝4＞0，,单纯形表为,基解,,,,于是对应的基解不是最优解。,六、基可行解的改进,只要让x2成为基变量,而取大于0的数,其它非基变量仍取0，则目标函数值必然下降.,f93x1－4x25x3,,令x2a＞0，仍取x10，x30，则有,为了保证可行性,令,x6一定≥0,于是让x5成为非基变量，即让x2进基，让x5出基，目标函数值必然得到改善（下降）,,现在的问题是让谁出基，成为非基变量,,进基原则,选择正检验数对应的变量作为进基变量。,出基原则,若第Ｌ个比值最小，则选最小比值所在行的基变量作为出基变量，若有相同最小比值，则任选一个。bLk称为主元；,求最小比值,设λkmax｛λj|λj0｝,则xk为进基变量,主元列对应的变量为进基变量,,主元行对应的变量为出基变量。,0,,最小者,,,,,出基变量,,,λk＞0，则xk进基,,主元,就是求新的基可行解，方法如下,以主元行为出发点，用初等行变换将主元列中主元bLk的上方及下方的元素全部变成0（包括检验数行在内），然后将主元变成化为１。这样就得到了新的可行基及基本可行解，再判断是否得到最优解。,从几何上讲就是从可行解集一个极点迭代到另一个极点，每次迭代都使目标函数得以下降，最终找到最优解。,计算公式,,七、换基迭代,1、求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零。,2、判断,3、用初等行变换求新的基可行解，再回到第2步判断新的基可行解是否为最优解。,注意以上步骤一定可以在有限步内终止。,八、单纯形方法的计算步骤,（a）若λj≤0（j＝１，２，，n）得到最优解；,（b）某个λk＞0且bik≤0（i1，2,,m）则问题无界；,（c）若存在λk＞0且biki1,,m不全非正，则进行换基。,解此问题恰好是以｛x1,x4,x6｝为初始可行基的典式，,,,x3,,3,10／3,较小,,,进基,出基,,初始单纯形表,,,主元,例,,,,,,,01/20－3/4－20－9,,,,x115/201/42010,,,,,,,,x60－5/20－3/4811,,,,x30－1/211/4003,4,,,,x2,,,,,,,,,由于非基变量的检验数都小于0，,故此表为最优表。,最优解为,最优值为f－11。,例求解问题,引入松弛变量，,将目标改为,于是初始单纯形表为,,解,,,,,,x1,,,,,,,,,,3,2,x2,1,18/7,5/2,4,,至此，所有检验数非正，满足最优性条件。,最优解为,最优值为－f＝－9，即f＝9。,,,