LP: non origin starting point

The problems of which all the bi are positive are made with Origin Starting Point. It is easy to have a basic solution and the simplex is compatible. For problems that are initially not feasible, we first try to solve the Auxiliary Problem.


In the auxiliary problem, we add an auxiliary variable x0. This variable fits in all constraints. We seek to minimize its value (maximize its opposite).


The first iteration is specific, we force the auxiliary variable to enter the base. The pivot line is the one whose bi is the smallest. The sequel follows the classic resolution of a simplex.


Once the dictionary is optimal, z is expressed as a function of non-basis variables. The origin of the variables in base is then feasible.


The new linear problem is as follows: