Généralités sur la programmation linéaire
37
(8)
)
(
=
0
j
j
j
I
j
x
z
c
Z
Z
avec
i
ij
I
i
j
c
t
z =
À partir du moment où l'on a , on peut obtenir
grâce à de simples calculs
matriciels.
Supposons que pour un
on ait
Rendons la variable correspondante positive, en laissant les autres variables hors base
nulles, le but de cette opération étant d'augmenter la fonction économique : en effet si
est l'accroissement de la variable , les autres variables hors base restant nulles,
l'accroissement
de la fonction économique est :
D'après l'équation (7), pour que l'on ait dans ces conditions une solution réalisable, il
faut que :
et
on en déduit :
1) si
pour tout
est positif quelle que soit la valeur
(positive) de
peut donc croître indéfiniment ainsi que les variables
et on obtient une solution réalisable à
variables infinies : le
domaine n'est pas borné, ce qui est contraire à l'hypothèse faite en II-3-5.
2) Il existe donc au moins un
; on doit alors avoir, pour respecter
pour tout
i/ > 0
si l'on fait croître jusqu'à sa limite :
i/ > 0 et si l'on appelle
l'indice tel que
pour tout
on voit que la variable
s'annule, si
.
Cette opération a donc consisté à rendre positive une variable hors base pour annuler une
variable de base.
À la fin, on a donc toujours
variables non nulles et variables nulles, donc une
solution de base : on est passé d'un sommet du polyèdre à un autre.
Remarque : il faut vérifier que les vecteurs colonnes de la matrice des contraintes
associées aux variables nouvelles de base sont bien indépendants.