Td3 : simplexe phase II
Exercice 1
On considère le problème linéaire (P) donné par :
Max Z = 2x₁+x₂+x₃
S.C. x₁+x₂+3x₃ ≤ 6
2x₁+x₂+5x₃ ≤ 8
x₁, x₃, x₃≽0
1- Donner la solution et la valeur optimale de (P), en utilisant la méthode du simplexe.
2- La solution est elle unique ? Justifier !
3- La solution x=(2,4,0) est elle une solution de base réalisable pour (P) ? est-elle optimale
pour (P) ?
Solution
1- Le système sous format standard, en ajoutant les variables d’écarts, est donné par
Max Z = 2x₁+x₂+x₃
S.C. x₁+x₂+3x₃+x4 = 6
2x₁+x₂+5x₃+x5 = 8
x₁, x2, x₃, x4, x5≽0
On applique l’algorithme du simplexe phase II. On prend comme base initial B=(x4, x5) et le
tableau initial est donné par
X1 X2 X3 X4 X5 C R
X4 1 1 3 1 0 6 6/1
X5 2 1 5 0 1 8 8/2=4
Δ 2 1 1 0 0 0
Comme Δ n’est pas négative alors on a doit faire une nouvelle itération. D’après le tableau, la
variable hors base dont le coefficient positif est le plus grand est donné par la variable X1,
donc X1 est la variable entrante dans la base. Comme la valeur minimale associée aux valeurs
des variables de base dans la colonne R est donné par la valeur de X5, donc X5 est la variable
sortante de la base
On obtient alors le nouveau tableau suivant
X1 X2 X3 X4 X5 C R
X4 0 1/2 1/2 1 -1/2 2
X1 1 1/2 5/2 0 1/2 4
Δ 0 0 -4 0 -1 -8
Comme Δ est négative, donc l’algorithme s’arrête et on a la solution optimale est
(X1,X2,X3)=(4,0, 0) et la valeur optimale est Zopt = 8.
2- La solution n’est pas unique car l’une des variables hors base a un coefficient nul dans la
ligne de delta.
3- Montrer que X = (2, 4, 0) est une solution de base réalisable pour (P) ce qui est équivalent
à X1=(2,4,0, x4 = 6- x₁-x₂-3x₃, x5 = 8-2x₁-x₂-5x₃)=(2,4,0, 0, 0) est une solution de base
réalisable pour (P) sous format standard ).
a. On a X1 vérifie toutes les contraintes de (P) sous format standard et que X1 ≥ 0
avec comme base réalisable associée est B=(A1, A2) « det(B)=-1 ». Donc une
solution de base réalisable pour (P) sous format standard et par suite X = (2, 4,
0) est une solution de base réalisable pour (P)
b. Aussi, X1 est sommet du polyèdre associé à (P) sous format standard et X = (2,
4, 0) est sommet du domaine d’admissible associé à (P)
Exercice 2
La fabrique RadioIn crée deux types de radios A et B. Chaque radio produite est le fruit des
efforts conjoints de 3 spécialistes Pierre, Paul et Jean. Pierre travaille au plus 24 heures par
semaine. Paul travaille au plus 45 heures par semaine. Jean travaille au plus 30 heures par
semaine. Les ressources nécessaires pour construire chaque type de radio ainsi que leurs prix
de vente sont donnés dans le tableau ci-dessous :
On suppose que l’entreprise n’a aucun problème à vendre sa production, quelle qu’elle soit.
a) Modéliser le problème de la recherche d’un plan de production hebdomadaire maximisant
le chiffre d’affaires de RadioIn sous forme d’un programme linéaire. Préciser clairement
les variables de décision, la fonction objectif et les contraintes.
b) Résoudre ce programme linéaire graphiquement et donner le plan de production optimal.
c) Résoudre, en utilisant la méthode du simplexe
d) Laquelle des contraintes est saturée par la solution trouvée et pourquoi ?
Solution
a-
- Objectif : maximisant le chiffre d’affaires de RadioIn. On constate que:
o La fabrication d’un type de radio est faite en fonction du nombre total d’heures
de travail par semaine des trois spécialistes.
- Les variables de décision sont données par :
o x1 : le nombre de radio de type A qui est fabriqué conjointement par les
spécialistes en une semaine.
o x2 : le nombre de radio de type B qui est fabriqué conjointement par les
spécialistes en une semaine.
- Construction du système de contrainte :
Pierre travaille au plus 24 heures par semaine et intervient 1h pour la fabrication d’un
radio de type A et 2h pour la fabrication d’un radio de type B, alors on déduit que :
x1 + 2x2 ≤ 24
Paul travaille au plus 45 heures par semaine et intervient 2h pour la fabrication d’un
radio de type A et 1h pour la fabrication d’un radio de type B, alors on déduit que :
2x1 + x2 ≤ 45.
Jean travaille au plus 30 heures par semaine et intervient 1h pour la fabrication d’un
radio de type A et 3h pour la fabrication d’un radio de type B, alors on déduit que :
x1 + 3x2 ≤ 30
comme le prix de vente d’un radio de type A est égale à 15 et que le prix de vente d’un
radio de type B est 10, donc la fonction objectif à maximiser est
z = 15x1 + 10x2
Donc, le Programme linéaire qui représente le plan de production hebdomadaire maximisant
le chiffre d’affaires de RadioIn est donné par :
max z 15 x1 10 x 2
s.c x 2 x 24
1 2
2 x1 x 2 45
x1 3 x 2 30
x1 0, x 2 0
b- La représentation graphique du problème est la suivante
grad(Z
On détermine la solution optimale graphiquement en représentant les lignes de niveau de la
fonction objectif. La solution optimale est x1 = 22 et x2 = 1 et sa valeur est égale à z=340.
c- Sous format standard, le problème est donné par :
max z 15 x1 10 x 2
s.c x 2 x x 24
1 2 3
2 x1 x 2 x 4 45
x1 3 x 2 x5 30
x1 0, x 2 0, , x3 0, x 4 0, x5 0
En prenant comme base admissible B = (x3, x4, x5) avec les variables hors base sont x1 et x2
On obtient la solution admissible X*=(0, 0, 24, 45, 30) et la valeur de la fonction objectif est
z* = 0.
Le premier tableau associé à la méthode du simplexe est donné par :
HB x1 x2 x3 x4 x5 C R
x3 1 2 1 0 0 24 24
x4 2 1 0 1 0 45 45/2
x5 1 3 0 0 1 30 30
Δ 15 10 0 0 0 0
2ème itération :
D’après le tableau ci-dessus, on déduit que la variable entrante est x1 et la variable sortante est
x4, d’où le tableau suivant :
HB x1 x2 x3 x4 x5 C R
x3 0 3/2 1 -1/2 0 3/2 1
x1 1 1/2 0 1/2 0 45/2 44
x5 0 5/2 0 -1/2 1 15/2 3
Δ 0 5/2 0 -15/2 0 -675/2
3ème itération :
D’après le tableau ci-dessus, on déduit que la variable entrante est x2 et la variable sortante est
x3, d’où le tableau suivant :
HB x1 x2 x3 x4 x5 C R
x2 0 1 2/3 -1/3 0 1
x1 1 0 -1/3 2/3 0 22
x5 0 0 -5/3 -4/3 1 5
Δ 0 0 -5/3 -20/3 0 -340
Comme Δ ≤ 0, on déduit que la méthode du simplexe s’arrête, d’où la solution optimale du
problème initiale est (x1, x2) = (22, 1) et la valeur optimale de la fonction objectif est zop=340.
d- On a comme les variables d’écart n’ont pas tous une valeur nulle et que x5 appartient à la
base optimale alors la troisième contrainte n’est pas saturée pour la solution optimale obtenue.
Toutes les autres contraintes sont saturées car x3=x4=0.
Exercice 3
Une entreprise dispose de deux machines M1 et M2 pour produire deux types d’articles A1 et
A2. La machine M1 travaille 80 heures par semaine et M2 travaille 110 heures par semaine. La
fabrication de chaque produit requiert l’utilisation des deux machines, dans le tableau ci-
dessous l’élément (i, j) donne le temps nécessaire (en heure) pour la fabrication de l’article Aj
par la machine Mi, ainsi que le profit cj que rapporte chaque unité de ces deux produits.
A1 A2
Temps sur la machine M1 2 4
Temps sur la machine M2 3 5
Profit cj 6 10
1- Donner une modélisation du problème linéaire, nommé (P), représentant l’objectif de
l’entreprise qui est de maximiser le profit.
2- Résoudre le problème (P) via la méthode du simplexe
3- La solution optimale obtenue de (P) est-elle unique ? (Justifier votre réponse).
Solution
1- On pose xi le nombre d’articles du type Ai produit par semaine.
On obtient alors le problème linéaire (P) suivant :
max Z = 6x1+10x2
2x1+4x2 ≤ 80
3x1+5x2 ≤ 110
x1, x2 ≥ 0
2- Le problème (P) sous format standard est donné par :
max Z = 6x1+10x2
2x1+4x2+x3 = 80
3x1+5x2+ x4 = 110
x1, x2, x3, x4 ≥ 0
Avec x3, x4 sont les variables d’écart. On applique l’algorithme de simplexe phase II
afin de résoudre (P).
On a une base admissible initiale est Bi=(x3, x4)
Le tableau initiale est donné par
X1 X2 X3 X4 C R
X3 2 4 1 0 80 20
X4 3 5 0 1 110 110/5
∆ 6 10 0 0 0
On a la variable entrante est x2 et la variable sortante est X3, donc le deuxième
tableau est donné par :
X1 X2 X3 X4 C R
X2 1/2 1 1/4 0 20 40
X4 1/2 0 -5/4 1 10 20
∆ 1 0 -5/2 0 -200
Ce tableau n’est pas optimal car ∆ n’est pas négative, donc on doit faire une autre
itération.
On a la variable entrante x1 et la variable sortante est x4, donc le troisième tableau
est donné par :
X1 X2 X3 X4 C R
X2 0 1 3/2 -1 10
X1 1 0 -5/2 2 20
∆ 0 0 0 -2 -220
Ce tableau est optimal car ∆ est négative, et la solution optimale est
(x1, x2) = (20, 10) et la valeur optimale Zmax = 220.
La solution optimale de (P) n’est pas unique car, il existe une variable hors base qui a une
valeur nulle (X3 = 0).
Exercice 4
Utiliser l’algorithme du simplexe pour trouver tous les sommets optimaux du problème
suivant :
Max z = 2x1 + 3x2 + 5x3 + 4x4
S.C x1+ 2x2 + 3x3 + x4 ≤ 5
x1 + x2 + 2x3 + 3x4 ≤ 3
x1, x2, x3, x4 ≥ 0
Solution
Le problème initial est sous la forme canonique et en ajoutant les variables d’écart, t1 et t2
alors on obtient la forme standard du problème initial, donnée par :
Max z = 2x1 + 3x2 + 5x3 + 4x4
S.C x1+ 2x2 + 3x3 + x4 + t1 = 5
x1 + x2 + 2x3 + 3x4 + t2 = 3
x1, x2, x3, x4, t1, t2 ≥ 0
On a comme b= (5, 3) ≥ 0, donc on peut appliquer la méthode simplexe phase II.
En prenant comme base admissible initial B = (t1, t2) avec les variables hors base sont x1, x2,
x3 et x4
On obtient la solution admissible initiale X*= (0, 0, 0, 0, 5, 3) et la valeur de la fonction
objectif est z* = 0.
Le premier tableau associé à la méthode du simplexe est donné par :
HB x1 x2 x3 x4 t1 t2 C R
t1 1 2 3 1 1 0 5 5/3
t2 1 1 2 3 0 1 3 3/2
Δ 2 3 5 4 0 0 0
2ème itération :
D’après le tableau ci-dessus, on déduit que la variable entrante est x3 et la variable sortante est
t2, d’où le tableau suivant :
HB x1 x2 x3 x4 t1 t2 C R
t1 -1/2 1/2 0 -7/2 1 -3/2 1/2 1
x3 1/2 1/2 1 3/2 0 2 3/2 3
Δ -1/2 1/2 0 -7/2 0 -5/2 -15/2
3ème itération :
D’après le tableau ci-dessus, on déduit que la variable entrante est x2 et la variable sortante
est t1, d’où le tableau suivant :
HB x1 x2 x3 x4 t1 t2 C R
x2 -1 1 0 -7 2 -3 1
x3 1 0 1 5 -1 7/2 1
Δ 0 0 0 0 -1 -1 -8
Comme Δ ≤ 0, on déduit que la méthode du simplexe s’arrête, d’où la solution optimale du
problème initiale est (x1, x2, x3, x4) = (0,1, 1, 0) et la valeur optimale de la fonction objectif est
zop= 8.
Remarque : les variables hors base x1 et x4 ont un coefficient nul dans la ligne de Δ, donc la
solution du problème n’est pas forcément unique.
Comment trouver tous les sommets optimaux ?
On a d’après le dernier tableau, on déduit pour toute solution optimale, on doit avoir t1
= t2 = 0 ceci est du au fait que dans la ligne des couts réduit les coefficients de t1 et t2
sont négative donc t1 et t2 ne peuvent pas entrer dans n’importe quelle nouvelle base
o par contre, on peut faire entrer x1 ou x4 et en utilisant la règle de Blend,
o alors on peut faire entrer la variable x1 et faire sortir la variable x3,
o or comme dans la ligne des couts réduit le coefficient de x1 est nul donc la
ligne des couts réduit ne sera pas modifier et on aura toujours t1 et t2 sont des
variables hors base
d’où et de la même manière, on peut repasser dans tous les sommets
optimaux puis on aura que la ligne des coûts réduit sera inchangée.
De plus, d’après le dernier tableau, on déduit que.
x2 = 1+ x1 + 7 x4
x3 = 1 – x1 - 5x4
Donc, toute solution optimale est solution du problème (Q) donné par
x2 = 1+ x1 + 7 x4
x3 = 1 – x1 - 5x4
xi ≥ 0 ; i=1..4
t1 = t2 = 0
Or, comme le rang de la matrice A qui est la matrice du système initiale est égal 2,
alors tout sommet à au minimum quatre valeur nulle c.a.d a au plus deux valeurs
strictement positives, ceci d’après théorème de caractérisation des sommets.
On sait que déjà t1=t2=0, il reste donc avoir les cas suivants qui doivent respecter le
fait que : tout sommet à au minimum quatre valeur nulle.
- Si (x1, x2, x3, x4) = (0, 0, 0, 0), ceci est impossible car on aura 1 = 0 d’après la premier
égalité du problème (Q).
- Si (x1, x2, x3) = (x1, x2, x4)= (x1, x3, x4)= (x2, x3, x4)= (0, 0, 0), on aura une
contradiction avec l’une des deux équations du problème (Q)
- Si (x1, x2) = (0, 0) alors x4 < 0, on n’a pas une solution admissible
- Si (x1, x3) = (0, 0) alors x4 = 1/5 et x2 = 12/5, donc (x1, x2, x3, x4) = (0, 12/5, 0, 1/5) est
une solution optimale
- Si (x1, x4) = (0, 0) alors x3 = 1, x2 = 1, donc (x1, x2, x3, x4) = (0, 1, 1, 0) est une solution
optimale
- Si (x2, x3) = (0, 0) alors x4 = -1 < 0, on n’a pas une solution admissible
- Si (x2, x4) = (0, 0) alors x1 = -1 < 0, on n’a pas une solution admissible
- Si (x3, x4) = (0, 0) alors x1 = 1 et x2 = 2, donc (x1, x2, x3, x4) = (1, 2, 0, 0) est une
solution optimale
-
En final, on a les trois sommets optimaux sont :
(x1, x2, x3, x4) = (1, 2, 0, 0) ;
(x1, x2, x3, x4) = (0, 1, 1, 0)
et (x1, x2, x3, x4) = (0, 12/5, 0, 1/5)
Exercice 5
Soit le programme linéaire (P) suivant
Max z = 10 x1 + 14 x2
S.C : x1 + x2 ≥ 12
x1 ≥ 8
x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
1- Montrer que A = (12, 0) est un sommet du domaine admissible de (P)
2- Résoudre le problème par la méthode du simplexe en prenant comme point de départ K
qui est la solution de base admissible K associée à A pour le problème de (P) sous format
standard.
Réponse
1- On a la forme standard du problème (P) est donnée par :
Donc, la solution de base admissible K associée à A est donnée par K=(12, 0, x3, x4, x5),
en utilisant la forme standard du problème (P), on déduit que x3=0 ; x4=4 et x5=6. Donc
les variables actives sont x1, x4 et x5 forment la base admissible B=(x1, x4, x5) associée à
K
2- Exprimons les variables de base et la fonction objectif en fonction des variables hors base
x2 et x3 :
z = 120 + 4 x2 + 10 x3
x1 = 12 - x2 + x3
x4 = 4 - x2 + x3
x5 = 6 - x2
Donc, le problème (P) peut s’écrire sous la forme suivante
max z = 120+4 x2+10 x3
x1+x2-x3=12
x2-x3+x4=4
x2+x5=6
x1≥0, x2≥0, x3≥0, x4≥0, x5≥0,
On a donc, une solution de base réalisable initiale (x1, x2, x3, x4, x5)= (12, 0, 0, 4, 6)
Le tableau du simplexe initial est donné par :
X1 X2 X3 X4 X5 C R
X1 1 1 -1 0 0 12
X4 0 1 -1 1 0 4
X5 0 1 0 0 1 6
Δ 0 4 10 0 0 -120
D’après le tableau ci-dessus, on a la variable X3 est une variable hors base dont la valeur dans
la ligne Δ est strictement positive et sa colonne ne contient que des valeurs négatives ou nulles,
donc la solution du problème initiale est non bornée d’après le cours.