《单纯形法.ppt》由会员分享，可在线阅读，更多相关《单纯形法.ppt（118页珍藏版）》请在三一办公上搜索。
1、第五章 单纯形法,在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是美国数学家GBDantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。,本章主要内容,线性规划问题解的基本概念单纯形解法解的最优性检验表解形式的单纯形法单纯形解法的一些问题及其处理方法,第1节 单纯形解法的基本原理与思路,线性规划问题解的基本概念单纯形解法解的最优性检验,一、线性规划问题解的基本概念,可行解最优解基及基本解可行基及基本可行解代数解与几何解的关系单纯形法的要点,最优解,一、线性规划问题解的基本概念,可行解:满足所有约束条件(包括非负条件)的解
2、称为可行解.即可行域内所有点.,x1+x2300,2x1+x2400,x1 0,x20,s.t.,x2250,x1,200,0,200,300,可行域内的所有点称为:可行解.,maxz=50 x1+100 x2,一、线性规划问题解的基本概念,可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点.最优解:达到最优的可行解.最优解.基本可行解:可行域内的顶点(边界).,基本可行解,初始基本可行解:由于求最优解是一个循环迭代的过程,那么,我们将第一次找到的可行域的顶点。,一、线性规划问题解的基本概念,基及基本解:,目标函数：maxz=50 x1+100 x2,x1+x2300,2
3、x1+x2400,x1 0,x20,s.t.,x2250,maxz=50 x1+100 x2,x1+x2+s1=300,2x1+x2+s2=400,x1 0,x20,si0,s.t.,x2+s3=250,一、线性规划问题解的基本概念,基及基本解:,maxz=50 x1+100 x2+0s1+0s2+0s3,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2+0s1+1s2+0s3=400,x1 0,x20,s10，s20，s30,s.t.,0 x1+1x2+0s1+0s2+1s3=250,基及基本解:,s.t.,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2
4、+0s1+1s2+0s3=400,x1 0,x20,si0,0 x1+1x2+0s1+0s2+1s3=250,基及基本解:,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2+0s1+1s2+0s3=400,x1 0,x20,si0,0 x1+1x2+0s1+0s2+1s3=250,这是一个3X5的矩阵:,其中:,基及基本解:,这是一个3X5的矩阵:,从A中任取一个mxm的子矩阵B,只要B的秩为m,则称B为线性规划问题中的一个基.,基及基本解:,基中每一列(一个向量)称为该基的一个基向量(对B而言)。,是基,的三个基向量。,A中基之外的其它列称为B的非基向量。,是基,的三个基向
5、量.,又如:B,而A中其它两列,则称为B的非基向量.,原模型为:,s.t.,P3与变量s1对应,P4与变量s2对应,P5与变量s3对应,故称s1,s2,s3为基B的基变量,相应地,x1,x2成为B的非基变量.,s1 s2 s3,基及基本解:,s.t.,基及基本解:,s.t.,基及基本解:,s.t.,此方程有无穷多个解,为找最优解,可先令非基变量:x1=x2=0,S1=300,s2=400,s3=250,外加 x1=0,x2=0,基及基本解:,x1=0,x2=0,S1=300,s2=400,s3=250,本解是从基B中求出的,故被称为线性规划的基本解.(要求令非基变量为0,然后从基中解出而得),
6、再看另一个基本解:,s.t.,此方程有无穷多个解,为找最优解,可先令非基变量:s2=s3=0,x1=100,x2=250,s1=-50,外加 s2=0,s3=0,求得满足约束条件的解:基本解,S1=300,s2=400,s3=250,x1=0,x2=0,求得约束条件的解:基本解,S1=300,s2=400,s3=250,x1=0,x2=0,S1=-50 为负,超出可行域的范围;无效,所有决策量非负,在可行域内,称为基本可行解.相应地,B被称为可行基.,线性规划求解流程:,基及基本解:,在求解最优解时,往往会首先找到一个可行基,求出基本可行解,然后通过基本可行解,逐步迭代求出最优解.一般经验认为
7、,可找A中的单位矩阵.,作为(初始)可行基.,二、最优性检验,求出的基本可行解是否最优。还要进行检验！怎么检验？,1。最优性检验的依据-检验数j,是否最优，一般与目标函数的值有关，大家先来看目标函数的值：,在目标函数中，有基变量，也有非基变量；由于基变量可以用非基变量代换掉，这样，目标式中只留下了非基变量。,二、最优性检验,目标式中只留下了非基变量。或者说，基变量的目标系数化为0。,在目标式中，Z0为常量（不变），Xj0，只要看系数j的情况，,2。最优解判别定理定理：在求最大目标函数时，对于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最大值就是Z0。在求最小目标函数时，对
8、于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最小值就是Z0。,三、基变换,如果初始可行解不是最优解，那么，我们将要重新选择可行基，求出基本可行解，再检验。具体过程为：（1）先确定入基变量。根据检验系数j的大小确定把非基变量调入基中；一般认为，从j0中挑选最大的非基变量替换到基变量中，这一过程称为入基变量过程。（2）同时，要从可行基中挑选出一个向量，作为出基变量。换出的原则是求出的决策变量非负；或者挑选,比值最小的行的原基变量为出基变量。要求,例子,例子的标准型,标准型,标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第I个约束行为型的,左边增加松驰量x
9、n+i非负,同时令Cn+i=0.3.第I个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第I个约束行的bn+i为负的,则左右两边同时反号,保证bn+i.=0,线性方程组的增广矩阵表示,它的初始可行基,初始基本可行解,初始基变量 是松弛变量。初始可行解（只要满足非负条件）初始基本可行解目标函数与最优性检验,第一次迭代,确定入基变量，应当是，它的系数是4。确定出基变量，方法如下，得,确定新基和求解新的基本可行解,新基新的基变量：新的基本可行解,新的基本可行解和目标函数,基本可行解目标函数,第二次迭代,确定入基变量：确定出基变量：,确定新基和求解新的基本可行解,新基新的基变量：
10、新的基本可行解,新的基本可行解和目标函数,基本可行解目标函数,第三次迭代,确定入基变量：确定出基变量：,确定新基和求解新的基本可行解,新基新的基变量：新的基本可行解,基本可行解目标函数这是最优解。最大目标函数值为2600。,新的基本可行解和目标函数,复习 2006-10-19,线性规划的标准化：LP解的基本概念：单纯形表格形式求解,标准型,标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第i个约束行为型的,左边增加松驰量xn+i非负,同时令Cn+i=0.3.第i个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第i个约束行的bn+i为负的,则左右两边同时反
11、号,保证bn+i.=0,标准型,标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第i个约束行为型的,左边增加松驰量xn+i非负,同时令Cn+i=0.3.第i个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第i个约束行的bn+i为负的,则左右两边同时反号,保证bn+i.=05.若变量Xj 0，则令Xj=-Xj*,有 Xj*06.若变量Xj正负不限，令Xj=Xj1-Xj2,Xj1,Xj2 0,标准型,1.试将下列线性规划化为标准形式：min f=3x1-2x2+4x3s.t.2x1+3x2+4x3300 x1+5x2+6x3400 x1+x2+x3 200
12、x3正负不限，x1,x2 0,解：令 g=-f(x),x3=x31-x32,且x31,x32 0 max g=-3x1+2x2-4x31+4x32+0 x4+0 x5+0 x6s.t.2x1+3x2+4(x31-x32)-x4=300 x1+5x2+6(x31-x32)+x5=400 x1+x2+x31-x32+x6=200,第2节、单纯形表格解法,建立基本可行解计算变量的检验数判断是否最优若不是最优解，换基计算新的基本可行解迭代计算直到求得最优解或可判断无最优解为止,建立初始基本可行基,对于小于等于情况，通过标准化，每个约束条件的左边加上了一的松弛变量，该松弛变量的系数矢量是单位矢量。当约束
13、条件的右手项都大于等于零时，可令松弛变量为初始基本可行基。,关于解的最优性检验,设线性规划模型为,令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得,令则目标函数可写成所以可用j 判断是否最优解，它叫做检验数。,单纯形解法,例子:,表解形式的单纯形法,例子:,提取系数，填入表格：,s.t.,1x1+1 x2+1s1+0s2+0s3=300,2x1+1 x2+0s1+1s2+0s3=400,x1 0,x20,si0,0 x1+1x2+0s1+0s2+1s3=250,初始单纯形表,初始单纯形表,目标系数区,约束条件系数区,右端系数,检验系数区,基变量区,初始单纯形表,初始单纯形表,初始单纯形
14、表,初始单纯形表,初始单纯形表,初始单纯形表,0,0,0,0,0,初始单纯形表,50,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,x1,50,x1,50,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,第3节 求目标函数值最小的线性规划的问题的单纯形表解法,第3节 求目标函数值最小的线性规划的问题的单纯形表解法,第3节 求目标函数值最小的线性规划的问题的单纯形表解法,a1,a2是人为加上去的,称为人工变量.M代表无限大的数.在求解过程中,必须让人工变量从基中换出,
15、(即使得人工变量为0),否则如果到最后,人工变量仍不能从基变量中换出,则该线性规划无可行解.,初始单纯形表,初始单纯形表,初始单纯形表,1/2,初始单纯形表,X1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0最优值：z=-z=-(-800)=800,第4节几种特殊情况,一.无可行解二.无界解三.无穷多最优解.四.退化问题,4.几种特殊情况,一、无可行解：目标函数：max z=20 x1+30 x2约束条件：3x1+10 x2150 x1 30 x1+x240 x1,x20,4.几种特殊情况,max z=20 x1+30 x2-Ma 3x1+10 x2+s1=150
16、 x1+s2=30 x1+x2-s3+a1=40 x1,x2,s1,s2,s3,a10,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,11+7M/10,初始单纯形表,4.几种特殊情况,x1=30,x2=6,s1=0,s2=0,s3=0,a1=40，其最大目标函数为780-4M，由于a1 0,故所得解不是最优解。人工变量非0，表明原模型无最优解。,4.几种特殊情况,二、无界解目标函数：max z=x1+x2约束条件：x1x21-3x1+2x2 6 x1,x20,4.几种特殊情况,二、无界解目标函数：max z=x1+x2约束条件：x1x2+s1=1-3x1+2x2+s2=6 x1,x2
17、,s1,s20,初始单纯形表,初始单纯形表,X1=1,x2=0,s1=0,s2=9，不是最优解，但a12=-1,a22=-1,此线性规划的目标函数可以取得无限大。,线性规划有无界解:至少有一个检验系数0,且该列的系向量的每个元素aij都小于或等于0,则该规划问题是无界的.,4.几种特殊情况,三、无穷多个最优解目标函数：max z=50 x1+50 x2约束条件：x1+x2300 2x1+x2400 x2250 x1,x20,4.几种特殊情况,三、无穷多个最优解目标函数：max z=50 x1+50 x2约束条件：x1+x2+s1=300 2x1+x2+s2=400 x2+s3=250 x1,x
18、2,s1,s2,s30,初始单纯形表,初始单纯形表,初始单纯形表,非基变量的检验数=0,找到了最优解：x1=50,x2=250,s1=0,s2=50,s3=0MAX z=15000式中除基变量的j=0外，还有非基变量s3也为0，此时可断定此线性规划模型有无穷多个解！,初始单纯形表,初始单纯形表,250,200,100,100,200,300,x1,x2,Z1,Z2,点：Z1+(1-)Z2,4.几种特殊情况,四、退化问题在单纯形计算过程中，基变量有时存在两个以上相同的的最小比值，这样就在下一次迭代中就有了一个或几个基变量等于0，这称之为退化。目标函数：max z=2x1+1.5x3约束条件：x1
19、-x22 2x1+x34 x1+x2+x33 x1,x2,x30,4.几种特殊情况,目标函数：max z=2x1+1.5x3约束条件：x1-x2+s1=2 2x1+x3+s2=4 x1+x2x3+s3=3 x1,x2,x3,s1,s2,s30,初始单纯形表,初始单纯形表,初始单纯形表,1/2,初始单纯形表,初始单纯形表,最后获得了模型的最优解：X1=1,x2=0,x3=2,s1=1,s2=0,s3=0,退化处理原则（避免循环）：（1）在所有检验数大于0的非基变量中，选一个下标最小的作为入基变量。（2）在存在两个或两个以上最小比值时，选一个下标小的基变量为出基变量。,五、单纯形解法中的一些问题及其处理方法,换入变量的选择问题下标最先原则检验数最大原则换出变量的选择问题比值最小原则下标最先原则无换出变量的情况无界解非基变量检验数有等于零多个最优解的情况,习题,P.98，习题3、4、6,
