1. Forme standard
x + y + e1 = 4 ; x + e2 = 2 ; y + e3 = 3. Les cinq variables sont non négatives. On écrit Z − 3x − 2y = 0. La base initiale est e1, e2, e3 ; x = y = 0.
2. Tableau initial
| Base | x | y | e1 | e2 | e3 | Second membre |
|---|
| e1 | 1 | 1 | 1 | 0 | 0 | 4 |
| e2 | 1 | 0 | 0 | 1 | 0 | 2 |
| e3 | 0 | 1 | 0 | 0 | 1 | 3 |
| Z | -3 | -2 | 0 | 0 | 0 | 0 |
3. Premier pivot
x entre car son coefficient −3 est le plus négatif sur la ligne Z. Les rapports admissibles sont 4/1 = 4 et 2/1 = 2. La ligne e3 est exclue car son coefficient de x est nul. e2 sort ; le pivot vaut 1. Soustraire la ligne pivot à e1 et ajouter trois fois la ligne pivot à Z.
| Base | x | y | e1 | e2 | e3 | Second membre |
|---|
| e1 | 0 | 1 | 1 | -1 | 0 | 2 |
| x | 1 | 0 | 0 | 1 | 0 | 2 |
| e3 | 0 | 1 | 0 | 0 | 1 | 3 |
| Z | 0 | -2 | 0 | 3 | 0 | 6 |
4. Second pivot
y entre. Les rapports positifs sont 2/1 = 2 pour e1 et 3/1 = 3 pour e3 ; e1 sort. Soustraire la ligne pivot à e3 et ajouter deux fois cette ligne à Z.
| Base | x | y | e1 | e2 | e3 | Second membre |
|---|
| y | 0 | 1 | 1 | -1 | 0 | 2 |
| x | 1 | 0 | 0 | 1 | 0 | 2 |
| e3 | 0 | 0 | -1 | 1 | 1 | 1 |
| Z | 0 | 0 | 2 | 1 | 0 | 10 |
5. Lecture et vérification
Avec e1 = e2 = 0, on lit x = 2, y = 2 et e3 = 1. Le gain vaut 3 × 2 + 2 × 2 = 10. Les contraintes donnent 2 + 2 = 4, 2 ≤ 2 et 2 ≤ 3. La ligne finale exprime Z = 10 − 2e1 − e2 : puisque les écarts sont non négatifs, aucune solution réalisable ne peut dépasser 10. L’optimum est donc atteint en (2, 2).