next up previous
Next: About this document ...

IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD3: les 9 et 10/10/2000


1.
En utilisant la méthode décrite dans le cours, calculez une solution réalisable de base pour le problème des pompiers.

Les équations du programme auxiliaire peuvent s'écrire (en supprimant 2 contraintes évidemment inutiles)


x1+x2+y = 60 (1)
x1+x3+y = 100 (2)
x2+x3+y = 120 (3)
x1+x2+x3 = 200 (4)
x1 = 0 (5)
x2 = 0 (6)
x3 = 0 (7)
y = 0 (8)

La solution des base initiale est [0,0,0,120], intersection des équations (3,5,6,7).

Première itération: on essaie les 16 systèmes:
(1,5,6,7) solution [0,0,0,60] non réalisable
(2,5,6,7) solution [0,0,0,100] non réalisable
(4,5,6,7) aucune solution
(5,6,7,8) solution [0,0,0,0] non réalisable
(1,3,6,7) solution [-60,0,0,120] non réalisable
(2,3,6,7) solution [-20,0,0,120] non réalisable
(3,4,6,7) solution [200,0,0,120] non réalisable
(3,6,7,8) aucune solution
(1,3,5,7) aucune solution
(2,3,5,7) solution [0,20,0,100] réalisable
(3,4,5,7) solution [0,200,0,-80] non réalisable
(3,5,7,8) solution [0,120,0,0] non réalisable
(1,3,5,6) solution [0,0,60,60] réalisable
(2,3,5,6) aucune solution
(3,4,5,6) solution [0,0,200,-80] non réalisable
(3,5,6,8) solution [0,0,120,0] non réalisable

Si je choisis la solution (2,3,5,7), la seconde itération commence avec:
(1,3,5,7) aucune solution
(3,4,5,7) solution [0,200,0,-80] non réalisable
(3,5,6,7) solution [0,0,0,120] réalisable
(3,5,7,8) solution [0,120,0,0] non réalisable
(1,2,5,7) solution [0,-40,0,100] non réalisable
(2,4,5,7) solution [0,200,0,-100] non réalisable
(2,5,6,7) solution [0,0,0,100] non réalisable
(1,2,3,7) solution [-60,-40,0,160] non réalisable
(2,3,4,7) solution [90,110,0,10] réalisable
etc.

Et la troisième itération pourrait commencer à (2,3,4,7) et trouver enfin:
(2,3,4,8) solution [80,100,20,0] réalisable et optimale (du programme auxiliaire)
Donc les équations (2,3,4) (mais sans y) donnent la solution réalisable de base [80,100,20] du programme initial.

2.
Si on ajoute au programme auxiliaire de la question 1 deux nouvelles contraintes $x_1+x_2-x_3 \ge 0$ et $-3x_1+2x_2+4x_3 \ge 0$, la solution (0,0,0) devient l'intersection des plans de 5 contraintes. Quels sont les comportements possibles de la version de l'algorithme qui choisit toujours le premier ``sommet'' différent du sommet actuel et qui donne la même valeur de la fonction objective (si aucun sommet voisin ne donne amélioration).

Il faut ajouter les équations des 2 nouvelles contraintes:
x1+x2-x3 = 0     (9)
-3x1+2x2+4x3 = 0    (10).

La solution initiale [0,0,0,120] est l'intersection des 6 équations (3,5,6,7,9,10). Un sous-ensemble de ces 6 mais sans l'équation (3) ne peut pas avoir une solution unique (aucune occurrence de y); donc il y a 10 représentations de ce point comme intersection de 4 contraintes, à savoir (3) et (5,6,7), (5,6,9), (5,6,10), (5,7,9), (5,7,10), (5,9,10), (6,7,9), (6,7,10), (6,9,10) ou (7,9,10).

Il y a les sommets voisins avec une meilleure valeur de -y:
[0,20,20,80] (intersection de (2,3,5,9)
[0,20,0,100] (2,3,5,7)
[114.3, 0,85.7,34.3] (3,4,6,10)
[100,0,100,20] (3,4,6,9).

L'intersection (3,7,9,10) est la seule qui n'est pas voisin d'au moins un de ces sommets et l'algorithme va trouver une sortie de la solution initiale à la deuxième itération dans le pire des cas.




next up previous
Next: About this document ...
Mike ROBSON
2000-10-16