运筹学课件 单纯形法的迭代原理.ppt
运筹学教程四、单纯形法的迭代原理四、单纯形法的迭代原理1、确定初始基可行解、确定初始基可行解 (1)初始可行基的确定初始可行基的确定观观察察法法观观察察系系数数矩矩阵阵中中是是否否含含有有现现成成的单位阵？的单位阵？LP限限制制条条件件中中全全部部是是“”类类型型的的约约束束将将新新增增的的松松弛弛变变量量作作为为初初始始基基变变量量，对应的系数列向量构成单位阵；对应的系数列向量构成单位阵；运筹学教程先将约束条件标准化，再引入非负先将约束条件标准化，再引入非负的人工变量，的人工变量，以人工变量作为初始基变以人工变量作为初始基变量，其对应的系数列向量构成单位阵，量，其对应的系数列向量构成单位阵，称为称为“人造基人造基”；然后用大然后用大M法或两阶段法求解；法或两阶段法求解；线性规划限制条件都是线性规划限制条件都是“”或或“=”类类型的约束型的约束运筹学教程等式约束左端引入人工变量的目的等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个使约束方程的系数矩阵中出现一个单位阵单位阵，用单位阵的每一个列向量对应的决策变量用单位阵的每一个列向量对应的决策变量作为作为“基变量基变量”，这样，出现在单纯形表，这样，出现在单纯形表格中的格中的B(i)列（即约束方程的右边常数）列（即约束方程的右边常数）值正好就是基变量的取值。值正好就是基变量的取值。运筹学教程如果限制条件中既有如果限制条件中既有“”类型的约束，类型的约束，又有又有“”或或“=”类型的约束，怎么办？类型的约束，怎么办？构造单位阵构造单位阵问题问题初始可行基一定要选初始可行基一定要选单位阵单位阵？b列正好就是基变量的取值，因此称列正好就是基变量的取值，因此称b列列为为解答列解答列运筹学教程（2）写出初始基可行解）写出初始基可行解令令非非基基变变量量取取0，基基变变量量对对应应b(i)，一一起起构构成初始基可行解成初始基可行解运筹学教程此时此时LP的标准型为的标准型为运筹学教程在约束条件中的变量系数矩阵中总会有一个单位矩阵在约束条件中的变量系数矩阵中总会有一个单位矩阵在约束条件中的变量系数矩阵中总会有一个单位矩阵在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基初始可行基初始可行基初始可行基：当线性规划的约束条件均为当线性规划的约束条件均为，其松弛变量的系数矩阵为单位，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为矩阵；当线性规划的约束条件均为或或=，为便于找到初始基，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。可行解，构造人工变量，人为产生一个单位矩阵。运筹学教程初始基本可行解：初始基本可行解：初始基本可行解：初始基本可行解：式中式中p p1 1,p,pm m 为基变量为基变量,同其所对应的同其所对应的x x1 1,x,x2 2,.,.,x xm m为基变量；其它变量为基变量；其它变量x xm+1m+1,x,xm+2m+2，,x xn n为非基变量。令所有的非基变量等于零。为非基变量。令所有的非基变量等于零。运筹学教程定义：两个基可行解称为相邻的，如果它们之间变换定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。且仅变换一个基变量。初始基可行解的前初始基可行解的前m m个为基变量，个为基变量，2、基变换、基变换代入约束条件有代入约束条件有运筹学教程系数矩阵的增广矩阵系数矩阵的增广矩阵因为因为p1,pm,是一个基，其他向量是一个基，其他向量pj可以这个基可以这个基的线性组合表示：的线性组合表示：运筹学教程相减，然后乘上一个正数,加上经过整理得到：找到满足约束方程组的另一点：第j个大于0只变换1个变量；前m个变量必须换出1个运筹学教程其中其中是是X X（1 1）的第的第j j个坐标的值，要使个坐标的值，要使X X（1 1）是一个是一个基可行解，对所有的基可行解，对所有的i=1,m,i=1,m,存在存在令这m个不等式至少有一个等号成立，当运筹学教程是一个可行解。因为变量是一个可行解。因为变量x11,x21,xl-11,xl+11,xm1,xj1所对应的向量，所对应的向量，经过重新排列后加行经过重新排列后加行b列形成的增广矩阵为：列形成的增广矩阵为：Lalj(1/alj)=1rL(-al-1j)+rL-10-(bL/aLj)+bL-1运筹学教程所以，所以，P P1 1,P,P2 2,P,Pl-1l-1,P,Pj j,P,Pl+1l+1,P,Pm m,是一个基。是一个基。进行初等行变换，将第进行初等行变换，将第L L行乘上行乘上1/a1/aljlj,再分别乘以再分别乘以-a aijij,(i,(i=1,l-1,l+1,m)=1,l-1,l+1,m)加到各行，增广矩阵加到各行，增广矩阵的左边变成一个单位矩阵，的左边变成一个单位矩阵，运筹学教程、最优性检验和解的判别、最优性检验和解的判别将代入目标函数计算：运筹学教程最优性判别最优性判别、如果所有的检验数，表明现有的顶点对应、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。的基可行解为最优解。、当所有的检验数，又对某个非基变量、当所有的检验数，又对某个非基变量xj的检验数等于，并且可以找到的检验数等于，并且可以找到0,这表明可以找这表明可以找到一个顶点目标函数达到最大，说明到一个顶点目标函数达到最大，说明LP有无穷多个最有无穷多个最优解。优解。、如果存在某个检验数、如果存在某个检验数0,又又0,表明目标函数达到无限，说明表明目标函数达到无限，说明LP有无界解。有无界解。运筹学教程第四节第四节单纯形法计算步骤单纯形法计算步骤第一步：求第一步：求初始基可行解，列出初始单纯初始基可行解，列出初始单纯形表。形表。将将LPLP化为标准型，化为标准型，并加以整理。并加以整理。引入适当的引入适当的松驰变量、剩余变量和人工变量，使约束条件化松驰变量、剩余变量和人工变量，使约束条件化为等式，为等式，并且约束方程组的系数阵中有一个单位并且约束方程组的系数阵中有一个单位阵。阵。运筹学教程 cjc1cmcjcnCB基bx1xmxjxnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn cj-zj00运筹学教程第二步：最优性检验第二步：最优性检验计算检验数，检查：计算检验数，检查：计算检验数，检查：计算检验数，检查：所有检验数是否所有检验数是否所有检验数是否所有检验数是否 0 0 0 0？是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；还有正检验数还有正检验数还有正检验数还有正检验数检查相应系数列检查相应系数列 0 0？是是结束，该结束，该LPLP无界解。无界解。不属于上述两种情况不属于上述两种情况不属于上述两种情况不属于上述两种情况，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？运筹学教程选择（最大）选择（最大）正检验数正检验数正检验数正检验数对应的系数列为对应的系数列为主元列主元列主元列主元列，主元列对应的非，主元列对应的非基变量基变量x xk k 为为换入变量；换入变量；换入变量；换入变量；最小比值最小比值对应的行为对应的行为主元行主元行主元行主元行，主元行对应的基变量，主元行对应的基变量x xl l为为换出变量换出变量换出变量换出变量。主元行和主元列的交叉元素主元行和主元列的交叉元素alklk称为主元素。称为主元素。第三步：基变换第三步：基变换运筹学教程利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基可行解和相完成一次迭代，得到新的基可行解和相应的目标函数值应的目标函数值运筹学教程该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；检验数行全部变为非正值；（得到最优解）得到最优解）或或主元列主元列 0 0（无界）（无界）运筹学教程例题：使用单纯形法求解线性规划问题例题：使用单纯形法求解线性规划问题解：化成标准形式运筹学教程其约束条件系数矩阵的增广矩阵为其约束条件系数矩阵的增广矩阵为p3,p4,p5构成单位矩阵，对应的基变量构成单位矩阵，对应的基变量x3,x4,x5,令非基变量令非基变量x1,x2=0,找到一个初始基可行解找到一个初始基可行解X=(0,0,15,24,5)T,以此列出初始单纯形表以此列出初始单纯形表运筹学教程Cj21000CB基基bX1X2X3X4X50X315051000X424620100X5511001j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)210001=2-(00+06+01)=2;2=1-(05+02+01)=13=0-(01+00+01)=0;4=0-(00+01+01)=05=0-(00+00+01)=0 运筹学教程检验检验数数1和和2均大于均大于0，所以表中的基可行解不是最，所以表中的基可行解不是最优优解。解。12，选择选择最大正最大正检验检验数数对应对应的系数列的系数列为为主元列，主元列，主元列主元列对应对应的非基的非基变变量量X1为换为换入入变变量；量；，运筹学教程Cj21000CB基基bX1X2X3X4X50X315051000X424620100X5511001j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)21000最小比最小比值对应值对应的行的行为为主元行，主元行主元行，主元行对应对应的基的基变变量量X4为换为换出出变变量。得到一个新的基量。得到一个新的基P3,P1,P5，列出新的，列出新的单纯单纯形表，形表，继续计继续计算。算。x12142/601/60014/601-1/601/30-1/30运筹学教程Cj21000CB基基bX1X2X3X4X50X315051002X1412/601/600X5104/60-1/61j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)01/30-1/302最大，最大，X2为进基变量；为进基变量；x21106/40-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2运筹学教程X5为出基变量。P2,P3,P1一个新的基,列出新的单纯形表，继续计算。Cj21000CB基基bX1X2X3X4X50X315/20015/4-15/22X17/21001/4-1/21X23/2010-1/43/2j=Cj-Zj=Cj-(C1a1j+C2a2j+Cmamj)000-1/4-1/2运筹学教程1=02=03=04=0-(05/4+21/4-11/4)=-1/45=0-(-015/2-21/2+13/2)=-1/2所有的所有的0，基变量不含有人工变量，基变量不含有人工变量，所以可行解所以可行解X=(7/2,3/2,15/2,0,0)T为最优解，为最优解，代入目标函数得到代入目标函数得到Z=8.5运筹学教程小结小结1 1、线性规划单纯形法基本原理。、线性规划单纯形法基本原理。2 2、单纯形法计算步骤。、单纯形法计算步骤。作业1.3(1)1.4(1)
