next up previous
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?
(m+n)n(m-n)
(b)
en calculant tous les sommets une fois?
$\left( \begin{array}{c}m\\ n\end{array} \right)$
(Donner une formule générale et l'évaluer pour (m,n) égal à (8,4), (16,8) et (32,16)).
192, 1536, 12288 (parcours)
70, 601080390, 1832624140942590464
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. On peut construire un chemin de Pi à Qi à Pi+1 où tous les P sont sur le plan qui coupe le globe en deux et tous les Q sont un peu à l'est. Il y a aussi des lignes Pi-Ri, Ri-Pi+1 Qi-Ri, et Qi-Si avec Ri sur le plan, entre Pi et Pi+1 et un peu au sud-ouest de Qi et Si est au nord de Qi et au sud-ouest de Pi+1. Donc le chemin Pi-Qi-Pi+1 est le chemin trouvé par l'algorithme. En ajoutant des lignes de sorte que toute section de la surface du demi globe entourée des lignes est un triangle, et définissant une contrainte dont l'équation est celle du plan qui contient les trois sommets de chaque triangle, on découvre le programme linéaire avec les propriétés souhaitées.
(Plus facile à démontrer quà décrire en mots!)
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?
Oui.
Je vais construire récursivement, en dimension n un ensemble de 2n points $P_0,P_1,\cdots P_{2^n-1}$ bornée par 2n hyperplans et une fonction linéaire $f_n(x_1,\cdots,x_n)$ telle que fn monte en parcourant le chemin $P_0,P_1,\cdots P_{2^n-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 $P_0,P_1,\cdots P_{2^n-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=2M+1-fn(Pi).
    Donc ces nouveaux points sont sur l'hyperplan $x_{n+1}=2M+1-f_n(x_1,x_2,\cdots,x_n)$.
  • La nouvelle fonction est $f_{n+1}(x_1,\cdots,x_{n+1})=2x_{n+1}+f_n(x_1,\cdots,x_n)$.
    On trouve que fn+1 monte en parcourant $P_0,P_1,\cdots P_{2^n-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)=max+1>max=fn+1(P2n-1),
    fn+1 monte en parcourant $P_{2^n},\cdots P_{2^{n+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(2M+1-fn(Pi-1)-(2M+1-fn(Pi)))+fn(Pi-1)-fn(Pi)=fn(Pi)-fn(Pi-1)>0



next up previous
Next: About this document ...
Mike ROBSON
2000-10-13