U.S.T.H.
B
Faculté de Mathématiques
Département de Recherche Opérationnelle
Master 1 ERO
Module: Décomposition des Grands Systèmes
Série d’exercices N◦ 2
Exercice 1 Soient les programmes linéaires suivants
x1 + 2x2 + 3x3 − x4 + x5 + x6 = Z(max)
x1 − x2 + 2x3 + x4 − x5 ≤ 12
2x1 + x2 − x3 + 3x4 + x5 + 2x6 ≤ 10
x1 + x2 ≤4
5x1 + 3x2 ≤ 15
(P1 ) x3 − 3x4 ≤4
x 3 + 2x 4 ≤ 6
4x5 + 3x6 ≤ 12
3x5 + 4x6 ≤ 12
5x5 + 2x6 ≤ 10
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
2x1 − x2 + 2x3 + x4 = Z(max)
−2x1 + x2 + 2x3 + x4 ≤ 10
x1 − x2 + x3 + 2x4 ≤ 8
3x 1 + 4x2 + 2x3 + 3x4 ≤ 24
(P2 ) x1 − 3x2 ≤4
x1 + 2x2 ≤6
x 3 − 4x 4 ≤ 4
2x3 + 4x4 ≤ 10
x1 , x2 , x3 , x4 ≥ 0.
1. Formuler les PL sous formes matricielles. Définir toutes les matrices utilisées.
2. Donner tous les points extrêmes des ensembles réalisables correspondants aux contraintes
indépendentes.
3. Ecrire chaque PL en terme de ses points extrêmes.
Exercice 2 Résoudre les programmes linéaires suivants par la méthode de Dantzig Wolfe.
6x1 + 5x2 + 3x3 + 4x4 = Z(max)
x1 + x 2 + x3 + x4 ≤ 7
2x1 + x2 + x3 + 3x4 ≤ 17
x 1 + x2 ≤5
(P1 )
3x1 + 2x2 ≤ 12
x3 + 2x4 ≤ 8
2x 3 + x4 ≤ 10
x1 , x2 , x3 , x4 ≥ 0.
1
2x1 + 3x2 + x3 + 2x4 = Z(max)
2x1 + 3x2 + x3 + 2x4 ≤ 10
x1 − 2x3 + 3x4 ≤ 8
−x1 + x2 ≤2
(P2 )
3x 1 + x 2 ≤ 8
x3 + 3x4 ≤ 12
3x3 − 2x4 ≤ 3
x1 , x2 , x3 , x4 ≥ 0.
2x1 + x2 + 2x3 + x4 = Z(max)
2x1 + 3x2 + x3 + 2x4 ≥ 10
x1 − 2x3 + 3x4 ≤ 8
−x1 + x2 ≥2
(P3 )
3x 1 + x 2 ≤ 8
x3 + 3x4 ≤ 12
3x3 − 2x4 ≥ 3
x1 , x2 , x3 , x4 ≥ 0.
Exercice 3 Soient les programmes linéaires suivants
2x1 + 3x2 + 4x3 + 2x4 = Z(max)
2x1 + 4x2 + 3x3 + 2x4 ≤ 12
x1 − x2 + 2x3 − x4 ≤ 3
x1 − x2 ≤1
(P1 )
−x1 + x2 ≤2
x 3 + x 4 ≥ 5
2x3 + 5x4 ≤ 12
x1 , x2 , x3 , x4 ≥ 0.
x1 − 3x2 + 4x3 − x4 = Z(max)
x1 − x2 + x3 − 2x4 ≤ 12
x1 + 3x2 + 2x3 + 6x4 ≥ 12
−3x1 + 4x2 ≤6
(P2 )
4x1 + 5x2 ≥ 15
−x 3 + x 4 ≥ 5
−2x3 + 5x4 ≤ 12
x1 , x2 , x3 , x4 ≥ 0.
Pour chaque PL :
1. Formuler sous forme matricielle
2. Utiliser les contraintes de liaisons pour définir des bornes sur les variables
3. Donner un programme linéaire quivalent, dans lequel le domaine réalisable du problème
esclave est bornè.
4. Ecrire alors le problème maitre équivalent.
