第三章 对偶理论和灵敏度分析(第7-8节).ppt

参数线性规划是研究参数（C、b）中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量： 目标函数在某区间内是这个参变量的线性函数。 约束条件在某区间内是这个参变量的线性不等式。 若 C 按(C+ λC*) 或 b 按(b+λb*)连续变化，而目标函数值 z 是参数λ的线性函数时，下式称为参数线性规划： 参数线性规划问题的分析步骤： （1）令λ= 0 求解得最终单纯形表； （2）将λC* 或λb* 项反映到最终单纯形表中去； （3）随λ值的增大或减小，观察原问题或对偶问题： 确定表中现有解（基）允许λ的变动范围。 当λ变动超出该范围时，用单纯形法或对偶单纯形法求取新的解。 （4）重复步骤（3），直到继续增大或减小时，表中的解（基）不再出现变化为止。 例 分析λ值变化时，下述参数线性规划问题最优解得变化。 一、目标函数系数中参数λ的影响分析 解：（1）令λ=0，求出最终单纯形表，如下所示。 -1/2 3/2 -1/2 -15/2 x5 0 -1/4 0 0 0 c j – z j -1/4 0 1 0 3/2 x2 1 1/4 0 0 1 7/2 x1 2 5/4 1 0 0 15/2 x3 0 x4 x3 x2 x1 b XB CB θi 0 0 1 2 cj （2）将λC* 项反映到最终单纯形表中去 -1/2-5/2 λ 3/2 -1/2 -15/2 x5 0 -1/4+1/4 λ 0 0 0 c j – z j -1/4 0 1 0 3/2 x2 1+λ 1/4 0 0 1 7/2 x1 2+λ 5/4 1 0 0 15/2 x3 0 x4 x3 x2 x1 b XB CB θi 0 0 1+2λ 2+λ cj 时表中解为最优。 （3）当λ 1 时，变量 x4 的检验数 0，需将 x4 换入，利用单纯形法继续跌代。 -1/2-5/2 λ 3/2 -1/2 -15/2 x5 0 -1/4+1/4 λ 0 0 0 c j – z j - -1/4 0 1 0 3/2 x2 1+λ 14 1/4 0 0 1 7/2 x1 2+λ 6 [ 5/4 ] 1 0 0 15/2 x3 0 x4 x3 x2 x1 b XB CB θi 0 0 1+2λ 2+λ cj -2-λ 0 1 -6 x5 0 0 1/5-1/5λ 0 0 c j – z j 0 1/5 1 0 3 x2 1+λ 0 -1/5 0 1 2 x1 2+λ 1 4/5 0 0 6 x4 0 x4 x3 x2 x1 b XB CB θi 0 0 1+2λ 2+λ cj 时表中解为最优。 0 -1/8 -3/2 0 0 c j – z j 0 -1/8 1/2 1 0 2 x2 3 1 1/2 -2 0 0 4 x5 0 0 1/4 0 0 1 4 x1 2 x5 x4 x3 x2 x1 b XB CB θi 0 0 0 3 2 cj 原问题的最终单纯形表： 如果变量 x3 的目标函数系数变为 变量 x3 对应的约束条件系数列向量变为 问题的最优解为多少？ 解：x3 在最终单纯形表中为非基变量。 （1） （2） （3）在最终单纯形表中用 列替代 x3列，并不再保留 x3 ： 0 0 1 0 x5 0 -1/8 3/8 0 0 c j – z j 16/3 -1/8 3/8 1 0 2 x2 3 8 1/2 1/2 0 0 4 x5 0 8/5 1/4 [5/4] 0 1 4 x1 2 x4 x2 x1 b XB CB θi 0 4 3 2 cj 即出现了第二种情况（原问题可行，对偶问题不可行）利用单纯形法： 0 0 1 0 x5 0 -1/5 0 0 -3/10 c j – z j -1/5 0 1 -3/10 4/5 x2 3 2/5 0 0 -2/5 12/5 x5 0 1/5 1 0 4/5 16/5 4 x4 x2 x1 b XB CB θi 0 4 3 2 cj 出现了第一种情况（原问题可行，对偶问题也可行），问题达到最优。 3. 原变量 xj（ xj 在最终单纯形表中为基变量）参数 aij 的变化分析 将变量 xj 的变化反映到最终单纯形表上： （1）增加一列 （2）在最终单纯形表中用 列替代 xj 列，将 xj 列从最终单纯形表中删除（基矩阵受影响）； 引入人工变量，编制新的单纯形表，求出最优解 非可行解 非可行解 用对偶单纯形法继续跌代求出最优解 可行解 非可行解 用单纯形法继续跌代求出最优解 非可行解 可行解 问题的最优解或最优基不变 可行解 可行解 结论或继续计算的步骤 对偶问题 原问题 （3）将 变为基变量，并将 列变为单位矩阵， 重新计算各变量的检验数，并