Aller au contenu
Optimisation 2 · L3

Leçon 3 sur 5

Programmation linéaire et méthode du simplexe

Je sais mettre un programme linéaire sous forme standard, relier solutions de base et sommets, dérouler la méthode du simplexe en tableaux, reconnaître les cas particuliers et lire dans le tableau final la solution et les prix duaux.

  • 1 h 30
  • 6 exercices corrigés
  • QCM de 7 questions

À la fin de la leçon, vous saurez :

  • Mettre un programme linéaire sous forme standard avec variables d'écart
  • Relier solutions de base réalisables et sommets du polyèdre admissible
  • Dérouler l'algorithme du simplexe en tableaux (variable entrante, test du rapport, pivot)
  • Reconnaître un problème non borné, une solution multiple, une base dégénérée et savoir démarrer en deux phases
  • Lire la solution optimale et les prix duaux dans le tableau final

Avant de commencer : Leçon 2 (dualité lagrangienne, dual d'un programme linéaire) ; algèbre linéaire (systèmes, rang, pivot de Gauss).

1Je découvre

Mme Bangoura a compris, à la leçon 2, que la production optimale de Kindia Jus est x = (3, 1). Mais elle l'a trouvée en dessinant le polygone des contraintes et en calculant la marge à chaque sommet. Avec deux produits, c'est facile. Avec les quinze références que l'usine prévoit pour l'an prochain (jus, sirops, confitures, fruits séchés) et une trentaine de contraintes (machines, sucre, bouteilles, camions vers Conakry et Mamou), il n'y a plus de dessin possible, et le nombre de sommets se compte en millions.

En 1947, George Dantzig a proposé une idée simple : partir d'un sommet et passer, à chaque étape, à un sommet voisin meilleur, jusqu'à ce qu'aucun voisin ne soit meilleur. C'est la méthode du simplexe, encore au cœur des logiciels de planification utilisés dans l'industrie, les mines et la logistique.

Comment passer méthodiquement d'un sommet à un meilleur, comment savoir qu'on a atteint l'optimum, et que lit-on dans le dernier tableau ?

La suite se lit avec votre compte Kharandi Université

La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.

Voir toutes les leçons de Optimisation 2

Signaler une erreur dans cette leçon

Toutes les leçons de Optimisation 2

Pose ta question à Karamö