第二次和第三次课合订单纯形法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,04 十一月 2026,第二次和第三次课合订单纯形法,一、基本思想,从标准型的LP模型的一个基可行解出发，判断是否是最优。如果是最优解，结束运算；否则，设法找到一个更优（目标函数值减小）的基本可行解。如此继续，经过有限次迭代代，就可以找到LP的最优解或判别LP问题有没有最优解。,第三节 单纯形法（Simplex method）,(1947)G.B.Dantzig,找出一个初始基本可行解,是否最优,转移到另一个基本可行解,（找出更小的目标函数值）,最优解,是,否,循,环,结束,基本思想框图,如何找初始基本可行解？,如何判断是否最优解？,如何转换基本可行解？,求,回顾上一节例1：,的一个基本解和一个基本可行解.,解:,约束方程的增广矩阵为：,x,2,x,4,注意到,A,是,24,矩阵,r(A)2.,由于第2列和第4列线性无关,构成一个2阶单位子块,，,因此可构成一个基矩阵.,取,为基变量,为自由变量,用自由变量表,表示基变量得如下同解方程组:,又因50,60,该解显然非负，因此这个解也是一个基本可行解。,x,2,x,4,基变量取为其他变量的情况,若取,为基变量,为自由变量,由于基本解,中自由变量全取零,所以只需对第一,列,第二列以及常数项列组成的矩阵初等行变换至行最简形:,由此可得基本解:,又因30,80,该解显然非负，因此这个解也是一个基本可行解。,结论:,若系数矩阵,A,中存在m阶单位子块,得到基本可行解之后,如何判断它是否是最优解呢?,设约束线性方程组AX=b的系数矩阵,A,的秩R(A)=m,则有如下结论成立：,记增广矩阵为（A,b），,其中,基变量的取值为单位子块中1所对应的右边常数,项非负,且对应的常数,那么从增广矩阵中便可读出一个基本可行解.,项的值,自由变量取值全为零.,该解是否最优呢?,将,代入目标函数表达式中消去,得,注意到,的系数为-100,而可行域中,可见,当,时,目标函数值减小,所以,不是最优解.,思考:,若此时目标函数中自由变量,的系数均大于零,那么这个解是否是最优解?,1.单纯形表,中心部位,A,右列,b,底行(检验行),0,右下端,目标函数中常数项的相反数,目标函数中变量的系数,底线,二、单纯形表及容许的运算,r,(,A,),m,2.容许运算,中心部位,A,b,右列,底行,0,右下端,1)底线以上的行可进行初等行变换(三种);,2)底线以上的行乘常数后加至底行(包括右下端).,底线,使表具备下面四个特点:,3.终止条件(最优性条件),当表格具备如下特点:,右列元素非负,中心部位具有 m 阶单位子块,底行中相应于单位子块位置的元素,为0(基变量对应的底行元素为零),底行其他元素非负(自由变量对应的元素非负),则从表格中即可读得LP问题的最优解和最优值.,满足 时,可读出基本可行解,满足 时,判断该解是否最优.,满足 时,可断定该基本可行解是最优解.,最优解(值)的读法:,单位子块中1所在列对应的变量(基变量)取相应右列的值,其余变量(自由变量)取值为零,将它们写在一起即是一个最优解.,而此时,右下端元素的相反数,即为相应的,最优值,.,2,0,-4,1,6,-1,1,3,0,5,1,-3,2 4,0,2,0,-4,1,6,-1,1,3,0,5,-10,0,27 0,-9,的系数为-10,清华大学出版社,.,例3.,用单纯形法求解,解:将上述线性规划化为标准形:,方法一：,1,1,1,1,0 0,12,2,1,-1,0 1 0,6,-1 3 0,0 0 1,9,-1,2,-1 0 0 0,0,0,1/2,3/2,1,-1/2,0,9,1,1/2,-1/2,0,1/2,0,3,0,7,/2,-1/2,0,1/2,1,12,0 5,/2,-3,/2,0 1,/2,0,3,满足,但,不,满足,满足,但,不,满足,0,1/3,1,2/3,-1/3,0,6,1,2/3,0,1/3,1/3,0,6,0,11/3,0,1/3,1/3,1,15,0,3,0 1 0 0,12,满足,略去松弛变量,得原LP最优解为,最优解:,注:由于最终表底行中自由变量,对应的系数为0,故有无穷多最优解，即该最优解不是唯一最优解。,方法二：,1,1,1,1,0 0,12,2,1,-1,0 1 0,6,-1 3 0,0 0 1,9,-1,2,-1,0 0 0,0,1,1,1,1,0 0,12,3,2,0,1 1,0,18,-1 3,0,0,0,1,9,0 3,0,1,0 0,12,满足,但,不,满足,满足,1,1,1,1,0 0,12,3,2,0,1 1,0,18,-1 3,0,0,0,1,9,0 3,0,1,0 0,12,满足,最优解:,最优值为,略去松弛变量,得原LP最优解为,五.收敛性定理,定理2.2,在已知一个基本可行解(初始基本可行解)的前提下使用单纯形表求解LP问题时,若每次迭代得到的基本可行解中基变量均大于零(称非退化的),则算法必有限步终止,。,证明:基本可行解有限+非退化(不出现循环),总能找到最优解.,主要内容结束，下面为选读内容,设,是基变量，,是非基变量，,则基矩阵,并记,六、单纯性法中的理论分析（选读内容）,线性规划问题的规范式,与基变量,对应的,规范式,与基变量,对应的,规范式,1.4 单纯形法（Simplex method）,定义,2.12,令,称,为变量,x,j,的判别数或检验数.,规范式中，令非基变量为0,得到基本解,其中,则,x,0,是基本可行解.,其中 为A的列向量,为B,-1,A的列向量,1.基可行解是最优解的判别,个别结论的证明（举例）,定理,2.4.,设,x,0,是线性规划,(LP)对应于基,基可行解.,与基变量,对应的规范式中，若,x,0,的全体判别数非负，即,则,x,0,是线性规划,(LP)的最优解。,最优性条件,设,x,0,对应的目标函数值为,f,0,。,证明：,对于任意的可行解,由规范式,由于,，所以有,即,x,0,是最优解,。,定理,2.5,设,x,0,是线性规划,(LP)对应于基,基可行解.,与基变量,对应的规范式中,，若存在,且对所有的,则线性规划,(LP)无最优解。,2.无最优解的情况,证明：,用,乘上式得,所以,由于,是,的一组基，,因为,是一个基本可行解，,所以有,上面两式相减，得,若令,因此,则上式说明,是约束方程组,的解。,其中,是第k个分量，,所以,因为,是一个基本可行解，,