第一章线性规划&1.6 单纯形法的进一步讨论,运筹学,胡运权,第五版

§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage1of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage1of82020年2月26日星期三前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。一、大M法：【例1.15】用大M法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、、§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage2of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage2of82020年2月26日星期三【解】首先将数学模型化为标准形式5,,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量，x6、，x7，目标函数中加入―MR6―MR7一项，得到人工变量单纯形法数学模型再用前面介绍的单纯形法求解，见下表。7,,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj－§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage3of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage3of82020年2月26日星期三Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M0－Mx6x5x7－4123－1－2121－1000101000014101→j3－2M2+M－1+2M↑－M000－M0－1x6x5x3－6－3253－2001－1000100013→81j5－6M5M↑0－M0020－1x2x5x3－6/53/5－2/5100001－1/53/5－2/50103/531/5→11/5j5↑000023－1x2x1x301010000111025/32/31331/319/3j000－5－25/3§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage4of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage4of82020年2月26日星期三（1）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如(参看第二章第一节)；（2）M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；MMM232)(10)4()(31（3）在第二张中x7已出基，故没有计算第七列的数值，同理，第三、四张表中x6、x7都已出基，故第六、七列没有计算；（4）第三、四张表中的基变量没有人工变量x6、x7，因而检验数中不含M；（5）可以看出，人工变量是帮助我们寻求原问题的可行基，第三张表就找到了原问题的一组基变量x2、x5、x3，此时人工变量就可以从模型中退出，也说明原规划有可行解，但不能肯定有最优解。§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage5of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage5of82020年2月26日星期三【例1.16】求解线性规划0,426385min21212121xxxxxxxxZ【解】加入松驰变量x3、x4化为标准型4,,2,1,0426385max42132121jxxxxxxxxxZZj在第二个方程中加入人工变量x5，目标函数中加上Mx5一项，得到§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage6of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage6of82020年2月26日星期三5,,2,1,0426385max5421321521jxxxxxxxxMxxxZZj用单纯形法计算如下表所示。Cj5－800MbCBXBx1x2x3x4x50Mx3x53※11－2100－1016→4λjM-5↑2M-80-M05Mx1x5101/3－7/31/3－1/30－10122λj029/3-7/3M5/3-1/3M-M0§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage7of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage7of82020年2月26日星期三•表中σj≤0，j=1，2，…，5，从而得到最优解X=（2，0，0，0，2），Z=10+2M。但最优解中含有人工变量x5≠0说明这个解是伪最优解，是不可行的，因此原问题无可行解。§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage8of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage8of82020年2月26日星期三•二、两阶段法•由于大M不是一个确定的数，所以大M法适宜于手工•计算，而不适合求解。为此，引入两阶段法。•第一阶段：•给线性规划加入人工变量，并构造辅助规划。辅助•规划的目标函数为•minw=xn+1+……+xn+m•这里xn+1,……,xn+m为人工变量。§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage9of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage9of82020年2月26日星期三•以人工变量为初始基变量,列表计算。若本阶段无最优解，表示原线性规划无解，停止计算；若有最优解，则转第二阶段。•第二阶段：•在第一阶段最优表中，去掉人工变量，换上原问题目标函数，作为本阶段初始表，以此用单纯形法进行迭代运算，求出结果。mnjxmibxxaxxwjiinnjjijmnn,1,0,,1,min11§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage10of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage10of82020年2月26日星期三•例13用两阶段法求解•minz=x1+5x22x1+3x2≤62x1+x2≥1x1,x2≥0•解：第一阶段：•将问题化为等式约束引进人工变量x5得辅助规划：•minz=x1+5x2+0x3+0x4minw=x52x1+3x2+x3=62x1+3x2+x3=62x1+x2–x4=12x1+x2–x4+x5=1x1,x2,x3,x4≥0x1,x2,x3,x4,x5≥0§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage11of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage11of82020年2月26日星期三minw=x52x1+3x2+x3=62x1+x2–x4+x5=1x1,x2,x3,x4,x5≥0CBXBb0x10x20x30x41x5i0x36231006/21x51[2]10-111/2-2-1010§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage12of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage12of82020年2月26日星期三0x350211-10x11/211/20-1/21/200001§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage13of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage13of82020年2月26日星期三第一阶段有最优解。第二阶段：去掉人工变量，换上原线性规划目标函数（见下表）。最优解：X*=(1/2050)TZ*=1/2CBXBb1x15x20x30x40x3502111x11/211/20-1/209/201/2§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage14of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage14of82020年2月26日星期三几个问题•若存在两个以上相同的最小比值，就会出现退化解。理论上讲，退化解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。。基一般选下标小的变量入基可任取其中一个变量入值，有两个或两个以上相同、检验数相同)(}0{max1jj化情况。，此时出现退上的基变量同时变为一定的时候，有两个以的值增加到变量有相同值，此时在非基、最小比值相同0}0{min2'''iikabixaiki§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage15of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage15of82020年2月26日星期三当计算中出现最小比值相同的情况时，可按Bland规则来计算。Bland规则：①在σj0中，选下标小的非基变量入基；②对相同的最小比值，选下标小的基变量出基。•σj与i的计算同max问题.,,,2,10,minmin3得问题的最优解时数满足当所有非基变量的检验问题对于问题最优解的判别、njzcjjj§1.7单纯形法的进一步讨论Ch1LinearProgrammingPage16of8§1.6单纯形法的进一步讨论Ch1LinearProgrammingPage16of82020年2月26日星期三解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解.无界解的判断:某个σk0且ajk≤０（j=1，2,…,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。