Généralités sur la programmation linéaire
21
(autrement dit, tout point du segment
appartient à ).
Un point extrême d'un ensemble convexe est un point appartenant à tel qu'on ne
puisse pas trouver deux points a et b tels que
b
a
c =
Avec
(plus trivialement, c n'appartient à aucun segment contenu dans , sauf s'il en est une
des extrémités).
Si on reprend le petit exemple analysé précédemment (l'entreprise de camions), le
domaine
ensemble des productions réalisables est convexe : c'est le polygone
(figure 1). Les points extrêmes sont ici les points
, sommets du
polygone : ils sont en nombre fini.
Par contre, si l'on dessine un cercle dans R
2 , on obtient également un domaine convexe,
mais tous les points de la circonférence sont des points extrêmes ; ils sont une infinité.
Rappelons également que si l'on a n points
n
a
a
a ,...
2
,
1
de , une combinaison linéaire
convexe de ces n points est un point a qui s'écrit
n
n a
a
a
a
2
2
1
1
=
avec
A présent, nous allons démontrer un certain nombre de théorèmes sur la programmation
linéaire en utilisant la forme standard, c'est-a-dire la forme obtenue après addition des
variables d'écart transformant les inéquations en équations.
Nous avons donc le programme
b
x
A =
0
x
Max
cx
z
avec