Chemins optimaux dans graphes algorithme de DANTZIG + programmation java - Recherche Operationnelle
I. Introduction
1) Graphe valué.
![](https://3.bp.blogspot.com/-3KbBuvdESrI/WFQhOi5puTI/AAAAAAAANsM/S2nKBNiHDqoyqiiZHWtGnplSqS9caQWQgCLcB/s1600/image001.jpg)
![](https://2.bp.blogspot.com/-G3aFVUsxmhc/WFQhOo8pJwI/AAAAAAAANsU/aFhyUOsrnRg6WynLauPLscif7nq5WuQ3QCLcB/s1600/image002.jpg)
![](https://4.bp.blogspot.com/-RZhPdMFvcV4/WFQhOkkSs3I/AAAAAAAANsQ/uEu4MjJK5X0ASiPQT4WMlQhIFdf5twGPQCLcB/s1600/image003.jpg)
2) Chemin de longueur optimal.
![](https://1.bp.blogspot.com/-2RPiq6FsPsw/WFQhPD06QCI/AAAAAAAANsY/mdcUXx73GpwESSl35OYURiLAYfOk28TxgCLcB/s1600/image004.jpg)
![](https://4.bp.blogspot.com/-NAGGmkS59KA/WFQhPL2k-eI/AAAAAAAANsg/-qwusyAZul8VsYU6Q85kHIIiHQtU_drrwCLcB/s1600/image005.jpg)
![](https://1.bp.blogspot.com/-o1ZePdqyMQE/WFQhPOugoxI/AAAAAAAANsc/fuH2QTU-q0sxe7AyyM9VTfyOF1T5MVcbQCLcB/s1600/image006.jpg)
![](https://1.bp.blogspot.com/-jSdORylgm8g/WFQhPnTL9dI/AAAAAAAANsk/cW7mfU139fwNUoKINU--RN97Cy7kGrmMQCLcB/s1600/image007.jpg)
![](https://2.bp.blogspot.com/-hpnXS92cCSc/WFQhPu7X4SI/AAAAAAAANso/5vCG4vRG5ekWNCXk1bd54ln46Mnvag5kwCLcB/s1600/image008.jpg)
3) Condition d’existence :
Exemple: circuit de longueur négatif
![](https://4.bp.blogspot.com/-S1G1OgDeNT8/WFQhQfHviXI/AAAAAAAANtA/7OsbfsKvdJ4RmxeYEs2sdlag7gKs98x4wCLcB/s320/image013.png)
La longueur du circuit suivant est -2. C’est donc un circuit absorbant.
1) Exemples :
- Sommets correspondre aux localités
- Arcs correspondre aux routes (A chaque route on fait correspondre 2 arcs de sens opposés)
![Graphe chemin optimale recherche operationnelle](https://3.bp.blogspot.com/-pnEktONuhzE/WFQhRZHHMaI/AAAAAAAANtI/sbyiNpmhQi0nmjcn0jyDslfFLHYH8fi4QCLcB/s1600/image014.png)
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
![](https://3.bp.blogspot.com/-HY8SKL9CzK0/WFQhRQPZtcI/AAAAAAAANtM/GyTKEYoHbZg2LaUmU_xZ15yvECOIg_e2wCLcB/s1600/image015.jpg)
0
|
si
|
i = 1
|
|
t.q λi =
|
si
|
i>1
|
|
+ ∞
|
|
3. Calculer de proche les différences λj – λi pour tout arc
(xi,xj) ![](https://1.bp.blogspot.com/-Cw-FuTOYpNg/WFQhRvAc9FI/AAAAAAAANtQ/5d9gu8M66k4IZ25dC9KvG26xNLiXroBigCLcB/s1600/image016.jpg)
, et remplacer λj par λi + l(i,j) si λj – λi >l(i,j)
![](https://1.bp.blogspot.com/-Cw-FuTOYpNg/WFQhRvAc9FI/AAAAAAAANtQ/5d9gu8M66k4IZ25dC9KvG26xNLiXroBigCLcB/s1600/image016.jpg)
![](https://1.bp.blogspot.com/-KwmqqYTAfNk/WFQhRt1S-8I/AAAAAAAANtU/R_f9oHAyGoo3vtarLssI_5aEpWOb3hX_ACLcB/s1600/image017.jpg)
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)]
![](https://4.bp.blogspot.com/-mCGYbXeDUB0/WFQhRuEBsuI/AAAAAAAANtY/_GIgnEId2bsJ_WUbdqkkv3CZPyH5mXnbwCLcB/s1600/image018.jpg)
![](https://1.bp.blogspot.com/-Cw-FuTOYpNg/WFQhRvAc9FI/AAAAAAAANtQ/5d9gu8M66k4IZ25dC9KvG26xNLiXroBigCLcB/s1600/image016.jpg)
(a) λ1 = 0 E {x1}
(b)
xi ![](https://3.bp.blogspot.com/-usX3yVnGXtg/WFQhRwcvL7I/AAAAAAAANtk/PQFJdRWOwb0d5wd4TJ8s6ocNk6Gpci4VwCLcB/s1600/image020.jpg)
on associe xi*
Ē = X – E t. q
![](https://1.bp.blogspot.com/-HNHW88X5ACM/WFQhR94uvyI/AAAAAAAANtg/-pUZGslauFEJRKNAMkdIrETfN2Y_-AZ9ACLcB/s1600/image019.jpg)
![](https://3.bp.blogspot.com/-usX3yVnGXtg/WFQhRwcvL7I/AAAAAAAANtk/PQFJdRWOwb0d5wd4TJ8s6ocNk6Gpci4VwCLcB/s1600/image020.jpg)
![](https://3.bp.blogspot.com/-n_TZnaZQ6XI/WFQhSEP9lFI/AAAAAAAANtc/uO9Jn-Md5HUa6x37uHljlhfWfc29Yt-zwCLcB/s1600/image021.jpg)
![](https://3.bp.blogspot.com/-usX3yVnGXtg/WFQhRwcvL7I/AAAAAAAANtk/PQFJdRWOwb0d5wd4TJ8s6ocNk6Gpci4VwCLcB/s1600/image020.jpg)
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
![](https://4.bp.blogspot.com/-mCGYbXeDUB0/WFQhRuEBsuI/AAAAAAAANtY/_GIgnEId2bsJ_WUbdqkkv3CZPyH5mXnbwCLcB/s1600/image018.jpg)
![](https://2.bp.blogspot.com/-mVMkq1lIWks/WFQhSm_AfuI/AAAAAAAANt4/1NG77oiRcacjElhbAXmIDPrwj_SkycRkQCLcB/s1600/image026.jpg)
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
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};
![](https://4.bp.blogspot.com/-92hqqQc8rCs/WFQhS_-HhGI/AAAAAAAANt8/U5exxTkxHakSDPWieuELlO1W4OpOskaVACLcB/s1600/image027.jpg)
fin pour;
pour i ← 1 à k - 1 faire
MatMin(i,k) ←min{d(xj,xk)+MatMin(i,j)|(xj,xk)
U};
![](https://4.bp.blogspot.com/-92hqqQc8rCs/WFQhS_-HhGI/AAAAAAAANt8/U5exxTkxHakSDPWieuELlO1W4OpOskaVACLcB/s1600/image027.jpg)
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
Enregistrer un commentaire