MIAGE Master 1 MIAGE Master 1
Recherche Opérationnelle 1
TD8: novembre 2006
Programmation Linéaire en Nombres Entiers

  1. Appliquer l'algorithme de Dakin au programme:
    x1+x2+x3+x4 ≤ 200

    3x1-3x2+4x3-4x4 ≤ 150

    4x1-5x2-2x3+2x4 ≤ 160

    -2x1-3x2+2x3+4x4 ≤ 250

    Maximiser -x1+x2+2x3+2x4

    Un programme pour résoudre des programmes linéaires (sans contrainte que les variables soient entières) est disponible (~jrobson/RO/ProgLin.exe).

  2. Exprimez par des programmes linéaires en 0-1 la recherche dans le réseau donné:

    1. d'un plus court chemin de A à I

    2. d'un plus court chemin hamiltonien (qui visite chaque sommet une seule fois) de A à I

    Sommets: A(source), B, C, D, E, F, G, H, I(destination)

    Arêtes (avec distance):
    AB(2), AC(5), AD(7), BF(6), BG(5), CD(3), CF(3), CG(4),
    CH(3), DE(4), EG(4), EH(1), FI(6), FG(3), GI(5), GH(4), HI(3)
    Si vous résolvez vos programmes (avec l'ajout des contraintes que les variables sont ≤ 1) par le programme ProgLin utilisé pour la question 1, obtenez-vous les plus courts chemins demandés?



File translated from TEX by TTH, version 3.05.
On 23 Nov 2006, 13:35.