运筹学单纯形法迭代原理.ppt

《运筹学单纯形法迭代原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单纯形法迭代原理三.单纯形法的基本思想1、顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据？转移条件？转移结果？使目标函数值得到改善得到LP最优解，目标函数达

2、到最优值2．需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优——判断标准是什么？解LP问题单纯形法的基本思路：初始可行基：设法在约束矩阵中构造出一个m阶单位阵初始基本可行解检验数进基变量：检验数离基变量：最小比值准则1.确定初始基本可行解LP:？希望在化LP的标准形式时，A中都含有一个m阶单位阵。观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束——将新增的松弛变量(+)作为初始基变量，对应的系数列向量构成单位阵；LP限制条件有“≥”类型的约束——左端新增剩余变量(-)后，再加上一个非负的新变量—人工变量。LP

3、限制条件有“=”类型的约束——直接在左端加上人工变量。在引入人工变量后，与原先的约束方程不完全等价，为此，需要在目标函数上做些“修正”——大M法或两阶段法非基变量取0，算出基变量，搭配在一起构成初始基本可行解：2.建立判别准则判断：初始基本可行解或经过若干次迭代后得到的新基本可行解—当前解—是否为最优解？一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式为：典式若用非基变量表示目标函数的表达式：典式检验数其中（1）最优性判别定理（2）有无穷多个“最优解”的判别定理3、进行基变换（1）进基变量的确定——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函

4、数得到改善。（2）离基变量的确定——在保持解的可行性的前提下，使目标函数较快增大。>=<当时，为使，需要从而，最大可取到最小比值原则则该LP无最优解。离基变量：是可行解！是否还是基本解？是从而，目标函数得到了改善。第四节单纯形表（1）建立初始单纯形表，假定B=I，b≥0设maxZ=c1x1+c2x2+…+cnxn将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0写成增广矩阵的形式-Zx1x2xmxm+1……xn右端检验数行-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB最后一行是检验数行，标出了对应决策变量xj的检验数第一行是价值系数行

5、，标出了决策变量xj的价值系数cj第二行是标示行，标出了表中主体各行的含义。第一列标出了基变量的价值系数。第二列标出了当前基变量的名称。第三列是右端项，前m个元素是当前基本可行解的基变量的取值最小比值准则-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCB将初始数据填入上表，可得到初始单纯形表。观察检验数行，若所有的，则停止计算。否则进行下一步。1.检验当前基本可行解是否为最优解？最优性判别定理2.检验是否为无界解？则该LP无最优解。3.选择进基变量从而xm+t是进基变量，pm+t为进基向量，并称表中pm+t所在的列为主列。4.选择离基变量最小比值准

6、则从而xl是离基变量，并称表中离基变量所在的行为主行。5.基变换主行和主列的交叉元素称为主元素al,m+t-Z0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnmaaaaaass...0...00...1...00............0...10...0...0111,21,211,1++++mmmbxcbxcbxc:::222111clxlbl00...0al,m+1...aln[]主行同除以al,m+t,即将主元素化为1将新的主行的(-ai,m+t)倍分别加到第i行，即将主列的其他元素化为0.将新的主行的倍分别加到最后一行，即

7、将xm+t的检验数化为0.-Z'0-ZXBcjx1x2xmxm+1……xnc1c2cmcm+1……cnCBnmmnmmnmnma'a'a'a'a'a'ss...0...00...1...00............0...10...0...0111,21,211,1++++mmmb'xcb'xcb'xc:::222111cm+txm+tb'm+t00...0a'l,m+1...a'ln''6.回到1,对新解作最优性检验。例：用单纯形法求解线性规划问题解：标准化：以对应的系数列向量构成一单位矩阵，取初始基