Résolution
d’un programme linéaire
Méthode graphique
exercices
PROGRAMME LINÉAIRE
⚫ FONCTION OBJECTIF
⚫ Maximiser ou minimiser z = c1x1 +… + cnxn
⚫ Contraintes
⚫ a11x1+ … + a1nxn (, =, ) b1
⚫ a21x1+ … + a2nxn (, =, ) b2
⚫ am1x1 +… + amnxn (, =, ) bm
⚫ Contraintes de non-négativité
⚫ xj 0 ; j = 1, 2, 3, … n
⚫ avec
⚫ xj variables de décision (inconnues)
⚫ aij, bi, cj paramètres du programme linéaire
Méthode Graphique
⚫ Valable si 2 variables de décision
seulement.
⚫ Le nombre de contraintes est quelconque.
⚫ Repose sur une représentation des
contraintes dans un plan.
Contrainte =inégalité à 2 variables
⚫ a1x1 + a2x2 <= b ; b > 0, a1 >0, a2 > 0
x2 b/a2
>b
Demi-espace
admissible
<= b
b/a1
x1
l’optimum est un des points extrêmes
x2
x1
Exemple 1
⚫ MAXIMISER z = 3 x1 + 5 x2
⚫ Contraintes :
⚫ x1 4
⚫ 2 x2 12
⚫ 3 x1 + 2 x2 18
⚫ x1 0 ; x2 0
ZONE DE SOLUTION RÉALISABLE
Zone limitée par les contraintes du problème et
par la positivité des variables :
x2
3x1 + 2 x2 = 18
8 x1 = 4
6 2 x2 = 12
SR
4
0 x1
2 4 6 8 10
FONCTION OBJECTIVE
Déplacement de la fonction objective à l’intérieur
de la zone de solution réalisable pour atteindre un
extremum
x2
z = 36 = 3x1 + 5x2 8 Solution
optimale
(2,6)
6 x1 = 2
z = 20 = 3x1 + 5x2 x2 = 6
4 Max Z = 36
z = 10 = 3x1 + 5x2
2
0 x1
2 4 6 8 10
Exemple 2
⚫ Maximiser Z = x1 + 2x2
2x1 + x2 4
x1 + x2 8
-x1 + x2 4
x1 5
x1 0, x2 0
Exemple 2 (suite)
x2
-x1 + x2 = 4 X1 = 2
8 X2 = 6
Z = 14
6 x1 = 5
x1 + x2 = 8
SR
2
2x1 + x2 = 4
0 x1
2 4 6 8 10
Exemple de MINIMISATION
⚫ Minimiser
Z = x1 – x2
Sachant que :
½ x1 + x2 8
-x1 + 8x2 40
x1 8
x2 8
x1 0, x2 0
PROBLÈME DE MINIMISATION
X1 = 8
x2
X2 = 6
x2 = 8 Min Z = 2
8
6
-x1 + 8x2 = 40
4 SR
x1 = 8
2 ½x1 + x2 = 8
0 2 4 6 8 10 12 14 16 18 20 x1
Exemple 3
Max 25x + 30x ⚫ Maximisation du profit
B C
S.C.
1 x + 1 x 40 ⚫ Contrainte de rareté
200 B 140 C d’une ressource
0 x 6000 Contraintes de
B ⚫
demande
0 x 4000
C
Solution graphique de l’exemple 1
xC
xB = 6000
6000 192’000
xC = 1400
4500
3000 Solution
optimale
SR
1500
0 xB
0 1500 3000 4500 6000 7500 9000
Cas possibles
La zone SR peut être :
⚫ Vide:Contraintes contradictoires
(pas de solution optimale)
⚫ borné : le problème possède toujours au
moins une solution optimale
⚫ non borné : selon la fonction objectif
⚫ Si MIN : il y a une solution finie
⚫ Si MAX : Solution non bornée
Le nombre de solutions optimales ?
- Une seule.
- Une infinité :
si deux sommêts réalisent l’optimum
(tout le segment reliant les deux
sommêts optimaux)
