第一章 线性规划与单纯形法第5节精选PPT.ppt

《第一章 线性规划与单纯形法第5节精选PPT.ppt》由会员分享，可在线阅读，更多相关《第一章 线性规划与单纯形法第5节精选PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 线性规划与单纯形法第5节第1页，本讲稿共28页5.1 人工变量法人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量人工变量x xn+1n+1,x,xn+mn+m，得到第2页，本讲稿共28页 以xn+1,，xn+m为基变量，并可得到一个mm单位矩阵。令非基变量x1,xn为零，便可得到一个初始基可行解X(0)=(0,0,0,b1,b2,bm)T因为人工变量是后加入原约束条件的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解原问题有解。若在最终表中当所有cj-zj0，而在其中还有某个非零

2、人工变量，这表示原问题无可行解原问题无可行解。以下讨论如何解含有人工变量的线性规划问题。第3页，本讲稿共28页1大M法在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响；为此假定人工变量在目标函数中的系数为(-M)(M为任意大的正数)，这样目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。第4页，本讲稿共28页例8 现有线性规划问题，试用大M法求解。第5页，本讲稿共28页解解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到这里M是一个任意大的正数。第6页，本讲稿共28页 因本例的目标函数是要求min，

3、所以用所有cj-zj0来判别目标函数是否实现了最小化。用单纯形法进行计算时，见表1-6。第7页，本讲稿共28页在表1-6的最终计算结果表中，表明已得到最优解是：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=-2第8页，本讲稿共28页2.两阶段法用电子计算机求解含人工变量的线性规划问题时，只能用很大的数来代替M，这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。第9页，本讲稿共28页第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量人

4、工变量，并构造仅含人工变量的目标函数和要求实现最构造仅含人工变量的目标函数和要求实现最小化小化。如第10页，本讲稿共28页第一阶段求解用单纯形法求解上述模型：若得到=0，这说明原问题存在基可行解，可以进行第二段计算。否则原问题无可行解，应停止计算。第11页，本讲稿共28页第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第3节单纯形法相同。下面举例说明 第12页，本讲稿共28页例9 试用两阶段法求解线性规划问题 第13页，本讲稿共28页解 先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的

5、数学模型为：第14页，本讲稿共28页第一阶段用单纯形法求解，见表1-7。求得的结果是=0，得到最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因人工变量人工变量x6=x7=0，所以(0，1，1，12，0)T是这线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数。进行第二阶段计算，见表1-8。第15页，本讲稿共28页表 1-7第16页，本讲稿共28页第二阶段计算，见表1-8第17页，本讲稿共28页从表1-8中得到最优解为x1=4,x2=1,x3=9,目标函数值 z=-2.第18页，本讲稿共28页5.2 退化 单纯形

6、法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解。第19页，本讲稿共28页尽管计算过程的循环现象极少出现，但还是有可能的。如何解决这问题?先后有人提出了“摄动法”，“字典序法”。1974年由勃兰特(Bland)提出一种简便的规则，简称勃兰特规则：(1)选取cj-zj0中下标最小的非基变量xk为换入变量，即k=min(jcj-zj0)

7、(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。按勃兰特规则计算时，一定能避免出现循环。证明可参考文献4第20页，本讲稿共28页5.3 检验数的几种表示形式 本书以max z=CX;AX=b,X0为标准型；以cj-zj0，（j=1,2,n）为最优解的判别准则。还有其他的形式。为了避免混淆，现将几种情况归纳如下。第21页，本讲稿共28页设x1,x2,xm为约束方程的基变量，于是可得第22页，本讲稿共28页将它们代入目标函数后，可有两种表达形式第23页，本讲稿共28页判别准则的选择要求目标函数实现最大化时，若用(1-37)式来分析，就得到cj-zj0,（j=1,2，

8、,n）的判别准则。若用(1-38)式来分析，就得到zj-cj0,（j=1,2,n）的判别准则。同样，在要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时分别用cj-zj0或zj-cj0，（j=1,2,n）来判别目标函数已达到最小。读者可按自己的习惯选用。读者可按自己的习惯选用。第24页，本讲稿共28页几种判别准则的汇总，表1-9。第25页，本讲稿共28页5.4 5.4 单纯形法小结单纯形法小结根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-10。分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。第26页，本讲稿共28页 表 1-10第27页，本讲稿共28页(2)对目标函数求max的线性规划问题，用单纯形法计算步骤的框图见图1-9。第28页，本讲稿共28页