On considère un problème d’optimisation linéaire à n + m variables réelles et m contraintes d’égalité en plus des contraintes de positivité des variables :
où les cj (1 ≤ j ≤ n), aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) et bi (1 ≤ i ≤ m) sont des paramètres réels.Notations. On pose:A = (aik), i ∈ {1, …, m}, k ∈ {1, …, n + m}x = (x1, x2, …, xn+m)tc = (c1, c2, …, cn=m)b = (b1, b2, …, bm)t.
Le problème s’écrit maintenant : Maximiser z = cx avec Ax = b et x ≥ 0.
Cette expression s’appelle parfois la forme canonique d’un problème d’optimisation linéaire. Remarquons qu’un problème sous forme standard prend la forme canonique après introduction des variables d’écart.Suite des notations. Soient xk1, …, xkk m des n + m variables et xkm+1, …, xkm+n les autres variables, on note :xB le vecteur-colonne (xk1, …,xkm)txN le vecteur-colonne (xkm+1, …, xkm+n)tB la matrice formée par les m colonnes de A correspondant aux coefficients de xk1, …,xkm (en respectant l’ordre des variables)AN la matrice formée par les n colonnes de A correspondant aux coefficients de xkm+1, …,xkm+n (en respectant l’ordre des variables)cB le vecteur-ligne (ck1, …. ckm+n …,ckm)cN le vecteur-ligne xkm+1, …,xkm+nProposition 2.1. Les variables xk1 ,…, xkm constituent une base si et seulement si la matrice B correspondante est inversible.Preuve. Le système Ax = b s’écrit BxB + ANxN = b ou encore BxB − ANxN Si B est inversible, Ax = b est équivalent à xB = B−1b − B−1ANxN : xB est bien une base. Réciproquement, si xk1 ,…, …