4. Simplex method

The simplex method was developed by G. Dantzig (1947). It comprises two phases:

• phase 1 – initialization: find a feasible basic solution (or detect the impossibility: ${\mathcal{D}}_R=\varphi$ );

• phase 2 – progression: move from one vertex to a neighbouring vertex to increase the objective function F (or detect a non-major objective function F).

The terminology of the simplex method comes from the fact that we call n-simplex, or simply simplex, the convex envelope of a set of n + 1 points (n = 1: a segment, n = 2: a triangle, n = 3: a tetrahedron).

We'll start by describing phase 2, i.e....