Scribd
Importer
165 vues2 pages

TD N°3: Résolution Avec La Méthode Simplexe: D'un PL

Le document présente plusieurs exercices sur la résolution de programmes linéaires à l'aide de la méthode du simplexe. Chaque exercice implique la formulation d'un problème, la détermination de solutions réalisables, et l'optimisation des fonctions objectives. Les exercices couvrent des cas de maximisation et de minimisation, ainsi que l'introduction de variables supplémentaires pour respecter les contraintes.

Transféré par

Nathalie Loubeyre
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
165 vues2 pages

TD N°3: Résolution Avec La Méthode Simplexe: D'un PL

Le document présente plusieurs exercices sur la résolution de programmes linéaires à l'aide de la méthode du simplexe. Chaque exercice implique la formulation d'un problème, la détermination de solutions réalisables, et l'optimisation des fonctions objectives. Les exercices couvrent des cas de maximisation et de minimisation, ainsi que l'introduction de variables supplémentaires pour respecter les contraintes.

Transféré par

Nathalie Loubeyre
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°3 : Résolution d’un PL avec la méthode simplexe

Exercice n°1 :

On considère le programme linéaire suivant :

Max z = 6𝑥1 + 7𝑥2 + 8𝑥3

𝑥1 + 2𝑥2 + 𝑥3 ≤ 100

3𝑥1 + 4𝑥2 + 2𝑥3 ≤ 120

2𝑥1 + 6𝑥2 + 4𝑥3 ≤ 20

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

1. Mettre le programme linéaire sous la forme standard.


2. Déterminer la première solution réalisable de base (de départ), en précisant les variables de base
hors base, puis tracer le tableau simplexe initial.
3. Changer la base et appliquer les règles de pivotage jusqu’à ce que la solution optimale soit atteinte
et donner la solution réalisable de chaque itération ainsi que la valeur de la fonction objectif
correspondante.

Exercice n°2 :

On considère le programme linéaire suivant :

Max z = x1 - x2
2 x1 - x2 ≥ -4
x1 - x2 ≤ 4
x1 + x2 ≤ 10
x1 , x2 ≥ 0

1. Résoudre le programme par la méthode du simplexe, et déduire la solution optimale 𝑆1 .


2. Monter qu’il existe un autre sommet optimal 𝑆2 dans le segment [ 𝑆1 , 𝑆2 ].

Exercice n°3 :

Marwa HARZI Optimisation et complexité -- ALSM62


On considère le programme linéaire suivant :

Max z = 3 x1 + 6 x2 - x3 + x4
x1 + ½ x2 + x3 ≤ 2
x1 + 3 x2 + x3 - x4 ≤ 3
2 x1 - x2 − x3 + 3 x4 ≤ 4
x1 , x2 , x3 , x4 ≥ 0

Résoudre le programme par la méthode du simplexe, et déduire la solution optimale.

Exercice n°4 :

On considère le programme linéaire suivant :

Min z = 2 x1 + 3 x2 + x3

x1 + 4 x2 + 2 x3 ≥ 8

– 3 x1 – 2 x2 ≤ – 6

x1 , x2 , x3 ≥ 0

Peut être transformé sous la forme suivante à laquelle s’applique la méthode simplexe.
Min z = 2 x1 + 3 x2 + x3 + M x6 + M x7
x1 + 4 x2 + 2 x3 − x4 + x6 = 8
3 x1 + 2 x2 − x5 + x7 = 6
x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0

1. Quel est le rôle des variables x4 , x5 ?

2. Quel est le rôle des variables x6 , x7 ?

3. Pourquoi introduire les variables x6 , x7 après avoir introduit x4 , x5 ?

4. Quel est le rôle de M ? et pourquoi sa valeur doit être suffisamment grande ?

5. Chercher la solution optimale du problème.

Marwa HARZI Optimisation et complexité -- ALSM62

Vous aimerez peut-être aussi