INSEA - Modèles Discrets - Algorithme Du Simplexe

Modèles discrets
2ème année
ROAD | DSE |DS
Wadie CHATT
INSEA | 2020-2021
Questions
Algorithme du
simplexe
Algorithme du simplexe
Exemple
Résoudre le programme linéaire ci-après :
max 𝑋1 + 2𝑋2 = 𝑧
s.c −3𝑋1 + 2𝑋2 ≤ 2
(𝑃) −𝑋1 + 2𝑋2 ≤ 4
𝑋1 + 𝑋2 ≤ 5
𝑋1 , 𝑋2 ≥ 0
L’objectif étant de trouver 𝑿𝟏 et 𝑿𝟐 pour que Z soit maximale

Exemple
Ajout des variables d’écart
Déterminer une solution de

base réalisable
Solution OUI
optimale Stop
?
Non
Trouver une solution
admissible
Tableau du simplexe
Coefficients de la fonction objectif du P de départ
Variables de base et hors base

Coef. Des Valeurs des variables de
Nbre
variables Variables Matrice des coefficients de la forme canonique par base de la solution de
d’itération
de base de base rapport à la base réalisable J du système linéaire base réalisable associée à
s
dans P J
Opposé de la valeur de la
Max Coût réduit relatif à la base réalisable J
fonction objectif
Valeur de la fonction
Min Opposé du Coût réduit relatif à la base réalisable J
objectif
Résolution de l’exemple
max 𝑋1 + 2𝑋2 = 𝑧
s.c −3𝑋1 + 2𝑋2 ≤ 2
(𝑃) −𝑋1 + 2𝑋2 ≤ 4
𝑋1 + 𝑋2 ≤ 5
𝑋1 , 𝑋2 ≥ 0
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
−𝑋1 + 𝑋2 + 𝒕𝟑 = 5
Algorithme du simplexe max 𝑋1 + 2𝑋2 = 𝑧
s.c −3𝑋1 + 2𝑋2 ≤ 2
Résolution de l’exemple −𝑋1 + 2𝑋2 ≤ 4
(𝑃)
𝑋1 + 𝑋2 ≤ 5
𝑋1 , 𝑋2 ≥ 0
Solution de base réalisable ?

𝑋1 = 0, 𝑋2 = 0
𝒕𝟏 = 2
𝒕𝟐 = 4
𝒕𝟑 = 5
𝒛=𝟎 Optimale
Tableau du simplexe
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
𝑋1 + 𝑋2 + 𝒕𝟑 = 5 Contraintes
Variables hors base
1 2 0 0 0 0 1
X1 X2 t1 t2 t3 C K
0 t1
Variables
0 0 t2
de base
0 t3
Max
Tableau du simplexe
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
𝑋1 + 𝑋2 + 𝒕𝟑 = 5
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2
0 t3
Max
Tableau du simplexe
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
𝑋1 + 𝑋2 + 𝒕𝟑 = 5
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2 -1 2 0 1 0 4
0 t3
Max
Tableau du simplexe
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
𝑋1 + 𝑋2 + 𝒕𝟑 = 5
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max
Tableau du simplexe
max 𝑋1 + 2𝑋2 = 𝑧
−3𝑋1 + 2𝑋2 + 𝒕𝟏 = 2
−𝑋1 + 2𝑋2 + 𝒕𝟐 = 4 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
𝑋1 + 𝑋2 + 𝒕𝟑 = 5
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max 1 2 0 0 0 0
Tableau du simplexe
Déterminer la colonne Pivot Colonne Pivot
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max 1 2 0 0 0 0
Chercher le Max { coefficients de Z}
Variable entrante : X2
Tableau du simplexe
Déterminer la ligne Pivot
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 -3 2 1 0 0 2
0 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max 1 2 0 0 0 0
𝑪
Calculer au niveau de la colonne K
𝑪𝒑
Tableau du simplexe
Pivot 1 2 0 0 0 0
Ligne X1 X2 t1 t2 t3 C K
Pivot
0 t1 -3 2 1 0 0 2 1
0 0 t2 -1 2 0 1 0 4 2
0 t3 1 1 0 0 0 5 5
Max 1 2 0 0 0 0 0
𝑪
𝑪𝒑
Trouver le Min { K , K>0} Variable sortante : t1
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3 2 1 0 0 2
1 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max 1 2 0 0 0 0
𝑳𝒑
Calculer au niveau ligne pivot (P=2)
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 -1 2 0 1 0 4
0 t3 1 1 0 0 0 5
Max 1 2 0 0 0 0
𝑳𝒑
Calculer au niveau ligne pivot 𝑪𝒑 = 0 (sauf le Pivot)
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 -1 0 2 0 1 0 4 -2*LP+Li
0 t3 1 0 1 0 0 0 5 -LP+Li
Max 1 0 2 0 0 0 0 -2*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 2 -1 1 0 2 -2*LP+Li
0 t3 1 0 1 0 0 0 5 -LP+Li
Max 1 0 2 0 0 0 0 -2*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 2 -1 1 0 2 -2*LP+Li
0 t3 5/2 0 1 -1/2 0 1 4 -LP+Li
Max 1 0 2 0 0 0 0 -2*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 -1 1 0 2 -2*LP+Li
0 t3 5/2 0 -1/2 0 1 4 -LP+Li
Max 4 0 -1 0 0 -2 -2*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
Est-ce la solution est optimale ?
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 -1 1 0 2
0 t3 5/2 0 -1/2 0 1 4
Max 4 0 -1 0 0 -2
∀ coefficients {Z} ≤ 𝟎 La solution n’est pas optimale

Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 -1 1 0 2
0 t3 5/2 0 -1/2 0 1 4
Max 4 0 -1 0 0 -2
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
1 0 t2 2 0 -1 1 0 2
0 t3 5/2 0 -1/2 0 1 4
Max 4 0 -1 0 0 -2
𝑪
𝑪𝒑
Tableau du simplexe
Pivot 1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
Ligne 2 X2 -3/2 1 1/2 0 0 1 -2/3
Pivot
1 0 t2 2 0 -1 1 0 2 1
0 t3 5/2 0 -1/2 0 1 4 8/5
Max 4 0 -1 0 0 -2
𝑪
𝑪𝒑
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1 -2/3
2 1 X1 2 0 -1 1 0 2 1
0 t3 5/2 0 -1/2 0 1 4 8/5
Max 4 0 -1 0 0 -2
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 -3/2 1 1/2 0 0 1
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 5/2 0 -1/2 0 1 4
Max 4 0 -1 0 0 -2
𝑳𝒑
Calculer au niveau ligne pivot (P=2) 𝑪𝒑 = 0 (sauf le Pivot)
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 -3/2 1 1/2 0 0 1 3/2*LP+Li
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 5/2 0 -1/2 0 1 4 -5/2*LP+Li
Max 0 4 0 -1 0 0 -2 -4*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 -3/2 1 -1/4 3/4 0 5/2 3/2*LP+Li
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 5/2 0 -1/2 0 1 4 -5/2*LP+Li
Max 0 4 0 -1 0 0 -2 -4*LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 -3/2 1 -1/4 3/4 0 5/2 3/2*LP+Li
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 5/2 0 3/4 -5/4 1 3/2 -5/2*LP+Li
Max 0 4 0 -1 0 0 -2 -4*LP+Li
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 -3/2 1 -1/4 3/4 0 5/2 3/2*LP+Li
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 5/2 0 3/4 -5/4 1 3/2 -5/2*LP+Li
Max 0 4 0 1 -2 0 -6 -4*LP+Li
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 0 3/4 -5/4 1 3/2
Max 0 0 1 -2 0 -6

Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 0 3/4 -5/4 1 3/2
Max 0 0 1 -2 0 -6
Variable entrante : t1
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2
2 1 X1 1 0 -1/2 1/2 0 1
0 t3 0 0 3/4 -5/4 1 3/2
Max 0 0 1 -2 0 -6
𝑪
𝑪𝒑
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2 -10
Ligne 2 1 X1 1 0 -1/2 1/2 0 1 -2
Pivot 0 t3 0 0 3/4 -5/4 1 3/2 2
Max 0 0 1 -2 0 -6
𝑪
Calculer au niveau de la colonne K Pivot
𝑪𝒑
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2
3 1 X1 1 0 -1/2 1/2 0 1
0 t1 0 0 3/4 -5/4 1 3/2
Max 0 0 1 -2 0 -6
𝑳𝒑
Calculer au niveau de la ligne pivot (P=3/4)
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 -1/4 3/4 0 5/2
3 1 X1 1 0 -1/2 1/2 0 1
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 1 -2 0 -6
𝑳𝒑
Calculer au niveau de la ligne pivot (P=3/4) 𝑪𝒑 = 0 (sauf le Pivot)
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 -1/4 3/4 0 5/2 1/4*LP+Li
3 1 X1 1 0 0 -1/2 1/2 0 1 1/2*LP+Li
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 0 -2 0 -6 -LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 -1/4 1/3 1/3 3 1/4*LP+Li
3 1 X1 1 0 0 -1/2 1/2 0 1 1/2*LP+Li
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 0 -2 0 -6 -LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 -1/4 1/3 1/3 3 1/4*LP+Li
3 1 X1 1 0 0 -1/2 -1/3 -2/3 2 1/2*LP+Li
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 0 -2 0 -6 -LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 -1/4 1/3 1/3 3 1/4*LP+Li
3 1 X1 1 0 0 -1/2 -1/3 -2/3 2 1/2*LP+Li
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 0 -1/3 -4/3 -8 -LP+Li
𝑳𝒑
𝑷
Tableau du simplexe
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 1/3 1/3 3
3 1 X1 1 0 0 -1/3 -2/3 2
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 -1/3 -4/3 -8
∀ coefficients {Z} ≤ 𝟎 La solution est optimale

Tableau du simplexe
Solution optimale
1 2 0 0 0 0
X1 X2 t1 t2 t3 C K
2 X2 0 1 0 1/3 1/3 3
3 1 X1 1 0 0 -1/3 -2/3 2
0 t1 0 0 1 -5/3 4/3 2
Max 0 0 0 -1/3 -4/3 -8
𝑿𝟏 = 2 𝑿𝟐 = 3 𝒁= 8
Exercice
Exercice
L’entreprise « YAZAKI » envisage de faire parvenir à

Renault Maroc tous les jours la totalité de sa
production des lots de pièces et de câbles, qui seront
conditionnés en vue du transport, dès leur arrivée dans
l’entrepôt de Renault, puis stockés une semaine avant
leur chargement vers l’exportation (après contrôle par
échantillonnage) .
Exercice
Caractéristique de l’entreposage :
La partie de l’entrepôt affectée à ce stockage a une capacité maximale de 100 m3

Les lots des pièces et des câbles occupent respectivement un volume de 1 m3 et 0,5 m3
Caractéristique du conditionnement :
Le conditionnement nécessite 12 minutes par lot de pièces, et 9 minutes par lot de

câbles
Le magasinier travaille du lundi au vendredi sur un contrat de 25 heures / semaine
Exercice
Caractéristique de la production:
La production de la société « Yazaki » s’effectue sur 5 jours / semaine.
Pour des raisons et d’organisation, la production journalière maximale est 32 lots
de câbles.
Caractéristique de la marge brute à maximiser :

Renault Maroc facture le conditionnement / entreposage au prix de 2 € par lot de
pièces, et 1,20 € par lots de câbles.
La marge brute est de 75% du prix de vente sur cette activité
Exercice
Objectifs :
Modéliser le programme linéaire correspondant à

la maximisation de la marge brute hebdomadaire
de Renault Maroc
Résoudre le problème avec la méthode du simplexe
Interpréter et vérifier les résultats

Exercice
Modélisation :
𝑋1 : Nombre de lots de pièces

𝑋2 : Nombre de lots de câbles
Contraintes de l’entreposage : 𝑋1 + 1/2𝑋2 ≤ 100
1 3
Contraintes du conditionnement : ( )𝑋1 + ( )𝑋2 ≤ 25
5 20
Contraintes de production : 𝑋2 ≤ 160
max 3/2𝑋1 + 9/10𝑋2 = 𝑧
A vos claviers (stylos ;-)
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

s.c 𝑋1 + 1/2𝑋2 ≤ 100
1 3
(𝑃) ( )𝑋1 + ( )𝑋2 ≤ 25
5 20
𝑋2 ≤ 160
𝑋1 , 𝑋2 ≥ 0
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25 𝑋1 , 𝑋2 , 𝒕𝟏 𝒕𝟐 , 𝒕𝟑 ≥ 𝟎
5 1 20 2
𝑋2 + 𝑡3 = 160
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25
5 1 20 2
𝑋2 + 𝑡3 = 160
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1
0 0 t2
0 t3
Max
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25
5 1 20 2
𝑋2 + 𝑡3 = 160
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2
0 t3
Max
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25
5 1 20 2
𝑋2 + 𝑡3 = 160
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2 1/5 3/20 0 1 0 25
0 t3
Max
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25
5 1 20 2
𝑋2 + 𝑡3 = 160
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2 1/5 3/20 0 1 0 25
0 t3 0 1 0 0 1 160
Max
Exercice
max 3/2𝑋1 + 9/10𝑋2 = 𝑧

𝑋1 + 1/2𝑋2 + 𝑡1 = 100
1 3
𝑋 + 𝑋 + 𝑡2 = 25
5 1 20 2
𝑋2 + 𝑡3 = 160
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2 1/5 3/20 0 1 0 25
0 t3 0 1 0 0 1 160
Max 3/2 9/10 0 0 0 0
Exercice
Colonne Pivot
Déterminer la colonne Pivot
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2 1/5 3/20 0 1 0 25
0 t3 0 1 0 0 1 160
Max 3/2 9/10 0 0 0 0
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
0 t1 1 1/2 1 0 0 100
0 0 t2 1/5 3/20 0 1 0 25
0 t3 0 1 0 0 1 160
Max 3/2 9/10 0 0 0 0
𝑪
𝑪𝒑
Exercice

Pivot 3/2 9 0 0 0 0
Ligne X1 X2 t1 t2 t3 C K
Pivot 0 t1 1 1/2 1 0 0 100 100
0 0 t2 1/5 3/20 0 1 0 25 125
0 t3 0 1 0 0 1 160 -
Max 3/2 9/10 0 0 0 0
𝑪
𝑪𝒑
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100 100
1 0 t2 1/5 3/20 0 1 0 25 125
0 t3 0 1 0 0 1 160 -
Max 3/2 9/10 0 0 0 0
𝑳𝒑
𝑷
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100
1 0 t2 1/5 3/20 0 1 0 25
0 t3 0 1 0 0 1 160 -
Max 3/2 9/10 0 0 0 0
𝑳𝒑
𝑷
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100
1 0 t2 0 1/5 3/20 0 1 0 25 -1/5*LP+Li
0 t3 0 0 1 0 0 1 160 - 0*LP+Li
Max 0 3/2 9/10 0 0 0 0 -3/2*LP+Li
𝑳𝒑
𝑷
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100
1 0 t2 0 1/5 1/20 -1/5 1 0 5 -1/5*LP+Li
0 t3 0 0 1 0 0 1 160 - 0*LP+Li
Max 0 3/2 9/10 0 0 0 0 -3/2*LP+Li
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100
1 0 t2 0 1/5 1/20 -1/5 1 0 5 -1/5*LP+Li
0 t3 0 0 1 0 0 1 160 - 0*LP+Li
Max 0 3/2 9/10 0 0 0 0 -3/2*LP+Li
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 1/2 1 0 0 100
1 0 t2 0 1/5 1/20 -1/5 1 0 5 -1/5*LP+Li
0 t3 0 0 1 0 0 1 160 - 0*LP+Li
Max 0 3/2 3/20 -3/2 0 0 -150 -3/2*LP+Li

Et on continue de la
même manière
Exercice

3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 0 3 -10 0 50
2 9 X2 0 1 -4 20 0 100
0 t3 0 0 4 -20 1 60 -
Max 0 0 -9/10 -3 0 -165
∀ coefficients {Z} ≤ 𝟎 La solution est optimale

Interprétation des résultats
3/2 9 0 0 0 0
X1 X2 t1 t2 t3 C K
3/2 X1 1 0 3 -10 0 50
2 9 X2 0 1 -4 20 0 100
0 t3 0 0 4 -20 1 60 -
Max 0 0 -9/10 -3 0 -165
𝑿𝟏 = 50 𝑿𝟐 = 100 𝒁= 165
𝒕𝟑 = 60
Exercice
Interprétation des résultats ?
𝑿𝟏 = 50 𝑿𝟐 = 100 𝒕𝟑 = 60 𝒁= 165
𝟓𝟎 ∶ Nombre de lots de pièces à produire

𝟏𝟎𝟎 ∶ Nombre de lots de câbles à produire
𝟏𝟔𝟓 € ∶ la marge brute hebdomadaire . Elle est atteinte par

une production de 50 lots de pièces et de 100 lots de câbles
Les deux premières contraintes (entreposage et conditionnement)sont saturées étant donné que t1 et t2 sont nuls
ON peut encore stocker 60 lots de lots de câbles par semaine (t3 = 60)
Algorithme du dual
simplexe
Algorithme du dual simplexe
Principe
1ière approche :
Remplacer la résolution du problème posé par celle de son dual.
Avantageux lorsque le problème posé comporte plus de contraintes

que d’inconnues.
2ième approche : Démarche duale
Partir d’une solution irréalisable satisfaisant aux critères d’optimalité,

calculer une suite de solutions primales irréalisables vérifiant
constamment ces critères et aboutissant éventuellement à une solution
primale-réalisable laquelle sera optimale.
L’algorithme dual du simplexe s’applique au primal et non au dual.

Algorithme
Algorithme
Algorithme

INSEA - Modèles Discrets - Algorithme Du Simplexe

Transféré par

Droits d'auteur :

Formats disponibles

INSEA - Modèles Discrets - Algorithme Du Simplexe

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

INSEA - Modèles Discrets - Algorithme Du Simplexe

Transféré par

Droits d'auteur :

Formats disponibles

Modèles discrets

L’objectif étant de trouver 𝑿𝟏 et 𝑿𝟐 pour que Z soit maximale

Ajout des variables d’écart

Déterminer une solution de

Coefficients de la fonction objectif du P de départ

Variables de base et hors base

Ajout des variables d’écart

Solution de base réalisable ?

Déterminer la colonne Pivot Colonne Pivot

Chercher le Max { coefficients de Z}

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Est-ce la solution est optimale ?

∀ coefficients {Z} ≤ 𝟎 La solution n’est pas optimale

Déterminer la colonne Pivot Colonne Pivot

Chercher le Max { coefficients de Z}

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Est-ce la solution est optimale ?

∀ coefficients {Z} ≤ 𝟎 La solution n’est pas optimale

Déterminer la colonne Pivot Colonne Pivot

Chercher le Max { coefficients de Z}

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

Déterminer la ligne Pivot

3 1 X1 1 0 0 -1/2 1/2 0 1 1/2*LP+Li

Déterminer la ligne Pivot

3 1 X1 1 0 0 -1/2 1/2 0 1 1/2*LP+Li

Déterminer la ligne Pivot

3 1 X1 1 0 0 -1/2 -1/3 -2/3 2 1/2*LP+Li

Déterminer la ligne Pivot

3 1 X1 1 0 0 -1/2 -1/3 -2/3 2 1/2*LP+Li

Est-ce la solution est optimale ?

∀ coefficients {Z} ≤ 𝟎 La solution est optimale

L’entreprise « YAZAKI » envisage de faire parvenir à

La partie de l’entrepôt affectée à ce stockage a une capacité maximale de 100 m3

Le conditionnement nécessite 12 minutes par lot de pièces, et 9 minutes par lot de

Caractéristique de la marge brute à maximiser :

Modéliser le programme linéaire correspondant à

Résoudre le problème avec la méthode du simplexe

Interpréter et vérifier les résultats

𝑋1 : Nombre de lots de pièces

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

Ajout des variables d’écart

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

max 3/2𝑋1 + 9/10𝑋2 = 𝑧

Chercher le Max { coefficients de Z}

Déterminer la ligne Pivot