Optimisation et Innovation : Programmation en Nombres Entiers (PNE) et Nombres Entiers Mixtes (PNEM)

La recherche opérationnelle est un domaine qui utilise des modèles mathématiques, des statistiques et des algorithmes pour aider à la prise de décision dans la planification et l'opération de systèmes complexes. La programmation en nombres entiers (PNE) et la programmation en nombres entiers mixtes (PNEM) sont deux techniques importantes dans ce domaine, souvent utilisées pour résoudre des problèmes d'optimisation où certaines ou toutes les variables de décision sont contraintes à prendre des valeurs entières.

Programmation en Nombres Entiers (PNE)

La PNE est un cas spécial de programmation linéaire où toutes les variables de décision sont contraintes à prendre des valeurs entières. Cela est souvent nécessaire lorsque les variables de décision représentent des éléments qui ne peuvent pas être divisés, comme des objets ou des personnes.

Exemple de PNE : Problème de Sac à Dos

Supposons que vous ayez un sac à dos pouvant supporter un poids maximum et une série d'objets, chacun ayant un poids et une valeur. Le but est de maximiser la valeur totale des objets dans le sac à dos sans dépasser le poids maximum. Soit xi la variable de décision indiquant si l'objet i est pris (1) ou non (0). Le problème peut être formulé comme suit:

• Fonction objectif: Maximiser ∑n i=1  vi​xi
• Contrainte de poids: ∑n i=1 wixi ​≤W
• Contraintes d'intégrité: xi ​∈{0,1} pour tout i

Prenons un exemple concret pour illustrer ceci. Imaginons que vous avez un sac à dos qui peut supporter un poids maximum de 15 kg et vous avez 5 objets avec les poids et valeurs suivants :

• Objet 1 : poids 3 kg, valeur 10
• Objet 2 : poids 4 kg, valeur 20
• Objet 3 : poids 7 kg, valeur 30
• Objet 4 : poids 8 kg, valeur 40
• Objet 5 : poids 2 kg, valeur 5

Nous voulons maximiser la valeur totale des objets dans le sac à dos sans dépasser le poids maximum de 15 kg.

Les variables de décision sont x1 ,x2, x3, x4, x5, où xi​=1 si l'objet i est choisi et xi=0 sinon.

La fonction objectif, qui vise à maximiser la valeur totale des objets dans le sac, est :

Maximiser Z=10x1+20x2+30x3+40x4+5x5

​

La contrainte de poids s'assure que le poids total des objets choisis ne dépasse pas 15 kg :

3x1+4x2+7x3+8x4+2x5​≤15

Et les contraintes d'intégrité assurent que les variables de décision ne peuvent prendre que les valeurs 0 ou 1 :

xi ∈{0,1} pour tout i=1,2,3,4,5

Pour résoudre ce problème, on utilise généralement un solveur de programmation linéaire en nombres entiers, car il est NP-difficile de le résoudre par des méthodes analytiques pour de grandes instances. Le solveur explorera l'ensemble des solutions possibles pour trouver celle qui maximise la fonction objectif tout en respectant la contrainte de poids et les contraintes d'intégrité.

En termes simples, le solveur va évaluer différentes combinaisons des objets pour déterminer laquelle offre la plus grande valeur sans dépasser la capacité maximale du sac à dos. Ce processus peut impliquer de regarder des combinaisons telles que prendre les objets 1, 2 et 5, ou peut-être les objets 3 et 4, et ainsi de suite, jusqu'à ce que la combinaison optimale soit trouvée.

Voyons comment cela se déroule en calculant effectivement la solution optimale avec un exemple de code Python

from pulp import *

# Définir le problème

prob = LpProblem("Le_Probleme_du_Sac_a_Dos", LpMaximize)

# Définir les variables de décision

x1 = LpVariable("x1", 0, 1, LpInteger)

x2 = LpVariable("x2", 0, 1, LpInteger)

x3 = LpVariable("x3", 0, 1, LpInteger)

x4 = LpVariable("x4", 0, 1, LpInteger)

x5 = LpVariable("x5", 0, 1, LpInteger)

# Fonction objectif

prob += 10*x1 + 20*x2 + 30*x3 + 40*x4 + 5*x5, "ValeurTotale"

# Contrainte de poids

prob += 3*x1 + 4*x2 + 7*x3 + 8*x4 + 2*x5 <= 15, "ContraintePoids"

# Résoudre le problème

prob.solve()

# Afficher le résultat

resultat = {

  "Status": LpStatus[prob.status],

  "Valeur maximale": value(prob.objective),

  "Objets à prendre": {1: x1.varValue, 2: x2.varValue, 3: x3.varValue, 4: x4.varValue, 5: x5.varValue}

}

resultat

Le solveur évalue les différentes combinaisons des objets, en tenant compte à la fois de la contrainte de poids et de l'objectif de maximisation de la valeur. En utilisant un solveur dans un environnement approprié, nous obtenons le statut de la solution (par exemple, optimal), la valeur maximale possible pour les objets sélectionnés dans le sac à dos, et quels objets prendre (représentés par les valeurs 1 pour les objets à prendre et 0 pour ceux à laisser).

Pour résoudre pratiquement ce type de problème, vous pouvez utiliser des logiciels de programmation mathématique comme PuLP en Python, Gurobi, CPLEX, ou un outil en ligne qui permet de résoudre des problèmes de programmation linéaire. Vous définiriez le problème de la même manière que décrit, et le solveur vous fournirait la solution optimale, en indiquant quels objets mettre dans le sac à dos pour maximiser la valeur sans dépasser le poids limite.

Programmation en Nombres Entiers Mixtes (PNEM)

La PNEM est une extension de la PNE où certaines variables sont contraintes à être entières tandis que d'autres peuvent prendre des valeurs continues. Cela est utile pour les problèmes où certaines décisions sont discrètes tandis que d'autres sont continues.

Exemple de PNEM : Planification de Production

Imaginez une usine qui fabrique plusieurs produits. Pour chaque produit, il y a une demande à satisfaire, des coûts de production, et la décision de produire ou non le produit est discrète (oui ou non), tandis que la quantité à produire est continue.

Soit xi la variable de décision représentant la quantité du produit i à produire et yi une variable binaire indiquant si le produit i est produit (1) ou non (0).

• Fonction objectif: Maximiser le profit total, donné par ∑ n i=1 (pi​xi​−ci​xi​)−fiyi, où pi​, ci​, et fi représentent respectivement le prix, le coût de production, et le coût fixe du produit i.
• Contraintes de demande: xi≥di​yi pour tout i, où di est la demande pour le produit i.
• Contraintes d'intégrité et de continuité: yi ​∈{0,1} et xi​≥0 pour tout i.

Un solveur de programmation linéaire en nombres entiers (PLNE) est un outil algorithmique utilisé pour trouver la meilleure solution à des problèmes d'optimisation où les variables de décision doivent prendre des valeurs entières. Ces solveurs utilisent diverses méthodes pour explorer l'ensemble des solutions possibles et identifier celle qui optimise la fonction objectif tout en respectant les contraintes du problème.

Fonctionnement d'un Solveur PLNE

Voici une vue d'ensemble de comment fonctionnent ces solveurs :

1. Formulation du Problème: Le premier pas est de formuler mathématiquement le problème, en définissant une fonction objectif à maximiser ou minimiser et en établissant des contraintes linéaires sur les variables.
2. Branch and Bound (Branche et Limite): Cette méthode est la plus courante dans les solveurs PLNE. Elle consiste à diviser le problème initial en sous-problèmes plus petits (branching) et à évaluer des bornes sur la meilleure solution possible pour ces sous-problèmes (bounding). Si une borne indique qu'un sous-problème ne peut pas contenir la solution optimale, ce sous-problème est éliminé (pruning).
3. Cutting Planes (Plans de Coupe): Cette technique ajoute de nouvelles contraintes linéaires (coupes) pour éliminer des régions de l'espace de recherche sans exclure la solution optimale. Cela aide à réduire l'espace de recherche plus efficacement.
4. Branch and Cut: Une combinaison des deux méthodes précédentes, utilisant à la fois le branchement et l'ajout de coupes pour améliorer l'efficacité de la recherche.
5. Heuristiques: Certains solveurs implémentent des heuristiques pour trouver rapidement des solutions proches de l'optimum. Bien que ces solutions ne soient pas garanties comme étant les meilleures possibles, elles peuvent être suffisamment proches pour être utiles dans la pratique.

Exemples d'Application

• Planification de Production: Un fabricant doit décider du nombre d'unités de chaque produit à fabriquer (des entiers) pour maximiser le profit tout en respectant les contraintes de capacité de production et de demande du marché.
• Problème de Sac à Dos: Comme mentionné précédemment, sélectionner un sous-ensemble d'objets à mettre dans un sac à dos pour maximiser la valeur totale sans dépasser la capacité de poids du sac.
• Routage de Véhicules: Dans un problème de routage de véhicules, une entreprise doit décider des itinéraires que ses véhicules doivent emprunter pour livrer des marchandises aux clients. L'objectif est de minimiser le coût total, comme la distance parcourue, tout en respectant les contraintes comme la capacité des véhicules et les fenêtres de livraison des clients. Les décisions comprennent le nombre de véhicules à utiliser et l'itinéraire de chaque véhicule, qui peuvent être modélisés comme des variables entières ou binaires (par exemple, 1 si un véhicule emprunte une certaine route, 0 sinon).
• Planification d'Horaires: Attribuer des créneaux horaires à des cours dans une université de manière à éviter les conflits pour les étudiants et les enseignants, tout en maximisant l'utilisation des salles de classe.