运筹学-第一章-单纯形法进一步讨论

运筹帷幄之中决胜千里之外单纯形法进一步讨论窦志武云南财经大学物流学院单纯形法的进一步讨论－人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。例：minz=2x1+3x2maxz=-2x1-3x2+0x3s.tx1+x23标准化s.tx1+x2-x3=3x1+2x2=4x1+2x2=4x10,x20xj0,(j=1,2,3,4)maxz=-2x1-3x2+0x3-Mx4-Mx5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5)引进人工变量，及M——非常大正系数，模型转变为这种处理方法称为大M法，以下则可完全按单纯形法求解。1．大M法单纯形法的进一步讨论－人工变量法单纯形法的进一步讨论－人工变量法例1.10用大M法解下列线性规划012210243423max321321321321321xxxxxxxxxxxxxxxZ、、解：首先将数学模型化为标准形式5,,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：123671234612351237max324342102210,1,2,,7jZxxxMxMxxxxxxxxxxxxxxxjL－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论－人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M-Mx63-650-1013/50x58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——0x531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→jj→jj单纯形法的进一步讨论－人工变量法例1.11用大M法解下列线性规划12312312313123max32114232+10Zxxxxxxxxxxxxxx、、解：首先将数学模型化为标准形式1231234123513max3211423210,1,2,,5jZxxxxxxxxxxxxxxjL系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论－人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：1234567123412356137max3311-42+3210,1,2,,7jZxxxxxMxMxxxxxxxxxxxxxxjL+0+0－其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论－人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-201000113-6M-1+M-1+3M0-M000x4103-20100-1－-Mx610100-11-21-1x31-2010001－1-1+M00-M0-3M+1→→jj单纯形法的进一步讨论－人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70x4123001-22-54-1x210100-11-2－-1x31-2010001－Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3→单纯形法的进一步讨论－两阶段法用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。第一阶段：在原线性规划问题中加入人工变量，构造如下模型：1111111111min00nnmnnnnmmnnnmmxxxxaxaxxbaxaxxbLLLMMOL10nmxxL对上述模型求解（单纯形法），若ω=0,说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。单纯形法的进一步讨论－两阶段法第一阶段的线性规划问题可写为：67123412356137min2=1142321xxxxxxxxxxxxxx127,,0xxx，第一阶段单纯形法迭代的过程见下表单纯形法的进一步讨论－两阶段法Cj00000-1-1CBXBbx1x2x3x4x5x6x70x4111-21100011-1x63-4120-1103/2-1x71-20100011ω46130-1000x4103-20100-1－-1x610100-11-210x31-2010001－ω10100-10-30x4123001-22-50x210100-11-20x31-2010000ω000000-1-1→→单纯形法的进一步讨论－两阶段法第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：x,x,xxxxxxxxxxxxxxxxZmax0123241123721731653214321321，单纯形法的进一步讨论－两阶段法cj3-1-100cBxBbx1x2x3x4x50x4123001-24-1x210100-1－-1x31-20100－Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3→第二阶段：54321003xxxxxZmax∴最优解为（41900），目标函数Z=2单纯形法的进一步讨论通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。无可行解C-3-2-1000-M-MCBXBbx1x2x3x4x5x6x7x8θ0-M-Mx4x7x86431111000010-10-101001-100-1016/1-3/1Z-7M-6-4M-15-M-3+M-2+M-1-2M0-M-M000-M-2x4x7x23431021010-110-10-101001-100-1013/14/1-ZZ-3+M0-3-M0-M-202-M-3-M-2x1x7x23131021010-100-3-1-1-11101-100-101003-3M3-M-M1-M0-1例单纯形法的进一步讨论运算到检验数全负为止，仍含有人工变量，无可行解。单纯形法的进一步讨论无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解无最优解C2200θCXBBx1x2x3x40X31-11100X42-1/2101Z022001=20因但所以原问题无最优解1-1P=01-2单纯形法的进一步讨论退化即计算出的θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）：⑴当存在多个时，选下标最小的非基变量为换入变量；(2)当θ值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。单纯形法的进一步讨论0j无穷多最优解若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例３：最优表：非基变量检验数，所以有无穷多最优解。C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-14=0单纯形法的进一步讨论单纯形法的进一步讨论解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个k0且aik≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。单纯形法的进一步讨论单纯性法小结:建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上xj≥0xj无约束xj≤0bi≥0bi0≤=≥maxZminZxsxa求解图解法、单纯形法单纯形法不处理令xj=xj′-xj″xj′≥0xj″≥0令xj’=-xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z′=-ZminZ=－maxz′0-M停止Ajjjzc:求0j所有kj即找出max)()0(0jika对任一)0(lklkiiaab计算lkxx替换基变量用非基变量新单纯形表列出下一个ax含有量中是否基变0j非基变量的有某个最优解一唯无可行解最优解无穷多是否环循否否否是是是循环无界解