Scribd
Importer
31 vues23 pages

Exercices corrigés sur le simplexe

Ce document présente plusieurs exercices sur la méthode du simplexe pour résoudre des problèmes de programmation linéaire. Il explique comment appliquer l'algorithme du simplexe et résoudre des exercices avec des solutions multiples, non bornées ou avec redondance parmi les contraintes.

Transféré par

gowero6402
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
31 vues23 pages

Exercices corrigés sur le simplexe

Ce document présente plusieurs exercices sur la méthode du simplexe pour résoudre des problèmes de programmation linéaire. Il explique comment appliquer l'algorithme du simplexe et résoudre des exercices avec des solutions multiples, non bornées ou avec redondance parmi les contraintes.

Transféré par

gowero6402
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

TD n°2: Simplexe

• Dans les exercices suivants, appliquer


l’algorithme du simplexe pour
résoudre le problème de
programmation linéaire
Exercice 1: solution multiple

• déterminer la solution optimale ?


x y S1 S2 Cj
S1 2 4 1 0 12
S2 4 3 0 1 16
1 2 0 0 0
• Forme 1 • Forme 2
x y S1 S2 Cj
S1 2 4 1 0 12
S2 4 3 0 1 16
1 2 0 0 0

• Forme 3 : [Link] • Forme 4 Lien:phpsimplex

5
• Le test d'arrêt ?
• Solution ?
• D’autres solutions?
Solution n° 1 : X=0, Y=3, S1=0, S2=7

Solution n° 2 : X=14/5, Y=8/5, S1=0, S2=0


Exercice 2: le modèle n'admet pas MAX Z = x1 + 2x2
de solution optimale
x1 + 2x2 <= 5
2x1 + x2 <= 6
x1 + x2 >= 4
and x1,x2 >= 0
=4-(5*1)/2=(8-5)/2=3/2
• Cette solution est admissible
?
• x1 + x2 ≥ 4.?
Solution : X1=7/3, x2=4/3
Exercice 3 : ( solutions non bornées)

MAX Z = x1 - x2 + x3

2x1 - x2 - 2x3 <= 4


2x1 - 3x2 - x3 <= -5
-x1 + x2 + x3 >= -1
and x1,x2,x3 >= 0
MAX Z = x1 - x2 + x3

2x1 - x2 - 2x3 <= 4


2x1 - 3x2 - x3 <= -5
-x1 + x2 + x3 >= -1
and x1,x2,x3 >= 0
• La variable qui va sortir ?
• La solution ?

• il n'existe pas de solution optimale finie , Z n'est pas bornée (unbounded)


Si dans la colonne correspondant à la variable entrante toutes les variables
de base ont un coefficient négatif ou nul alors il n'existe pas de solution
optimale finie (aucune contrainte ne limite l'augmentation de la valeur de la
variable entrante et en conséquence la valeur de la fonction objectif n'est
pas bornée)
Exercice 4: (redondance)

MAX Z = 5x1 + 6x2


subject to
3x1 + 6x2 <= 8
6x1 + 12x2 <= 16
and x1,x2 >= 0
• S=0!!!!!!!!!!!!!
• J’ai pas remarqué que ….?

Sol : X1 = 8/3 , X2 = 0
S=0 une contrainte est redondante
Ex 5:

Est-ce qu’ il y a toujours un ou plusieurs


sommet parmi les solutions optimales d’un
problème linéaire ?
(justifier votre réponse )

Vous aimerez peut-être aussi