Chemins optimaux dans graphes algorithme de DANTZIG + programmation java - Recherche Operationnelle


I.             Introduction

1)   Graphe valué.


On dit qu’un graphe G = (X,U) est valué si pour tout arc u  U on fait correspondre un réel l(u).

Si G = (X,U) est graphe valué  u  U. l(u) est appelé longueur ou valuation de l’arc u.

2)   Chemin de longueur optimal.


On appelle problème du chemin optimal le problème suivant :

Trouver un chemin µ allant de sommet x au sommet y tq la longueur de µ :      l(µ) =   soit optimal (optimal = maximum ou minimum)

3) Condition d’existence :


Considérons un chemin de x à y : µ comprenant un circuit w de longueur négatif qui s’appel un circuit absorbant.

Soit µ’ le chemin de x à y sans emprunter le circuit w. Soit µ1 le chemin de x à y en utilisant n fois le circuit w. 

Donc le chemin min n’existe pas

Exemple: circuit de longueur négatif



La longueur du circuit suivant est -2. C’est donc un circuit absorbant.


1) Exemples :


Considérons la carte routière et cherchons la route la plus courte d’une localité à une autre.

Le graphe est obtenu de la façon suivante :

-         Sommets correspondre aux localités

-         Arcs correspondre aux routes (A chaque route on fait correspondre 2 arcs de sens opposés)

recherche operationnelle

II.              Algorithmes de résolution


Le problème du plus court chemin a été résolu par de nombreux algorithmes. Parmi ces algorithmes on peut trouver l’algorithme de

Ford, algorithme de DANTZIG(ou de MOORE-DIJKSTRA), algorithme de BELLMAN, etc. Différents problèmes peuvent être posés autour de la recherche de plus court chemin.







i.             Un premier problème consiste à rechercher le plus court chemin entre deux points donnés. C’est-à-dire déterminer le chemin de plus petite longueur qui relie ces points.

ii.             Un deuxième problème consiste à déterminer, à partir d’un point donné le plus court chemin pour aller à tous les autres

sommets.

iii.      Enfin, un troisième problème consiste à trouver, pour n’importe quelle paire de sommets, le chemin le plus court entre eux.

1)    Algorithme de Ford.


On suppose que le graphe G ne contient pas de circuit négatif G = (X,U) |X| = n.

1.     Numéroter  les  sommets  dans  un  ordre  quelconque  à

l’exception de l’origine et l’extrémité du chemin qui doivent être numérotés respectivement x1 et xn

2.     Affecter provisoirement, à tout sommet xi un poids λi
0
si
i = 1

t.q λi  =
si
i>1

+ ∞




            3. Calculer de proche les différences      λj – λi  pour tout arc
(xi,xj) , et remplacer λj       par  λi + l(i,j) si λj – λi  >l(i,j)
4.     Arrêter la procédure lorsqu’aucun λi  ne peut plus être

modifié.
Soit λn* la valeur final de λn. Donc la valeur du chemin minimal est λn*.

2)    Algorithme de DANTZIG

Soit x1 l’origine et xn l’extrémité entre lesquels on désire connaitre le chemin de longueur minimale [ l(u) ≥ 0,  u  U G = (X,U)]
(a)           λ1 = 0 E {x1}
(b)      xi  on associe xi*  Ē = X – E         t. q


(c) On pose
 

Puis on revient à (b) jusqu’on atteint xn (si l’on veut seulement déterminer le chemin de v0 minimale entre x1 et xn). Ou bien quand E = X (dans le cas où on désire connaitre les chemins de valeurs minimale entre x1 et xi
xi  X – { x1 }.

III.             Implémentation de l’algorithme de DANTZIG.


Cet algorithme détermine la plus courte distance entre tous les couples de sommets d’un graphe valué G = (X,U). On suppose que le graphe ne contient pas de circuit absorbant. On commence par numéroter les sommets d’une manière quelconque. Ensuite, une matrice nommée MatMin de taille n x n (n= nombre de sommets) est construite indiquant pour chaque sommet la plus courte distance qui le sépare d’un autre sommet. L’idée est de considérer un sous-graphe pour lequel on détermine les plus courtes distances entre ses sommets. Ensuite, itérativement, on rajoute un sommet dans ce sous-graphe, on met les plus courtes distances à jour et on recommence jusqu’à ce que le sous-graphe soit le graphe lui même. Rappelant que dans ce TP on s’intéressera aux problèmes de type (iii).

A l’itération k, le sous-graphe a k sommets et ce sont ceux numérotés de 1 à k. A l’itération k + 1, on ajoute le sommet k + 1 dans le sous-graphe. Les distances sont mises à jour de la manière suivante. Tout d’abord on détermine la plus courte distance entre le sommet k + 1 et n’importe quel autre sommet. Cela s’exprime par:
MatMin(k + 1, i)  = min{d(xk + 1,xj) + MatMin(j,i)} pour  i allant de
1 jusqu’à k. Cela veut dire que l’on considère que pour aller de k + 1 à i, on passe par un des sommets de 1 à k. On conserve la longueur du plus court chemin. De la même manière, on détermine




la plus courte distance entre n’importe quel sommet et le sommet k + 1.
MatMin(i,k + 1)  = min{d(xj,xk + 1) + MatMin(i,j)} pour i = 1...k.

Enfin, on met à jour la plus courte distance de chaque sommet de 1 à k vers chaque sommet de 1 à k car peut être que le plus court chemin entre deux de ces sommets passe par k + 1.

MatMin(i,j) = min{MatMin(i,j) , MatMin(i,k + 1) + MatMin(k + 1,j)} pour i, j = 1...k.

Algorithme

Entrées: G = (X,U) un graphe.

Sorties: MatMin une matrice contenant les plus courtes distances.
Début

pour i  1 à n faire pour j  1 à n faire

si i = j alors MatMin(i,i)  0; sinon MAtMin(i,j)  +∞;

fin pour; fin pour;
pour k  1 à n faire
pour i  1 à k - 1 faire 
MatMin(k,i)min{d(xk,xj)+MatMin(j,i)|(xk,xj) U};
fin pour;

pour i  1 à k - 1 faire 
MatMin(i,k)min{d(xj,xk)+MatMin(i,j)|(xj,xk) U};
fin pour;

pour i  1 à k - 1 faire pour j  1 à k - 1 faire

MatMin(i,j)min{MatMin(i,j),MatMin(i,k)+ MatMin(k,j)};

fin pour; fin pour;

fin pour;

Fin

Le corps de la classe AlgoDantzig


/**

*    classe gérant les graphes

*  @version 1.0

*  @date 14/12/2016


*/
import java.util.*; public class AlgoDantzig{

private Graphe gr;  // le graphe

private float matMin[][]; // la matrice contenant les chemins optimaux entre les sommets

public AlgoDantzig(){

}

public AlgoDantzig(Graphe gr){

….

}

public void algorithm(){

….

}

public float[][] getMatriceMinimal(){

….

}

public static void main(String args[]){

….

}

}


Commentaires