IUP MIAGE
IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD3: le 7/11/2002
- 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):
- en utilisant un parcours naïf des sommets du polytope
si le nombre d'itérations était m+n?
(m+n)nm
- 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)).
384, 3072, 24576 (parcours)
495, 735471, » 2.0 1012 (tous les sommets)
- 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.
- Démontrer qu'un polytope en dimension n
et à 2n faces 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?
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.