53

CHAPITRE IV

PROGRAMMATION LINÉAIRE

LE MÉTHODE GRAPHIQUE.
Introduction.
La méthode graphique est la façon la plus simple de résoudre des problèmes de programmation linéaire, laquelle
consiste à tracer les équations correspondantes aux contraintes dans des coordonnées cartésiennes, étant
chaque variable représentée sur l'un des axes, de sorte que la zone soit parfaitement délimitée
fait qu'il soit possible de trouver une solution, en essayant alors de localiser dans celle-ci le point qui optimise la fonction
objectif.
Dans cette méthode, comme chaque variable est représentée sur un axe, seuls les problèmes pouvant être traités sont ceux qui ont
au maximum 3 variables, car nous ne pouvons pas représenter plus de 3 dimensions.
Dans ce texte, nous nous occuperons uniquement des cas à 2 variables, car ce sont les exemples qui sont généralement...
ils sont gérés par la méthode graphique pour être représentés sur un plan, même s'ils sont plus simples,
illustrent de manière appropriée le procédé de solution des problèmes.

Méthodologie.
Un procédé divisé en étapes du présent méthode peut être le suivant :
Étape 1.- Formuler le problème. C'est-à-dire convertir les données et les informations que l'on a sur le problème en un
système d'équations dûment posées comme programmation linéaire. Cette étape ne sera plus développée
ici puisque cela a été traité dans le chapitre précédent.
Étape 2.- Représenter une variable du problème sur chaque axe cartésien, puis procéder à tracer les
équations des contraintes dans le plan formé.
Chaque intersection d'une paire de contraintes formera un sommet de la zone de solution, étant le premier
de ces origines, car c'est le point d'intersection des contraintes de non-négativité.
Alors il y aura autant de sommets que d'intersections possibles entre une paire donnée de contraintes, déjà
soit-elles fonctionnelles ou de non-négativité.
Cela délimite la zone faisable de solution en fonction du type de contraintes du problème.
Étape 3.- Tracer les équations de la fonction objectif, en donnant différentes valeurs à Z, en voyant lesquelles d'entre elles
restent dans la zone réalisable de solution.
Nous devons souligner que cette étape peut être omise, car l'objectif est de trouver le point qui correspond à la
solution du problème qui sera celui qui optimisera la Z, ce qui sera effectué à l'étape suivante.
Étape 4.- Trouver la solution du problème, c'est-à-dire, cette droite parmi celles tracées à l'étape précédente qui
optimisez la fonction objectif. Ici, nous devons commenter qu'il peut exister plusieurs solutions optimales d'un
problème, si l'une des droites correspondant aux contraintes est parallèle à la droite de la fonction
objectif ; dans le cas contraire, il existera une solution optimale unique, qui sera celle qui maximisera ou minimisera
la Z, selon le cas.
Cette étape peut également être réalisée en trouvant la valeur de Z de chacun des sommets de la région
solution feasible, that Z which is maximum or minimum depending on the type of problem in question, will be the
solution du même.
Pour illustrer cette procédure, nous présenterons 4 exemples résolus, qui ont déjà été posés.
Exemple IV.1.-Résoudre par la méthode graphique le problème.
Max Z = 0,5 A + 0,4 B
Soumise aux restrictions suivantes :
2 A + B < 20 (1)
A + B < 16 (2)
Étant A, B non négatifs.

Solution :
Ici, nous commencerons la méthodologie, à partir de l'étape 2, puisque la 1 a déjà été effectuée, alors
nous représenterons A sur l'axe des abscisses et B sur l'axe des ordonnées.
54
Ensuite, nous tracerons les équations des contraintes en considérant les inégalités comme des égalités, c'est-à-dire
dire
2 A + B = 20 (1)
A + B = 16 (2)

Si nous regardons le type d'équations de chaque contrainte, nous nous rendrons compte qu'il s'agit de droites, les
quels pourront être tracés en localisant 2 points, cela se fait de la manière suivante :
Pour l'équation ( 1 ) :
2A + B = 20
Si 0
Si 0
Alors les points sont P (A =1 0, B = 20) et P (A =210, B = 0)
Pour l'équation ( 2 ) :
A + B = 16
Si 0
Si 0
Étant les points Q (A1= 0, B = 16) et Q (A 2= 16, B = 0).

Une représentation graphique de ces équations est montrée dans la figure IV.1.
Un commentaire supplémentaire est que, comme A et B doivent être non négatifs, cela délimite la zone.
factible de solution au premier quadrant.
B
P
1
20 Figure IV.1 Graphique du
exemple IV.1
Équation 1
Q
16 1
Zone 1

PQ
12

huit
Zone 3
Équation 2

Zone 2
4

P Q
2 2
O
4 8 12 16 20 Un
Dans la figure, nous avons marqué 3 zones numérotées de 1 à 3 dont nous commenterons ce qui suit :
La zone 1 se trouve en dessous de la droite correspondant à l'équation 1 et au-dessus de la droite de l'équation 2.
cela signifie que comme les restrictions sont de type inférieur ou égal à ( < ), la zone satisfait à la première
restriction and does not meet the second, therefore it is not a feasible region of the solution, since to achieve
cela devra répondre aux deux.
La zone 2 se trouve en dessous de la droite de l'équation 2 et au-dessus de la droite de l'équation 1, donc
semble respecter la deuxième contrainte, mais pas la première, donc ce n'est pas une région faisable de
solution.
 55
Pour sa part, la zone 3 se situe en dessous des droites des équations 1 et 2, respectant donc
toutes les restrictions, la région étant faisable pour la solution, elle est donc représentée marquée par des lignes
diagonales pointillées, restant comprise entre les points O-Q -PQ-P. 1 2
Dans ce cas, il y a 4 sommets du problème qui sont les points O, Q, 1 PQ et P.2
Nous allons maintenant procéder à l'étape 3, en traçant certaines droites de la fonction objectif, en lui donnant différentes
valeurs à Z. Dans ce cas particulier, nous prendrons 2 droites, d'abord celle qui passe par le point Q 1où
A=0, B=16, donc Z sera égal à 0.5 x A + 0.4 x B = 0.5 x 0 + 0.4 x 16 = 6.4
Pour tracer cette ligne droite, nous avons besoin de 2 points, l'un est1 le Q d'où a été pris la valeur de 6,4.
l'autre peut être quand B = 0, alors.
Z = 6.4 = 0.5 A + 0.4 ( 0 )
d'où
A = 6.4 / 0.5 = 12.8
Étant l'autre point (A = 12.8, B = 0), que nous appellerons R.
Pour l'autre droite, nous prendrons celle qui passe par le point P 2où A = 10, B = 0, Z étant égal à 0,5 x A +
0,4 x B = 0,5x10 + 0,4x0 = 5.
Pour tracer cette droite, nous avons besoin d'un second point, que nous prendrons lorsque A = 0, alors
Z = 5 = 0,5 A + 0,4 B = 0,5 ( 0 ) + 0,4 B
d'où
B = 5 / 0.4 = 12,5
Étant ce deuxième point (A = 0, B = 12,5), que nous appellerons S.
Ces 2 droites sont présentées avec la région faisable de solution dans la figure IV.2
B
20

Figure IV.2 Graphique des 2 droites

Q
16 1
de la fonction objectif, Z=6.4 et
Z=5.
S
PQ
12

Ligne
Ligne Z=6.4
Z=5
4

P
2 R
O
4 8 12 16 20 Un
Comme on peut le voir sur la figure, la ligne Z = 5 se trouve entièrement dans la zone de solution, tandis que
que la droite Z = 6.4 a certains points à l'intérieur de cette zone, mais d'autres à l'extérieur de celle-ci.
Une observation importante est que ces 2 droites sont parallèles, ce qui est logique, car les coefficients 0,5
y 0.4 qui multiplient les variables A et B respectivement sont des constantes, seul la valeur de Z varie, étant
ces coefficients constants, la pente de la droite sera également constante, donc en ayant le même
pendant, les lignes seront parallèles.
Enfin, nous passons à l'étape 4, qui consiste à trouver la droite parallèle aux 2 de la figure IV.2 qui
reste dans la zone de solution et maximise Z.
De la figure IV.2, nous voyons que la ligne de Z = 6.4 est meilleure dans ce sens que celle de Z = 5, mais encore
des lignes parallèles pourraient être tracées pour rester dans la zone de solution. Selon
56
méthodologie indiquée pour l'étape 4, une manière simple de vérifier cela est d'obtenir la Z des 4 sommets
que forment la zone de solution. Ce que nous allons effectuer immédiatement :
Point O (A = 0, B = 0)
Alors
Z = 0,5 A + 0,4 B
= 0,5 ( 0 ) + 0,4 ( 0 ) = 0

Point Q 1(A = 0, B = 16)

Alors
Z = 0.5 A + 0.4 B
= 0.5 ( 0 ) + 0.4 ( 16 ) = 6.4

Point PQ (les coordonnées ne sont pas connues).

Par conséquent, la première étape sera d'obtenir sa localisation, pour cela nous savons que ce point est l'intersection.
de la droite de la contrainte numéro 1 avec la droite de la contrainte numéro 2, donc si nous résolvons les
en résolvant ces 2 équations de contraintes simultanément, nous obtiendrons les valeurs de A et B qui correspondent à
point PQ, alors :
2A + B = 20 (1)
A + B = 16 (2)
Si nous soustrayons l'équation (2) de (1), nous aurons :
2A - A + B - B = 20 - 16
A= 4
Avec cette valeur de A, nous l'utiliserons dans l'équation (2) pour obtenir :
4 + B = 16
de où B = 16 - 4 = 12
Par conséquent, les coordonnées du point PQ sont (A = 4, B = 12), pour Z nous aurons :
Z = 0,5 A + 0,4 B
= 0.5 (4) + 0.4 (12)
= 2 + 4.8 = 6.8
Enfin, le point P (A = 10,
2 B = 0)
Alors Z = 0.5 A + 0.4 B
= 0.5 (10) + 0.4 (0)
=5
D'ici, nous voyons que la solution du problème est le point d'intersection des lignes des contraintes,
PQ, où
A= 4
B = 12
6.8

Exemple IV.2.-Résoudre le problème

Min Z = 10A + 9B
Soumis aux restrictions :
A + 2B > 12 (1)
2A + B > 10 (2)
Étant A et B non négatives
Solution :
Nous commençons la résolution du problème à partir de l'étape 2 en représentant A sur l'axe des abcisses et B
dans les ordonnées.
Nous allons immédiatement grapher les équations des contraintes en prenant les inégalités comme des égalités,
alors :
A + 2B = 12 (1)
2A + B = 10 (2)

Pour pouvoir tracer ces 2 droites, nous avons besoin de 2 points connus sur chacune d'elles, alors pour la
nous aurons d'abord :
Ec. (1) : A + 2B = 12
 57
Si A = 0, B = 12 / 2 = 6, point P (A 1= 0, B = 6)
Si B = 0, A = 12, point P (A
2 = 12, B = 0)
Pour sa part, pour la deuxième équation, nous aurons :
Ec ( 2): 2A + B = 10
Si A = 0, B = 10, point Q (A1 = 0, B = 10)
Si B = 0, A = 10 / 2 = 5, point Q (A2= 5, B = 0)

Ces droites sont représentées graphiquement dans la figure IV.3

B
12 Figure IV.3. Graphique des
restrictions et la région
Q
10 1 solution faisable du
exemple IV.2
8 Équation 2
Zone
P
1 1
6
PQ
4
Zona
Équation 1
2 3 Zone
2
P
2
O Q
2 Un
2 4 6 8 10 12 14
Nous présentons également 3 zones, dont nous expliquerons ce qui suit :
La zone 1 se trouve en dessous de la ligne de l'équation 2 et au-dessus de la ligne de l'équation 1. Comme les
Les restrictions sont dans ce cas du type supérieur ou égal à ( > ), cette zone respecte la première restriction,
mais pas avec la deuxième.
Pour sa part, la zone 2 respecte la deuxième restriction, car elle se situe au-dessus de la ligne de son
équation, mais pas avec la première, car elle reste en dessous de la ligne correspondant à son équation.
Enfin, la zone 3 ne respecte aucune des 2 restrictions, car elle se trouve en dessous des 2 lignes.
correspondantes à leurs équations.
Par conséquent, la zone faisable de solution sera celle du premier quadrant (puisque A et B doivent être non)
négatives), qui reste au-dessus des deux lignes des équations des restrictions, c'est-à-dire la ligne
formée par les points P -PQ-
2 Q dans 1 la figure IV.3.
Dans ce cas, nous sauterons l'étape 3 et passerons directement à l'étape 4, où le point de solution sera celui
que nous minimise Z de la région réalisable, ce point doit être situé à l'un des sommets de
cette zone. Dans ce cas, nous aurons 3 sommets qui sont les points Q, 1 PQ et P.2
Pour le point Q (1A= 0, B= 10), nous aurons :
Z = 10A + 9B
= 10 (0) + 9 (10) = 90

Pour le point P (A
2 = 12, B = 0), nous aurons :
Z = 10A + 9B
= 10 (12) + 9 (0) = 120
58
Pour le point PQ, qui est l'intersection des droites correspondant aux contraintes, nous devons
Tout d'abord, trouver votre localisation, pour cela nous résoudrons le système d'équations simultanées :
A + 2B = 12 (1)
2A + B = 10 (2)
Si nous soustrayons 2 fois l'équation 2 de l'équation 1, nous aurons :
A - 2(2A) + 2B - 2(B) = 12 - 2 (10)
A - 4A + 2B - 2B = 12 - 20
-3A = -8
8/3
Et si nous substituons cette valeur dans l'équation (1), cela nous donnera :
8/3 + 2B = 12
2B = 12 - 8/3 = 36/3 - 8/3 = 28/3
B = 28/3/2 = 28/6 = 14/3

Par conséquent, le point PQ est situé en (A = 8/3, B = 14/3), cela nous donnera pour Z :
Z = 10A + 9B
= 10 ( 8/3) + 9 ( 14/3)
= 80/3 + 126/3 = 206/3
D'ici, nous voyons que la solution est située en ce point PQ, qui est celui qui fournit le Z minimum et
respecte les restrictions, donc la solution est :
A = 8/3
B = 14/3
Z = 206/3

Exemple IV.3.-Résoudre le problème de programmation linéaire :

Max Z = 2A + 1,5B
Sous réserve des restrictions :
A+B=1 (1)
0,4A + 0,3B < 0,36 (2)
Étant A et B non négatifs.

Solution :
Tout comme dans les exemples précédents, nous commencerons par la deuxième étape, en plaçant A sur l'axe des
abcisses et B dans les ordonnées.
Nous allons également tracer les contraintes dans le plan cartésien, la seconde avec le signe d'égalité, est
dire
A+B=1 (1)
0,4A + 0,3B = 0,36 (2)
Pour la première équation, nous prendrons les points :
Q1 (A = 0, B = 21) et Q (A = 1, B = 0)
Tandis que pour la seconde nous aurons :
Si A = 0, 0,3B = 0,36
B = 0,36/30 = 1,2

Et si B = 0, 0,4 A = 0,36
A = 0,36/0,40 = 0,9
Étant donné les points1 P ( A = 0, B = 1,2) et P (A
2 = 0,9, B = 0)

Une représentation graphique de ces équations est montrée dans la figure IV.4, où les droites sont présentées.
correspondant aux restrictions, les points de base à partir desquels ont été tracés et le point PQ qui
c'est l'intersection des lignes.
 59
B
P1 Figure IV.4. Graphique du cas
1.2 de l'exemple IV.3
Q1
1.0 Équation 2

0,8

0,6
PQ
0,4
Équation 1
0.2
Q2
O P2
0,2 0,4 0,6 0,8 1.0 1.2 A
Il est pertinent de commenter que la deuxième contrainte est de type inférieur ou égal à (<), donc
cela délimite la zone faisable de solution sous cette ligne et dans le premier quadrant, c'est-à-dire
le triangle O - P - 1P. Mais
2 la première restriction est de type égal ( = ), cela signifie que la solution
doit rester à un point sur la droite de l'équation 1, par conséquent la région feasible de solution est le
tranche de cette droite qui se trouve à l'intérieur du triangle O - P1- P et2qui est représentée dans la figure par un trait
plus épais, car c'est la seule partie qui respecte les deux contraintes, cela signifie que la solution
sera comprise entre Q et PQ. 1
Maintenant, selon l'étape 4, qui nous dit que la solution se localise à un sommet de la zone faisable,
cela signifie que celle-ci sera située à l'un des 2 points extrêmes Q et PQ. 1
Nous le saurons en calculant la Z de chacun de ces points :
Pour le point Q 1( A= 0,B = 1.0)
Z = 2A + 1,5B
= 2 ( 0 ) + 1.5 ( 1 ) = 1.5
Pour le point PQ, nous ne connaissons pas sa localisation, donc nous l'obtiendrons en résolvant
simultanément le système d'équations formé par les 2 contraintes :
A+B=1 (1)
0,4A + 0,3B = 0,6 (2)

Ici, nous pouvons isoler une variable de l'équation (1), disons A, et remplacer cette expression dans la
équation (2), avec cela nous aurons :
De la Ec (1) :
A=1-B (1)
En remplaçant dans l'Éq.(2) :
0.4 A + 0.3 B = 0.36 (2)
0,4 (1 - B) + 0,3 B = 0,36
Laquelle en enlevant les parenthèses :
0.4 - 0.4B + 0.3B = 0.36
En regroupant les termes,
-0,4B + 0,3B = 0,36 - 0,40
-0.04
Enfin, nous avons dégagé B
60
B = -0.04 / (-0.1) = 0.4
Et comme de l'Éc. (1), A = 1 - B
A = 1 - 0,4 = 0,6
Par conséquent, le point PQ est situé en (A = 0.6, B = 0.4)
Et la Z respectif sera :
Z = 2A + 1,5 B
= 2(0,6) + 1,5 (0,4)
= 1,2 + 0,6 = 1,8
La Z majeure est cette dernière, donc la solution est :
A = 0.6
B = 0.4
Con Z = 1,8

Exemple IV.4.-Maximiser la fonction objectif

Max Z = 80 A + 75 B
Soumise aux restrictions :
2A + B < 1.3 (1)
A + 2B < 1,5 (2)
A+B=1 (3)
Étant A et B non négatives et également entières.
Solution :
Comme le problème est déjà posé, passons à l'étape 2, en plaçant A sur l'axe des abscisses et B sur
le des ordonnées et nous procédons à tracer les restrictions, prenant comme égalités leurs équations,
alors :
2A + B = 1,3 (1)
A + 2B = 1,5 (2)
A + B = 1 (3)
Nous allons maintenant prendre 2 points de chaque équation pour pouvoir tracer la droite correspondante, ainsi nous aurons :
Pour l'équation (1) :
Si A = 0, B = 1.3
Si 0
A = 1.3/2 = 0.65
Les points seront P1(A = 0, B = 1,3) et P (A2= 0,65, B = 0)

Pour l'équation (2) :

Si 0
B = 1.5/2 = 0.75
Si 0
Les points seront Q 1( A = 0, B = 0,75) et Q ( A2 = 1,5, B = 0)
Et pour l'équation (3) :
Si 0
Si 0
Ses points seront R 1( A = 0, B = 1) et R (2A = 1, B = 0)

Dans la figure IV.5, le graphique contenant ces équations est présenté.

 61
B
Figure IV.5. Graphique de l'exemple
IV.4
1.6

1.2
Équation 1

0,8
Équation 3

0,4
Équation 2

O
Un
0,4 0,8 1,2 1.6 2.0 2.4
Les deux premières restrictions sont de type inférieur ou égal à (<), l'aire marquée avec des diagonales.
la qui satisfait aux deux contraintes ; cependant, la troisième contrainte étant du type égal à ( = ),
implique que la solution doit rester sur la droite de cette équation, si nous observons la figure nous voyons que cette
la droite n'entre à aucun moment dans la zone signalée par des diagonales, cela signifie qu'il n'existe pas de région
factible de solution qui satisfait les 3 contraintes, c'est pourquoi nous pouvons dire que ce problème n'a pas
solution.
Une situation qu'il convient de souligner ici est le fait que la solution de ce problème depuis son
le planning indiquait que les variables A et B devraient être entières, cela aurait impliqué de chercher
combinations entières des 2 variables qui resteraient dans la zone feasible de solution, celle-ci étant
cette combinaison entière qui aurait maximisé Z.
62
PROBLÈMES PROPOSÉS.

IV.1.- Maximiser Z = 4A + 3B
Soumise aux restrictions
A+B<6
A< 4
B<5
Étant A et B non négatifs et entiers.

IV.2.- Minimiser Z = 6A + 8B
Soumise aux restrictions
2A + B > 18
A> 6
B>5
Étant A et B non négatifs.

IV.3.- Minimiser Z = 7X + 9Y
Soumise aux restrictions
2X + 3Y > 36
X + Y > 14
Étant A et B non négatifs.

IV.4.- Maximiser Z = 4X + 6Y
Soumise aux restrictions
X + Y < 10
X<7
Y < 5
Avec X, Y entiers et non négatifs.

IV.5.- Minimiser Z = 6A + 5B
Soumise aux restrictions
A + B > 16
A> 4
A< 6
Avec A et B entiers et non négatifs.

IV.6.- Maximiser Z = 6X + 9Y
Soumise aux restrictions
X + 2Y < 20
2X + Y < 24
Con X, Y non négatives.

IV.7.- Maximiser Z = 40C + 38D

Soumise aux restrictions
C + D < 30
C < 15
D < 18
Con C et D entiers et non négatifs.