IUP MIAGE
Master 1 Recherche Opérationnelle 1
TD6: le 10/11/2005
Programmation Linéaire en Nombres Entiers

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

    3x1-3x2+4x3-4x4 15

    4x1-5x2-2x3+2x4 16

    -2x1-3x2+2x3+4x4 25

    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/simplexe).

  2. Trouver un flot maximum et la coupe minimum associée pour le réseau donné: dessiner le flot dans le réseau après chaque recherche d'une chaîne augmentante.

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

    Arêtes (avec capacités dans chaque sens):
    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), GI(5), HI(3)




File translated from TEX by TTH, version 3.05.
On 10 Nov 2005, 13:19.

symboles bricolés par sed