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