第1章 线性规划与单纯形法 第3节优秀课件.ppt

《第1章 线性规划与单纯形法 第3节优秀课件.ppt》由会员分享，可在线阅读，更多相关《第1章 线性规划与单纯形法 第3节优秀课件.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 线性规划与单纯形法 第3节第1页，本讲稿共37页3.1 举例第2页，本讲稿共37页3.1 举例约束条件的系数矩阵为可看到x3,x4,x5的系数构成的列向量第3页，本讲稿共37页3.1 举例P3,P4,P5是线性独立的，这些向量构成一个基B。对应于B的变量x3,x4,x5为基变量.当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T第4页，本讲稿共37页3.1 举例本基可行解的本基可行解的经济经济含含义义是：工厂没有安排生是：工厂没有安排生产产产产品品、，资资源都没有被利用，所以工厂的利源都没有被利用，所以工厂的利润为润为z=0。非

2、基变量非基变量x1,x2(即没有安排生产产品即没有安排生产产品，)的系数的系数都是正数，因此将非基变量变换为基变量，目标函都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产数的值就可能增大。从经济意义上讲，安排生产产品品或或，就可以使工厂的利润指标增加。所以只，就可以使工厂的利润指标增加。所以只要在目标函数的表达式中还存在有正系数的非基变要在目标函数的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。非基变量与基变量进行对换。第5页，本讲稿共37页3.1 举例如何

3、确定如何确定换换入、入、换换出出变变量量一一般般选选择择正正系系数数最最大大的的那那个个非非基基变变量量x2为为换换入入变变量量，将将它它换换到到基基变变量量中中，同同时时还还要要确确定定基基变变量中哪一个量中哪一个换换出来成出来成为为非基非基变变量。量。可按以下方法来确定可按以下方法来确定换换出出变变量：量：分分析析(1-13)式式，当当将将x2定定为为换换入入变变量量后后，必必须须从从x3,x4,x5中中确确定定一一个个换换出出变变量量，并并保保证证其其余余的的变变量量仍仍然非然非负负，即，即x3,x4,x50。第6页，本讲稿共37页3.1 举例如何确定换入、换出变量当x1=0时，由(1-

4、13)式得到第7页，本讲稿共37页3.1 举例如何确定如何确定换换入、入、换换出出变变量量当当x2取何取何值时值时，才能，才能满满足非足非负负要求呢？要求呢？从从(1-15)式可看出，只有式可看出，只有选择选择 x2=min(8/2,-,12/4)=3时时，才能使，才能使(1-15)式成立。式成立。因因当当x2=3时时，基基变变量量x5=0，这这就就决决定定用用x2去去替替换换x5。第8页，本讲稿共37页3.1 举例为为了求得以了求得以x3,x4,x2为为基基变变量的一个基可行解和量的一个基可行解和进进一步分析一步分析问题问题，需将，需将(1-13)中中x2的位置与的位置与x5的位置的位置对换

5、对换，得到，得到第9页，本讲稿共37页3.1 举例高斯消去法高斯消去法将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：第10页，本讲稿共37页3.1 举例再将(1-17)式代入目标函数式(Z=2x1+3x2)得到第11页，本讲稿共37页 从目标函数的表达式可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即X(1)还不是最优解。再用上述方法确定换入、换出变量，继续迭代，得到另一个基可行解X(2)=(2,3,0,8,0)T再经过一次迭代，又得到一个基可行解X(3)X(3)=(4,2,0,0,4)T (作业，回去自己做）作业

6、，回去自己做）这时得到目标函数的表达式是：z=141.5x3 0.125x4 可见所有非基变量x,x4的系数都是负数，这说明若要用剩余资源x3,x4，就必须支付附加费用。第12页，本讲稿共37页3.1 举例所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件时，工厂可以得到最大利润。第13页，本讲稿共37页小结通过上例，可将每步迭代得到的结果与图解法做一对比。例1的线性规划问题是二维的，即有两个变量x1,x2。当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。该

7、凸多面体上的顶点，就是基可行解。初始基可行解为 X(0)=(0,0,8,16,12)T，对应于图1-2中的原点(0，0)；X(1)=(0,3,2,16,0)T对应于图中的Q4点(0，3)；X(2)=(2，3，0，8，0)T对应于Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图中的 Q2点(4，2)。第14页，本讲稿共37页从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)，相当于图中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。第15页，本讲稿共37页3.1 单纯形表法用例1的标准型来说明单纯形表计算步骤第16页，本讲稿共37页3.

8、1 单纯形表法步骤(1)取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，见下表。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。第17页，本讲稿共37页3.1 单纯形表法第18页，本讲稿共37页表的说明表的说明XB列中填入基变量，这里是列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；它们是与基变量相对应的；b列中填入约束方程组右端的常数；列

9、中填入约束方程组右端的常数；cj行中填入基变量的价值系数行中填入基变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按列的数字是在确定换入变量后，按规则计算后填规则计算后填入；入；最后一行称为检验数行，对应各非基变量最后一行称为检验数行，对应各非基变量xj的检验数的检验数是是第19页，本讲稿共37页3.1 单纯形表法步骤(2)计算非基变量的检验数 各非基变量的检验数为1=c1z1=2(01+04+00)=22=c2z2=3(02+00+04)=3 填入表1-3的底行对应非基变量处。第20页，本讲稿共37页3.1 单纯形表 它它所所在在行行对对应应的的x5为为换换出出变变量量，x2所

10、所在在列列和和x5所所在在行行的的交交叉叉处处4称称为为主元素或枢元素主元素或枢元素(pivot element)第21页，本讲稿共37页3.1 单纯形表步骤(4)以4为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB 列中将x2 替换x5,于是得到新表.第22页，本讲稿共37页3.1 单纯形表步骤(5)检查新表的所有cjzj,这时有c1z1=2；说明x1应为换入变量。重复步骤(2)步骤(4)的计算步骤，得下表。第23页，本讲稿共37页3.1 单纯形表步骤(6)下表最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解第24页，本讲稿共

11、37页3.1 单纯形表 最优解X*=X(3)=(4,2,0,0,4)T；目标函数的最大值 z*=14第25页，本讲稿共37页3.2 初始基可行解的确定(1)直接观察 线性规划问题第26页，本讲稿共37页 从Pj(j=1,2,n)中一般能直接观察到存在一个 初始可行基第27页，本讲稿共37页 (2)加松弛变量对所有约束条件是“”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量，重新编号第28页，本讲稿共37页令xm+1=xm+2=xn=0，则xi=bi(i=1,2,m)，所以得到一个初始基可行解 X=(b1,b2,bm,0,0)T第29页，本讲稿共37页 (3)加非负

12、的人工变量对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量，对等式约束再加上一个非负的人工变量，则可以得到一个单位矩阵。第30页，本讲稿共37页3.33.3最优性检验与解的判别最优性检验与解的判别1 最优解的判别定理 若X(0)=(b1,b2,bm,0,0)T为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。第31页，本讲稿共37页 2.无穷多最优解判别定理若X(0)=(b1,b2,bm,0,0)T为一个基可行解，对于一切j=m+1，,n，有j0，又

13、存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。第32页，本讲稿共37页3无界解判别定理若X(0)=(b1,b2,bm,0,0)T为一基可行解，有 一 个 m+k 0，并 且 对 i=1,2,m，有ai,m+k 0存在,那么该线性规划问题具有无界解(或称无最优解)。第33页，本讲稿共37页3.4 3.4 基变换基变换3.5 3.5 迭代迭代(旋转运算旋转运算)一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到第34页，本讲稿共37页令非基变量xm+1,xm+2,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时为按规则确定xl为换出变量第35页，本讲稿共37页为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过技术约束条件系数矩阵的增广矩阵进行初等变换来实现 第36页，本讲稿共37页经过初等变换后的新增广矩阵是非基变量xm+1,，xl,xn为零时，得到新的基可行解第37页，本讲稿共37页