Chapitre 2 Algorithme du simplexe
Nous avons présenté au chapitre précédent les grands principes de l'algorithme du
simplexe qui permet de résoudre un programme linéairement mis sous forme standard.
Nous allons à présent appliquer ces principes sur des exemples pour dégager les règles
pratiques de l'algorithme. Comme premier exemple, nous allons prendre le cas de
l'entreprise fabriquant des camions qui nous avait servi d'introduction au chapitre
précédent.
2.1. UN EXEMPLE SIMPLE
Le programme linéaire que nous avions étudié géométriquement au paragraphe I du
premier chapitre était le suivant :
(1)
Nous allons d'abord mettre ce programme sous forme standard, en ajoutant les variables
d'écart
On obtient :
(2)
Nous pouvons à présent appliquer les règles de l'algorithme du simplexe :
1) Trouver une solution de base.
Ici
; il s'agit donc de trouver une solution réalisable, c'est-à-dire
respectant les contraintes (2) telle que 3 variables parmi
soient non
nulles et 2 variables nulles.
Nous avons présenté au chapitre précédent les grands principes de l'algorithme du
simplexe qui permet de résoudre un programme linéairement mis sous forme standard.
Nous allons à présent appliquer ces principes sur des exemples pour dégager les règles
pratiques de l'algorithme. Comme premier exemple, nous allons prendre le cas de
l'entreprise fabriquant des camions qui nous avait servi d'introduction au chapitre
précédent.
2.1. UN EXEMPLE SIMPLE
Le programme linéaire que nous avions étudié géométriquement au paragraphe I du
premier chapitre était le suivant :
(1)
Nous allons d'abord mettre ce programme sous forme standard, en ajoutant les variables
d'écart
On obtient :
(2)
Nous pouvons à présent appliquer les règles de l'algorithme du simplexe :
1) Trouver une solution de base.
Ici
; il s'agit donc de trouver une solution réalisable, c'est-à-dire
respectant les contraintes (2) telle que 3 variables parmi
soient non
nulles et 2 variables nulles.