IUP MIAGE
IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD3: le 7/11/2002
Le pire cas d'algorithmes de programmation linéaire
- Combien de fois doit-on calculer les xi d'une solution de
base
dans la solution d'un programme linéaire:
- en utilisant un parcours naïf des sommets du polytope
si le nombre d'itérations était m+n? (C'est-à-dire
le parcours très naïf où on calcule à chaque itération
toutes les solutions voisines)
- 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)).
- 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'une hyperface
qui contient la solution optimale à un voisin d'un voisin
de la solution optimale mais ensuite sortir de cette hyperface.
(Et même plusieurs fois)
-
- Démontrer qu'un polytope en dimension n
et à 2n hyperfaces (contraintes) peut avoir
(au moins) 2n sommets.
- Et qu'il y a un chemin simple qui parcourt tous les sommets.
- 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?
File translated from
TEX
by
TTH,
version 3.05.
On 7 Nov 2002, 17:22.