Methode du simplex
Introduction
La méthode du simplex impose l'utilisation d'équation (et non d'inéquation comme c'était le cas jusqu'ici...)
Pour remedier a ce problème, on introduit des variables d'écart :
- [MIN] Z = 10.x1 + 4.x2
- x1 >= 4
- x2 >= 6
- 1.x1 + 2.x2 >= 20
- 2.x1 + 1.x2 >= 17
|
<=>
|
- [MIN] Z = 10.x1 + 4.x2
- x1 - x3 = 4
- x2 - x4 = 6
- 1.x1 + 2.x2 - x5 = 20
- 2.x1 + 1.x2 - x6 = 17
|
Dans cet exemple, ont a introduit les variables d'écart x3, x4, x5, x6.
La methode par l'exemple...
Etant donné le caractère relativement complexe de la methode du simplex, nous allons etayer cette présentation par
un problème concret qui sera résolu au fur et a mesure... Voici l'énnoncé de cet exemple :
-
La fonction a optimiser :
[MAX] Z = 3.x1 + 2.x2 + x3 + x4 + 5.x5
-
Les contraintes :
- 3.x1 + x3 - x5 = 3
- x1 + x2 - 3.x4 = -12
- x2 + x3 + x5 = 4
-
La contrainte de positivité :
x1, x2, x3, x4, x5 >= 0
|
Quelques conventions / notation
- Soit m le nombre de contraintes du problème (dans notre cas : m=3)
- Soit m+n le nombre de variables du problème (dans notre cas : m+n=5, donc n=2)
-
On représente les coéficients de la fonction a opimiser par le vecteur C =
{c1, c2, c3, c4, c5}
Dans notre cas C = {3, 2, 0, 0, 5}
- On représente les variables par un vecteur X = {x1, x2, x3, x4, x5}
-
On représente les coeficients Ai,j par une matrice A :
Dans notre cas :
-
On va distinguer dans cette matrice les vecteurs colonnes (A1, A2, ... , A5)
Dans notre cas :
-
On note B le vecteur qui contient tout le second membre des equation représentant les contraintes
Dans notre cas :
Quelques définitions
-
Solution : C'est un (m+n)-uplet qui vérifie l'équatio matricielle A.X = B
-
Solution possible : c'est une solution qui vérifie la contrainte de positivité
(x1, x2, ... , x5 positifs)
-
Solution (possible) de base : c'est une solution possible qui vérifie en plus :
- Parmi les m+n quantités xj, il y a n valeures nulles
-
Les vecteurs colonnes Aj dont les indices j sont ceux des n non nuls :
- sont linéairement indépendants
- constituent une base
- constituent une famille libre
Ces trois derniers points ont le même sens mathématique...
-
Solution Optimale : solution (de base) qui optimise la fonction Z.
Pour faire le lien entre la méthode géométrique et le calcul matriciel...
-
Théorème 1 :
Tout point de l'ensemble des solutions qui correspond a une solution de base
est un point extrème de l'ensemble des solutions possibles. On appelle point extrème
tout sommet du polyèdre dont les faces sont les hyperplans définis par les équations
linéaires des contraintes...
-
Théorème 2 :
-
définitions :
-
Convexe : un convexe est un ensemble tels que si on prend 2 points et qu'on les relie entre eux,
le segment formé fait parti de l'ensemble...
Ensemble convexe... Ensemble non convexe...
-
Envellope convexe : l'envellope convexe de plusieurs points est le plus
petit convexe qui contient ces points...
L'envellope convexe de 3 points est le triangle formé en les reliant...
-
Le théorème :
La fonction économique (Z) atteint sont optimum en un point extrème. Si cette
fonction atteint son optimum en plusieurs points extrèmes alors elle prendra son optimum
en tous points de l'envellope convexe de ces points.
Etape 1 : choix d'une solution initiale
La méthode :
-
Pour trouver une solution initiale, on pose :
-
x1, x2, ... , xn = 0
-
xn+1, xn+2, ... , xm >= 0
Le fait de poser n variables nulles permet de déterminer les m restantes en utilisant les contraintes...
Dans notre cas :
-
Les contraintes :
- 3.x1 + x3 - x5 = 3 (équation 1)
- x1 + x2 - 3.x4 = -12 (équation 2)
- x2 + x3 + x5 = 4 (équation 3)
-
On pose x1, x2 = 0 et x3, x4, x5 >= 0
-
On résoud le nouveau système :
-
D'aprés l'équation 2 : -3.x4 = -12 <=> x4 = 3
-
D'aprés les équations 1 et 3 :
-
x3 - x5 = 3
-
x3 + x5 = 4
<=> x3 = 7/2 et
x5 = 1/2
-
pour obtenir la solution initiale : On remplace dans Z :
Zinit = 7/2 + 4 + 5/2 = 10
-
On va chercher les coefficients des vecteurs hors base à partir des vecteurs de base. On désigne les &gama;ij
les coeficients de la décomposition.
-
i est compris entre 1 et n, j est compris entre n+1 et m.
-
Tout vecteur hors base se décompose ainsi :
Etape 2 : détermination du Γ
Notation...
- On utilise l'indice i pour représenter les vecteurs hors base...
- On utilise l'indice j pour représenter les vecteurs de base...
-
On appelle K la matrice formée par les vecteur de base :
Dans notre cas :
dans notre exemple
-
A1 = Γ13.A3 +
Γ14.A4 +
Γ15.A5
-
A2 = Γ23.A3 +
Γ24.A4 +
Γ25.A5
On remplace les vecteurs A1, ..., A5 par leurs valeurs :
L'équation matricielle a résoudre est :
Inversion de la matrice K (calcul de K-1)
On décrit le système linéaire associé à la matrice K :
calcul des coeficients Γij
On peut alors déterminer les coeficients Γij:
Ce qui nous donne :