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

四、单纯形法的迭代原理

1、确定初始基可行解

(1)初始可行基的确定

观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束——将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；四、单纯形法的迭代原理1

先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；

线性规划限制条件都是“≥”或“=”类型的约束——先将约束条件标准化，再引入非负的人工变量，2

等式约束左端引入人工变量的目的

使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。

等式约束左端引入人工变量的目的3①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎么办？构造单位阵

问题②初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为解答列①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型4（2）写出初始基可行解——

令非基变量取0，基变量对应b(i)，一起构成初始基可行解（2）写出初始基可行解——5此时LP的标准型为

运筹学课件单纯形法的迭代原理6在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基：当线性规划的约束条件均为≤，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为≥或=，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。在约束条件中的变量系数矩阵中总会有一个单位矩阵当线性规划的约7初始基本可行解：

式中p1,…,pm为基变量,同其所对应的x1,x2,…..,xm为基变量；其它变量xm+1,xm+2，……,xn为非基变量。令所有的非基变量等于零。初始基本可行解：式中p1,…,pm为基变量,同其所对应的8定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。初始基可行解的前m个为基变量，2、基变换代入约束条件有定义：两个基可行解称为相邻的，如果它们之间变换2、基变换代入9系数矩阵的增广矩阵因为p1,…,pm,是一个基，其他向量pj可以这个基的线性组合表示：系数矩阵的增广矩阵因为p1,…,pm,是一个基，其他向量pj10相减，然后乘上一个正数θ,加上经过整理得到：找到满足约束方程组的另一点：第j个大于0只变换1个变量；前m个变量必须换出1个相减，然后乘上一个正数θ,加上经过整理得到：找到满足约束方程11其中θ是X（1）的第j个坐标的值，要使X（1）是一个基可行解，对所有的i=1,…,m,存在令这m个不等式至少有一个等号成立，当其中θ是X（1）的第j个坐标的值，要使X（1）是一个基可行解12

是一个可行解。因为变量x11,x21,xl-11,xl+11,…………xm1,xj1所对应的向量，经过重新排列后加行b列形成的增广矩阵为：Lalj×(1/alj)=1rL×(-al-1j)+rL-10-(bL/aLj)+bL-1

13所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是一个基。进行初等行变换，将第L行乘上1/alj,再分别乘以-aij,(i=1,…,l-1,l+1,…,m)加到各行，增广矩阵的左边变成一个单位矩阵，所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是14３、最优性检验和解的判别将代入目标函数计算：３、最优性检验和解的判别将代入目标函数计算：15最优性判别１、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。２、当所有的检验数，又对某个非基变量xj的检验数等于０，并且可以找到>0,这表明可以找到一个顶点目标函数达到最大，说明LP有无穷多个最优解。３、如果存在某个检验数>0,又≤0,表明目标函数达到无限，说明LP有无界解。最优性判别１、如果所有的检验数，表明现有的顶点对应的基16

第四节单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。

将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。第四节单纯形法计算步骤第一步：求初始基可行解，列出初始17cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn

cj-zj0…0…cjc1…cm…cj…cnCB基bx1…xm…xj18第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤0？是——结束，该LP无界解。不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？第二步：最优性检验19

选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量xk为换入变量；最小比值对应的行为主元行，主元行对应的基变量xl为换出变量。主元行和主元列的交叉元素alk称为主元素。第三步：基变换选择（最大）正检验数第三步：基变换20

利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基可行解和相应的目标函数值利用矩阵的初等行变换把主元列变成单位向量，主元素变为21该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（无界）

该迭代过程直至下列情况之一发生时停止22例题：使用单纯形法求解线性规划问题解：化成标准形式例题：使用单纯形法求解线性规划问题解：化成标准形式23其约束条件系数矩阵的增广矩阵为p3,p4,p5构成单位矩阵，对应的基变量x3,x4,x5,令非基变量x1,x2=0,找到一个初始基可行解X=(0,0,15,24,5)T,以此列出初始单纯形表其约束条件系数矩阵的增广矩阵为p3,p4,p5构成单位矩阵24Cj21000CB基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

Cj21000CB基bX1X2X3X4X50X315051025检验数σ1和σ2均大于0，所以表中的基可行解不是最优解。σ1>σ2，选择最大正检验数对应的系数列为主元列，主元列对应的非基变量X1为换入变量；，检验数σ1和σ2均大于0，所以表中的基可行解不是最优解。σ126Cj21000CB基bX1X2X3X4X50X315051000X424[6]20100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000θ最小比值对应的行为主元行，主元行对应的基变量X4为换出变量。得到一个新的基P3,P1,P5，列出新的单纯形表，继续计算。

x12142/601/60014/601-1/601/30-1/30Cj21000CB基bX1X2X3X4X50X315051027Cj21000CB基bX1X2X3X4X50X315051002X1412/601/600X510[4/6]0-1/61σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)01/30-1/30σ2最大，X2为进基变量；x21106/40-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2Cj21000CB基bX1X2X3X4X50X315051028X5为出基变量。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/2X5为出基变量。P2,P3,P1一个新的基,列出新的单纯形29σ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=0所有的σ≤0，基变量不含有人工变量，30小结1、线性规划单纯形法基本原理。2、单纯形法计算步骤。作业1.3(1)1.4(1)小结1、线性规划单纯形法基本原理。作业31四、单纯形法的迭代原理

1、确定初始基可行解

(1)初始可行基的确定

观察法——观察系数矩阵中是否含有现成的单位阵？LP限制条件中全部是“≤”类型的约束——将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；四、单纯形法的迭代原理32

先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；

线性规划限制条件都是“≥”或“=”类型的约束——先将约束条件标准化，再引入非负的人工变量，33

等式约束左端引入人工变量的目的

使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。

等式约束左端引入人工变量的目的34①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎么办？构造单位阵

问题②初始可行基一定要选单位阵？b列正好就是基变量的取值，因此称b列为解答列①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型35（2）写出初始基可行解——

令非基变量取0，基变量对应b(i)，一起构成初始基可行解（2）写出初始基可行解——36此时LP的标准型为

运筹学课件单纯形法的迭代原理37在约束条件中的变量系数矩阵中总会有一个单位矩阵初始可行基：当线性规划的约束条件均为≤，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为≥或=，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。在约束条件中的变量系数矩阵中总会有一个单位矩阵当线性规划的约38初始基本可行解：

式中p1,…,pm为基变量,同其所对应的x1,x2,…..,xm为基变量；其它变量xm+1,xm+2，……,xn为非基变量。令所有的非基变量等于零。初始基本可行解：式中p1,…,pm为基变量,同其所对应的39定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。初始基可行解的前m个为基变量，2、基变换代入约束条件有定义：两个基可行解称为相邻的，如果它们之间变换2、基变换代入40系数矩阵的增广矩阵因为p1,…,pm,是一个基，其他向量pj可以这个基的线性组合表示：系数矩阵的增广矩阵因为p1,…,pm,是一个基，其他向量pj41相减，然后乘上一个正数θ,加上经过整理得到：找到满足约束方程组的另一点：第j个大于0只变换1个变量；前m个变量必须换出1个相减，然后乘上一个正数θ,加上经过整理得到：找到满足约束方程42其中θ是X（1）的第j个坐标的值，要使X（1）是一个基可行解，对所有的i=1,…,m,存在令这m个不等式至少有一个等号成立，当其中θ是X（1）的第j个坐标的值，要使X（1）是一个基可行解43

是一个可行解。因为变量x11,x21,xl-11,xl+11,…………xm1,xj1所对应的向量，经过重新排列后加行b列形成的增广矩阵为：Lalj×(1/alj)=1rL×(-al-1j)+rL-10-(bL/aLj)+bL-1

44所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是一个基。进行初等行变换，将第L行乘上1/alj,再分别乘以-aij,(i=1,…,l-1,l+1,…,m)加到各行，增广矩阵的左边变成一个单位矩阵，所以，P1,P2,…,Pl-1,Pj,Pl+1,…,Pm,是45３、最优性检验和解的判别将代入目标函数计算：３、最优性检验和解的判别将代入目标函数计算：46最优性判别１、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。２、当所有的检验数，又对某个非基变量xj的检验数等于０，并且可以找到>0,这表明可以找到一个顶点目标函数达到最大，说明LP有无穷多个最优解。３、如果存在某个检验数>0,又≤0,表明目标函数达到无限，说明LP有无界解。最优性判别１、如果所有的检验数，表明现有的顶点对应的基47

第四节单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。

将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。第四节单纯形法计算步骤第一步：求初始基可行解，列出初始48cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2.cmx1x2.xmb1b2.bm10.000.1a1ja2j.amja1na2n.amn

cj-zj0…0…cjc1…cm…cj…cnCB基bx1…xm…xj49第二步：最优性检验计算检验数，检查：所有检验数是否≤0？

是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤0？是——结束，该LP无界解。不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？第二步：最优性检验50

选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量xk为换入变量；最小比值对应的行为主元行，主元行对应的基变量xl为换出变量。主元行和主元列的交叉元素alk称为主元素。第三步：基变换选择（最大）正检验数第三步：基变换51

利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。完成一次迭代，得到新的基可行解和相应的目标函数值利用矩阵的初等行变换把主元列变成单位向量，主元素变为52该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（无界）

该迭代过程直至下列情况之一发生时停止53例题：使用单纯形法求解线性规划问题解：化成标准形式例题：使用单纯形法求解线性规划问题解：化成标准形式54其约束条件系数矩阵的增广矩阵为p3,p4,p5构成单位矩阵，对应的基变量x3,x4,x5,令非基变量x1,x2=0,找到一个初始基可行解X=(0,0,15,24,5)T,以此列出初始单纯形表其约束条件系数矩阵的增广矩阵为p3,p4,p5构成单位矩阵55Cj21000CB基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

Cj21000CB基bX1X2X3X4X50X315051056检验数σ1和σ2均大于0，所以表中的基可行解不是最优解。σ1>σ2，选择最大正检验数对应的系数列为主元列，主元列对应的非基变量X1为换入变量；，检验数σ1和σ2均大于0，所以表中的基可行解不是最优解。σ157Cj21000CB基bX1X2X3X4X50X315051000X424[6]20100X5511001σj=Cj-Zj=Cj-(C1a1j+C2a2j+…+Cmamj)21000θ最小比值对应的行为主元行，主元行对应的基变量X4为换出变量。得到一个新的基P3