16
Recherche opérationnelle
En conséquence, le problème revient à trouver un point M de D tel que la distance de 0 à
la droite passant par M et parallèle aux droites x 1 + 2x 2 = constante soit la plus grande
possible. Sur la figure, on a tracé une droite (∆) de la forme x 1 + 2x 2 = constante.
Pour avoir le point (ou les points) cherché, il suffit de déplacer la droite
parallèlement à elle-même en la rapprochant de 0, jusqu'à ce qu'elle « touche » le
domaine D.
Il est aisé de voir que la position de
est alors
et que le point cherché est le point
B de coordonnées
.
La résolution de ce programme linéaire a été facilitée par le fait que le nombre de
variables (2) permettait une représentation géométrique. Ce n'est pas le cas en général et
nous allons avoir recours à présent à des méthodes plus élaborées.
Néanmoins, de ce petit exemple, il convient de retenir les résultats suivants, qui ne sont
que la transcription des résultats que nous allons trouver dans le cas général :
1) le domaine des solutions réalisables est convexe, pour
, c'est un
polygone.
2) le point où la fonction économique est maximale est un sommet du domaine
convexe des solutions réalisables.
3) parmi les contraintes du programme, il en est qui sont à l'optimum
« strictement » respectées (ici 2x 1 + x 2 ≤ 350) ; ce sont les contraintes « non
saturées ». D'autres sont « juste » respectées (le point B est tel que x 1 + 3x 2 =
450 et x 1 + x 2 = 200) ; ce sont les contraintes saturées.
1.2. ETUDE DU CAS GENERAL
1.2.1. Forme générale d'un programme linéaire
Comme il a été dit ci-dessus, résoudre un programme linéaire consiste à maximiser (ou
minimiser) une fonctionnelle linéaire d'un nombre fini quelconque de variables positives
ou nulles, ces variables devant respecter un nombre fini quelconque de contraintes
linéaires. Un programme linéaire peut toujours s'écrire de la façon suivante :
Soit n variables
obéissant aux contraintes :
2
2
1
1
11
x
a
x
a
n
a 1 n
x
1
b
2
2
2
1
21
x
a
x
a
n
a 2 n
x
2
b
2
2
1
1
x
a
x
a
m
m
n
n
m x
a
m
b
1
x 0
0
2
x
Recherche opérationnelle
En conséquence, le problème revient à trouver un point M de D tel que la distance de 0 à
la droite passant par M et parallèle aux droites x 1 + 2x 2 = constante soit la plus grande
possible. Sur la figure, on a tracé une droite (∆) de la forme x 1 + 2x 2 = constante.
Pour avoir le point (ou les points) cherché, il suffit de déplacer la droite
parallèlement à elle-même en la rapprochant de 0, jusqu'à ce qu'elle « touche » le
domaine D.
Il est aisé de voir que la position de
est alors
et que le point cherché est le point
B de coordonnées
.
La résolution de ce programme linéaire a été facilitée par le fait que le nombre de
variables (2) permettait une représentation géométrique. Ce n'est pas le cas en général et
nous allons avoir recours à présent à des méthodes plus élaborées.
Néanmoins, de ce petit exemple, il convient de retenir les résultats suivants, qui ne sont
que la transcription des résultats que nous allons trouver dans le cas général :
1) le domaine des solutions réalisables est convexe, pour
, c'est un
polygone.
2) le point où la fonction économique est maximale est un sommet du domaine
convexe des solutions réalisables.
3) parmi les contraintes du programme, il en est qui sont à l'optimum
« strictement » respectées (ici 2x 1 + x 2 ≤ 350) ; ce sont les contraintes « non
saturées ». D'autres sont « juste » respectées (le point B est tel que x 1 + 3x 2 =
450 et x 1 + x 2 = 200) ; ce sont les contraintes saturées.
1.2. ETUDE DU CAS GENERAL
1.2.1. Forme générale d'un programme linéaire
Comme il a été dit ci-dessus, résoudre un programme linéaire consiste à maximiser (ou
minimiser) une fonctionnelle linéaire d'un nombre fini quelconque de variables positives
ou nulles, ces variables devant respecter un nombre fini quelconque de contraintes
linéaires. Un programme linéaire peut toujours s'écrire de la façon suivante :
Soit n variables
obéissant aux contraintes :
2
2
1
1
11
x
a
x
a
n
a 1 n
x
1
b
2
2
2
1
21
x
a
x
a
n
a 2 n
x
2
b
2
2
1
1
x
a
x
a
m
m
n
n
m x
a
m
b
1
x 0
0
2
x