18
Recherche opérationnelle
x, vecteur colonne
=
b, vecteur colonne
=
,
c, vecteur ligne
= (c 1 …c n )
le problème posé ci-dessus peut alors s'écrire :
Nous utiliserons souvent une autre forme que la forme canonique, appelée forme
standard et obtenue de la façon suivante :
On transforme les inégalités
en égalités en introduisant m variables
supplémentaires dites variables d'écart. En effet, le programme linéaire :
2
12
1
11
x
a
x
a
n
a 1 x
1
b
(I)
2
2
1
1
x
a
x
a
m
m
mn
a
n
x
m
b
2
1 x
x
0
n
x
Max
n
n x
c
x
c
x
c
Z
...
2
2
1
1
est équivalent au suivant :
2
12
1
11
x
a
x
a
n
a 1
=
1
n
n
x
x
1
b
(II)
2
22
1
21
x
a
x
a
n
a 2
=
2
n
n
x
x
2
b
2
2
1
1
x
a
x
a
m
m
mn
a
=
m
n
n
x
x
m
b
1
,
2
1,
n
n x
x
x
x
0
m
n
x
Max
m
n
n
n
n
x
x
x
c
x
c
x
c
Z
0
...
0
...
'
1
2
2
1
1
(Les contraintes
proviennent des inégalités
du programme (I))
Les variables
sont appelées variables d’écart, par opposition aux
variables x 1 , x 2 …x n appelées variables principales.
La forme (II), où toutes les inégalités sont transformées en égalités est appelée forme
standard.
Si l'on utilise les notations matricielles pour un programme ramené à la forme standard
(après adjonction de m variables d'écart), on obtient