何为线性规划的基本可行解？

Question

如题所述

Answer 1

基本可行解求法如下：

在一个线性规划模型的标准型下，当某个基被选定之后，这个基对应的非基变量值都被令为0，此时这个线性规划模型标准型的约束条件部分就成为了一个仅包含基变量的线性方程组，求解这个线性方程组就可以把此时该基对应的基变量的值求出来。

这种做法求出的所有变量的值，被称为该基对应的基解。

一般地，也常将这种做法得到的该基所有基变量的值称为基解。

当某个基被选定之后，如果计算出该基的基解≥0, 即其中每个基变量的值都是≥0, 则此基解被称为基本可行解。

可行解是满足约束条件的解，基本解对应基向量的非基变量为零，基解不一定为可行解，可行解也不一定为基解，既是可行解又是基本解的解是基本可行解，最优解是基本可行解中使目标函数达到最优的解。

在线性规划问题中，满足非负约束的基本解称为基本可行解或基本可行解。如果线性规划问题存在可行解，则必须存在一个基本可行解。

可行解是基本可行解的充要条件如下：非零分量对应的系数矩阵的列向量是线性无关的。基本可行解对应可行域中的极点，是有限的。如果存在一个有界最优解，至少有一个基本可行解是最优解。