V.3. La dualité en programmation linéaire
Références
[7] Concis et dense. Très bon.
[26] [21], [22] et [24] contiennent de nombreux exemples simples et des illustrations ; elles intègrent la Programmation linéaire dans un domaine plus vaste,
répertorié sous le vocable de « Recherche Opérationnelle ».
[27] Description et analyse des principales méthodes de résolution numérique
des problèmes de programmation linéaire reposant sur l’algorithme du simplexe, ainsi que les programmes nécessaires à leur mise en œuvre sur microordinateur.
[28] [CS] Très complets sur la question ; de véritables « Bibles ». Longtemps dominée par les algorithmes du type « méthode du simplexe », la résolution
numérique des programmes linéaires a subi un véritable révolution avec l’apport de N. Karmarkar (1984). Les techniques du type « points intérieurs »
(cf. l’Exercice V.25 pour une idée) commencent à prendre place dans les
formations du niveau 2 e cycle : voir le chapitre 4 de [8] et les chapitres XIII
et XIV de [24] par exemple. La 4 e partie de [4] et les ouvrages [20] et [25]
sont consacrés pour l’essentiel à ces nouvelles approches.
* Exercice V.1. Soit l’ensemble-contrainte d’un programme linéaire dans R 5 décrit de la manière suivante :
2x 1 + x 2 + x 3 = 8, x 1 + 2x 2 + x 4 = 7, x 2 + x 5 = 3
x i 0 pour tout i = 1, . . . , 5.
1 ◦ ) Combien y a-t-il de bases au plus ? Quelles sont ces bases et les éléments
de base associés ?
2 ◦ ) Déterminer toutes les bases admissibles.
Solution : L’ensemble-contrainte est décrit sous la forme
Ax = b
x 0
, avec A ∈ M 3,5 (R) de rang 3.
Il y a au plus
5
3
= 10 bases.
Bases
Éléments de base associés
Statut (admissible ou non)
J = {1, 2, 3} x = (1, 3, 3, 0, 0)
admissible
J = {1, 2, 4} x =
5
2 , 3, 0, −
3
2 , 0
non admissible
175
Références
[7] Concis et dense. Très bon.
[26] [21], [22] et [24] contiennent de nombreux exemples simples et des illustrations ; elles intègrent la Programmation linéaire dans un domaine plus vaste,
répertorié sous le vocable de « Recherche Opérationnelle ».
[27] Description et analyse des principales méthodes de résolution numérique
des problèmes de programmation linéaire reposant sur l’algorithme du simplexe, ainsi que les programmes nécessaires à leur mise en œuvre sur microordinateur.
[28] [CS] Très complets sur la question ; de véritables « Bibles ». Longtemps dominée par les algorithmes du type « méthode du simplexe », la résolution
numérique des programmes linéaires a subi un véritable révolution avec l’apport de N. Karmarkar (1984). Les techniques du type « points intérieurs »
(cf. l’Exercice V.25 pour une idée) commencent à prendre place dans les
formations du niveau 2 e cycle : voir le chapitre 4 de [8] et les chapitres XIII
et XIV de [24] par exemple. La 4 e partie de [4] et les ouvrages [20] et [25]
sont consacrés pour l’essentiel à ces nouvelles approches.
* Exercice V.1. Soit l’ensemble-contrainte d’un programme linéaire dans R 5 décrit de la manière suivante :
2x 1 + x 2 + x 3 = 8, x 1 + 2x 2 + x 4 = 7, x 2 + x 5 = 3
x i 0 pour tout i = 1, . . . , 5.
1 ◦ ) Combien y a-t-il de bases au plus ? Quelles sont ces bases et les éléments
de base associés ?
2 ◦ ) Déterminer toutes les bases admissibles.
Solution : L’ensemble-contrainte est décrit sous la forme
Ax = b
x 0
, avec A ∈ M 3,5 (R) de rang 3.
Il y a au plus
5
3
= 10 bases.
Bases
Éléments de base associés
Statut (admissible ou non)
J = {1, 2, 3} x = (1, 3, 3, 0, 0)
admissible
J = {1, 2, 4} x =
5
2 , 3, 0, −
3
2 , 0
non admissible
175