最优化理论复习--对偶单纯形方法及灵敏度分析

2023-12-20 21:41:01

对偶单纯形方法

定义:设 x ( 0 ) x^{(0)} x(0) 是(L)问题的基本解(不一定是可行解(极点)),如果它的对偶问题的解释可行的,则称 x ( 0 ) x^{(0)} x(0) 为原问题的对偶可行基本解
从而衍生出结论:当对偶可行的基本解是原问题的可行解时,由于判别数 < = 0 <= 0 <=0 ,因此,他就是原问题的最优解。

这样在用单纯形法是就不用保证右端项 > = 0 >=0 >=0了, 而是要保证判别数是 < = 0 <=0 <=0

对比:
一般单纯形方法:要保证右端项 > = 0 >= 0 >=0, 尽量将判别数化为 < = 0 <= 0 <=0
对偶单纯形方法:要保证判别数 < = 0 <= 0 <=0, 尽量将右端项化为 > = 0 >= 0 >=0

方法也对称过来了的,步骤变成了先根据最小的右端项 B ? 1 b B^{-1}b B?1b 找出基变量,然后根据 c B N ? c N y j \frac{c^BN - c^N}{y_j} yj?cBN?cN?(比值为正的情况下)最小的检验数比对应系数找入基变量

根据单纯形法最大化问题Max的检验数要都保证 > = 0 >= 0 >=0

在这里插入图片描述
在这里插入图片描述
如果初始问题的对偶可行的基本解不易得到,则需要解一个扩充问题,通过这个问题的求解,给出原问题的解答。了解不考(
在这里插入图片描述

灵敏度分析

f ( x ) = c B B ? 1 b ? ( c B B ? 1 N ? c N ) x N f(x) = c_BB^{-1}b - (c_BB^{-1}N - c_N)x_N f(x)=cB?B?1b?(cB?B?1N?cN?)xN?

x B x_B xB? x N x_N xN?右端
x B x_B xB? I m I_m Im? B ? 1 N B^{-1}N B?1N B ? 1 b B^{-1}b B?1b
f0 c B B ? 1 N ? ? ? c N c_BB^{-1}N\ -\ c_N cB?B?1N???cN? c B B ? 1 b c_BB^{-1}b cB?B?1b

价值系数 c k c_k ck?发生改变

  1. 非基变量的价值系数改变
    在这里插入图片描述
    该非基变量下面的判别数 < = 0 <=0 <=0时最优解不变

  2. 基变量的价值系数发生改变
    在这里插入图片描述
    基变量的价值系数改变后,检验数除了基变量的检验数没有改变外,全都改变了,分析时将价值系数换掉重新计算一下

右端向量b发生改变

b改变 → \rightarrow 基变量的取值发生改变 → \rightarrow 函数值发生改变
分为

  • B ? 1 b ′ > = 0 B^{-1}b'>=0 B?1b>=0判别数没有发生改变,最优解没有发生改变
  • B ? 1 b ′ < 0 B^{-1}b'<0 B?1b<0此时是对偶可行的,将右端项变为 B ? 1 b ′ B^{-1}b' B?1b,目标函数值改为 c B B ? 1 b ′ c_BB^{-1}b' cB?B?1b再使用对偶单纯形方法求解

在这里插入图片描述
问:b在什么范围变化时,最优基不变?
答:当 B ? 1 b ′ > = 0 B^{-1}b'>=0 B?1b>=0是不变


改变约束矩阵

  1. 当发生改变的列不是原来的基矩阵
    那么 B ? 1 B^{-1} B?1也不发生改变,将最优表的系数左乘 B ? 1 B^{-1} B?1,就变成了改变之后的系数,而最右端的系数为 B ? 1 b B^{-1}b B?1b不发生改变,若检验数小于零,最优基不发生改变
    在这里插入图片描述
  2. 当基变量的系数发生了改变,那问题就需要重新计算了

增加新的约束

  1. 若原最优解满足新增加的约束,则它仍是新游戏的最优解
  2. 若原最优解不满足新增加约束
    在这里插入图片描述
    在这里插入图片描述

文章来源:https://blog.csdn.net/m0_64372178/article/details/134864878
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。