next up previous
Next: About this document ...

IUP MIAGE

IUP3 Recherche Opérationnelle 1

TD2: le 3/10/2000

1.
Combien de fois doit-on calculer les xi d'une solution de base dans la solution d'un programme linéaire:
(a)
en utilisant un parcours naïf des sommets du polytope si le nombre d'itérations était m+n?
(b)
en calculant tous les sommets une fois?
(Donner une formule générale et l'évaluer pour (m,n) égal à (8,4), (16,8) et (32,16)).
2.
Dans le cas d'un parcours des sommets où on choisit toujours le meilleur des sommets voisins, donner un exemple du fait que le chemin peut commencer à un sommet d'un hyperplan qui contient la solution optimale mais sortir de cet hyperplan.
(Et même plus d'une fois)
3.
(a)
Démontrer qu'un polytope en dimension n et à 2n faces peut avoir (au moins) 2n sommets.
(b)
Et qu'il y a un chemin simple qui parcourt tous les sommets.
(c)
Est-il possible qu'un parcours qui choisit à chaque itération un voisin aléatoire avec une valeur de la fonction objective supérieure à celle du sommet actuel suive un tel chemin?




Mike ROBSON
2000-10-03