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é:

(a) d’un plus court chemin de A à I

(b) 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), F I(6), F G(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?