Scribd Logo
Importer

Bienvenue sur Scribd !

  • 532 vues

    TD PCC - Correction

    Transféré par

    TunENSTAB
    Le document présente plusieurs algorithmes pour résoudre des problèmes de plus court chemin, notamment les algorithmes de Dijkstra, Ford et pour les graphes sans circuits. Il propose également une extension de l'algorithme de Ford pour résoudre un problème d'optimisation multi-objectifs. Enfin, il modélise un problème décisionnel sous la forme d'un graphe valué.

    Droits d'auteur :

    © All Rights Reserved

    TD PCC - Correction

    Transféré par

    TunENSTAB
    532 vues4 pages
    Le document présente plusieurs algorithmes pour résoudre des problèmes de plus court chemin, notamment les algorithmes de Dijkstra, Ford et pour les graphes sans circuits. Il propose également une extension de l'algorithme de Ford pour résoudre un problème d'optimisation multi-objectifs. Enfin, il modélise un problème décisionnel sous la forme d'un graphe valué.

    Description originale:

    TD PCC _ Correction

    Titre original

    TD PCC _ Correction

    Copyright

    © © All Rights Reserved

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente plusieurs algorithmes pour résoudre des problèmes de plus court chemin, notamment les algorithmes de Dijkstra, Ford et pour les graphes sans circuits. Il propose également une extension de l'algorithme de Ford pour résoudre un problème d'optimisation multi-objectifs. Enfin, il modélise un problème décisionnel sous la forme d'un graphe valué.

    Droits d'auteur :

    © All Rights Reserved
    532 vues4 pages

    TD PCC - Correction

    Transféré par

    TunENSTAB
    Le document présente plusieurs algorithmes pour résoudre des problèmes de plus court chemin, notamment les algorithmes de Dijkstra, Ford et pour les graphes sans circuits. Il propose également une extension de l'algorithme de Ford pour résoudre un problème d'optimisation multi-objectifs. Enfin, il modélise un problème décisionnel sous la forme d'un graphe valué.

    Droits d'auteur :

    © All Rights Reserved
    sur 4

    Optimisation

    CORRECTION TD 1
    LE PROBLEME DU PLUS COURT CHEMIN
    ET SES EXTENSIONS

    Exercice 1 :
    a. Le graphe ne comprend pas de cots ngatifs, on peut donc appliquer aussi bien
    lalgorithme de Dijkstra que lalgorithme de Ford. De plus, le graphe ne comprend pas de
    circuits, on peut donc appliquer lalgorithme des graphes sans circuits.

    b.
    Algorithme de Dijktra :

    Itration 1 2 3 4 5 6 7 8
    0 0 12/1 4/1 2/1
    1 - 12/1 4/1 - 20/4 31/4
    2 - 11/3 - - 19/3 31/4
    3 - - - - 19/3 14/2 31/4
    4 - - - - 19/3 - 18/6 23/6
    5 - - - - 19/3 - - 22/7
    6 - - - - - - - 22/7
    7 - - - - - - - -

    La solution est : 1 3 2 6 7 8 de cot 22.

    Algorithme de Ford :

    Itration 1 2 3 4 5 6 7 8
    0 0 12 4 2
    1 0 11 4 2 19 15 31
    2 0 11 4 2 19 14 19 24
    3 0 11 4 2 19 14 18 23
    4 0 11 4 2 19 14 18 22
    5 0 11 4 2 19 14 18 22

    La solution est : 1 3 2 6 7 8 de cot 22.

    Algorithme pour les graphes sans circuits :


    Etape 1 : Numrotation
    Nud 8 : 1, Nud 7 : 2, Nud 5 : 3, Nud 6 : 4, Nud 2 : 5, Nud 3 : 6, Nud 4 : 7, Nud
    1 : 8.

    1
    Optimisation

    5 4
    2 3 6

    12
    8 7 4
    9
    1 4 3 6 15
    7
    3 8
    5
    2 4 1
    2 18
    4 29 8

    Etape 2 : Calcul des valeurs des variables ui :


    u1 = 0
    u2 = min (0 + 4) = 4
    u3 = min (8 + 4) = 12
    u4 = min (0 + 9 ; 4 + 4) = 8
    u5 = min (3 + 8) = 11
    u6 = min (7 + 11 ; 15 + 12) = 18
    u7 = min (18 + 12 ; 0 + 29) = 29
    u8 = min (12 + 11 ; 4 + 18 ; 2 + 29) = 22

    La solution est : 1 3 2 6 7 8 de cot 22.

    Exercice 2 :
    1.
    On construit le graphe suivant :

    (3;6) (5;9) (2;3)


    RN
    4 DP CP PP
    (5;3) (0;0)
    S (4;6) T
    RP

    DA CA PA (0;0)
    (2;9)
    RA (2;9) (3;12) (1;6)

    Le problme de planification optimale du nouveau produit est ainsi modlise comme un


    problme de plus court chemin entre les sommets S et T du graphe ci-dessus.

    2. Algorithme de Ford avec extension :


    On applique lalgorithme de Ford en :
    - maintenant 2 tiquettes pour chaque sommet (di, ci) et,

    2
    Optimisation

    - nliminant que les chemins domins.

    Un chemin P1 (d1, c1) est domin par le chemin P2 (d2, c2) ssi d1 d2 et c1 c2

    Itratio RN RP RA DP DA CP CA PP PA T
    n
    0 (5, (4, (2, + + + + + + +
    3) 6) 9)
    1 (8, 9) (7, + + + + +
    (7, 12)
    12) (6,
    (5, 15)
    15) (4,
    18)
    2 (13, (11, 21) + + +
    18) (10,
    (12, 24)
    21) (8, 27)
    (10, (7, 30)
    24)
    (9, 27)
    3 (15, 11) (14, +
    (12, 24)
    27) (11, 30)
    (13, (12,
    24) 27)
    (10,
    30)
    4 (10,
    30)

    Le plus court chemin de cot infrieur ou gale au budget (30 MD) a une dure de 10 :

    S RA DP CA PP T

    Exercice 3 :
    1. On dfinit le graphe G = [X, U] de la manire suivante :
    - un sommet est associ chaque dbut danne,
    - un arc relie les sommets i et j si et seulement si i < j. Cet arc correspond la
    dcision dacheter une voiture neuve au dbut de lanne i et de la revendre au
    dbut de lanne j.
    - la longueur de chaque arc est la somme des cots dachat et de maintenance moins
    le prix de rcupration :

    3
    Optimisation

    cij = p(i) + s=0,j-i-1 r(s) - v(j-i)

    1 2 3 6

    Le problme revient dterminer un plus court chemin entre les sommets 1 et 6 dans ce
    graphe.

    2. Calcul des cots des arcs :


    c12 = 5, c13 = 12, c14 = 21, c15 = 31, c16 = 44, c23 = 7, c24 = 14, c25 = 23, c26 = 33, c34 = 8, c35 = 15,
    c36 = 24, c45 = 8, c46 = 15, c56 = 9.
    Le chemin optimal est : (1, 2, 4, 6) de cot minimal z* = 34.

    Vous aimerez peut-être aussi