IUP MIAGE

IUP3 Recherche Opérationnelle 1

TD2: le 3/10/2000

1. Combien de fois doit-on calculer les x_{i} 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) 2^{n} 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 suit un tel chemin?