运筹学课件 单纯形法的迭代原理

运筹学教程四、单纯形法的迭代原理1、确定初始基可行解(1)初始可行基的确定观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束——将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；运筹学教程先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；线性规划限制条件都是“≥”或“=”类型的约束——运筹学教程等式约束左端引入人工变量的目的使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。运筹学教程①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎么办？构造单位阵问题②初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为解答列运筹学教程（2）写出初始基可行解——令非基变量取0，基变量对应b(i)，一起构成初始基可行解运筹学教程)...3,2,1(0..11njxbxPtsxcMaxZjnjjjnjjj此时LP的标准型为运筹学教程100010001),,,(21mPPPB在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基：当线性规划的约束条件均为≤，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为≥或=，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。运筹学教程TmTmbbbxxxX)0,...,0,0,,......,,()0,...,0,0,,,,(2100201)0(初始基本可行解：式中p1,…,pm为基变量,同其所对应的x1,x2,…..,xm为基变量；其它变量xm+1,xm+2，……,xn为非基变量。令所有的非基变量等于零。运筹学教程定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。初始基可行解的前m个为基变量，2、基变换TmooxxxX),...,,...,(00201)0(代入约束条件有miiibxp10)...3,2,1(0..11njxbxPtsxcMaxZjnjjjnjjj运筹学教程系数矩阵的增广矩阵mnmjmmmnjmnjmnjmmbaaabaaabaaabpppppp,,1,2,2,21,21,1,11,1121..1.00................0...10......0.....01.........因为p1,…,pm,是一个基，其他向量pj可以这个基的线性组合表示：miiijjpap1运筹学教程miiijjpap1miiibxp1)0(bppaxbxppapjimiijimiiimiiijj10101)(,)(相减，然后乘上一个正数θ,加上经过整理得到：njjjbxp1TmjmjaxaxX)0,...,...,0,,...,(0101)1(找到满足约束方程组的另一点：0)(1miiijjpap第j个大于0只变换1个变量；前m个变量必须换出1个运筹学教程,00ijiaxaljxaaxalijijiji00}0|min{,0上式成立，令)(,0)(,00liliaxiji其中θ是X（1）的第j个坐标的值，要使X（1）是一个基可行解，对所有的i=1,…,m,存在令这m个不等式至少有一个等号成立，当运筹学教程是一个可行解。因为变量x11,x21,xl-11,xl+11,…………xm1,xj1所对应的向量，经过重新排列后加行b列形成的增广矩阵为：mmjljllljljljjmljlbababababababpppppp10000....010000000000100..000.100...............00.......01......111122111121Lalj×(1/alj)=1rL×(-al-1j)+rL-10-(bL/aLj)+bL-1TmjmjaxaxX)0,...,...,0,,...,(0101)1(运筹学教程所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是一个基。进行初等行变换，将第L行乘上1/alj,再分别乘以-aij,(i=1,…,l-1,l+1,…,m)加到各行，增广矩阵的左边变成一个单位矩阵，),...,,,,...,,(),,.,,,,.,(11211111111mljlTjmmjlljlljxxxxxxababababb是相邻的基可行解。与)0()1(XX运筹学教程３、最优性检验和解的判别将代入目标函数计算：)1()0(XX和jjmiijijjmiijijjmiijiimiiizcaccaccZcaxcZxcZ11)0(10)1(10)0(][][运筹学教程最优性判别１、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。２、当所有的检验数，又对某个非基变量xj的检验数等于０，并且可以找到0,这表明可以找到一个顶点目标函数达到最大，说明LP有无穷多个最优解。３、如果存在某个检验数0,又≤0,表明目标函数达到无限，说明LP有无界解。0j0jjjP取值无限，,0,00ijijiaax运筹学教程第四节单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。运筹学教程cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amncj-zj0…0…miininjacc1运筹学教程第二步：最优性检验计算检验数，检查：所有检验数是否≤0？是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤0？是——结束，该LP无界解。不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？运筹学教程选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量xk为换入变量；最小比值对应的行为主元行，主元行对应的基变量xl为换出变量。主元行和主元列的交叉元素alk称为主元素。第三步：基变换}0|{maxjjjklklikikiabaab}0|min{运筹学教程利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基可行解和相应的目标函数值运筹学教程该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（无界）运筹学教程例题：使用单纯形法求解线性规划问题0,52426155.2max212121221xxxxxxxstxxZ解：化成标准形式052426155.0002max515214213254321xxxxxxxxxstxxxxxZ运筹学教程其约束条件系数矩阵的增广矩阵为5100112401026151015054321bpppppp3,p4,p5构成单位矩阵，对应的基变量x3,x4,x5,令非基变量x1,x2=0,找到一个初始基可行解X=(0,0,15,24,5)T,以此列出初始单纯形表运筹学教程Cj21000CB基bX1X2X3X4X50X315051000X424620100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000σ1=2-(0×0+0×6+0×1)=2;σ2=1-(0×5+0×2+0×1)=1σ3=0-(0×1+0×0+0×1)=0;σ4=0-(0×0+0×1+0×1)=0σ5=0-(0×0+0×0+0×1)=0运筹学教程}0|max{jjklklikikiabaab0|min4624)15,624,015min(0|minlklikikiabaab检验数σ1和σ2均大于0，所以表中的基可行解不是最优解。σ1σ2，选择最大正检验数对应的系数列为主元列，主元列对应的非基变量X1为换入变量；，运筹学教程Cj21000CB基bX1X2X3X4X50X315051000X424[6]20100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000θ最小比值对应的行为主元行，主元行对应的基变量X4为换出变量。得到一个新的基P3,P1,P5，列出新的单纯形表，继续计算。x12142/601/60014/601-1/601/30-1/30运筹学教程Cj21000CB基bX1X2X3X4X50X315051002X1412/601/600X510[4/6]0-1/61σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)01/30-1/30σ2最大，X2为进基变量；5.16/41)6/41,6/24,515min(0|minlklikikiabaab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/2σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)000-1/4-1/2运筹学教程σ1=0σ2=0σ3=0σ4=0-(0×5/4+2×1/4-1×1/4)=-1/4σ5=0-(-0×15/2-2×1/2+1×3/2)=-1/2所有的σ≤0，基变量不含有人工变量，所以可行解X=(7/2,3/2,15/2,0,0)T为最优解，代入目标函数得到Z=8.5运筹学教程小结1、线性规划单纯形法基本原理。2、单纯形法计算步骤。作业1.3(1)1.4(1)