FACULTE DES SCIENCES 3 ème Année L.
F
ECONOMIQUES ET DE GESTION Ing. Eco. & Financière
DE SOUSSE chargé du cours : Mr Mourad Belkahla
Année Universitaire 2023/2024
SERIE 3 RECHERCHE OPERATIONNELLE
Algorithme du simplexe
EXERCICE 1
Soit le problème de programmation linéaire suivant :
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 3𝑥1 + 2𝑥2
𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 2𝑥2 ≤ 7
2𝑥1 + 𝑥2 ≤ 8
−𝑥1 + 𝑥2 ≤ 2
𝑒𝑡 𝑥1 , 𝑥2 ≥0
1) Ajouter les variables d’écart
2) Résoudre par la méthode du simplexe
3) Tracer la région réalisable et indiquer graphiquement le chemin suivi par l’algorithme
du simplexe.
4) Vérifier en traçant la droite de la fonction objectif que le point obtenu par l’algorithme
du simplexe est bien optimum.
EXERCICE 2
Une entreprise fabrique trois produits 𝑃1 , 𝑃2 et 𝑃3 à partir de trois composants 𝑐1 , 𝑐2 et 𝑐3 .
Les contraintes d’approvisionnement sont telles que l’entreprise dispose, chaque semaine de 70
composants 𝑐1 , de 80 composants 𝑐2 et de 60 composants 𝑐3 . Pour fabriquer 𝑃1 , il faut 1 unité
de 𝑐1 , 2 unités de 𝑐2 , et 3 unités de 𝑐3 . ;pour fabriquer 𝑃2 , il faut 2 unités de 𝑐1 , 1 unité de 𝑐2 , et
2 unités de 𝑐3 . Pour fabriquer 𝑃3 , il faut 4 unités de 𝑐1 , 2 unités de 𝑐2 , et 2 unités de 𝑐3 . Les
marges sur les ventes sont de 3Dinars pour 𝑃1 , de 5 Dinars pour 𝑃2 et de 6 Dinars pour 𝑃3 .
On note par 𝑥 , 𝑦 , 𝑒𝑡 𝑧 les nombres d’unités de 𝑃1 , 𝑃2 et 𝑃3 fabriquées au cours d’une semaine.
1) Ecrire le programme linéaire permettant de maximiser la marge sur les ventes
hebdomadaires.
2) Nous allons résoudre ce problème par la méthode du simplexe.
a) Préciser pour chaque étape, en justifiant les choix effectués, la variable entrante, la
variable sortante et le pivot.
b) Quelle particularité du dernier tableau montre que l’optimum est atteint ?
c) Quel est le programme optimal de production ? quelle est la marge correspondante ?
1
d) Si l’entreprise fabrique le programme optimal, combien reste-il de composants de
chaque sorte ?
EXERCICE 3
Soit le tableau de simplexe suivant où la fonction objectif est à maximiser
Cj 1 2 0 0 0 XB
CB Variables x 1 x2 e1 e2 e3
de base
x1 1 0 1 0 -2 2
e2 0 0 -2 1 3 2
x2 0 1 0 0 1 2
Zj
Zj-Cj
1) Compléter les lignes du tableau.
2) Dites s’il s’agit d’un tableau optimal.
3) Quelle est la solution de base associée à ce tableau et quelle est la valeur correspondante
de la fonction objectif.
4) Combien de contraintes comporte le programme linéaire.
5) Ecrire le programme linéaire.
EXERCICE 4
Trois types de poudre servant à propulser une fusée doivent être mélangés pour fournir un
carburant répondant à des spécifications données :
- Puissance propulsive ≥ 2
- Facteur corrosif ≤ 6.4
- Poids (𝑘𝑔/𝑑𝑚3 ) ≤ 8
Pour un 𝑑𝑚3 de poudre on a les données suivantes
Poudre A B C
Puissance propulsive 10 5 2
Facteur corrosif 10 4 6
Poids (kg) 6 10 8
Coût 10 5 8
1) On a besoin de 60 𝑑𝑚3 de poudre pour la fusée. Quel est le coût minimum du carburant
demandé ?
2) Déduire de ces données un problème de programmation linéaire et l’exprimer sous
forme standard.
2
EXERCICE 5
Résoudre par la méthode du simplexe les programmes linéaires suivants :
a)
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 4𝑥1 + 5𝑥2 + 𝑥3
𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 𝑥1 + 𝑥2 + 𝑥3 ≤ 8
𝑥1 + 2𝑥2 − 𝑥3 ≥ 2
𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
b)
𝑀𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 28𝑥1 + 24𝑥2
𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 4𝑥1 + 2𝑥2 ≥ 6
8𝑥1 + 2𝑥2 ≥ 8
𝑒𝑡 𝑥1 , 𝑥2 ≥ 0
EXERCICE 6
On considère le programme linéaire suivant
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒𝑟 𝑍 = 5𝑥1 − 2𝑥2 + 14𝑥3
𝑆𝑜𝑢𝑠 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠 2𝑥1 + 2𝑥2 − 𝑥3 ≥ 2
3𝑥1 − 4𝑥2 ≤ 3
𝑥2 + 3𝑥3 ≤ 5
𝑒𝑡 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
1) Mettre le programme linéaire (𝑃) sous forme standard.
2) Résoudre (𝑃) par l’algorithme du simplexe.
3) La solution de (𝑃) est-elle unique ?
3
EXERCICE 7
Le tableau de simplexe suivant est obtenu en minimisant une fonction objectif z soumise à trois
contraintes technologiques.
Cj a d 0 0 0 XB
CB VB x1 x2 e1 e2 e3 VVB
-2/3 0 1 0 1/6 46
-18 0 0 1 5/2 k
b 1 0 0 -1/6 4
Zj m
Zj-Cj c e h j -1/2
a) Donner les variables de base de ce tableau.
b) La structure du tableau force certains paramètres à prendre une valeur unique et précise.
Indiquer quels sont ces paramètres et déterminer leurs valeurs.
c) À quelles conditions doivent répondre les paramètres pour que la solution de base
associée à ce tableau soit dégénérée?
d) À quelles conditions doivent répondre les paramètres pour que la solution de base
associée à ce tableau soit l’unique solution optimale du modèle linéaire?
e) À quelles conditions doivent répondre les paramètres pour que le tableau soit optimal et
que le modèle admette une infinité de solutions optimales?
f) À quelles conditions doivent répondre les paramètres pour que le modèle linéaire ne soit
pas borné.