Scribd
Importer
2 vues2 pages

EX05

Le document présente la résolution d'un programme linéaire par la méthode du simplexe en deux phases, avec une fonction objectif à minimiser et des contraintes sous forme d'inégalités. La première phase consiste à éliminer les variables artificielles, tandis que la seconde phase vise à optimiser la fonction objectif, aboutissant à une solution optimale de (x1, x2, x3) = (6, 2, 0) avec une valeur minimale de Z = 18. Les étapes incluent la mise sous forme standard, le pivotement et l'optimisation finale.

Transféré par

iliyass.ouafi
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
2 vues2 pages

EX05

Le document présente la résolution d'un programme linéaire par la méthode du simplexe en deux phases, avec une fonction objectif à minimiser et des contraintes sous forme d'inégalités. La première phase consiste à éliminer les variables artificielles, tandis que la seconde phase vise à optimiser la fonction objectif, aboutissant à une solution optimale de (x1, x2, x3) = (6, 2, 0) avec une valeur minimale de Z = 18. Les étapes incluent la mise sous forme standard, le pivotement et l'optimisation finale.

Transféré par

iliyass.ouafi
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

Résolution d’un Programme Linéaire

Méthode du Simplexe (Deux Phases)

Énoncé
min Z = 2x1 + 3x2 + 4x3
sous contraintes : 4x1 + 8x2 + 6x3 ≥ 40
200x1 + 150x2 + 100x3 ≥ 1500
x1 , x2 , x3 ≥ 0

1. Mise sous forme standard


Pour les contraintes ≥, on introduit :

• variables d’excès : s1 , s2

• variables artificielles : a1 , a2

4x1 + 8x2 + 6x3 − s1 + a1 = 40


200x1 + 150x2 + 100x3 − s2 + a2 = 1500

x1 , x2 , x3 , s1 , s2 , a1 , a2 ≥ 0

2. Phase I : élimination des variables artificielles


Fonction auxiliaire :

W = a 1 + a2

Tableau initial
Base x1 x2 x3 s 1 s 2 a1 a2 b
a1 4 8 6 −1 0 1 0 40
a2 200 150 100 0 −1 0 1 1500
W −204 −158 −106 1 1 0 0 −1540

1
Pivot
La variable entrante est x1 (coefficient le plus négatif).
Test du rapport :
40
= 10
4
1500
= 7.5
200
Donc a2 sort de la base.

Nouveau tableau
Base x1 x2 x3 s1 s2 a1 a2 b
a1 0 5 4 −1 0.02 1 −0.02 10
x1 1 0.75 0.5 0 −0.005 0 0.005 7.5
W 0 −5 −4 1 −0.02 0 1.02 −10
Après quelques pivots supplémentaires, les variables artificielles sortent de la base.

3. Phase II : optimisation
On revient à la fonction objectif :

Z = 2x1 + 3x2 + 4x3


Le simplexe donne la solution optimale suivante :

x1 = 6, x2 = 2, x3 = 0

4. Valeur optimale
Z = 2x1 + 3x2 + 4x3

Z = 2(6) + 3(2) + 4(0)

Z = 18

Solution optimale
(x1 , x2 , x3 ) = (6, 2, 0)

Zmin = 18

Vous aimerez peut-être aussi