运筹学基础-对偶线性规划-2课件.pptVIP

最终单纯形表 【解】 继续迭代得下表 【解】 以此题为例 又例 【解】 (a)第2个约束条件右端项增大到32 继续迭代得下表 【解】 (b)若第2个约束条件变为 6x1+2x2≤24+l 最终单纯形表 【解】 继续迭代得下表 继续迭代得下表 继续迭代得下表 五、增加一个约束条件的分析 得下表 得下表 得下表 【例】上例中 检验数?j b XB CB 比 值 Cj x5 x4 x3 x2 x1 0 0 0 1 2 -15/2 5/4 1 0 0 15/2 -1/2 1/4 0 0 1 7/2 3/2 -1/4 0 1 0 3/2 x2 x1 x3 1 2 0 -1/2 -1/4 0 0 0 -17/2 若增加一个变量x6，有c6=3, P6=(3,4,2)T，试分析最优解的变化。 maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 maxZ=2x1 + x2 +3 x6 5x2 +3x6 ≤15 6x1 + 2x2 +4x6 ≤ 24 x1 + x2 +2x6 ≤ 5 x1 , x2 , x6 ≥0 将其反映到最终单纯形表中得下表 检验数?j b XB CB 比 值 Cj x5 x4 x3 x2 x1 0 0 0 1 2 -15/2 5/4 1 0 0 15/2 -1/2 1/4 0 0 1 7/2 3/2 -1/4 0 1 0 3/2 x2 x1 x3 1 2 0 -1/2 -1/4 0 0 0 -17/2 因s6=10 ,故用单纯形法继续计算 2 1 0 -7 3 x6 增加变量x6，有c6=3, P6=(3,4,2)T，试分析最优解的变化。 检验数sj=cj-zi= cj –y*Pj ， Pj*=B-1Pj 检验数?j b XB CB 比 值 Cj x5 x6 x4 x3 x2 x1 0 3 0 0 1 2 -9/4 0 3/8 1 7/2 0 51/4 -1/2 0 1/4 0 0 1 7/2 3/4 1 -1/8 0 1/2 0 3/4 x6 x1 x3 3 2 0 -5/4 0 -1/8 0 -1/2 0 -37/4 由此得新的解为 x1=7/2， x2=0， x3=51/4， x4=0， x5=0，x6=3/4， Max z*=2×7/2+3×3/4=37/4 四、分析aij变化的影响 假如xj在最终表中为基变量，则aij的变化将使最终表中的B-1变化，因此有可能出现原问题与对偶问题均为非可行解的情况。 【例】上例中， c2=3，x2的系数向量变为P2=(8，4，1)T，试分析最优解的变化。 【解】同上例 maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 maxZ=2x1 +3x2 8x2 ≤15 6x1 + 4x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 检验数?j b XB CB 比 值 Cj x4 x5 x3 x2 x1 0 3 0 1 2 5/4 -15/2 1 0 0 15/2 1/4 -1/2 0 0 1 7/2 -1/4 3/2 0 1 0 3/2 x2 x1 x3 1 2 0 -1/4 -1/2 0 0 0 -17/2 11/2 1/2 1/2 3/2 因原问题与其对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续计算。 将第一行x3+4x4 -24x5= -9 化为标准型-x3-4x4 +24x5=9 再加上人工变量 -x3 -4x4 +24x5 +x6 =9 检验数?j b XB CB 比 值 Cj x5 x4 x3 x‘2 x1 0 0 0 3 2 -24 4 1 0 0 -9 -2 1/2 0 0 1 2 3 -1/2 0 1 0 3 x‘2 x1 x3 3 2 0 -5 1/2 0 0 0 -13 检验数?j b XB CB 比 值 Cj x5 x6 x4 x3 x’2 x1 0