Optimisation en informatique
Optimisation en informatique
Programmation Linéaire, Mathématiques · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document traite de l'optimisation en informatique, plus précisément de la programmation linéaire en nombres entiers (PLNE). Il s'adresse aux étudiants et chercheurs en optimisation et informatique, souhaitant comprendre les principes, modèles et méthodes de résolution des problèmes d'optimisation combinatoire avec contraintes d'intégralité.
La programmation linéaire en nombres entiers est une forme de programmation linéaire dans laquelle certaines variables doivent prendre des valeurs entières. On distingue :
Maximiser :
x1 + 64.0 x2
Sous contraintes :
50 + x31 ≤ 250 2 4 − ≥ x1 − 3 x1, x2 ≥ 0 et entiers
Le point optimal continu est (1.95, 4.92) avec un objectif de 5.0628, tandis que le point optimal entier est (5, 0) avec un objectif de 5.
La programmation linéaire (PL) et la programmation linéaire en nombres entiers (PLNE) sont très différentes :
Ce cours abordera l'utilité de la PLNE et les méthodes de résolution des PLNE.
Objectif : choisir les emplacements pour construire des usines et entrepôts dans deux villes, Lyon et Toulouse.
| Rentabilité | Coût | |
|---|---|---|
| Usine à Lyon | 9 | 6 |
| Usine à Toulouse | 5 | 3 |
| Entrepôt à Lyon | 6 | 5 |
| Entrepôt à Toulouse | 4 | 2 |
Variables de décision :
Contraintes :
Objectif :
max 9x1 + 5x2 + 6y1 + 4y2
min Z = -9x1 - 5x2 - 6y1 - 4y2
s.c.
y1 + y2 ≤ 1
y1 ≤ x1
y2 ≤ x2
6x1 + 3x2 + 5y1 + 2y2 ≤ 10
x1, x2, y1, y2 ∈ {0,1}
model ExempleBase
uses "mmxprs" ! utilise le solveur Xpress-Optimizer
declarations
x1, x2, y1, y2 : mpvar ! variables
end-declarations
! fonction objectif
Z:= (-9)*x1 -5*x2 -6*y1 -4*y2
! contraintes
y1 + y2 <= 1
y1 <= x1
y2 <= x2
6*x1 + 3*x2 + 5*y1 + 2*y2 <= 10
! variables binaires
x1 is_binary
x2 is_binary
y1 is_binary
y2 is_binary
! résolution
minimize (Z)
writeln("Solution: ", getobjval) ! affichage valeur Z
writeln("valeur de x1 : ", getsol(x1))
writeln("valeur de x2 : ", getsol(x2))
writeln("valeur de y1 : ", getsol(y1))
writeln("valeur de y2 : ", getsol(y2))
end-model
Solution obtenue :
On distingue deux cas :
Pour n variables binaires, il existe 2^n solutions possibles. Par exemple :
L'énumération complète est donc impraticable en optimisation discrète.
On « oublie » la contrainte d’intégralité et on résout le problème en variables continues. Cela donne un programme linéaire classique, résoluble par exemple par la méthode du simplexe.
Exemple sur le modèle de base :
Interprétation :
Si l’on connaît une solution admissible (entière) de valeur Z', alors la valeur optimale entière est comprise entre la valeur optimale de la relaxation continue et Z'.
Exemple :
Le B&B est une méthode efficace pour résoudre les PLNE. Elle combine :
La solution de la relaxation continue n’est pas entière (x1=5/6). On « branche » sur x1 en deux cas :
Chaque cas définit un sous-ensemble de solutions entières à explorer.
On peut élaguer S1 car la solution entière est connue et meilleure que la borne inférieure. Pour S2, on continue à brancher, par exemple sur x2 :
On poursuit avec S4, en branchant sur y1 :
Ensuite, on branche sur y2 dans S5 :
Les autres noeuds sont élagués car leurs bornes inférieures sont supérieures à la meilleure solution courante.
La solution optimale est trouvée avec Z = -14, après avoir exploré un nombre limité de noeuds, bien inférieur à l'énumération complète.
Pour des variables entières non binaires, on choisit une variable fractionnaire x5 = 132.48 par exemple, et on crée deux branches :
Le principal défi est la recherche de solutions admissibles, ce qui est un problème NP-complet en général. Il n’existe pas de méthode rapide générale. Souvent, on se contente des solutions trouvées lors de la résolution des relaxations continues. Des heuristiques comme l’arrondi peuvent être utilisées dans certains cas.
Le temps de calcul dépend du nombre de noeuds explorés, chaque noeud nécessitant la résolution d’un programme linéaire continu.
En général, la résolution d’un programme linéaire continu est rapide, mais la résolution d’un PLNE peut être longue.
Problème avec n=1000 variables binaires générées aléatoirement :