Chapitre 8 • La pro gram ma tion linéaire
300
Figure 8.1
Les contraintes sont aisées à repré sen ter. Ainsi la contrainte x 1 < 1 000 signi
fie que dans le qua drant posi tif, les points dont la coor don née x 1 excède 1 000 sont
exclus du domaine des solu tions. Or, x 1 5 1 000 repré sente une droite D 1 ver ti cale,
ortho go nale à l’axe Ox 1 au point x 1 5 1 000 : à toutes les solu tions res pec tant cette
contrainte, sont asso ciés des points com pris entre D 1 et l’axe Ox 2 (et au dessus de
l’axe Ox 1 ). On rai son nerait de même pour la contrainte x 2 < 500 (la droite D 2 , hori
zon tale, a pour équa tion x 2 5 500).
Si le pro blème ne com por tait que les contraintes 0 < x 1 < 1 000 et 0 < x 2 < 500
le domaine « admis sible », c’est àdire le domaine des points asso ciés aux solu
tions véri fiant ces contraintes, serait le rec tangle OABC. Mais x 1 1 2x 2 5 1 750 est
aussi l’équa tion d’une droite D 3 dont l’inter sec tion avec la droite D 1 est le point E
(x 1 5 1 000, x 2 5 375) et l’inter sec tion avec D 2 est le point F (x 1 5 750, x 2 5 500).
Le domaine des solu tions admis sibles d de notre pro blème est donc le poly gone
convexe OAFEC, à la fron tière ou à l’inté rieur duquel se trouvent les points asso ciés
à ces solu tions admis sibles.
Jus qu’à présent nous ne nous sommes occu pés que des contraintes ; pour choi sir
parmi les solu tions admis sibles une solu tion qui soit opti male, nous devons chercher
à maxi mi ser la fonc tion nelle z 5 4x 1 1 12x 2 (« fonc tion éco no mique »), cf fig. 8.2.
L’ensemble (ou « lieu ») des points tels que z 5 0, est la droite Δ 0 d’équa tion
x 2 5 2
1
3
x 1 ; elle n’a qu’un seul point com mun avec le domaine admis sible : c’est le
point Ο (pro duc tion nulle et donc béné fice nul !). Le lieu des points tels que z 5 4 000
est la droite Δ 4 000 , paral lèle à Δ 0 et pas sant par le point C (x 1 5 1 000, x 2 5 0).
Pour une valeur don née arbi trai re ment à la fonc tion éco no mique, soit z 5 a, on peut
montrer que la dis tance de l’origine Ο à la droite Δ α est : OH 5
a
"4
2 1 12
2
.
Ainsi la valeur α de la fonc tion éco no mique est- elle pro por tion nelle à OH. Dès lors,
pour maxi mi ser z, il suf fira de tra cer une droite paral lèle à Δ 0 dont la dis tance à
300
Figure 8.1
Les contraintes sont aisées à repré sen ter. Ainsi la contrainte x 1 < 1 000 signi
fie que dans le qua drant posi tif, les points dont la coor don née x 1 excède 1 000 sont
exclus du domaine des solu tions. Or, x 1 5 1 000 repré sente une droite D 1 ver ti cale,
ortho go nale à l’axe Ox 1 au point x 1 5 1 000 : à toutes les solu tions res pec tant cette
contrainte, sont asso ciés des points com pris entre D 1 et l’axe Ox 2 (et au dessus de
l’axe Ox 1 ). On rai son nerait de même pour la contrainte x 2 < 500 (la droite D 2 , hori
zon tale, a pour équa tion x 2 5 500).
Si le pro blème ne com por tait que les contraintes 0 < x 1 < 1 000 et 0 < x 2 < 500
le domaine « admis sible », c’est àdire le domaine des points asso ciés aux solu
tions véri fiant ces contraintes, serait le rec tangle OABC. Mais x 1 1 2x 2 5 1 750 est
aussi l’équa tion d’une droite D 3 dont l’inter sec tion avec la droite D 1 est le point E
(x 1 5 1 000, x 2 5 375) et l’inter sec tion avec D 2 est le point F (x 1 5 750, x 2 5 500).
Le domaine des solu tions admis sibles d de notre pro blème est donc le poly gone
convexe OAFEC, à la fron tière ou à l’inté rieur duquel se trouvent les points asso ciés
à ces solu tions admis sibles.
Jus qu’à présent nous ne nous sommes occu pés que des contraintes ; pour choi sir
parmi les solu tions admis sibles une solu tion qui soit opti male, nous devons chercher
à maxi mi ser la fonc tion nelle z 5 4x 1 1 12x 2 (« fonc tion éco no mique »), cf fig. 8.2.
L’ensemble (ou « lieu ») des points tels que z 5 0, est la droite Δ 0 d’équa tion
x 2 5 2
1
3
x 1 ; elle n’a qu’un seul point com mun avec le domaine admis sible : c’est le
point Ο (pro duc tion nulle et donc béné fice nul !). Le lieu des points tels que z 5 4 000
est la droite Δ 4 000 , paral lèle à Δ 0 et pas sant par le point C (x 1 5 1 000, x 2 5 0).
Pour une valeur don née arbi trai re ment à la fonc tion éco no mique, soit z 5 a, on peut
montrer que la dis tance de l’origine Ο à la droite Δ α est : OH 5
a
"4
2 1 12
2
.
Ainsi la valeur α de la fonc tion éco no mique est- elle pro por tion nelle à OH. Dès lors,
pour maxi mi ser z, il suf fira de tra cer une droite paral lèle à Δ 0 dont la dis tance à