为何极小化问题中最优基变量的简约成本为正？

• 为何基本最优变量的简约成本为正？
• 为何在极小化问题中，最优基变量的简约成本为正？

\ENCODING=ISO-8859-1 
\Problem name: IloCplex 
Minimize 
obj: 325255008 y(1) + 207016000 y(2) + 
511.284124007454 x(1,2,1,2,1,1,1,1,1,1) + 
511.284124007454 x(1,2,1,2,1,2,1,1,2,2) + 
511.284124007454 x(1,2,1,2,2,2,2,2,2,2) + 
511.284124007454 x(1,2,2,3,1,1,2,2,2,2) + 
511.284124007454 x(1,2,2,3,1,2,2,2,3,3) + 
511.284124007454 x(1,2,2,3,2,2,3,3,3,3) + 
511.284124007454 x(1,2,3,1,1,1,3,3,3,...

先澄清一个常见的认知：在标准单纯形法逻辑里，最优解中的基变量简约成本通常是0。这是因为构建单纯形表时，我们会通过行变换把目标函数中基变量的系数消去，所以它们的简约成本被置为0。你提到的“基变量简约成本为正”的情况，大概率是遇到了退化最优解的场景，咱们拆解来看：

1. 退化最优解下的特殊情况 #

当最优基解是退化的（也就是至少有一个基变量的取值为0），这时候如果尝试把这个取值为0的基变量换出基、同时引入一个非基变量，目标函数值不会变化（因为退化）。这种情况下，这个取值为0的基变量的简约成本可能呈现为正——本质上它的行为更像“潜在的非基变量”：因为当前取值是0，增加它的取值会导致目标函数上升（对应极小化问题），完全符合非基变量的最优性条件（简约成本非负）。

2. 极小化问题的最优性逻辑 #

对于极小化LP问题，最优解的判定标准是所有非基变量的简约成本都非负：如果某个非基变量的简约成本为负，说明增加它的取值能让目标函数更小，当前解就不是最优的。而基变量的简约成本，在非退化的最优解中一定是0；只有在退化场景下，取值为0的基变量才可能有正的简约成本，这时候它和非基变量的逻辑一致——增加它的取值会让目标函数变大，所以不会被选入基中，当前解依然是最优的。

额外小提示 #

如果你看到基变量简约成本为正，可以先检查该基变量的取值是否为0（退化情况）。另外，有些求解器在输出结果时，可能会因为计算精度或内部定义，对退化基变量的简约成本显示为正而非严格的0，但核心逻辑还是和退化最优解相关。

内容的提问来源于stack exchange，提问作者rbl