32
Recherche opérationnelle
On constate que la contrainte (I) est superflue.
Par ailleurs, le segment
est parallèle à la direction ( ) de la fonction économique.
Le maximum de celle-ci est trouvé en
, et en tout point du segment
, donc en
tout point s'exprimant sous la forme d'une combinaison linéaire convexe
Remarque : la circonstance suivant laquelle il existe une infinité de solutions optimales,
comme précédemment, est appelée dégénérescence de second type.
Le terme de dégénérescence de premier type est réservé au cas, déjà examiné, où une
solution de base est constituée de moins de m variables non nulles.
Dans ce cas, il y a plus de n variables nulles, ce qui veut dire que le sommet dans
correspondant à la solution de base est l'intersection de plus en plus de n hyperplans pris
soit dans les hyperplans x j = 0, soit dans les hyperplans
b
x
a j
ij
n
j
=
1
=
1.4. INTRODUCTION A L'ALGORITHME DU SIMPLEXE
Nous savons donc que le maximum de la fonction économique est trouvé en un sommet
(éventuellement plusieurs) du polyèdre convexe des solutions réalisables.
Par ailleurs, nous savons trouver théoriquement ces sommets : il suffit de choisir
vecteurs P i , indépendants parmi P 1 , P 2 , P n+m et de résoudre le système,