MIAGE Master 1 MIAGE Master 1
Recherche Opérationnelle 1
TD9: le 21 novembre 2007
Programmation Linéaire en Nombres Entiers

  1. Appliquer l'algorithme de Dakin au programme dont les paramètres sont donnés dans le fichier : ~jrobson/RO/dakin.dat.

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

  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 simplexe utilisé pour la question 1, obtenez-vous les plus courts chemins demandés?



File translated from TEX by TTH, version 3.05.
On 20 Nov 2007, 14:54.