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 $\min\{c^Tx \mid Ax = b, x \in \Bbb{R}_+^n\}$ 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.

  1. Introduce artificial variables $y$ to find an initial BFS: solve $\min\{||y||_1 \mid Ax+y = b, x \in \Bbb{R}_+^n, y \in \Bbb{R}^m\}$ 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.
  2. Solve the original LP by simplex algorithm.

Reference: http://www.maths.qmul.ac.uk/~ffischer/teaching/opt/notes/notes8.pdf

history | excerpt history