Scribd
Importer
5 vues2 pages

Optimisation par Simplexe en PL

Le document présente un exemple de programmation linéaire (PL) pour une firme produisant deux produits, A et B, avec des ressources M1, M2 et M3. Il décrit la formulation du problème, la transformation en forme canonique, et la résolution par la méthode du simplexe, aboutissant à une solution optimale avec une valeur Z de 22. Les tableaux successifs montrent les itérations et les choix de pivots nécessaires pour atteindre cette solution.

Transféré par

Sara Rzg
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
5 vues2 pages

Optimisation par Simplexe en PL

Le document présente un exemple de programmation linéaire (PL) pour une firme produisant deux produits, A et B, avec des ressources M1, M2 et M3. Il décrit la formulation du problème, la transformation en forme canonique, et la résolution par la méthode du simplexe, aboutissant à une solution optimale avec une valeur Z de 22. Les tableaux successifs montrent les itérations et les choix de pivots nécessaires pour atteindre cette solution.

Transféré par

Sara Rzg
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master

EHEC, Alger Année Universitaire 2012/2013


Groupe 09

Exemple du cours
Soit une firme produisant du A et du B avec du M1, du M2 et du M3, selon le tableau
suivant :

A B Stocks
M1 2 1 8
M2 1 2 7
M3 0 1 3
Gain / unité 4 5

a) Formulation en PL

Max (Z)= 4 + 5

2 + ≤8

+2 ≤7

≤2

, ≥0

b) Résolution avec le simplexe

Le PL n’est pas sous forme canonique, il faut d’abord le transformer en rajoutant des
variables artificielles : y1, y2, y3.

Max (Z)= 4 + 5

2 + + =8

+2 + =7

+ =2

, , , , ≥0

Base x1 x2 y1 y2 y3 B
y1 2 1 1 0 0 8
y2 1 2 0 1 0 7
y3 0 1 0 0 1 3
F obj 4 5 0 0 0 0

La solution initiale est ( , , , , )=(0,0,8,7,3) avec une valeur Z=0, la base contient
{ , , }. On cherche à améliorer la solution en choisissant un pivot suivant les critères en
cours (voir section 3. Algorithme du simplexe).

1
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2012/2013
Groupe 09

Ligne du pivot : ′ =

Autres lignes : ′ = − ′ , ′ = − ′ , ′ = − ′

Le nouveau tableau :

Base x1 x2 y1 y2 y3 B
y1 2 0 1 0 -1 5
y2 1 0 0 1 -2 1
x2 0 1 0 0 1 3
F obj 4 0 0 0 -5 -15
La solution courante est ( , , , , )=(0,3,5,1,0) avec une valeur Z=15, la base contient
{ , , }. On choisit un nouveau pivot.

Ligne du pivot : ′ =

Autres lignes : ′ = − ′ , ′ = − ′ , ′ = − ′

Le nouveau tableau :

Base x1 x2 y1 y2 y3 B
y1 0 0 1 -2 3 3
x1 1 0 0 1 -2 1
x2 0 1 0 0 1 3
F obj 0 0 0 -4 3 -19
La solution courante est ( , , , , )=(1,3,3,0,0) avec une valeur Z=19, la base contient
{ , , }. On choisit un nouveau pivot. Selon les étapes du cours, on devrait choisir
l’élément -2 comme pivot mais le choix de cet élément revient à faire sortir x1 de la base pour
y faire entrer y3. Pour conserver les variables de décision dans la base, on choisit la ligne pivot
1 pour que y1 (qui est une variable artificielle) quitte la base.

Ligne du pivot : ′ = 3

Autres lignes : ′ = − (− ) ′ , ′ = − ′ , ′ = − ′

Le nouveau tableau :

Base x1 x2 y1 y2 y3 B
y3 0 0 1/3 -2/3 1 1
x1 1 0 2/3 -1/3 0 3
x2 0 1 -1/3 2/3 0 2
F obj 0 0 0 -4 3 -22
La solution courante est ( , , , , )=(3,2,0,0,0) avec une valeur Z=22, la base contient
{ , , }. Le vecteur C est entièrement nul ou négatif. Fin du simplexe. La solution obtenue
est optimale.

Vous aimerez peut-être aussi