第5章-1单纯形法-10-课件

本章主要内容v线性规划问题解的基本概念v单纯形解法v解的最优性检验v表解形式的单纯形法v单纯形解法的一些问题及其处理方法第1节 单纯形解法的基本原理与思路v线性规划问题解的基本概念v单纯形解法v解的最优性检验一、线性规划问题解的基本概念v可行解v最优解v基及基本解v可行基及基本可行解v代数解与几何解的关系v单纯形法的要点最优解一、线性规划问题解的基本概念v可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点.x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.x x2 2250250 x12000200300可行域内的所有点称为:可行解可行解可行解可行解.maxmaxz=50 xz=50 x1 1+100 x+100 x2 2一、线性规划问题解的基本概念v可行解:满足所有约束条件(包括非负条件)的解称为可行解.即可行域内所有点.v最优解:达到最优的可行解.最优解.v基本基本可行解:可行域内的顶点(边界).基本可行解v初始基本可行解:由于求最优解是一个循环迭代的过程,那么,我们将第一次找到的可行域的顶点。一、线性规划问题解的基本概念基及基本解:目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.x x2 2250250maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 2+s+s1=1=3003002x2x1 1+x+x2 2+s2=400+s2=400 x x1 1 0,x0,x2 20,0,si0si0s.t.s.t.x x2 2+s3 =250+s3 =250一、线性规划问题解的基本概念基及基本解:maxmaxz=50 xz=50 x1 1+100 x+100 x2 2+0s1+0s2+0s3+0s1+0s2+0s31x1x1 1+1 x+1 x2 2+1s+1s1+0s2+0s3 =1+0s2+0s3 =3003002x2x1 1+1 x+1 x2 2+0s1+1s2+0s3=400+0s1+1s2+0s3=400 x x1 1 0,x0,x2 20,0,s10s10，s20s20，s30s30s.t.s.t.0 x1+1x0 x1+1x2 2+0s1+0s2+1s3=250+0s1+0s2+1s3=250基及基本解:s.t.1x1x1 1+1 x+1 x2 2+1s+1s1+0s2+0s3 =1+0s2+0s3 =3003002x2x1 1+1 x+1 x2 2+0s1+1s2+0s3=400+0s1+1s2+0s3=400 x x1 1 0,x0,x2 20,0,si0si00 x1+1x0 x1+1x2 2+0s1+0s2+1s3=250+0s1+0s2+1s3=250基及基本解:1x1x1 1+1 x+1 x2 2+1s+1s1+0s2+0s3 =1+0s2+0s3 =3003002x2x1 1+1 x+1 x2 2+0s1+1s2+0s3=400+0s1+1s2+0s3=400 x x1 1 0,x0,x2 20,0,si0si00 x1+1x0 x1+1x2 2+0s1+0s2+1s3=250+0s1+0s2+1s3=250这是一个3X5的矩阵:其中:基及基本解:这是一个3X5的矩阵:从A中任取一个mxm的子矩阵B,只要B的秩为m,则称B为线性规划问题中的一个基.基及基本解:基中每一列(一个向量)称为该基基的一个基向量(对B而言)。是基的三个基向量。A中基之外的其它列称为B的非基向量。是基的三个基向量.又如: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=0S1=300,s2=400,s3=250,外加 x1=0,x2=0基及基本解:x1=0,x2=0,S1=300,s2=400,s3=250,本解是从基B中求出的,故被称为线性规划的基本解.(要求令非基变量为0,然后从基中解出而得)再看另一个基本解: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被称为可行基可行基.线性规划求解流程:确定初始确定初始基本可行解基本可行解最优解？最优解？否否转移到新转移到新的基本可行解的基本可行解给出最优解给出最优解是是基及基本解:在求解最优解时,往往会首先找到一个可行基,求出基本可行解,然后通过基本可行解,逐步迭代求出最优解.一般经验认为,可找A中的单位矩阵.作为(初始)可行基.二、最优性检验求出的基本可行解是否最优。还要进行检验！怎么检验？1。最优性检验的依据-检验数j是否最优，一般与目标函数的值有关，大家先来看目标函数的值：在目标函数中，有基变量，也有非基变量；由于基变量可以用非基变量代换掉，这样，目标式中只留下了非基变量。二、最优性检验目标式中只留下了非基变量。或者说，基变量的目标系数化为0。在目标式中，Z0为常量（不变），Xj0，只要看系数j的情况，2。最优解判别定理定理：在求最大目标函数时，对于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最大值就是Z0。在求最小目标函数时，对于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最小值就是Z0。三、基变换如果初始可行解不是最优解，那么，我们将要重新选择可行基，求出基本可行解，再检验。具体过程为：（1）先确定入基变量。根据检验系数j的大小确定把非基变量调入基中；一般认为，从j0中挑选最大的非基变量替换到基变量中，这一过程称为入基变量过程。（2）同时，要从可行基中挑选出一个向量，作为出基变量。换出的原则是求出的决策变量非负；或者挑选比值最小的行的原基变量为出基变量。要求例子子例子的标准型标准型标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第I个约束行为型的,左边增加松驰量xn+i非负,同时令Cn+i=0.3.第I个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第I个约束行的bn+i为负的,则左右两边同时反号,保证bn+i.=0线性方程组的增广矩阵表示v它的初始可行基初始基本可行解v初始基变量 是松弛变量。v初始可行解（只要满足非负条件）v初始基本可行解v目标函数与最优性检验第一次迭代v确定入基变量，应当是 ，它的系数是4。v确定出基变量 ，方法如下，得确定新基和求解新的基本可行解v新基v新的基变量：v新的基本可行解新的基本可行解和目标函数v基本可行解v目标函数第二次迭代v确定入基变量：v确定出基变量：确定新基和求解新的基本可行解v新基v新的基变量：v新的基本可行解新的基本可行解和目标函数v基本可行解v目标函数第三次迭代v确定入基变量：v确定出基变量：确定新基和求解新的基本可行解v新基v新的基变量：v新的基本可行解v基本可行解v目标函数v这是最优解。最大目标函数值为2600。新的基本可行解和目标函数复习 2019-10-19v线性规划的标准化：vLP解的基本概念：v单纯形表格形式求解标准型标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第i个约束行为型的,左边增加松驰量xn+i非负,同时令Cn+i=0.3.第i个约束行为型的,左边增加剩余变量xn+i非负,同时令Cn+i=0.4.第i个约束行的bn+i为负的,则左右两边同时反号,保证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 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节、单纯形表格解法v建立基本可行解v计算变量的检验数v判断是否最优v若不是最优解，换基v计算新的基本可行解v迭代计算直到求得最优解或可判断无最优解为止建立初始基本可行基v对于小于等于情况，通过标准化，每个约束条件的左边加上了一的松弛变量，该松弛变量的系数矢量是单位矢量。v当约束条件的右手项都大于等于零时，可令松弛变量为初始基本可行基。关于解的最优性检验v设线性规划模型为v令基为B，并作相应的矩阵分割，从约束条件得v代入目标函数v得v令v则目标函数可写成v所以可用j 判断是否最优解，它叫做检验数。单纯形解法v例子:表解形式的单纯形法v例子:提取系数，填入表格：s.t.1x1x1 1+1 x+1 x2 2+1s+1s1+0s2+0s3 =1+0s2+0s3 =3003002x2x1 1+1 x+1 x2 2+0s1+1s2+0s3=400+0s1+1s2+0s3=400 x x1 1 0,x0,x2 20,0,si0si00 x1+1x0 x1+1x2 2+0s1+0s2+1s3=250+0s1+0s2+1s3=250初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值0Zj初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值0Zj目标系数区目标系数区约束条件系数区右右端端系系数数检验系数区检验系数区基基变变量量区区初始单纯形表迭代次数基变量CBx1x2s1s2s3b比值501000000Zj初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000111003002101040001001250Zj初始单纯形表迭代次数基变量CBx1x2s1s2s3b比值501000000111003002101040001001250Zj初始单纯形表迭代次数基变量CBx1x2s1s2s3b比值501000000S1011100300S2021010400S3001001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400S3001001250ZjZ=0初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400S3001001250Zj00000Z=000000初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400S3001001250Zj00000Z=010000050初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400S3001001250Zj00000Z=050100000初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400 x201001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400 x210001001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400 x210001001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S1011100300S2021010400 x210001001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S101010-150S202001-1150 x210001001250ZjZ=25000初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S101010-150S202001-1150 x210001001250Zj010000100Z=25000初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000S101010-150S202001-1150 x210001001250Zj010000100Z=2500050000-100初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000S101010-150S202001-1150 x210001001250Zj010000100Z=2500050000-100初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S101010-150S202001-1150 x210001001250Zj010000100Z=2500050000-100初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000000S101010-150S202001-1150 x210001001250Zjx150 x150初始单纯形表迭代次数基变量CBx1x2s1s2 S3b比值501000000 x1501010-150S202001-1150 x210001001250Zj初始单纯形表迭代次数基变量CBx1x2s1s2 S3b比值501000000 x1501010-150S202001-1150 x210001001250Zj初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000 x1501010-150S2000-21150 x210001001250ZjZ=27500初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000 x1501010-150S2000-21150 x210001001250Zj5010050050Z=27500初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000 x1501010-150S2000-21150 x210001001250Zj5010050050Z=2750000-500-50第3节 求目标函数值最小的线性规划的问题的单纯形表解法第3节 求目标函数值最小的线性规划的问题的单纯形表解法第3节 求目标函数值最小的线性规划的问题的单纯形表解法a1,a2是人为加上去的,称为人工变量.M代表无限大的数.在求解过程中,必须让人工变量从基中换出,(即使得人工变量为0),否则如果到最后,人工变量仍不能从基变量中换出,则该线性规划无可行解.初始单纯形表迭代次数基变量CBx1X2s1s2S3a1A2b比值-2-3000-M-M0a1-M11-10010350a2-M110-1001125S302100100600Zj-2M-MMM0-M-M-475M-2+2M-3+M-M-M000初始单纯形表迭代次数基变量CBx1X2s1s2S3a1A2b比值-2-3000-M-M1a1-M01-1101-1225x1-2100-1001125S30010210-2350Zj-2-MM-M+20-MM-2-225M-2500-3+M-MM-2002-2M初始单纯形表迭代次数基变量CBx1X2s1s2S3a1A2b比值-2-3000-M-M2a1-M01/2-10-1/21050 x1-21001/200300S200011/20-1175Zj-2-1-M/2M0-1-M/2-M0-50M-6000-2+M/2-M01+M/20-M1/2初始单纯形表迭代次数基变量CBx1X2s1s2S3a1A2b比值-2-3000-M-M3x2-301-2-2-120100 x1-210111-10250S2000111-1-1125Zj-2-3401-40-80000-40-1-M+4-MX1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0最优值：z=-z=-(-800)=800第4节几种特殊情况v一.无可行解v二.无界解v三.无穷多最优解.v四.退化问题4.几种特殊情况v一、无可行解：v目标函数：max z=20 x1+30 x2v约束条件：3x1+10 x2150v x1 30v x1+x240v x1,x204.几种特殊情况v max z=20 x1+30 x2-Mav v 3x1+10 x2+s1=150v x1+s2=30v x1+x2-s3+a1=40v x1,x2,s1,s2,s3,a10初始单纯形表迭代次数基变量CBx1X2s1s2S3a1b比值2030000-M0s103101000150s2010010030a1-M1100-1140Zj-M-M00M-M-40M20+M30+M00-M0初始单纯形表迭代次数基变量CBx1X2s1s2S3a1b比值2030000-M0 x2303101000150s2010010030a1-M1100-1140Zj-M-M00M-M-40M20+M30+M00-M0初始单纯形表迭代次数基变量CBx1X2s1s2S3a1b比值2030000-M0 x2303/1011/1000015s2010010030a1-M1100-1140Zj-M-M00M-M-40M20+M30+M00-M0初始单纯形表迭代次数基变量CBx1X2s1s2S3a1b比值2030000-M0 x2303/101 1/1000015s2010010030a1-M7/100-1/100-1125Zj9-7M/10303+M/100M-M450-25M0-3-M/100-M011+7M/10初始单纯形表迭代次数基变量CBx1X2s1s2S3a1b比值2030000-M0 x23001 1/10-3/10006x12010010030a1-M001/10-7/10-114Zj20303+M/1011+7M/10M-M780-40M00-3-M/10-11-7M/10-M04.几种特殊情况v x1=30,x2=6,s1=0,s2=0,s3=0,a1=40，v其最大目标函数为780-4M，由于a1 0,v故所得解不是最优解。v人工变量非0，表明原模型无最优解。4.几种特殊情况v 二、无界解v目标函数：max z=x1+x2v约束条件：x1x21v -3x1+2x2 6v x1,x204.几种特殊情况v 二、无界解v目标函数：max z=x1+x2v约束条件：x1x2+s1=1v -3x1+2x2+s2=6v x1,x2,s1,s20初始单纯形表迭代次数基变量CBx1X2s1s2b比值11000s101-1101s20-32016Zj000001100初始单纯形表迭代次数基变量CBx1X2s1s2b比值11001x111-1101-s200-1319-Zj1-110102-10X1=1,x2=0,s1=0,s2=9，不是最优解，但a12=-1,a22=-1,此线性规划的目标函数可以取得无限大。此线性规划的目标函数可以取得无限大。线性规划有无界解:至少有一个检验系数0,且该列的系向量的每个元素aij都小于或等于0,则该规划问题是无界的.4.几种特殊情况v三、无穷多个最优解v目标函数：max z=50 x1+50 x2v约束条件：x1+x2300v 2x1+x2400v x2250v x1,x204.几种特殊情况v三、无穷多个最优解v目标函数：max z=50 x1+50 x2v约束条件：x1+x2 +s1=300v 2x1+x2+s2=400v x2 +s3=250v x1,x2,s1,s2,s30初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50500000s1011100300s2021010400s3001001250Zj0000005050000初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值50500001s101010-150s202001-1150 x25001001250Zj050005012500500000初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值50500002x1501010-150s2000-211150 x25001001250Zj50 5050001500000-5000非基变量的检验数=0v找到了最优解：vx1=50,x2=250,s1=0,s2=50,s3=0vMAX z=15000v式中除基变量的j=0外，还有非基变量s3也为0，此时可断定v此线性规划模型有无穷多个解！初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值50500002x1501010-150s2000-211150 x25001001250Zj50 5050001500000-5000初始单纯形表迭代次数基变量CBx1x2s1s2S3b比值50500003x15010-110100s3000-21150 x250012-10200Zj50 5050001500000-5000250200100100200300 x1x2Z1Z2点：Z1+(1-)Z24.几种特殊情况v四、退化问题v在单纯形计算过程中，基变量有时存在两个以上相同的的最小比值，这样就在下一次迭代中就有了一个或几个基变量等于0，这称之为退化。v目标函数：max z=2x1+1.5x3v约束条件：x1-x22v 2x1+x34v x1+x2+x33v x1,x2,x304.几种特殊情况v目标函数：max z=2x1+1.5x3v约束条件：x1-x2+s1=2v 2x1+x3+s2=4v x1+x2x3+s3=3v x1,x2,x3,s1,s2,s30初始单纯形表迭代次数基变量CBx1X2 X3s1s2S3b比值203/20000s101-101002s202010104s301110013Zj0000000203/2000初始单纯形表迭代次数基变量CBx1X2 X3s1s2S3b比值203/20001x121-101002s20021-2100s30021-1011Zj2-200004023/2-200初始单纯形表迭代次数基变量CBx1X2 X3s1s2S3b比值203/20002x1210002x2001-100s300001-111Zj2010104001/20-101/2初始单纯形表迭代次数基变量CBx1X2 X3s1s2S3b比值203/20003x121-101002x3 3/2021-2100s300001-111Zj213/2-13/2040-101-3/20初始单纯形表迭代次数基变量CBx1X2 X3s1s2S3b比值203/20004x121-1001-12x3 3/20210-122s100001-111Zj213/201/2150-100-1/2-1v最后获得了模型的最优解：vX1=1,x2=0,x3=2,s1=1,s2=0,s3=0退化处理原则（避免循环）：（1）在所有检验数大于0的非基变量中，选一个下标最小的作为入基变量。（2）在存在两个或两个以上最小比值时，选一个下标小的基变量为出基变量。五、单纯形解法中的一些问题及其处理方法v换入变量的选择问题下标最先原则检验数最大原则v换出变量的选择问题比值最小原则下标最先原则v无换出变量的情况无界解v非基变量检验数有等于零多个最优解的情况习题vP.98，习题3、4、6谢谢