INDEX 
d. Résolution d'un programme linéaire
La programmation linéaire peut être utiliser pour résoudre des programmes linéaires de petite taille. On se limite ici à des programmes linéaires du type entiers.
Considérons le programme linéaire suivant
Max 3x1 + 5x2
S.c 3 x1 + 2 x2
£ 94 x1 + 5 x2
£ 11x1
Î IN , x2 Î INLa décision à prendre est de déterminer les valeurs de x1 et x2. On peut assimiler le problème à un programme dynamique à deux étapes, où dans un premier temps, on doit déterminer la valeur de x1, et dans un deuxième temps la valeur de x2. Reste à savoir quels sont les états relatifs à chaque étape ?
Ces états doivent fournir l'information nécessaire pour aider à choisir notre décision.
Une simple réflexion nous amène à considérer, le nombre de ressources non utilisées dans les contraintes, comme étant des états possibles.
Un état est décrit par un vecteur (R1,R2), où R1 et R2 sont respectivement les ressources non utilisées dans la première et la deuxième contrainte.
A l'étape 1, l'unique état possible est S=(9,11).
La structure de base du problème est
étape n étape n+1
(R1,R2) cn xn (R1- a1n xn , R2- a2nxn )
fn((R1,R2), xn) = cn xn +
((R1- a1n xn , R2- a2nxn ))
avec 
(R1,R2) =
{ fn((R1,R2), xn)} pour n=1,2 et 
(R1,R2)=0
Etape 2
A l'étape 2, si on considère toutes les combinaisons possibles des valeurs de R1 et R2 alors on aura à considérer un nombre d'état total égale à 99 états. Or tous ces états ne sont pas réalisables dans le sens qu'on n'aura jamais par exemple dans l'étape 2 l'état (10,8). Ainsi, pour déterminer l'ensemble des états réalisables dans la deuxième étape, il suffit de considérer toutes les valeurs possible de x1 (0,1 et 2), et avoir par conséquence les états suivant: (9,11), (6,7) et (3,3).
|
|
f2 ((R1,R2), x2) = 5 x2 |
||||
|
S |
0 |
1 |
2 |
|
|
|
9,11 |
0 |
5 |
10 |
10 |
2 |
|
6,7 |
0 |
5 |
- |
5 |
1 |
|
3,3 |
0 |
- |
- |
0 |
0 |
Etape 1
On a : f1((R1,R2), x1) == 3 x1 +
((R1- 3 x1 , R2- 4 x1 ))
|
|
f1 ((R1,R2), x1) |
||||
|
S |
0 |
1 |
2 |
|
|
|
9,11 |
10 |
3+5=8 |
6 |
10 |
0 |
La solution optimale est (x1,x2)=(0,2) et la valeur de la fonction objectif est égale à 10.
Exercice 3: Résoudre les programmes linéaires suivants en utilisant la technique de la programmation dynamique:
S.c 8 x1 + 5 x2
£ 242 x1 + 5 x2
£ 13x1
Î IN , x2 Î INLa solution optimale est (x1,x2)=(1,2).
S.c 3 x1 + 2 x2
£ 53 x2 + 2 x3
£ 7x1
Î IN , x2 Î IN , x3 Î INLa solution optimale est (x1,x2,x3)=(1,1,2).
Cliquer ici pour enregistrer le chapitre 7 en format Word sur votre disque dur (436 Ko)
Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com
(s)
(s)