Recherche opérationnelle et programmation linéaire

📋 Plan du Cours

1. Formulation d’un programme linéaire
2. Résolution graphique et cas possibles
3. Forme standard et géométrie linéaire
4. Principe de la méthode du simplexe
5. Itérations de la méthode du simplexe
6. Initialisation par phase I
7. Dualité et optimalité

📖 1. Formulation d’un programme linéaire

🔑 Notions clés & Définitions

• Programmation linéaire : Programme qui cherche à maximiser ou minimiser une fonction linéaire de plusieurs variables soumises à des contraintes linéaires.

★ À maîtriser

• Pour produire x tonnes de A et y tonnes de B, avec des stocks de 300 tonnes de M1, 400 tonnes de M2 et 250 tonnes de M3, le profit à maximiser est $P=50x+100y$ sous les contraintes $x+y\leq300$, $2x+y\leq400$, $y\leq250$, $x\geq0$ et $y\geq0$.

Compléments

• La méthode du simplexe a été développée par G. B. Dantzig à partir de 1947.

📖 2. Résolution graphique et cas possibles

★ À maîtriser

• Dans l’exemple de production, le point B(50,250) donne un profit maximal de 27 500 Dh.

• Lorsqu’une solution finie existe, elle se trouve à un sommet du domaine des solutions admissibles.

Compléments