For questions about the two phase simplex method, which is an algorithm to solve a linear program which has no initial basic feasible solution.
The two-phase simplex method aims at finding solution(s) for a linear program (LP), which can be expressed as \begin{align}\min\quad& c^\top x\\\text{s.t.}\quad&Ax = b\\\quad& x \in \Bbb{R}_+^n\end{align} for some technology matrix $A \in {\cal M}_{m \times n}(\Bbb{R})$, in case of no obvious basic feasible solution (BFS). This algorithm consists of two stages, from which this algorithm is named.
- Introduce artificial variables $y$ to find an initial BFS: solve \begin{align}\min\quad&\|y\|_1\\\text{s.t.}\quad&Ax+y = b\\\quad&x \in \Bbb{R}_+^n,\\\quad& y \in \Bbb{R}^m\end{align} by using the simplex algorithm with initial BFS $(x,y) = (0,b)$. If the original LP is feasible, one will get $y=0$, so that the BFS is feasible for the original LP.
- Solve the original LP by simplex algorithm.
Reference: QMU London: Two-Phase Simplex Method
