IUP MIAGE
IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD7: le 3/12/2002
Programmation Linéaire en 0-1
Appliquer l'algorithme de Balas au programme:
x1-x2-2x3-3x4-2x5-x6 £ -3 |
|
-2x1+x2+x3+2x4+3x5+x6 £ 3 |
|
Maximiser -x1-4x2+2x3+2x4-5x5-3x6
(Il faut d'abord le transformer en un programme de minimisation
d'une fonction sans coefficients négatifs)
Rappel de quelques règles de l'algorithme
A un sommet créé
- Si une solution faisable déjà trouvée a une valeur de z
inférieure à l'évaluation de ce sommet, sortir;
- si toutes les contraintes ont une partie droite ³ 0,
noter la solution avec z égal à l'évaluation de ce sommet
et sortir;
- si, dans une contrainte, la somme des coefficients négatifs
est supérieure à la partie droite, sortir;
- si, dans une contrainte, la somme des coefficients négatifs
plus la valeur absolue du coefficient p est supérieure à la
partie droite, la variable p doit être fixée à
0 si son coefficient était positif et à 1 sinon.
(à noter que si le coefficient était négatif il a
déjà été pris en compte dans la somme)
et cette simplification produit un nouveau sommet où on applique
les mêmes règles...
File translated from
TEX
by
TTH,
version 3.05.
On 9 Dec 2002, 16:17.