3.3.3 La programmation linéaire mixte (PLM)
Un programme linéaire mixte est un type de
problème d'optimisation linéaire où les variables de
décision peuvent être à la fois des variables continues et
des variables binaires (ou entières). Il peut être formulé
sous la forme suivante :
(PLM)
|
{
|
maximiser z = c1x + c2y
sous contraintes : a1x + a2y < b
x > 0
y E {0,1}(ou y E N)
|
|
3.3.4 La programmation linéaire en nombres
entiers (PLNE)
De nombreux problèmes d'optimisation, issus de
domaines d'applications très divers, peuvent être
modélisés comme des programmes.
Les programmes linéaires ainsi obtenus sont
appelés programmes linéaires en nombres entiers.Ils sont souvent
difficiles à résoudre, du fait notamment que l'espace de
recherche est discret. Toutefois, la programmation linéaire en nombres
entiers est un outil utile de modélisation des problèmes et de
nombreuses approches de résolution ont été
développées. La formulation générale d'un PLNE est
la suivante :
(PLNE)
|
{
|
maximiser z = f(x1, x2, ... , xn)
sous contraintes : gá(x) <
bá; á E C
x E Nn
|
|
Avec gá(x) et bá sont
généralement composés uniquement de valeurs
entières.
Remarque 3.3.2. Dans le cas où
les composantes du vecteur x E Nn sont remplacées
par x E {0,1}n, on dit qu'on a un programme linéaire
en variables booléennes (PL en 0 - 1) qui
3.5 Théorie de la complexité
27
-Page 27-
s'écrit comme suit:
(PLB)
|
?
?????
?????
|
maximiser z = cx
sous contraintes: Ax = b
x E {0, 1}n
|
|
3.4 Théorie de la complexité
La théorie de la complexité s'attache à
classifier les problèmes selon leur difficulté relative à
l'algorithme de résolution, on distingue deux grandes classes de
problème (en terme de complexité), à savoir: Les
problèmes faciles et Les problèmes difficiles.
Les deux paramètres les plus importants pour mesurer
la qualité d'un algorithme sont : le temps de l'exécution de
l'algorithme et l'espace mémoire qu'il prendra pour résoudre un
problème d'une taille donnée.
Définition 3.4.1. Un algorithme
déterministe est un algorithme qui suit une séquence
d'ins-tructions préétablie et n'utilise pas de source de hasard
ou de choix aléatoire pour prendre des décisions.
3.4.1 Classes des problèmes d'optimisation
combinatoire
Les classes des problèmes d'optimisation combinatoire
sont des catégories qui permettent de classifier les problèmes
selon leur complexité et leur difficulté à être
résolus par des algorithmes efficaces.Parmi elles,on trouve:
· La classe "P" : Problèmes
pouvant être résolus en temps polynomial par un algorithme
déterministe.On dit que les problèmes de cette classe sont
faciles.
· La classe "NP" : Problèmes
pour lesquels une solution peut être vérifiée en temps
polynomial, mais pour lesquels il n'est pas clair qu'il existe un algorithme
déterministe qui puisse trouver une solution en temps polynomial.
· La classe "NP-complet":
Problèmes qui sont dans la classe NP et une solution de
celui-ci peut être vérifiée en un temps polynomial.
· La classe "NP-difficile": Un
problème de NP est dit NP-difficile, si et seulement si il existe un
problème NP-Complet qu'est réductible à lui en temps
polynomial.
| 
