《《单纯形法》PPT课件》由会员分享，可在线阅读，更多相关《《单纯形法》PPT课件（118页珍藏版）》请在金锄头文库上搜索。
1、第五章 单纯形法v在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,于是v美国数学家GBDantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。本章主要内容v线性规划问题解的基本概念v单纯形解法v解的最优性检验v表解形式的单纯形法v单纯形解法的一些问题及其处理方法第1节 单纯形解法的基本原理与思路v线性规划问题解的基本概念v单纯形解法v解的最优性检验一、线性规划问题解的基本概念v可行解v最优解v基及基本解v可行基及基本可行解v代数解与几何解的关系v单纯形法的要点最优解一、线性规划问题解的基本概念v可行解:满足所有约束条件(包括
2、非负条件)的解称为可行解.即可行域内所有点.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初始基本可行解: 由于求最优解是一个循环迭代
3、的过程,那么,我们将第一次找到的可行域的顶点。一、线性规划问题解的基本概念基及基本解:目目标标函数：函数：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
4、.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+0
5、s1+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
6、=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
7、与变量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
8、= -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被称为可行基可行基.线性规划求解流程:确定初始确定初始基本可行解基本可行解最优解？最优解？否否转移到新转移到新的基本可行解的基本可行解给出最优解给出最优解是是基及基本解:在求解最优解时,往往会首先找到一个可行基,求出基本可行解,然后通过基本可行解,逐步迭代求
9、出最优解.一般经验认为,可找A中的单位矩阵.作为(初始)可行基.二、最优性检验求出的基本可行解是否最优。还要进行检验！怎么检验？1。最优性检验的依据-检验数j是否最优，一般与目标函数的值有关，大家先来看目标函数的值：在目标函数中，有基变量，也有非基变量；由于基变量可以用非基变量代换掉，这样，目标式中只留下了非基变量。二、最优性检验目标式中只留下了非基变量。或者说，基变量的目标系数化为0。在目标式中，Z0为常量（不变），Xj0，只要看系数j的情况，2。最优解判别定理定理：在求最大目标函数时，对于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最大值就是Z0。在求最小目标函数时，
10、对于某个基本可行解，如果所有检验数j0，则这个可行解就是最优解。其中，最小值就是Z0。三、基变换如果初始可行解不是最优解，那么，我们将要重新选择可行基，求出基本可行解，再检验。具体过程为：（1） 先确定入基变量。根据检验系数j的大小确定把非基变量调入基中；一般认为，从j0中挑选最大的非基变量替换到基变量中，这一过程称为入基变量过程。（2）同时，要从可行基中挑选出一个向量，作为出基变量。换出的原则是求出的决策变量非负；或者挑选比值最小的行的原基变量为出基变量。要求例子子例子的标准型标准型标准型化原则:1.目标为min型的,价值系数一律反号令Z=-Z2.第I个约束行为型的,左边增加松驰量xn+i非
11、负,同时令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新的基变量
12、：v新的基本可行解新的基本可行解和目标函数v基本可行解v目标函数第三次迭代v确定入基变量：v确定出基变量：确定新基和求解新的基本可行解v新基v新的基变量：v新的基本可行解v基本可行解v目标函数v这是最优解。最大目标函数值为2600。新的基本可行解和目标函数复习 2006-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为负的,则左右两
13、边同时反号,保证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+x
14、2+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对于小于等于情况，通过标准化，每个约束条件的左边加上了一
15、的松弛变量，该松弛变量的系数矢量是单位矢量。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
16、, 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
