检验数(Reduced Cost)在线性规划中用于评估非基变量对目标函数值的贡献。以下是检验数的计算方法:
系数向量转置与单位向量的点乘
对于最小化形式的目标函数,非基变量的检验数可以通过将非基变量的系数向量与单位向量进行点乘来计算。
单位向量是一个具有与非基变量对应位置为1,其他位置为0的向量。
检验数计算公式为:`检验数 = 系数向量的转置 × 单位向量`。
单纯形法
单纯形法通过迭代寻找更优的基本可行解,每次迭代都会更新检验数。
检验数计算公式为:`检验数 = 基变量在目标函数中的系数 × 对应系数列的各个值之和 - 非基变量在目标函数中对应的系数`。
闭回路法
闭回路法通过寻找闭回路来计算检验数,闭回路是指从一个非基变量出发,沿水平或垂直方向前进,遇到基变量后转90度继续前进,最终回到出发点形成的回路。
检验数计算公式为:`检验数 = 闭回路上所有奇数顶点对应的单位运价之和 - 所有偶数顶点对应的单位运价之和`。
请根据具体情况选择合适的计算方法来计算检验数