《线性规划单纯形方法幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划单纯形方法幻灯片.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划单纯形方法第1页，共23页，编辑于2022年，星期一线性规划问题基本定理定理一定理一 若线性规划问题存在可行解，则问题的可行若线性规划问题存在可行解，则问题的可行 域是凸集。域是凸集。定理二定理二 线性规划问题的基本可行解线性规划问题的基本可行解 X 对应线性规划对应线性规划 问题可行域（凸集）的顶点。问题可行域（凸集）的顶点。定理三定理三 若线性规划问题有最优解，一定存在一个基若线性规划问题有最优解，一定存在一个基 可行解是最优解可行解是最优解(即最优解一定在某顶点上即最优解一定在某顶点上)。从上述三个定理可以看出，要求线性规划问题的从上述三个定理可以看出，要求线性规划问题的最优解，
2、只要比较可行域（凸集）各个顶点最优解，只要比较可行域（凸集）各个顶点(或或者说基可行解者说基可行解)对应的目标函数值即可，最大的就对应的目标函数值即可，最大的就是我们所要求的最优解。是我们所要求的最优解。第2页，共23页，编辑于2022年，星期一3.2 单纯形方法思路思路：从一个基可行解（极点）出发（如何从一个基可行解（极点）出发（如何去找一个基可行解？），判断其是否为最去找一个基可行解？），判断其是否为最优解，（如何判断？），优解，（如何判断？），若不是，则转换若不是，则转换到相邻的基可行解（另一个极点），并使到相邻的基可行解（另一个极点），并使目标函数值不断增大，一直找到最优解为目标函数值
3、不断增大，一直找到最优解为止。止。第3页，共23页，编辑于2022年，星期一 单纯形法：先找到一个初始基可行解，如果单纯形法：先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解（换基不是最优解，设法转换到另一个基可行解（换基迭代，即从极点到极点），并使目标迭代，即从极点到极点），并使目标 函数不断函数不断增大，一直到增大，一直到 找到最优解为止。找到最优解为止。B1X(1)B1X(1)B2X(2)B3X(3)BnX(n)XN=0X=(XB,XN)第4页，共23页，编辑于2022年，星期一2.3.1 单纯形表单纯形法的具体步骤：单纯形法的具体步骤：（一）确定初始基可行解（一）确定初
4、始基可行解在在L.P问题的标准型：问题的标准型：中，不妨设中，不妨设B是一个可行基，于是是一个可行基，于是A=（B,N)不失一般性假定不失一般性假定B=（P1,Pm),基变量基变量XB=（x1,xm)T N=(Pm+1,Pn),非基变量非基变量XN=（xm+1,xn)T.则则 X=XB,XN T相应有相应有C=(CB,CN)第5页，共23页，编辑于2022年，星期一于是，原问题化为：于是，原问题化为：第6页，共23页，编辑于2022年，星期一初始基可行解oI I第7页，共23页，编辑于2022年，星期一检验数检验数第8页，共23页，编辑于2022年，星期一为什么？为什么？第9页，共23页，编辑
5、于2022年，星期一。对上面分析过程进行总结：对上面分析过程进行总结：（1）在标准型中，找一个单位基矩阵并求）在标准型中，找一个单位基矩阵并求出该基对应的基可行解。出该基对应的基可行解。当当L.PL.P问题的约束条件全部为问题的约束条件全部为“”“”时，在变换时，在变换为标准型的过程引进松驰变量，就自然得到为标准型的过程引进松驰变量，就自然得到了一个单位矩阵了一个单位矩阵-初始可行基和初始基可初始可行基和初始基可行解。行解。（2）检验该基可行解是否最优？通过非基变）检验该基可行解是否最优？通过非基变量的检验数。量的检验数。（3）若不是最优，则另找一个基产生一个）若不是最优，则另找一个基产生一个
6、基可行解基可行解-换基迭代。直到最优。换基迭代。直到最优。对此原理，我们可以通过对此原理，我们可以通过单纯形表单纯形表来实现。来实现。第10页，共23页，编辑于2022年，星期一单纯形表单纯形表第11页，共23页，编辑于2022年，星期一说明说明1、表中基变量所在位置并不一定正好在前、表中基变量所在位置并不一定正好在前m个位个位置上，但总可以通过调换重新排成上表形式。置上，但总可以通过调换重新排成上表形式。2、表中最下一行称为检验数行，对应于非基变量、表中最下一行称为检验数行，对应于非基变量的检验数为：（用于检验是否还须继续迭代）的检验数为：（用于检验是否还须继续迭代）3、不难看出，基变量、不
7、难看出，基变量 的检验数的检验数均为均为0 第12页，共23页，编辑于2022年，星期一2.3.2 单纯形法的步骤单纯形法的步骤引例引例：解：解L.P问题问题第13页，共23页，编辑于2022年，星期一第一步：第一步：把模型化为标准形式后找出初始可行基，把模型化为标准形式后找出初始可行基，建立初始单纯形表（见下表）。建立初始单纯形表（见下表）。本例中取初始基本例中取初始基B B1 1=(P=(P3 3,P,P4 4)=I)=I,则则 c cj j 4 3 0 04 3 0 0C CB BX XB B b b x x1 1 x x2 2 x x3 3 x x4 40 00 0 x x3 3 x
8、x4 424242626 2 3 1 02 3 1 0 3 2 0 1 3 2 0 1 Z Z0 0 4 3 0 04 3 0 0第14页，共23页，编辑于2022年，星期一 c cj j 4 3 0 04 3 0 0C CB BX XB B b b x x1 1 x x2 2 x x3 3 x x4 40 00 0 x x3 3 x x4 424242626 2 3 1 02 3 1 0 3 2 0 1 3 2 0 1 Z Z0 0 4 3 0 04 3 0 0由表得基可行解由表得基可行解:第15页，共23页，编辑于2022年，星期一（二）最优检验二）最优检验第16页，共23页，编辑于202
9、2年，星期一第三步：换基迭代第三步：换基迭代第17页，共23页，编辑于2022年，星期一 第18页，共23页，编辑于2022年，星期一 cj 4 3 0 0CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3 Z 0 4 3 0 004x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3413 Z104/3 0 1/3 0 -4/334x2x1 4 6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 -1/5 -6/5第19页，共23页，编辑于2022年，星期一 1.1.上第一表中上第一表中,x,x1 1
10、为换入变量；为换入变量；又由于比值又由于比值=min(24/2=min(24/2，26/326/3）=26/3,=26/3,确定确定x x4 4为换出变量为换出变量.x.x1 1所在列和所在列和x x4 4所在行的交叉处所在行的交叉处为主元。进行迭代后，为主元。进行迭代后，X X(2)(2)=(26/3,0,20/3,0)=(26/3,0,20/3,0)T T，目标函数值为目标函数值为Z Z（2 2）=104/3=104/3，但不是最优值。，但不是最优值。2.2.第二次迭代第二次迭代x x2 2为换入变量，为换入变量，x x3 3为换出变量。为换出变量。进行迭代后，进行迭代后，X X(1)(1
11、)=(6=(6，4 4，0 0，0)0)T T,因最后一因最后一行的所有检验数都已是正数或零，因此行的所有检验数都已是正数或零，因此 目目标函数值为标函数值为Z Z*=Z=Z（3 3）=36=36是最优值。是最优值。第20页，共23页，编辑于2022年，星期一第21页，共23页，编辑于2022年，星期一 cj 3 1 0 0 0CBXBb x1 x2 x3 x4 x5000 x3X4x54218 1 1 1 0 0 -1 1 0 1 0 6 2 0 0 14-3 Z 0 3 1 0 0 0003x3X4x1153 0 2/3 1 0 -1/6 0 4/3 0 1 1/6 1 1/3 0 0 1/6 Z9 0 0 0 0 -1/2 第22页，共23页，编辑于2022年，星期一 该问题的最优解该问题的最优解X*=（3，0，1，5，0）T最优值最优值Z*=9 注意到：注意到：（1）最终表中有非基变量最终表中有非基变量x2的检验数为的检验数为0，且相应，且相应的列分量中含有正分量，因此，该问题有多重最优解。的列分量中含有正分量，因此，该问题有多重最优解。（2）如果是求如果是求minZ的问题，的问题，只须分别将最优检验只须分别将最优检验中的中的第23页，共23页，编辑于2022年，星期一