Généralités sur la programmation linéaire
17
0
n
x
Il s'agit de trouver
satisfaisant à ces contraintes et maximisant la
fonctionnelle, appelée fonction économique :
n
n x
c
x
c
x
c
z
2
2
1
1
=
Les , et appartenant à R
On peut en effet toujours écrire un programme linéaire sous cette forme, après
éventuellement les corrections suivantes :
1) s’il s'agit de minimiser :
n
n x
c
x
c
x
c
z
2
2
1
1
=
On maximisera :
n
n x
c
x
c
x
c
z
...
2
2
1
1
2) Si on a des contraintes du type :
2
2
1
1
x
a
x
a
i
i
in
a
i
n
b
x
on les transformera en :
i
n
in
i
i
b
x
a
x
a
x
a
...
2
2
1
1
3) Si on a des contraintes du type :
2
2
1
1
x
a
x
a
i
i
in
a
i
n
b
x =
elles équivalent à :
2
2
1
1
x
a
x
a
i
i
in
a
i
n
b
x
2
2
1
1
x
a
x
a
i
i
in
a
i
n
b
x
soit encore à :
2
2
1
1
x
a
x
a
i
i
in
a
i
n
b
x
i
n
in
i
i
b
x
a
x
a
x
a
...
2
2
1
1
On peut donc toujours se ramener à la forme énoncée ci-dessus, dite forme canonique
que l'on peut synthétiser en utilisant des notations matricielles.
Posons en effet :
A, matrice (m,n) =