Scribd Logo
Importer

Bienvenue sur Scribd !

  • 25 vues

    Note 11 12 2023

    Transféré par

    TRAVUS Emmanuel
    Ce document présente un problème de réduction d'un problème de flot maximal en un programme linéaire, et explique comment cette réduction peut être utilisée pour montrer qu'un problème est NP-complet.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Note 11 12 2023

    Transféré par

    TRAVUS Emmanuel
    25 vues2 pages
    Ce document présente un problème de réduction d'un problème de flot maximal en un programme linéaire, et explique comment cette réduction peut être utilisée pour montrer qu'un problème est NP-complet.

    Description originale:

    Note en Recherche Opérationnelle

    Titre original

    Note-11-12-2023

    Copyright

    © © All Rights Reserved

    Formats disponibles

    DOCX, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document présente un problème de réduction d'un problème de flot maximal en un programme linéaire, et explique comment cette réduction peut être utilisée pour montrer qu'un problème est NP-complet.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    25 vues2 pages

    Note 11 12 2023

    Transféré par

    TRAVUS Emmanuel
    Ce document présente un problème de réduction d'un problème de flot maximal en un programme linéaire, et explique comment cette réduction peut être utilisée pour montrer qu'un problème est NP-complet.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme DOCX, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format docx, pdf ou txt
    Vous êtes sur la page 1sur 2

    Exemple problème 1

    1- Associé un problème de flot maximal décrit par le réseau ci-dessus


    2- Dresser le premier tableau du simplexe pour le P.L précédent

    Traduction en un programme linéaire

    - Détermination des variables de décision


    o XSA, XSC, XSF, XAC, XAB XBP, XBD, XCA, XCF, XCD, XFC, XFE XFP, XDE, XEP
    - Détermination de la « fonction objectif »
    o Max f(Xi) = XSA + XSC + XSF
    - Détermination des contraintes
    o XSA <= 5 ; XSC <= 5 ; XSF <= 6 ; XAC <= 3 ; XAB <= 4; XBP <= 2 ; XBD <= 4 ; XCA <= … ; XCF, XCD,
    XFC, XFE XFP, XDE, XEP
    o XSA + XCA – XAB – XAC = 0
    o …
    o XDE + XFE - XEP = 0
    o XSA, XSC, XSF, XAC, XAB XBP, XBD, XCA, XCF, XCD, XFC, XFE XFP, XDE, XEP >= 0
    - Détermination du tableau simplexe :

    X X X X X X X X X X X X X X X E E E E E E E E E …
    S S S A C F C A C B D F F E B 1 2 3 4 5 6 7 8 9
    A C F C A C F B D D E E P P P
    M 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    a
    x
    0 0 1 0 0 - 1 1 0 0 0 - - 0 0 0 0
    1 1 1
    1 0 0 - 1 0 0 - 0 0 - - 0 0 - 0
    1 1 1 1 1
    0 1 0 1 - 1 - 0 - 0 0 0 0 0 0 0
    1 1 1
    0 0 0 0 0 0 0 1 0 - 0 0 0 0 - 0
    1 1
    0 0 0 0 0 0 0 0 1 1 - 0 0 0 0 0 0
    1
    0 0 0 0 0 0 0 0 0 0 1 1 0 - 0 0
    1
    1 1 5
    1 1 5
    1 1 6
    1 1 3
    1 1 4
    1 1 2
    …

    Réduction du problème

    Quand on est confronté à un nouveau problème P, on peut énoncer ce problème P comme un cas
    particulier d’un problème Q déjà connu. Résoudre le problème Q fournira une solution à notre
    problème P.
    Si cette transformation du problème P en un problème Q est peu coûteuse (polynomiale) alors on
    peut affirmer que le problème P n’est pas plus difficile que le problème Q.

    Exemple
    La réduction d’un problème linéaire de Flot max en un programme linéaire

    Application : Les problèmes NP-complet

    Quand on veut montrer qu’un problème est NP-complet, on réduit un problème qui a déjà été
    montré NP-complet dans ce nouveau problème. Ainsi le nouveau problème sera supposé être au
    moins aussi difficile qu’un problème NP-complet.

    Par conséquent il sera autorisé à appliquer des méthodes heuristiques.

    Problème des reines


    Soit N un entier strictement positif.

    Sur une grille de N * N cases, on souhaite placer un maximum de reines, de sorte qu’il n’y a pas deux
    reines qui soient en prise.

    RAPPEL : Deux reines sont dites en prise si elles partagent la même ligne, colonne, ou oblique
    (montante ou descendante).

    Exemple : (Les « O » représentent la position des reines sur l’échiquier


    Tableau 1 - Fonctionne

    O
    O
    O
    O
    O

    Tableau 2 - Ne fonctionne pas

    O
    O
    O

    O O

    Exemple : Proposer un algorithme qui résout ce problème pour un « N » donné quelconque

    Vous aimerez peut-être aussi