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.

LP23

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).

LP24

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.

LP25

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.

LP26

The new linear problem is as follows:

LP27

Publicités