Généralités sur la programmation linéaire
27
En conclusion, un point extrême du domaine D est obtenu en choisissant m vecteurs
P 1 , P 2 , P m indépendants parmi les
m
n
vecteurs P 1 , P 2 , P n+m et en résolvant le
système de Cramer :
b
P
x
P
x
P
x
m
m
=
2
2
1
1
Le point (
obtenu est un point extrême si les
sont
positifs ou nuls.
Si un certain nombre de x i parmi les x 1 , x 2 , …x m sont nuls, la solution est dite dégénérée.
La solution
correspondant à un point extrême est dite solution de
base du programme linéaire.
sont appelées les variables de base pour la solution de base considérée,
les variables hors base.
Une autre conclusion très importante de ces deux théorèmes est la suivante : le nombre
de points extrêmes du domaine des solutions réalisables, donc le nombre de solutions de
base est fini. En effet ce nombre est borné par
!
!
)!
(
m
n
m
n
C
m
m
n
nombre de système de
m vecteurs que l'on peut extraire des vecteurs
1.3.4. Définition géométrique des points extrêmes du domaine des solutions
réalisables.
D'après ce que l'on vient de voir, un point extrême est obtenu en annulant n variables x i
parmi les
variables du programme mis sous forme standard, et en résolvant le
système d'équations par rapport aux m variables restantes (variables de base).
Sur ces n variables nulles (variables hors base) un certain nombre p sont des variables
principales et
sont des variables d'écart.
Soit une variable principale hors base i
est l'équation d'un plan de coordonnées
dans
n (espace des variables principales).
Si maintenant on a une variable d'écart n+j hors base, soit n+j
, c'est que la
contrainte correspondant à cette variable d'écart est saturée. On a donc l'équation :
j
n
jn
j
j
b
x
a
x
a
x
a
=
2
2
1
1
qui est l'équation d'un hyperplan dans l'espace des variables principales (
n ).
Donc, un point extrême du domaine D correspond à l'intersection de n hyperplans dans
l'espace R
n des variables principales pris soit dans les hyperplans de coordonnées
(
) soit dans les hyperplans correspondants aux contraintes du programme linéaire
27
En conclusion, un point extrême du domaine D est obtenu en choisissant m vecteurs
P 1 , P 2 , P m indépendants parmi les
m
n
vecteurs P 1 , P 2 , P n+m et en résolvant le
système de Cramer :
b
P
x
P
x
P
x
m
m
=
2
2
1
1
Le point (
obtenu est un point extrême si les
sont
positifs ou nuls.
Si un certain nombre de x i parmi les x 1 , x 2 , …x m sont nuls, la solution est dite dégénérée.
La solution
correspondant à un point extrême est dite solution de
base du programme linéaire.
sont appelées les variables de base pour la solution de base considérée,
les variables hors base.
Une autre conclusion très importante de ces deux théorèmes est la suivante : le nombre
de points extrêmes du domaine des solutions réalisables, donc le nombre de solutions de
base est fini. En effet ce nombre est borné par
!
!
)!
(
m
n
m
n
C
m
m
n
nombre de système de
m vecteurs que l'on peut extraire des vecteurs
1.3.4. Définition géométrique des points extrêmes du domaine des solutions
réalisables.
D'après ce que l'on vient de voir, un point extrême est obtenu en annulant n variables x i
parmi les
variables du programme mis sous forme standard, et en résolvant le
système d'équations par rapport aux m variables restantes (variables de base).
Sur ces n variables nulles (variables hors base) un certain nombre p sont des variables
principales et
sont des variables d'écart.
Soit une variable principale hors base i
est l'équation d'un plan de coordonnées
dans
n (espace des variables principales).
Si maintenant on a une variable d'écart n+j hors base, soit n+j
, c'est que la
contrainte correspondant à cette variable d'écart est saturée. On a donc l'équation :
j
n
jn
j
j
b
x
a
x
a
x
a
=
2
2
1
1
qui est l'équation d'un hyperplan dans l'espace des variables principales (
n ).
Donc, un point extrême du domaine D correspond à l'intersection de n hyperplans dans
l'espace R
n des variables principales pris soit dans les hyperplans de coordonnées
(
) soit dans les hyperplans correspondants aux contraintes du programme linéaire