60
Recherche opérationnelle
2.3. RECHERCHE D'UNE SOLUTION DE BASE INITIALE
Prenons le petit exemple suivant :
(8)
4
3
2
1
x
x
x
2
2
3
2
1
x
x
x
0
,
,
3
2
1
x
x
x
On aura remarqué que, dans l'algorithme du simplexe, le second membre est toujours
positif, puisque c'est le vecteur des valeurs des variables de base pour le sommet
considéré.
En conséquence, si on veut transformer les inéquations de ce P.L en équations, on est
obligé d'introduire deux variables d'écart et de la façon suivante :
4
=
4
3
2
1
x
x
x
x
2
=
2
5
3
2
1
x
x
x
x
(9)
0
,
,
,
,
5
4
3
2
1
x
x
x
x
x
On remarquera le signe
pour la variable , dû à l'inégalité .
Une solution de base de ce P.L a 2 variables non nulles et 3 variables nulles.
Comme les variables de base doivent être positives, on ne peut plus prendre pour ces
variables les variables d'écart (ce qui ferait
,
).
On ne dispose pas d'une solution de base de départ immédiate.
Pour ce problème, nous allons ajouter une nouvelle variable
dans la seconde
contrainte, variable dite artificielle, a priori redondante par rapport à .
(10)
2
=
2
6
5
3
2
1
x
x
x
x
x
0
,
,
,
,
,
6
5
4
3
2
1
x
x
x
x
x
x
On voit qu'ainsi on a une solution de base évidente
2
=
4
=
0
=
,
,
,
6
4
5
3
2
1
x
x
x
x
x
x
et que par ailleurs, les variables de base sont bien exprimées en fonction des variables
hors base.
Cependant, il convient de noter que la solution trouvée n'appartient pas au polyèdre des
solutions réalisables : en effet, la deuxième contrainte du P.L initial n'est évidemment
pas respectée avec
4
=
4
3
2
1
x
x
x
x