Généralités sur la programmation linéaire
33
b
P
x i
i
m
i
=
1
=
Ce système est de Cramer pour les variables i ; si ces dernières sont toutes positives ou
nulles, on a bien obtenu ainsi un sommet du polyèdre (sinon, on recommence en
choisissant
autres vecteurs i ). Pour la solution de base ainsi trouvée, on peut calculer
la valeur de la fonction économique. On pourrait penser alors calculer cette valeur pour
tous les sommets du polyèdre, et comparer entre elles les grandeurs trouvées pour
obtenir le maximum. Cette méthode est très lourde.
Supposons en effet, pour fixer les idées, que m =10 et n = 20 (ce qui constitue un petit
programme linéaire, si on le compare à ceux qui sont utilisés couramment dans la
pratique).
Il faut essayer
30
10
C systèmes de
vecteurs indépendants, ce qui constitue plus de
systèmes de Cramer à résoudre.
On est donc confronté à un problème hautement combinatoire et, pour le résoudre, il est
nécessaire de disposer d'un algorithme, c'est-à-dire d'une procédure répétitive
permettant, de progresser rapidement vers la solution optimale.
Cet algorithme dit du simplexe sera exposé dans le chapitre suivant. Nous nous
contenterons ici d'en donner les principes. Nous commencerons par profiter des
renseignements dégagés par les théorèmes I à V pour proposer une autre écriture d'un
programme linéaire, à savoir l'écriture matricielle (alors que nous avons surtout utilisé
jusqu'ici une écriture vectorielle).