运筹学 单纯形法的进一步讨论

12010年8月管理工程学院《运筹学》1第五节单纯形法的进一步讨论◆人工变量法◆关于解的判别◆单纯形法小结22010年8月管理工程学院《运筹学》2一、人工变量法当线性规划的系数矩阵中不含单位矩阵时，怎么办？可以人为的添加变量，来构造单位矩阵。通过添加人工变量构造单位矩阵的方法，称为人工变量法。1.当约束条件是=时，添加人工变量。2.当约束条件是≥时，可以先添加一剩余变量（实质为松弛变量），然后再添加人工变量。32010年8月管理工程学院《运筹学》3◆大M法人工变量价值系数为“-M”，M为一个任意大的正数。原因：人工变量必须为0，这样当人工变量不为0时，目标函数就不能极大化。42010年8月管理工程学院《运筹学》4例1.9:解线性规划问题目标函数：2132minxxf约束条件：,35021xx,600221xx.0,021xx,1251x52010年8月管理工程学院《运筹学》5用单纯性表格解该线性规划475M-2+2Mi迭代次数Bc7654321xxxxxxx0576xxx11-10010100-10012100100ibBx-2-3000-M-M-M-M0350125600-3+M-M000-M350/1125/1600/2,350..6321xxxxts,6002521xxx0,,,,,,7654321xxxxxxx,125741xxx762132maxMxMxxxz62010年8月管理工程学院《运筹学》6516xxx-M-20100-100112501-1101-1225i迭代次数Bc7654321xxxxxxx0576xxx11-10010100-10012100100ibBxj475M-2-3000-M-M-2+2M-3+M-M-M000-M-M0350125600350/1125/1600/21j110210-13250-3+M-MM-2002-2M225M225/1------350/272010年8月管理工程学院《运筹学》72j516xxx-M-20100-100112501-1101-12251j110210-13500-3+M-MM-2002-2M225M225/1------350/23j416xxx-M-2001/2011/20-117501/2-10-1/2105011/2001/2003000½M-2-M0½M+10-M50M+60050*2300*2175*2412xxx-3-2001-20-12010010101-1025000111-1-112500-40-1-M+4-M800注：由于M为任意大数，x2和x5的检验数可以认为是一样大，这时最好选决策变量入基，而不是松弛、剩余和人工变量入基。82010年8月管理工程学院《运筹学》8所有的检验数都小于等于0，而且人工变量都已出基，已找到最优解。最优解为：.0,0,0,125,0,100,250,,,,,,2132121TTaasssxx最优目标函数值为：.800maxminzf92010年8月管理工程学院《运筹学》9例1.10：用单纯形法求解线性规划问题解：在(1.28b)中添加松弛变量，在(1.28c)中添加剩余变量，再添加人工变量，在(1.28d)中添加人工变量。得线性规划(1.28)可相应表示为：(1.28a)(1.28b)(1.28c)(1.28d)(1.28e)102010年8月管理工程学院《运筹学》10用单纯形法求解过程如下：112010年8月管理工程学院《运筹学》116M-304M+103M-4M0cj-zj30211-10-21-10-110[6]0403-310x430x21-Mx76-2M-34M10-M00cj-zj1111000-2[1]-10-11003100010x44-Mx61-Mx79x1x2x3x4x5x6x7CB基b-30100-M-Mcj→表1-6122010年8月管理工程学院《运筹学》12-3/2000-3/4-M+3/4-M-1/4cj-zj0001-1/2-1/2-1/2-1/2100-1/41/41/43/20103/4-3/41/40x400x25/21x33/200303/2-M-3/2-M+1/2cj-zj0001-1/2-1/2-1/2011/30001/310[2/3]01/2-1/21/60x400x23-3x11x1x2x3x4x5x6x7CB基b-00100-M-Mcj→表1-6续132010年8月管理工程学院《运筹学》13注意：计算时当人工变量出基后不可能再入基，则此变量对应的列下面的数值不用再计算（划红线部分）。区别：大M法中的松弛变量与人工变量142010年8月管理工程学院《运筹学》14◆两阶段法用计算机求解时，由于参数值和M取值上的误差，可能使计算结果发生错误。所以我们介绍两阶段法。152010年8月管理工程学院《运筹学》15阶段1：构造目标函数只包含人工变量的线性规划问题。即令目标函数中其他变量系数取零，人工变量的价值系数取1，目标函数求极小化，约束条件同上。阶段2：当阶段1中目标函数值为0时，即原线性规划有可行解时，从第一阶段的最终单纯形表出发，去掉人工变量，并按原问题的目标函数，继续寻求问题的最优解。162010年8月管理工程学院《运筹学》16例1.10：(两阶段法）阶段1：线性规划问题写为：172010年8月管理工程学院《运筹学》17用单纯形法求解过程如下表1-7：60403-40cj-zj30211-10-21-10-110[6]0403-310x430x21-1x76-2400-100cj-zj1111000-2[1]-10-11003100010x44-1x61-1x79x1x2x3x4x5x6x7CB基b00000-1-1cj→182010年8月管理工程学院《运筹学》18表1-7续00000-1-1cj-zj0001-1/2-1/2-1/2011/30001/3102/301/2-1/21/60x400x230x11x1x2x3x4x5x6x7CB基b00000-1-1cj→阶段2：将表1-7中人工变量x6、x7去掉，目标函数变为：◆注意：此时，检验数要重新计算。192010年8月管理工程学院《运筹学》19-3/2000-3/4cj-zj0001-1/2-1/2100-1/43/20103/40x400x25/21x33/200303/2cj-zj0001-1/2011/30010[2/3]01/20x400x23-3x11x1x2x3x4x5CB基b-30100cj→表1-8大M法和两阶段法简单比较：大M法计算量大但用的表格少；两阶段法计算量少，但用的表格稍多；两阶段法用来判别有无可行解比大M法好。202010年8月管理工程学院《运筹学》20二、关于解的判别◆例(1.2)用单纯形法求解线性规划问题x2x1Q2Q3Q1Q4212010年8月管理工程学院《运筹学》21解：本例用图解法求解时结果为无穷多最优解。用单纯形法求解，先化为标准形式222010年8月管理工程学院《运筹学》22000-200cj-zj001-200.510010-0.5000-412010000.250x322x120x584x23x1x2x3x4x5x6CB基b240000cj→◆由于表中非基变量x6的检验数为0，将其换入基变量得到下表。232010年8月管理工程学院《运筹学》23000-1.500cj-zj001-1-0.25010000.250000-20.510100.5-0.12500x302x140x644x22x1x2x3x4x5x6CB基b230000cj→从表中分别得两个最优解X1=(2,3,2,0,8,0)T，X2=(4,2,0,0,0,4)T，两点连线上的任一点也是最优解，即问题有无穷多最优解。242010年8月管理工程学院《运筹学》24◆说明：当求得一个问题的最优解，有某一非基变量的检验数为0时，问题有无穷多最优解。252010年8月管理工程学院《运筹学》25例1.11用单纯形法求解线性规划问题x2x1262010年8月管理工程学院《运筹学》26解：用图解法求解出本例具有无界解，用单纯形法求解，先化为标准形式272010年8月管理工程学院《运筹学》27用单纯形法计算过程见下表230cj-zj4010x316x1x2x3CB基b230cj→表中σ20，但x2列数字为0，即x2的取值可无限增大。由此目标函数值也无限增大，问题有无界解。282010年8月管理工程学院《运筹学》28◆说明：当某一检验数σi0，对应的Pi列数字全小于或等于0时，xi取值可无限增大，目标值也可无限增大，问题有无界解。292010年8月管理工程学院《运筹学》29例1.12用单纯形法求解线性规划问题302010年8月管理工程学院《运筹学》30解：在图解法中知本例无可行解。将其化为标准形式312010年8月管理工程学院《运筹学》31用单纯形法求解过程见表-1-M0-1.5-M-M0cj-zj110.500-10-1-110x200x522+M3+2M0-M0cj-zj2[2]100110-110x30-Mx53x1x2x3x4x5CB基b2300-Mcj→所有σi≤0，人工变量x5仍留在基变量中且取值不为0，故问题无可行解。322010年8月管理工程学院《运筹学》32◆说明：人工变量法中，当所有检验数σi≤0时，仍有人工变量留在基变量中且取值不为0，问题无可行解。332010年8月管理工程学院《运筹学》33三、单纯形法小结单纯形法基本思路是有选择地取基本可行解，即从可行域一个极点出发，沿可行域边界移到另一个相邻极点，要求新极点目标函数值不比原目标函数值差。◆给定LP先化为标准形式，选取或构造一单位矩阵为基，求出初始可行解列出初始单纯形表。342010年8月管理工程学院《运筹学》34线性规划模型变量约束条件右端项形式目标函数极大或极小xs和xa前的系数xj≥0xj≤0xj取值无约束bj≥0bj0加松弛变量xs时加人工变量xa时化为标准形式不变不变约束条件两端乘“-1”不变352010年8月管理工程学院《运筹学》35◆单纯形法计算步骤框图引进松弛、人工变量列出初始单纯形表计算非基变量检验数所有σj≤0否找出最大的σk0存在aik0是对所有aik0计算θi=bi/aik令θl=min{θi}找出主元素alk迭代运算1.用非基变量xk代替基变量xl2.对主元行（第l行）令bl/alk→bl，alj/alk→alj3.对主元列（k列）令1→alk，0→其他元素4.表中其他行列元素令否无界解是基变量中有0人工变量是无可行解否某非基变量检验数为0是无穷多最优解否唯一最优解