IUP MIAGE IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD3: le 7/11/2002

  1. Combien de fois doit-on calculer les xi d'une solution de base dans la solution d'un programme linéaire (où il y a n variables, m contraintes explicites et n contraintes implicites):

    1. en utilisant un parcours naïf des sommets du polytope si le nombre d'itérations était m+n?
      (m+n)nm
    2. en calculant tous les sommets une fois?
      (
      m+n
      n
      )
    (Donner une formule générale et l'évaluer pour (m,n) égal à (8,4), (16,8) et (32,16)).
    384, 3072, 24576 (parcours)
    495, 735471,  » 2.0 1012 (tous les sommets)
  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)
    Considérez un réseau de lignes sur la surface d'un demi globe où le point initial est le pôle sud et la fonction objective monte en allant vers le nord. Deux contraintes restreignent les solutions réalisables entre le plan vertical passant par le méridien de Greenwich et un autre plan parallèle et 1 kilomètre à l'est. sur le méridien de Greenwich, il y a des sommets P1,¼, P179 tous les degrés et un Ri à 0.3 degré au nord de chaque Pi; sur le plan 1 kilomètre à l'est, il y a un sommet Qi à 0.5 degré au nord de Pi et (sauf P1) un autre Si à 0.2 au sud de Pi. Aux antipodes il y a l'image miroir. (Plus facile à démontrer qu'à décrire en mots!) On voit que le meilleur voisin d'un Pi est Qi et que le meilleur voisin de Qi est Pi+1. Donc le chemin trouvé est Sud, P1, Q1, P2, Q2¼, tandis que Sud, P1¼,P179, Nord est un chemin possible restant dans la face des solutions initiale et optimale.

    1. Démontrer qu'un polytope en dimension n et à 2n faces 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?
      Oui.
      Je vais construire récursivement, en dimension n un ensemble de 2n points P0,P1,¼P2n-1 bornée par 2n hyperplans et une fonction linéaire fn(x1,¼,xn) telle que fn monte en parcourant le chemin P0,P1,¼P2n-1 à partir de la valeur fn(P0)=0.
      Pour n=1 c'est trivial.
      Pour construire les points et la fonction en dimension n+1 de ceux de dimension n:

      • Les nouveaux points Pi avec i < 2n sont construits par l'ajout d'une valeur xn+1=0 à l'ancien Pi
      • Soit M la valeur maximum de fn sur les points P0,P1,¼P2n-1, à savoir fn(P2n-1). Le nouveaux point P2n+1-1-i (i < 2n) est construit de l'ancien point Pi en ajoutant la nouvelle valeur xn+1=M+1-fn(Pi).
        Donc ces nouveaux points sont sur l'hyperplan xn+1=2M+1-fn(x1,x2,¼,xn) et les deux nouvelles contraintes sont xn+1 ³ 0 et xn+1 £ M-1-fn(x1,x2,¼,xn).
      • La nouvelle fonction est fn+1(x1,¼,xn+1)=2xn+1+fn(x1,¼,xn).
        On trouve que fn+1 monte en parcourant P0,P1,¼P2n-1 parce que xn+1=0 et donc fn+1 prend la même suite de valeurs que celles de fn sur les anciens Pi,
        fn+1(P2n)=M+1 > M=fn+1(P2n-1),
        fn+1 monte en parcourant P2n,¼P2n+1-1 parce que la terme 2xn+1 monte deux fois plus vite que fn baisse.
        fn+1(P2n+1-i)-fn+1(P2n+1-i-1)=2(xn+1[P2n+1-i]-xn+1[P2n+1-i-1])+fn(Pi-1)-fn(Pi)=2(M+1-fn(Pi-1)-(M+1-fn(Pi)))+fn(Pi-1)-fn(Pi)=fn(Pi)-fn(Pi-1) > 0



File translated from TEX by TTH, version 3.05.
On 7 Nov 2002, 17:24.