La Programmation Linéaire en Nombres Mixtes (PLNM), ou Mixed-Integer Linear Programming (MILP) en anglais, représente une branche avancée de l'optimisation mathématique. Elle étend la capacité de la Programmation Linéaire (PL) classique en permettant à certaines variables de décision d'être des nombres entiers, tandis que d'autres peuvent rester continues.
Cette distinction est fondamentale pour modéliser des problèmes réels complexes qui impliquent à la fois des choix binaires ou discrets ("oui/non", "combien d'unités") et des quantités continues ("quelle proportion", "combien de litres").
- Les variables entières sont idéales pour représenter des décisions indivisibles : par exemple, l'activation ou la désactivation d'une usine (0 ou 1), le nombre d'employés à affecter, ou le choix parmi un ensemble fini d'options.
- Les variables continues, quant à elles, gèrent les quantités qui peuvent prendre n'importe quelle valeur réelle dans un intervalle donné : par exemple, la production d'un volume de liquide, l'allocation de temps ou de ressources financières.
La PLNM est un outil puissant pour aborder des défis d'optimisation dans des domaines variés comme la logistique, la planification de production, la finance et la gestion de projets, où les décisions ont souvent une nature hybride.
Éléments Fondamentaux d'un Problème PLNM
Tout problème de Programmation Linéaire en Nombres Mixtes se structure autour de trois composantes principales :
-
Variables de Décision : Ce sont les inconnues du problème que le modèle doit déterminer. En PLNM, elles se divisent en :
- Variables entières : Pour les choix discrets.
- Variables continues : Pour les quantités mesurables.
-
Fonction Objective : Il s'agit d'une expression linéaire à maximiser (ex: profit, efficacité) ou à minimiser (ex: coût, temps). Elle encapsule l'objectif global de l'optimisation. Sa forme générale est :
\(Z = c_1x_1 + c_2x_2 + \dots + c_nx_n\)où \(c_j\) sont les coefficients de coût ou de profit associés à chaque variable \(x_j\).
-
Contraintes : Ces inégalités ou égalités linéaires définissent les limites et les interdépendances des variables de décision, reflétant les ressources disponibles, les capacités de production, les demandes du marché ou d'autres restrictions opérationnelles.
Formulation Mathématique Standard d'une PLNM
Un problème de PLNM est généralement formulé de la manière suivante :
Objectif :
Maximiser ou Minimiser \(Z = \sum_{j=1}^{n} c_jx_j\)
Sous les contraintes :
\(\sum_{j=1}^{n} a_{ij}x_j \le b_i \quad \text{pour } i = 1, \dots, m\)
Avec les types de variables :
\(x_j \in \mathbb{Z} \quad \text{pour } j \in I \quad \text{(Variables entières)}\)
\(x_j \in \mathbb{R} \quad \text{pour } j \in C \quad \text{(Variables continues)}\)
où \(I\) est l'ensemble des indices des variables entières et \(C\) celui des variables continues.
Méthodes de Résolution Courantes
La résolution des problèmes PLNM est intrinsèquement plus complexe que celle des PL pures, et elle s'appuie sur des algorithmes spécifiques :
- Méthode de Branch and Bound (Séparation et Évaluation) : Cette approche est la pierre angulaire de la résolution des PLNM. Elle décompose récursivement le problème original en sous-problèmes plus petits (branching). Pour chaque sous-problème, elle calcule des bornes (bounding) pour l'objectif. Grâce à ces bornes, l'algorithme peut élaguer des branches entières de l'arbre de rehcerche qui ne peuvent pas contenir de solution optimale, accélérant ainsi la convergence.
- Méthode des Plans Coupants (Cutting Plane Method) : Cette technique débute par la résolution d'une version "relaxée" du problème, où les contraintes d'intégralité sont ignorées. Si la solution obtenue n'est pas entièrement entière, de nouvelles contraintes linéaires (des "plans coupants") sont ajoutées dynamiquement. Ces coupes éliminent des portions du domaine faisable qui ne contiennent pas de solutions entières, sans pour autant exclure de solutions entières valides. Souvent combinée avec Branch and Bound pour former le "Branch and Cut", elle renforce l'efficacité de la résolution.
- Heuristiques et Métaheuristiques : Pour les PLNM de très grande taille ou avec des structures particulièrement difficiles, les méthodes exactes peuvent devenir trop coûteuses en temps de calcul. Des algorithmes heuristiques (comme les algorithmes génétiques, le recuit simulé ou la recherche tabou) sont alors employés pour trouver rapidement des solutions de bonne qualité, bien que sans garantie d'optimalité globale. Ils sont précieux dans de nombreuses applications industrielles où une solution "assez bonne" et rapide est préférable à une solution optimale très lente.
Exemple de Modélisation avec Python et PuLP : Problème de Décision d'Investissement et de Production
Illustrons la PLNM avec un cas classique de décision d'investissement et de production, en utilisant la bibliothèque Python PuLP.
Prérequis : Installez PuLP via pip :
pip install pulp
Description du problème :
Une entreprise envisage de lancer deux nouveaux articles : l'article A et l'article B.
- Pour produire l'article A, un coût fixe d'investissement de 1000 € est requis. Le profit par unité de l'article A est de 80 €.
- Pour produire l'article B, un coût fixe d'investissement de 1500 € est requis. Le profit par unité de l'article B est de 110 €.
Contraintes de ressources hebdomadaires :- Heures machine : 200 heures disponibles. L'article A nécessite 5 heures/unité, l'article B nécessite 7 heures/unité.
- Matières premières : 300 kg disponibles. L'article A nécessite 10 kg/unité, l'article B nécessite 8 kg/unité.
Objectif : Déterminer quels articles produire et en quelle quantité afin de maximiser le profit net total (profit de vente - coûts fixes d'investissement). Implémentation Python :
import pulp
# 1. Initialisation du modèle d'optimisation
modele_prod = pulp.LpProblem("DecisionsProduction", pulp.LpMaximize)
# 2. Définition des variables de décision
# Variables continues pour les quantités de production
qte_article_A = pulp.LpVariable('Quantite_Article_A', lowBound=0, cat='Continuous')
qte_article_B = pulp.LpVariable('Quantite_Article_B', lowBound=0, cat='Continuous')
# Variables binaires pour les décisions d'investissement (0=non, 1=oui)
dec_produire_A = pulp.LpVariable('Decision_Produire_A', cat='Binary')
dec_produire_B = pulp.LpVariable('Decision_Produire_B', cat='Binary')
# 3. Définition de la fonction objectif : Maximiser le profit net
# Profit des ventes - Coûts fixes d'investissement
profit_net = (80 * qte_article_A + 110 * qte_article_B) - \
(1000 * dec_produire_A + 1500 * dec_produire_B)
modele_prod += profit_net, "Profit Net Total"
# 4. Ajout des contraintes
# Contrainte d'heures machine
modele_prod += 5 * qte_article_A + 7 * qte_article_B <= 200, "Contrainte_Heures_Machine"
# Contrainte de matières premières
modele_prod += 10 * qte_article_A + 8 * qte_article_B <= 300, "Contrainte_Matiere_Premiere"
# Contraintes logiques (méthode du "Grand M") :
# La production d'un article n'est possible que si la décision d'investissement est prise.
# M est un nombre suffisamment grand pour ne pas restreindre la production si la décision est "oui".
M_grand = 10000
modele_prod += qte_article_A <= M_grand * dec_produire_A, "Lien_ProdA_InvestA"
modele_prod += qte_article_B <= M_grand * dec_produire_B, "Lien_ProdB_InvestB"
# 5. Résolution du problème
modele_prod.solve()
# 6. Affichage et interprétation des résultats
print(f"Statut de la résolution : {pulp.LpStatus[modele_prod.status]}")
print("-" * 40)
print("Décisions Optimales :")
if dec_produire_A.varValue == 1.0: # Utiliser 1.0 pour comparaison avec float
print(f" - Lancement de l'article A, quantité produite : {qte_article_A.varValue:.2f} unités")
else:
print(" - Pas de lancement de l'article A")
if dec_produire_B.varValue == 1.0:
print(f" - Lancement de l'article B, quantité produite : {qte_article_B.varValue:.2f} unités")
else:
print(" - Pas de lancement de l'article B")
print("-" * 40)
profit_max_obtenu = pulp.value(modele_prod.objective)
print(f"Profit net maximal réalisable : {profit_max_obtenu:.2f} €")
Résultat de l'exécution :
Statut de la résolution : Optimal
----------------------------------------
Décisions Optimales :
- Pas de lancement de l'article A
- Lancement de l'article B, quantité produite : 28.57 unités
----------------------------------------
Profit net maximal réalisable : 1642.86 €