3.3 Starting the method: artificial variables

With constraints \(Ax \leq b\) and \(b \geq 0\) the slacks give a starting BFS at the origin. With \(\geq \) or \(=\) constraints there is no obvious one, and artificial variables are added: for \(Ax = b\) with \(b \geq 0\) (multiply rows by \(-1\) if necessary), solve \[ \text {Phase I:}\quad \text {minimise } \sum _ia_i \quad \text {subject to}\quad Ax + a = b, \quad x, a \geq 0 , \] which starts from the BFS \(x = 0\), \(a = b\). The original problem is feasible if and only if the Phase I optimum is \(0\); then the final basis, after pivoting out any artificial variables left at value \(0\), is a BFS of the original problem, and Phase II continues from it with the true objective. The Big-M method combines the phases by adding \(M\sum a_i\) to the objective with \(M\) large; it is simpler by hand but numerically worse, because \(M\) must be large compared with the data.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.