Page 123 - 数学建模算法与应用

第四章 线性规划理论与应用

基向量：基向量是指构成基的列向量。
非基向量：非基向量是指不包含在基中的列向量。

基变量：基变量是指与基向量对应的决策变量。
非基变量：非基变量是指与非基向量对应的决策变量。

基本可行解：基本可行解是指满足所有约束的解，其中非基变量为零，基变
量为正。

最优解：最优解是指在所有可行解中使目标函数最小化的解。

四、线性规划中的定理

线性规划中有一些重要的定理，这些定理为求解线性规划问题提供了理论
基础：
基本可行解定理：如果一个线性规划问题有一个可行解，则必须有一个基本

可行解。
最优解定理：如果一个线性规划问题有一个最优解，那么必须有一个基本可

行解，即最优解。
对偶定理：每个线性规划问题都有一个对偶问题，原问题的最优解等于对偶

问题的最优解法。
互补松弛定理：如果原问题的最优解 x*x* 和对偶问题的最优解答 y*y* 满足
xi*（ATy*-c）i=0xi*（ATy*-c）i=0，则 x*x+ 和 y*y+ 分别是原问题和对偶问题

最优解。
退化解定理：如果线性规划问题有退化解（即具有零基变量的基本可行解），

则可能需要使用改进的单纯形法来求解。

113