IUP MIAGE IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD3: le 7/11/2002
Le pire cas d'algorithmes de programmation linéaire

  1. Combien de fois doit-on calculer les xi d'une solution de base dans la solution d'un programme linéaire:

    1. 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)
    2. 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'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)
    1. Démontrer qu'un polytope en dimension n et à 2n hyperfaces (contraintes) peut avoir (au moins) 2n sommets.
    2. Et qu'il y a un chemin simple qui parcourt tous les sommets.
    3. 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.