运筹学_对偶的规划.ppt

4 3 0 0 0 2 b x1‘ x2 x3 x4 x5 x1 2 x1 4 1.25 0 0 0.25 0 1 0 x5 4 0.5 0 -2 0.5 1 0 3 x2 2 0.375 1 0.5 -0.125 0 0 -0.375 0 1.5 0.125 0 0 现在所得到的解仍然是可行解，但不是最优解，以 x1’为换入变量进行变换 4 3 0 0 0 b x1‘ x2 x3 x4 x5 4 x1’ 3.2 1 0 0 0.2 0 0 x5 2.4 0 0 -2 0.4 1 3 x2 0.8 0 1 0.5 -0.2 0 Z=15.2 0 0 1.5 0.2 0 现在所得到的解是最优解，生产I 3.2个单位，II 0.8个单位，获利15.2元 资源数量（右端常数bi）变化 最终单纯形表中解相应地变为 由于b发生变化不影响检验数，对偶问题仍然可行，但是最优解会发生变化。要保证变换后的解还是最优解，即最优基不变，就需要保证变换后得到的解仍然是原问题的可行解，为此需要满足： 问题5：求例1中使最优基保持不变的b1,b2, b3的变化范围。 大家不要死记计算公式，在理解的基础上去求解问题！！！ 推出具体的值。比如课本p62，公式（3-6） cj 1 5 3 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 1/4 0 -13/4 0 1 1/4 -1 100 4 x4 2 0 -2 1 0 1 -1 200 5 x2 -3/4 1 11/4 0 0 -3/4 1 100 13/4 0 11/4 0 0 1/4 1 该值是如何得到的呢？为什么？ 类似的方法，我们可以求b2,b3允许的变化范围(练习） 原最优解变为非可行解，B不再是可行基， 需要重新计算最优解，怎么算呢？？ cj b 1 5 3 4 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 250 1/4 0 -13/4 0 1 1/4 -1 4 x4 350 2 0 -2 1 0 1 -1 5 x2 -50 -3/4 1 11/4 0 0 [-3/4] 1 13/4 0 11/4 0 0 1/4 1 cj b 1 5 3 4 0 0 0 CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 250 0 1/3 -7/3 0 1 0 -2/3 4 x4 850/3 1 4/3 5/3 1 0 0 1/3 0 x6 200/3 1 -4/3 -11/3 0 0 1 -4/3 3 1/3 11/3 0 0 0 4/3 约束条件矩阵元素aij变化 非基变量的系数变化 问题7：在例1所示的线性规划中，x3的系数变为 （1）(1,2,3)T （2）(1,3,2)T 原最优基是否会发生变化？ (1) 最优解不变 cj 1 5 3 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 1/4 0 -13/4 0 1 1/4 -1 100 4 x4 2 0 -2 1 0 1 -1 200 5 x2 -3/4 1 11/4 0 0 -3/4 1 100 13/4 0 11/4 0 0 1/4 1 (2) 最优基发生变化 如何计算新的最优解呢？？？ cj 1 5 3 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 1/4 0 -1/4 0 1 1/4 -1 100 4 x4 2 0 1 1 0 1 -1 200 5 x2 -3/4 1 -1/4 0 0 -3/4 1 100 13/4 0 -1/4 0 0 1/4 1 cj 1 5 3 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 x7 0 x5 3/4 0 0 1/4 1 1/2 -5/4 150 3 x3 2 0 [1] 1 0 1 -1 200 5 x2 -1/4 1 0 1/4 0 -1/2 3/4 150 15/4 0 0 1/4 0 1/2 3/4 Z=1350 基变量系数发生变化 基变量系数发生变化时，最优基发生变化，影响到所有的元素，需要重新运用单纯形法进行计算。 增加新的决策变量xn+1 否则需要在原单纯形表中增加一列，再进行迭代 问题8：在例1中增加变量x8，且p8=(2,5,3)T，c8 分别等于4和5时，最优解是否发生变化？ 新增加的变量为非基变量。 cj 1 5 3 4 0 0 0 5 b CB XB x1 x2 x3 x4 x5 x6 x7 x8 0 x5 1/4 0 -13/4 0 1 1/4 -1 1/4 100 4 x4 2 0 -2 1 0 1 -1 [2] 200 5 x2 -3/4 1 11/4 0 0 -3/