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

提出背景：

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

两阶段方法

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

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

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

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

大M法

在约束中增加人工变量$X_a=(y_1,\dots,y_m)^T$Xa​=(y1​,…,ym​)T，同时在目标函数中加上惩罚项$Me^TX_a$MeTXa​，如下：

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

• 上述线性规划有最优解，且$X_a^* = 0$Xa∗​=0时，原线性规划有最优解为$X^*$X∗
• 上述线性规划有最优解，且$X_a^* \neq 0$Xa∗​​=0时，原线性规划无最优解