3M239 : Optimisation linéaire et convexité 2018–2019
TP n◦ 3 : Résolution graphique en dimension 2
Objectif : Résoudre graphique les problèmes d’optimisation linéaire en dimension 2.
1 Résolution graphique d’un problème d’optimisation linéaire
Exercice 1 Un premier exemple. On s’intéresse au problème d’optimisation linéaire suivant :
Maximiser Z(x, y) = 2 x + y
sous les contraintes x +2 y 6 8
x+ y 6 5
9 x +4 y 6 36
x, y > 0
1. Donner une solution de base admissible du problème considéré.
2. À l’aide de la fonction plot de la librairie matplotlib, représenter l’ensemble admissible du pro-
blème. Que peut-on en conclure quant à l’existence de solutions ?
3. Quels sont les sommets du polyèdre tracé dans la question précédente ?
4. À l’aide de la représentation avec matplotlib des lignes de niveaux de la fonction objectif Z,
résoudre le problème.
5. Que se passe-t-il si l’on cherche à maximiser la fonction objectif Z2 (x, y) = x + y sous les mêmes
contraintes ?
6. On suppose, plus généralement, que la fonction objectif Z a (x, y) = ax+y dépend d’un paramètre a.
Décrire la solution du problème d’optimisation linéaire associé
Maximiser Z a (x, y) = a x + y
sous les contraintes x +2 y 6 8
x+ y 6 5
9 x +4 y 6 36
x, y > 0
en fonction des valeurs du paramètre a.
Exercice 2 Différentes situations en dimension 2. On considère les trois problèmes suivants :
Maximiser Z1 (x, y) = 2 x + y
sous les contraintes x+ y > 4
x +2 y 6 5
x > 2
x, y > 0
Maximiser Z2 (x, y) = 2 x − 3 y
sous les contraintes 3 x +2 y 6 6
x −2 y > 5
2x− y > 6
x, y > 0
Maximiser Z3 (x, y) = 30 x + 20 y
sous les contraintes x− y 6 −2
x− 4y 6 −2
2x+ y > 5
5x+ 7y 6 44
x, y > 0
Pour chacun des problèmes ci-dessus, traiter les questions suivantes :
1. Représenter à l’aide de matlplotlib le polyèdre des contraintes.
2. Tracer les lignes de niveaux de la fonction objectif.
3. Résoudre le problème d’optimisation linéaire.
D’après un énoncé de Maxime Chupin Sorbonne Université
3M239 : Optimisation linéaire et convexité 2018–2019
2 Solutions de base et sommets d’un polyèdre dans (R+ )2
Dans cette seconde partie du TP, on va explorer le lien entre les sommets d’un polyèdre dans (R+ )2
et les solutions de base d’un certain système linéaire. Ces dernières seront obtenues en appliquant la
méthode du pivot de Gauss-Jordan vue lors de la séance précédente.
Exercice 3 Recherche algébrique de solutions de base. Revenons au problème de l’Exercice 1.
1. Questions de cours
• En introduisant les variables d’écart 1, 2, 3 , écrire la formulation standard du problème.
• Écrire le problème obtenu après introduction des variables d’écart sous forme matricielle
AX = b, où A ∈ M3,6 (R) et b ∈ R3 .
• Donner une solution de base du système des contraintes. Est-elle admissible ?
2. Exploration des solutions de base
• Définir avec Python la matrice M = (A, b). C’est à cette matrice que l’on va appliquer la méthode
du pivot de Gauss-Jordan.
• On pose
1 2 1 0 0
V1 = 1® , V2 = 1® , 1 = 0® , 2 = 1® , 3 = 0®
© ª © ª © ª © ª © ª
«9¬ «4¬ «0¬ «0¬ «1¬
En utilisant la fonction pivot, définie dans le TP 2, calculer les coordonnées des vecteurs
V1,V2,V3, 1, 2, 3 dans les bases successives dans cet ordre
{V2, 2, 3 }, {V2, 1, 3 }, {V2, 1, 2 }, {V1, 1, 2 }, {V1, 1, 3 }, {V1,V2, 3 }, {V1,V2, 2 }, {V1,V2, 1 }.
• Quelles sont les solutions de base associées à chacune de ces bases ?
3. Solutions de base admissibles et sommet du polyèdre des contraintes.
• Parmi les solutions de base déterminées à la question précédente, lesquelles sont réalisables ?
• Comparer avec les sommets du polyèdre des contraintes du problème d’optimisation linéaire
considéré dans cet exercice. Que peut-on en déduire ?
D’après un énoncé de Maxime Chupin Sorbonne Université
