Leçon 5 sur 5
Optimisation en nombres entiers et applications à la planification
Je sais modéliser une décision de planification avec des variables entières et binaires, utiliser la relaxation linéaire comme borne, résoudre un petit problème par séparation et évaluation, comprendre le rôle des coupes et faire appel à un solveur.
- 1 h 30
- 6 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Expliquer pourquoi l'arrondi d'une solution continue ne suffit pas
- Modéliser avec des variables binaires (coûts fixes, choix logiques, incompatibilités, implications)
- Utiliser la relaxation linéaire comme borne et mesurer l'écart d'intégrité
- Résoudre un petit programme en nombres entiers par séparation et évaluation, et construire une coupe valide
- Formuler et résoudre un problème de planification de production ou de localisation
Avant de commencer : Leçons 2 et 3 (dualité, programmation linéaire et simplexe).
1Je découvre
La saison des mangues approche. Kindia Jus doit préparer son plan de production des trois prochaines semaines. Les commandes prévues sont de 3, 2 et 4 milliers de litres. Chaque semaine où la ligne de pasteurisation est mise en route, il faut la nettoyer et la régler : supposons que ce lancement coûte 10 millions de GNF, quelle que soit la quantité produite, avec une capacité de 5 milliers de litres par semaine. Garder un millier de litres en chambre froide d'une semaine à l'autre coûte 1 million de GNF.
Faut-il lancer la ligne chaque semaine (coûts de lancement élevés) ou produire en avance (coûts de stockage) ? La décision « lancer ou ne pas lancer » est un oui ou non : elle ne peut pas valoir 0,6. Le simplexe ne suffit plus.
Ce type de question se pose partout : nombre de camions à affréter pour une mine de Boké, choix des dépôts d'une entreprise de distribution, emplois du temps d'un centre de santé, affectation des équipes d'une usine.
Comment modéliser et résoudre des problèmes d'optimisation dont certaines variables doivent être entières, en particulier pour planifier une production ?
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.