线性规划——初始基的确定方法

提出背景：

对于一般线性规划，$A$中未必刚好有一个$m$阶单位矩阵，因此没有现成的初始基可行解

两阶段方法

引入人工变量，构造辅助线性规划

在上述辅助线性规划执行单纯形法，知道找到辅助线性规划的最优解$g^{?}$
①若$g^{?}>0$，则原线性规划无解
②若$g^{?}=0$

• 基变量全在$x_i$中，则基可行解就是原规划的初始基可行解
• 基变量不全在$x_i$中，如$y_k$仍是基变量，则检查单纯形表的第$k$行，若对应原线性规划的半段系数全是0，则可以删掉第$k$行，否则进行换基操作（无论正负，b值应该为0才对）

上述过程完成了第一阶段任务，第二阶段按照上述的初始基可行解，重新计算单纯形表格的判别数和函数值，然后执行单纯形法。

大M法

在约束中增加人工变量$X_a=(y_1,\dots ,y_m{)}^T$，同时在目标函数中加上惩罚项$M{e}^T{X}_a$，如下：

用单纯形法求解上述线性规划

• 上述线性规划有最优解，且$X_a^{?}=0$时，原线性规划有最优解为$X^{?}$
• 上述线性规划有最优解，且$X_a^{?}?=0$时，原线性规划无最优解