S6-RO - Etudiant
Transféré par
lahcen aouarS6-RO - Etudiant
Transféré par
lahcen aouarRecherche opérationnelle
EL BOUANANI
Département de Statistiques et Mathématiques
Appliquées à l'Économie et à la Gestion
FSJES Ain Sebaa
2018/2019
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 1 / 220
Plan du cours
1 Programmes linéaires et modélisation
2 La méthode graphique
3 La méthode du simplexe
4 Dualité en programmation linéaire
5 Analyse de sensibilité
6 Problème d'aectation
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 2 / 220
Programmes linéaires et modélisation
Chapitre 1 :
Programmes linéaires
et modélisation
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 3 / 220
Programmes linéaires et modélisation Introduction
1. Introduction
Dé nition de la recherche opérationnelle
La recherche opérationnelle est un ensemble de méthodes scienti ques pour
résoudre des problèmes d'optimisation liés aux organisations du monde réel.
La RO est aussi appelée aide à la décision : elle permet d'assister la prise
de décision en fournissant une réponse scienti que à des problèmes
organisationnels complexes (problèmes de gestion par exemple).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 4 / 220
Programmes linéaires et modélisation Introduction
Exemples de problèmes
Comment aller le plus vite de Casablanca à Rabat en voiture ?
Comment investir ses 10000 Dh d'économie de sorte à maximiser le
pro t obtenu après deux ans ?
Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?
Trouver un plus court chemin entre deux villes.
Emplois du temps : Plani er l'horaire des cours ou des examens, en
tenant compte des diérentes ressources (étudiants, professeurs,
locaux,...)
Dé nir le nombre du personnel dans une gare de trains ou une banque
suivant la fréquence de la clientèle.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 5 / 220
Programmes linéaires et modélisation Introduction
En conclusion, la recherche opérationnelle, face à un problème pratique de
décision, cherche à :
faire le mieux : coût minimal, meilleur pro t, plus courte distance, le
plus rapide...
avec les ressources disponibles :temps machine, postes de travail,
mémoire, ressource homme, matière première, moyens de transport. . .
La RO repose sur la construction des modèles (modélisation), et ce en
fonction des problèmes posés.
Il existe plusieurs techniques de modélisation comme la programmation
linéaire, la théorie des graphes, etc.
Elle est un carrefour entre les mathématiques (modélisation),
l'informatique (algorithmique) et l'économie (gestion, stratégie).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 6 / 220
Programmes linéaires et modélisation Introduction
Etapes d'un processus de RO
Détecter et comprendre le problème
Objectifs, contraintes
Données disponibles (variables de décision, paramètres, quantités de
matière première par ex...)
Traduire le problème réel sous forme de modèle mathématique
(programme linéaire par ex.)
Résolution du modèle
Choix d'un algorithme (Simplexe par ex.)
Utilisation des logiciels spécialisés (Excel, Lindo,...)
Validation du modèle et des résultats :
le modèle développé est-il conforme à la réalité ?
les résultats sont-ils valides et satisfaisantes ?
Prise de décision
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 7 / 220
Programmes linéaires et modélisation Introduction
Etapes d'un processus de RO
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 8 / 220
Programmes linéaires et modélisation Introduction
La programmation linéaire
Dé nition
Les problèmes de programmation linéaire (PL) sont des problèmes
d'optimisation où on maximise (ou on minimise) une fonction linéaire sous
des contraintes linéaires.
La programmation linéaire est un des domaines les plus utilisés de la RO.
Elle permet de résoudre des problèmes de gestion et particulièrement où le
gestionnaire doit déterminer, face à diérentes possibilités, l'utilisation
optimale des ressources de l'entreprise (main d'÷uvre, matières premières,
capitaux, espace,...) et qui sont disponibles en quantité limitée, pour
atteindre un objectif spéci que comme la maximisation des béné ces ou la
minimisation des coûts.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 9 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
2. Exemples de programmes linéaires
Exemple 1 :
Une entreprise de fabrication de châssis envisage la production de deux
nouveaux modèles au moyen des capacités résiduelles de ses trois ateliers.
Il s'agit respectivement d'un châssis en aluminium et d'un châssis en bois.
Le premier produit nécessite le passage dans le premier atelier pour
fabriquer le cadre en aluminium et dans le troisième atelier où le verre est
monté sur le châssis. Tandis que le second produit nécessite le passage
dans le deuxième atelier pour fabriquer le cadre en bois et dans le troisième
atelier où le verre est monté sur le châssis.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 10 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
Les marges unitaires, les temps de fabrication de chacun des produits dans
chacun des ateliers ainsi que les capacités hebdomadaires résiduelles de ces
ateliers sont donnés au tableau suivant :
Produit 1 Produit 2 Capacité
(châssis aluminium) (châssis bois) disponible
(heures/produit) (heures/produit) (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3 UM 5 UM
La question qui se pose est la suivante : combien faut-il produire de châssis
de chaque type par semaine pour maximiser le pro t net ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 11 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
1. Identi cation des variables de décision
La première étape consiste à choisir les variables du problème.
Les quantités que le modèle doit déterminer sont les productions de châssis
par semaine. Posons donc :
x1 : nombre de châssis du produit 1 (châssis en aluminium)
x2 : nombre de châssis du produit 2 (châssis en bois).
2. Expression de l'objectif
La deuxième étape consiste à formuler l'objectif.
L'entreprise désire maximiser son pro t net. La marge étant de 3 pour le
premier type de châssis et de 5 pour le second, l'objectif (ou fonction
économique) s'exprime comme suit :
max z = 3x1 + 5x2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 12 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
3. Expression des contraintes
La 3ème étape est la formulation des contraintes du problème.
Le temps pour assembler 1 châssis de type 1 dans l'atelier 1 est de 1 heure
où il reste 4 heures disponibles. D'où la contrainte de capacité de l'atelier1 :
x1 ≤ 4
De même, pour les contraintes de capacités des deux autres ateliers :
2x2 ≤ 12 et 3x1 + 2x2 ≤ 18
D'autre part, les quantités produites ne peuvent être négatives.
Mathématiquement : x 1 ≥ 0, x 2 ≥ 0
Finalement, le problème peut être formulé en programme linéaire :
⎧
⎪
⎪ max z = 3x1 + 5x2
⎪
⎪
⎨ x1 ≤ 4
(P1 ) 2x2 ≤ 12
⎪
⎪
⎪
⎪ 3x1 + 2x2 ≤ 18
⎩ x ≥0; x ≥0
1 2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 13 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
Exemple 2 :
Une ra nerie achète deux types de pétroles bruts dont elle retire de
l'essence, du gazole et du oul dans les pourcentages suivants :
Produits nis Brut 1 Brut 2
Essence 30 25
Gazole 40 25
oul 30 50
La ra nerie doit satisfaire à la demande de :
125 104 tonnes d'essence, 135 104 tonnes de gazole et 180 104 tonnes de
oul
L'achat d'une tonne de brut 1 coute 700 UM et une tonne de brut 2 coute
500 UM.
Quelles quantités de ces pétroles bruts devra t-on acheter pour répondre à
la demande au moindre coût ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 14 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
Compréhension du problème :
Le problème est de minimiser le coût d'achat de cette ra nerie. Ce
coût d'achat évolue en fonction des quantités de brut 1 et 2 à acheter.
Identi cations des variables de décision :
x1 : quantité de brut 1 à acheter
x2 : quantité de brut 2 à acheter
Fixation de l' objectif :
minimisation du coût
min z = 700x1 + 500x2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 15 / 220
Programmes linéaires et modélisation Exemples de programmes linéaires
Fixation de l' objectif :
minimisation du coût min z = 700x1 + 500x2
Mise en équations des contraintes économiques :
les variables x1 et x2 véri ent 3 contraintes :
Contrainte d'essence : 0 3 , x1 + 0, 25x2 ≥ 125 104
Contrainte de gazole : 0 4 , x1 + 0, 25x2 ≥ 135 104
Contrainte de oul : 0 3 , x1 + 0, 5x2 ≥ 180 104
Restriction des signes : contrainte de positivité x1 ; x2 ≥ 0
Modélisation mathématique
⎧
⎪
⎪ min z = 700x1 + 500x2
⎪
⎪
⎪
⎨ 0, 3x1 + 0, 25x2 ≥ 125 104
(P2 ) 0, 4x1 + 0, 25x2 ≥ 135 104
⎪
⎪
⎪
⎪ 0, 3x1 + 0, 5x2 ≥ 180 104
⎪
⎩ x ≥0; x ≥0
1 2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 16 / 220
Programmes linéaires et modélisation Formulation générale
Formulation générale d'un PL
Fonction objectif (économique) :
max (ou min) z = c1 x1 + c2 x2 + ... + cn xn
Contraintes :
a11 x1 + a12 x2 + ... + a1n xn ≤, =, ≥ b1
a21 x1 + a22 x2 + ... + a2n xn ≤, =, ≥ b2
.
.
.
am1 x1 + am2 x2 + ... + amn xn ≤, =, ≥ bm
Contraintes de positivité (non négativité) :
xj ≥ 0 ∀j = 1, ..., n
Avec,
xj : variables de décision (inconnues)
aij , bi , cj : paramètres du programme linéaire (connues).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 17 / 220
Programmes linéaires et modélisation Formulation générale
Formulation matricielle
Posons :
x = (x1 , x2 , ..., xn ) vecteur de Rn
où x1 , x2 , ..., xn sont les variables de décision.
c = (c1 , c2 , ..., cn ) ∈ Rn et b = (b1 , b2 , ..., bm ) ∈ Rm
⎛ ⎞
a11 a12 · · · a1n
⎜ a21 a22 · · · a2n ⎟
⎜ ⎟
A = ⎜ .. . .. . ⎟ (matrice de type (m × n))
⎝ . .
. . .
. ⎠
am 1 am 2 · · · amn
c T x =< c, x >= c1 x1 + ... + cn xn (produit scalaire dans Rn ) .
Alors, le programme linéaire peut s'écrire sous la forme :
⎧
⎨ min / max z = c T x
(PL) Ax ≤, =, ≥ b
⎩
x ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 18 / 220
Programmes linéaires et modélisation Formulation générale
Terminologie
Solution réalisable (solution admissible) :
x = (x1 , x2 , ..., xn ) est une solution réalisable si x satisfait toutes les
contraintes c-à-d Ax {≤, =, ≥} b et x ≥ 0.
Ensemble réalisable (région admissible) :
Ensemble de toutes les solutions réalisables.
Solution optimale :
Solution réalisable où la fonction objectif atteint la meilleure valeur
(maximum ou minimum).
Remarques :
1 Plusieurs solutions optimales sont possibles.
2 Géométriquement, la région admissible correspond à un polyèdre de
Rn (voir chapitre 2).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 19 / 220
Programmes linéaires et modélisation Formulation générale
Exemple 3 :
L'Ile des cocotiers produit du pétrole, des bananes et du soja. Les
marchands internationaux sont plus intéressés par le pétrole que par les
bananes et le soja, ce qui fait qu'il y a un dé cit à l'exportation des
produits agricoles sur cette île.
Pour soutenir l'agriculture, le gouvernement oblige les acheteurs de pétrole
à acheter aussi des bananes et du soja. Les achats sur cette île se feront
par lots qui peuvent être de 2 types :
des lots à dominante BANANE des lots à dominante SOJA
chaque lot contient chaque lot contient
pétrole 1 baril pétrole 1 baril
BANANES 0.4 tonnes BANANES 0.2 tonnes
SOJA 0.3 tonnes SOJA 0.6 tonnes
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 20 / 220
Programmes linéaires et modélisation Formulation générale
Les conditions de vente sont telles que tous les produits achetés dans cette
île doivent être immédiatement et en totalité emportés.
Un acheteur se présente avec un pétrolier et un cargo qui contient 2 cales
aménagées : la cale avant ne peut contenir que du soja, et la cale arrière ne
peut contenir que des bananes.
Les capacités sont les suivantes :
pétrole 1000 barils
cale arrière : BANANES 450 tonnes
cale avant : SOJA 450 tonnes
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 21 / 220
Programmes linéaires et modélisation Formulation générale
Le lot à dominante BANANE coûte 5.2 $. Le lot à dominante SOJA coûte
6.2 $, Tandis que les prix auxquels ont peut revendre ces produits sur le
marché mondial sont les suivants :
1 baril de pétrole 6$
1 tonne de BANANES 2$
1 tonne de SOJA 8$
Questions :
1 Quel problème mathématique doit résoudre l'acheteur pour constituer
sa cargaison ?
2 Quelles quantités de bananes, soja et pétrole va-t-il se procurer ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 22 / 220
Programmes linéaires et modélisation Formulation générale
Le calcul du chire d'aaires avec un lot BANANES et de SOJA est :
Produit quantités prix unitaire chire d'aaire
pétrole 1 baril 6$ 6$
bananes 0.4 tonnes 2$ 0.8 $
soja 0.3 tonnes 8$ 2.4 $
Total 9.2
Produit quantités prix unitaire chire d'aaire
pétrole 1 baril 6$ 6$
BANANES 0.2 tonnes 2$ 0.4 $
soja 0.6 tonnes 8$ 4.8 $
Total 11.2
En déduit le Béné ce par lot :
BANANES 9.2-5.2 = 4 $
SOJA 11.2-6.2 = 5 $
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 23 / 220
Programmes linéaires et modélisation Formulation générale
Soit x1 le nombre de lots BANANES, et soit x2 le nombre de lots SOJA.
Le problème de l'importateur est donc de choisir sa commande , c'est à
dire deux nombres x1 et x2 , de manière à rendre son béné ce le plus grand
possible.
Mathématiquement, le béné ce s'exprime en fonction de x1 et x2 par : on
désignera le béné ce par Z , on a :
Z = 4x1 + 5x2
l'importateur ne peut se procurer que des nombres positifs de lots :
x1 ≥ 0, x2 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 24 / 220
Programmes linéaires et modélisation Formulation générale
Chaque lot contient 1 baril de pétrole, si on achète x1 lots BANANE
et x2 lots SOJA, on obtiendra donc x1 + x2 barils de pétrole. Comme
la capacité du pétrolier n'est que de 1000 barils, on voit apparaître une
contrainte :
x1 + x2 ≤ 1000
Chaque lot BANANE contient 0.4 tonnes de bananes. Si on achète x1
lots BANANE, on lui fournira 0.4x1 tonnes de bananes. De même,
pour x2 lots SOJA, on a 0.2x2 tonnes de bananes. Au total
0.4x1 + 0.2x2 tonnes de bananes. La capacité de la cale qui permet de
recevoir des bananes n'est que de 450 tonnes de bananes, on voit
apparaître la contrainte :
0.4x1 + 0.2x2 ≤ 450
En procédant de manière analogue pour le soja que pour la banane, on
voit apparaître la contrainte :
0.3x1 + 0.6x2 ≤ 450
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 25 / 220
Programmes linéaires et modélisation Formulation générale
Résumons le programme linéaire de l'importateur : les commandes (x1 , x2 )
qu'il peut envisager sont celles du domaine
⎧
⎪
⎪ x 1 + x2 ≤ 1000
⎪
⎨ 0.4x1 + 0.2x2
⎪ ≤ 450
0.3x1 + 0.6x2 ≤ 450
⎪
⎪
⎪
⎪
⎩
x1 ≥ 0
x2 ≥ 0
L'objectif est de maximiser :
Z = 4x1 + 5x2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 26 / 220
Programmes linéaires et modélisation Formulation générale
Exemple 4 :
Un fermier élève des poulets, des canards et des dindons. Il veut avoir 500
volatiles, mais pas plus de 300 canards à la fois. Supposons que l'élevage
d'un poulet revienne à 15 francs, celui d'un canard à 10 F celui d'un dindon
à 40 F.
Admettons que le fermier puisse vendre ses poulets à 30 F pièce, les
canards à 20 F pièce et les dindons à D francs. Il voudrait savoir quelles
volailles il faut élever pour réaliser le pro t maximum.
1 Quelles contraintes pour ce programme linéaire.
2 Donnez en fonction de D l'expression du pro t.
3 Dans chacune des hypothèses suivantes, donnez la politique d'élevage
optimale du fermier : a) D = 60 F b) D = 50 F c) D = 55 F
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 27 / 220
Programmes linéaires et modélisation Formulation générale
Soit x1 le nombre de poulet, x2 le nombre de canard, et x3 le nombre de
dindon.
Le fermier veut avoir 500 volatiles.
x1 + x2 + x3 = 500
Mais pas plus de 300 canards à la fois.
x2 ≤ 300
La fonction objectif : Supposons que l'élevage d'un poulet revienne à
15 francs, celui d'un canard à 10 F celui d'un dindon à 40 F.
Admettons que le fermier puisse vendre ses poulets à 30 F pièce, les
canards à 20 F pièce et les dindons à D francs. Donc :
Pour un poulet le fermier gagne 15 francs.
Pour un canard le fermier gagne 10 francs.
Pour un dindon le fermier gagne D − 40 francs.
Soit Z le béné ce totale :
Z = 15x1 + 10x2 + (D − 40)x3
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 28 / 220
Programmes linéaires et modélisation Formulation générale
la positivité :
x 1 ≥ 0; x 2 ≥ 0 x3 ≥ 0
x1 + x2 + x3 = 500
donc x3 = 500 − x1 − x2 , ce qui permet de passer d'un problème à trois
variables à un problème à deux variable.
en eet
x1 +x2 +x3 = 500 x1 + x2 ≤ 500
⇒
x3 ≥0
x1 + x2 + x3 = 500
15x1 + 10x2 + (D − 40)x3 =Z ⇔
x1 + x2 + x3 = 500
(55 − D)x1 + (50 − D)x2 + (D − 40)500 =Z
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 29 / 220
Programmes linéaires et modélisation Formulation générale
Résumons le programme linéaire du fermier : les couples (x1 , x2 ) qu'il faut
envisager sont celles du domaine
⎧
⎪
⎪ x 1 + x2 ≤ 500
⎨
0x1 + x2 ≤ 300
⎪
⎪ x1 ≥ 0
⎩
x2 ≥ 0
L'objectif est de maximiser :
Z = (55 − D)x1 + (50 − D)x2 + (D − 40)500
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 30 / 220
Programmes linéaires et modélisation Formulation générale
Exemple 5 :
Dans l'île des Palmiers, les habitants ont formé une coopérative de
production où on ne rigole pas : tout le monde travaille. Une partie des
adhérents employés de la coopérative sont aectés à la cueillette des
orchidées sauvages, seule ressource exportable de l'île, tandis que les autres
sont occupés à pécher du poisson, principale source de nourriture de l'île.
Les habitants de l'île vivent dans deux villages, l'un situé au Nord, l'autre
au Sud, et pour nourrir les habitants de l'île, chaque semaine, les quantités
suivantes de poisson sont nécessaires :
Thon Morue Sardine
Quantités de poisson 900Kg 800Kg 700Kg
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 31 / 220
Programmes linéaires et modélisation Formulation générale
Les quantités de poisson rapportées par un pêcheur en une semaine n'ont
rien d'aléatoire et sont données par le tableau suivant :
Thon Morue Sardine
Pécheur du Nord 6Kg 20Kg 10Kg
Pécheur du Sud 30Kg 8Kg 10Kg
Tout employé de la coopérative qui ne va pas à la pêche est aecté à la
récolte des orchidées sauvages. Évidemment les orchidées ne sont pas les
mêmes au Nord de l'île et au Sud : un travailleur du nord en une semaine
rapporte une quantité d'orchidées qui vaut 50$, ce chire s'élève à 80$ au
sud.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 32 / 220
Programmes linéaires et modélisation Formulation générale
Évidemment, le problème de la coopérative est de nourrir la population
avec le moins d'employés pour pouvoir récolter un maximum d'orchidées
pour générer des revenus à l'exportation.
Nous devrons répondre aux questions suivantes :
Questions :
Quel problème mathématique doit résoudre la coopérative pour
employer au mieux la main d'oeuvre ?
quelles quantités de thon, morue et sardines va-t-on pêcher ?
Supposons que l'on ait le choix entre les deux propositions suivantes qui
toutes deux permettent de nourrir la population de l'île :
P1 : 70 travailleurs du Nord et 20 travailleurs du Sud
P2 : 36 travailleurs du Nord et 46 travailleurs du Sud
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 33 / 220
Programmes linéaires et modélisation Formulation générale
Selon la proposition1, 90 travailleurs sont occupés à la pêche, tandis que
selon les termes de la proposition2 , seulement 82 travailleurs sont distraits
de la production d'orchidées. On peut donc penser que la seconde
proposition est la meilleure, car elle permet de consacrer à la production
d'orchidées le plus grand nombre de personnes.
Ce raisonnement est FAUX, car les travailleurs n'ont pas la même
productivité : en eet, la valeur de la récolte d'orchidée d'un travailleur du
Nord est de 50$ tandis que celle d'un travailleur du Sud est de 80$.
P1 le manque à gagner est de 50 ∗ 70 + 80 ∗ 20 = 5100$.
P2 le manque à gagner est de 50 ∗ 46 + 80 ∗ 36 = 5480$
Le raisonnement économique ⇒ la proposition 1.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 34 / 220
Programmes linéaires et modélisation Formulation générale
Dans la théorie économique, on ne parle pas de manque à gagner, mais de
coût d'opportunité.
Soit alors x1 le nombre de pêcheurs de la zone Nord, et x2 le nombre de
pêcheurs de la zone Sud.
le coût d'opportunité de la coopérative ⇒ C = 50x1 + 80x2
Thon ⇒ 6x1 + 30x2 ≥ 900
Morue ⇒ 20x1 + 8x2 ≥ 800
Sardine ⇒ 10x1 + 10x2 ≥ 700
x 1 ≥ 0, x 2 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 35 / 220
Programmes linéaires et modélisation Formulation générale
Exemple 6 :
Le propriétaire d'un hôtel dans une station thermale décide de faire un
certain nombre d'aménagements a n de décrocher une étoile de plus. Pour
cela toutes les chambres doivent comporter une douche ou une salle de
bains, mais la proportion de chambres n'étant équipée que d'une douche ne
doit pas dépasser 25%. Une chambre peut être aménagée avec un lit
double (2 couchages) ou un lit double et un lit simple (3 couchages).
Cependant, vu la taille des chambres actuelles, seulement 50% de celles-ci
pourraient contenir 3 couchages. La quasi-totalité des clients seront des
curistes et optent donc en général pour une pension complète. Les heures
d'ouverture des thermes obligent le restaurant de l'hôtel à n'envisager
qu'un service unique xé à midi trente. La salle de restaurant ne pouvant
accueillir que 100 personnes, cela a bien sûr des conséquences sur le
nombre de chambres à proposer.
On suppose qu'en période de cure l'hôtel est systématiquement rempli.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 36 / 220
Programmes linéaires et modélisation Formulation générale
Écrire sans le résoudre le programme linéaire qui permettra de déterminer
le nombre de chambres de chaque type que devra aménager le propriétaire
a n de maximiser son béné ce. Les tarifs des chambres en Dirhams sont
données ci-dessous :
2 couchages 3 couchages
Douche 250 400
Salle de bains 300 450
On notera respectivement x1 , x2 , x3 , x4 , le nombre de chambres à 2
couchages avec douche, à 2 couchages avec salle de bains, à 3 couchages
avec douche, à 3 couchages avec salle de bains.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 37 / 220
Programmes linéaires et modélisation Formulation générale
1 la proportion de chambres n'étant équipée que d'une douche ne doit
pas dépasser 25% :
1 3 1 3 1
x1 + x3 ≤ (x1 + x2 + x3 + x4 ) ⇔ x1 − x2 + x3 − x4 ≤ 0
4 4 4 4 4
2 seulement 50% des chambres pourraient contenir 3 couchages :
1 1 1 1 1
x3 + x4 ≤ (x1 + x2 + x3 + x4 ) ⇔ − x1 − x2 + x3 + x4 ≤ 0
2 2 2 2 2
3 La salle de restaurant ne pouvant accueillir que 100 personnes, cela a
bien sûr des conséquences sur le nombre de chambres à proposer. On
suppose qu'en période de cure l'hôtel est systématiquement rempli :
2x1 + 2x2 + 3x3 + 3x4 = 100
4
x 1 , x2 , x3 , x4 ≥ 0
5 La fonction objectif :
Max Z = 250x1 + 300x2 + 400x3 + 450x4
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 38 / 220
Programmes linéaires et modélisation Formulation générale
⎧
⎪ 3 1 3 1
⎪
⎪ x − x + x − x ≤ 0
⎪
⎪
⎨ 4 1 4 2 4 3 4 4
1 1 1 1
− x 1 − x2 + x 3 + x4 ≤ 0
⎪
⎪ 2 2 2 2
⎪
⎪
⎪ 2x1 + 2x2 + 3x3 + 3x4 = 100
⎩ x1 , x2 , x3 , x4 ≥ 0
Max Z = 250x1 + 300x2 + 400x3 + 450x4
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 39 / 220
Programmes linéaires et modélisation Formulation générale
Exemple 7 :
Un fabriquant de ballons fait un béné ce de 8 DH, sur chaque petit ballon
et de 15 DH, sur chaque grand ballon.
Pour satisfaire à la demande des vendeurs, la production journalière de
petits ballons devrait se situer entre 30 et 80, et la production journalière
de grands ballons entre 10 et 30.
Pour maintenir une bonne qualité, le nombre total de ballons produits ne
devrait pas dépasser 80 par jour.
Combien de ballon de chaque type faudrait-il fabriquer quotidiennement
pour réaliser un béné ce maximum ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 40 / 220
Programmes linéaires et modélisation Formulation générale
Exercice :
Un atelier fabrique trois produits P1 , P2 , et P3 , en quantités x1 , x2 , et x3 .
Les marges unitaires des trois produits sont de 3, 4 et 12 dh respectivement.
♠ Le produit P1 nécessite 1 heure de travail par jour et le
marché ne peut absorber plus de 40 unités de ce produit.
♠ Le produit P2 nécessite 2 heures de travail par jour.
♠ Le produit P3 nécessite 3 heures de travail par jour et le
marché ne peut absorber plus de 80 unités de ce produit.
La capacité de travail dans l'atelier est de 300 heures par jour.
Déterminer le programme linéaire P de ce problème (La fonction objectif,
et les contraintes).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 41 / 220
Résolution des programmes linéaires : Méthode graphique
Chapitre 2 :
Résolution des programmes linéaires
Méthode graphique
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 42 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Maximisation
Un programme linéaire (PL), selon sa nature, peut être résolu des manières
diérentes :
1 Méthode graphique :
C'est une représentation géométrique plane dans le cas de deux
variables.
2 Algorithme du Simplexe :
Cet algorithme est recommandé lorsque le nombre de variables est
quelconque et il est très utilisé dans la pratique.
3 Recensement des sommets de la région admissible :
Cette méthode est possible tant que le nombre des sommets n'est pas
assez grand, c'est-à-dire, le nombre des variables et des contraintes
reste très limité. On prend le sommet qui optimise la fonction objectif.
Dans ce chapitre, nous allons présenter la méthode graphique en étudiant
les diérents cas de PL, suivant la nature de l'objectif (max ou min) et des
contraintes (inégalités, égalités ou mixtes).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 43 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Maximisation
1. Premier exemple : cas de maximisation
Reprenons l'exemple 1 du chapitre 1 :
Produit 1 Produit 2 Capacité
(châssis aluminium) (châssis bois) disponible
(heures/produit) (heures/produit) (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3 UM 5 UM
La question qui se pose est la suivante : combien faut-il produire de chassis
de chaque type par semaine pour maximiser le pro t net ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 44 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Maximisation
1.1 Modélisation du problème :
On a déjà montré que ce problème se ramène à résoudre le PL suivant :
⎧
⎪
⎪ max z = 3x1 + 5x2
⎪
⎪
⎨ x1 ≤ 4
(P1 ) 2x2 ≤ 12
⎪
⎪
⎪
⎪ 3x1 + 2x2 ≤ 18
⎩ x ≥0; x ≥0
1 2
où x1 est le nombre de châssis en aluminium et x2 est le nombre de
châssis en bois.
Représentation de la région admissible :
La première étape de la résolution consiste à représenter graphiquement la
région admissible. Dans notre cas, c'est l'ensemble des points (x1 , x2 )
satisfaisant les inégalités de (P1 ) .
Graphiquement une inégalité telle que 3x1 + 2x2 ≤ 18 correspond à un
demi-plan limité par la droite d'équation : 3x1 + 2x2 = 18.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 45 / 220
⎧
⎪
⎪ x ≤ ( )
⎪
⎪
⎨ x ≤ ( )
x + x ≤ ( )
⎪
⎪ x ≥ ( )
⎪
⎪
⎩ x ≥ ( )
z =k
Δk
x + x =k
− k
x + x =k ⇒ x = x +
Δk p=−
k= k= k=
Δ k= x + x =
( , ) ( ,− )
Δ x + x = ( , )
( , )
Δ x + x =
( , ) ( , )
k
z
z= x + x
x ∗ = (x ∗ , x ∗ )
D : x = D : x + x =
x∗
x =
x + x =
x∗ = ( , )
z∗ = x∗ + x∗ =
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Maximisation
1.2 Interprétation économique :
La solution optimale est x ∗ = (2 ; 6), donc il faut produire 2 châssis en
aluminium et 6 châssis en bois pour réaliser un pro t net maximal égal à
36 UM.
A l'optimum, la deuxième contrainte et la troisième contrainte sont
saturées mais la première contrainte ne l'est pas, car :
⎧ ∗
⎨ x1 = 2 < 4
2x ∗ = 2 × 6 = 12
⎩ 2∗
3x1 + 2x2∗ = (3 × 2) + (2 × 6) = 18
Donc, pour réaliser le pro t net maximal, il faut utiliser toute la capacité
disponible dans l'atelier 2 et l'atelier 3 (plein emploi), et il restera une
capacité dans l'atelier 1 (sous- emploi) égale à :
4 − x1∗ = 2 (heures par semaine).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 52 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
2. Deuxième exemple : cas de minimisation
Considérons maintenant un exemple où la fonction objectif doit être
minimisée :
Une compagnie possède deux mines de charbon A et B. La mine A produit
quotidiennement 1 tonne de charbon de qualité supérieure, 1 tonne de
qualité moyenne et 6 tonnes de qualité inférieure. La mine B produit par
jour 2, 4 et 3 tonnes de chacune des trois qualités. La compagnie doit
produire au moins 90 tonnes de charbon de qualité supérieure, 120 tonnes
de qualité moyenne et 180 tonnes de qualité inférieure.
Sachant que le coût de production journalier est le même dans chaque
mine, soit 1000 UM, quel est le nombre de jours de production dans la mine
A et dans la mine B qui minimisent le coût de production de la compagnie ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 53 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
2.1 Modélisation du problème
variables de décision :
x1 : nombre de jours de travail dans la mine A
x2 : nombre de jours de travail dans la mine B
Mise en équations des contraintes :
La mine A produit par jour 1 tonne de charbon de qualité supérieure,
tandis que la mine B en produit 2 tonnes. Comme la compagnie doit
satisfaire à la demande de 90 tonnes de charbon de qualité supérieure,
la première contrainte s'écrit :
x1 + 2x2 ≥ 90
De même, pour les deux autres qualités de charbon, on obtient :
x1 + 4x2 ≥ 120
6x1 + 3x2 ≥ 180
En plus, x1 et x2 , étant des nombres, véri ent la contrainte de
positivité : x1 ≥ 0 et x2 ≥ 0.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 54 / 220
z= x + x
⎧
⎪
⎪ min z = x + x
⎪
⎪
⎨ x + x ≥
x + x ≥
⎪
⎪
⎪
⎪ x + x ≥
⎩
x ≥ ; x ≥
A( ; ) D x + x =
x
B( ; ) D (D : x + x = )
C( ; ) D (D : x + x = )
D( ; ) D x
z= x + x
−
B
D D
x + x =
x + x =
x∗ = ( ; )
z∗ = x∗ + x∗ =
x∗ = ( ; ) z∗ =
⎧ ∗
⎨ x + x∗ = + ( × ) =
x∗ + x∗ = + ( × ) = >
⎩
x∗ + x∗ = ( × ) + ( × )=
− =
max z = x + x
x + x =
( , ) ( , )
( , ) ( , )
z = x + x
⎧
⎪
⎪ min z = x + x
⎪
⎪
⎨ x + x ≥
x + x ≥
⎪
⎪
⎪
⎪ x + x ≥
⎩
x ≥ ; x ≥
D
x + x =
B( ; ) C( ; )
⎧
⎪
⎪ max z = x + x
⎨
x + x ≥
⎪
⎪ x +x ≥
⎩
x ≥ ; x ≥
x x
z
z = +∞
⎧
⎪
⎪ max z = x + x
⎨
x +x ≤
⎪
⎪ x −x ≥
⎩
x ≥ ; x ≥
⎧ ⎧
⎨ x +x ≤ ⎨ x +x ≤
x −x ≥ ⇐⇒ −x + x ≤ − =⇒ x ≤−
⎩ ⎩
x ≥ ; x ≥ x ≥ ; x ≥
x ≥
Rn
−→
−→
−→
−→
−→
z =∞
∀x, y ∈ E , ∀α ∈ [ , ] αx + ( − α)y ∈ E
Rn
R
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
Exemples de polyèdres
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 70 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
Exercice 1 :
Une usine fabrique deux modèles de bureaux M1 et M2 . Les marges
unitaires, les temps de fabrication de chacun des produits dans chacun des
ateliers ainsi que les capacités disponibles de ces ateliers sont donnés au
tableau suivant :
M1 M2 Capacité disponible
Atelier 1 (sciage) 1 2 20
Atelier 2 (assemblage) 2 1 22
Atelier 3 (sablage) 1 1 12
Marge 300 UM 200 UM
La question que se pose la direction de l'usine est la suivante : combien
faut-il produire de bureaux de chaque modèle pour maximiser son pro t ?
Mêmes questions.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 71 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
Exercice 2 :
Un groupe d'étudiants organise un petit déjeuner pendant la pause de 10
heures. Pour pouvoir satisfaire la demande, ils doivent disposer au
minimum de 90 croissants, de 60 beignets et de 120 pains au chocolat.
Un supermarché propose 2 lots :
le lot A coûte 10 UM et il est composé de : 3 croissants, 1 beignet et
1 pain au chocolat,
le lot B coûte 20 UM et contient : 1 croissant, 1 beignet et 4 pains
au chocolat.
La question qui se pose est la suivante : combien de lots A et de lots B
doivent être achetés pour satisfaire la demande avec un coût minimum ?
1 Écrire le programme linéaire (P) modélisant ce problème.
2 Résoudre graphiquement (P).
3 Donner une interprétation économique des résultats trouvés en 2.
4 Combien de lots A et de lots B devraient être achetés s'ils avaient le
même prix 10 UM ? Justi er votre réponse.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 72 / 220
Résolution des programmes linéaires : Méthode graphique Méthode Graphique : Minimisation
Exercice 3 :
Un restaurateur a constaté que sa clientèle préfère les fruits de mer et qu'il
peut orir indiéremment :
des assiettes à 8 UM,
contenant 5 crevettes, 2 crabes et une huître.
des assiettes à 6 UM,
contenant 3 crevettes, 3 crabes et 3 huîtres.
Il dispose de 30 crevettes, 24 crabes et 18 huîtres.
La question que se pose le restaurateur est la suivante : comment doit-il
disposer ces assiettes pour réaliser la recette maximale ?
1 Modéliser le problème sous forme d'un programme linéaire.
2 Résoudre graphiquement le programme linéaire.
3 Donner une interprétation économique des résultats obtenus.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 73 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Astuce :
Dans ce paragraphe, nous allons voir une astuce pour trouver le sommet
optimale, dans le cas de PL avec une solution optimale unique.
Cette technique repose sur la comparaison des pentes, il faut remarquer
que entre deux droite D 1, et D 2 qui se croise, il est facile de deviner la
droite qui correspond à l'équation : (Δ1 ) : y = −0, 3x + 40, et celle qui
correspond (Δ2 ) : y = −x + 100.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 74 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Exemple 1 :
Reprenons le problème de minimisation de la coopérative de l'île des
Palmiers,
le coût d'opportunité de la coopérative s'écrit sous la forme :C = 50x1 +80x2
avec les contraintes suivantes :
Thon ⇒ 6x1 + 30x2 ≥ 900
Morue ⇒ 20x1 + 8x2 ≥ 800
Sardine ⇒ 10x1 + 10x2 ≥ 700
x1 ≥ 0, x2 ≥ 0
Il faut tracer les droites, et délimiter le domaine admissible.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 75 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Il est claire que la solution sera un point parmi les quatre sommets A, B, C,
et D. Le problème est de trouver lequel est le bon.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 76 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
On a les pentes suivantes :
⎧
⎪
⎪ Pente Sardine = −1
⎨
Pente Thon = − 0, 5
⎪ Morue = −2, 5
⎪
⎩
Pente
Pente Iso-Coût = −0, 625
Dans l'ordre croissant, on a :
Pente Morue < Pente Sardine < pente Iso-Coût < Pente Thon
-2,5 < -1 < -0,625 < -0,5
Ce qui nous amène à la conclusion suivante, le sommet optimal est le point
C, intersection entre la droite Sardine et la droite Thon.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 77 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Exemple 2 :
Considérons un exemple de maximisation, la règle est la même :
Max Z = 17x1 + 5x2 Pente Iso = − 3, 4
(U 1) 1, 5x1 + 10x2 ≥ 500 Pente U1 = − 1, 2
(U 2) 5x1 + 20x2 ≥ 2000 Pente U2 = −4
(U 3) 1, 25x1 + 0, 8x2 ≥ 200 Pente U3 = −10
(U 4) 4x1 + 5x2 ≥ 900 Pente U4 = −2, 47
x1 ≥ 0, x2 ≥ 0
Dans l'ordre on a :
Pente U3 < Pente U2 < pente Iso < Pente U4 < Pente U1
-10 < -4 < -3,4 < -2,47 < -1,2
Cela veut dire que le sommet optimal est le point d'intersection entre la
droite U2 et la droite U4. Cependant, d'après la représentation graphique
des contraintes, l'intersection entre U2 et U4 n'appartient pas au domaine
admissible illustré par le dessin suivant :
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 78 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Il apparaît clairement sur le dessin, que la contrainte U4 est redondante,
donc il ne faut pas la prendre en considération, cela implique que le
Moralité :
sommet optimal est l'intersection entre la droite U2 et la droite U1.
Cette méthode ne vaccine pas contre la représentation du domaine
admissible, qui permet d'éliminer les contraintes redondantes.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 79 / 220
Résolution des programmes linéaires : Méthode graphique Astuce
Chapitre 3 :
Résolution des programmes linéaires
La méthode du simplexe
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 80 / 220
La méthode du simplexe Présentation de la méthode
1. Présentation de la méthode du simplexe
Développée initialement par George Dantzig en 1947.
Outil principal de résolution des problèmes de programmation linéaire.
Il existe plusieurs formulations de cette méthode :
méthode des tableaux,
méthode algébrique (délicate dès que le nombre des variables et des
contraintes est important).
Méthode exacte itérative
et pour résoudre des problèmes linéaires de
grande taille :
Elle consiste à suivre un certain nombre d'étapes (itérations) avant
d'obtenir la solution d'un problème donné,
Elle permet de trouver la solution exacte en un nombre ni d'étapes.
Explore les sommets de la région admissible en améliorant à chaque
itération la valeur du critère.
Basée sur l'algèbre des matrices.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 81 / 220
La méthode du simplexe Notions générales
2. Notions générales
2.1 Rappels
Un programme linéaire s'écrit généralement sous la forme :
⎧
⎪ max (ou min) z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn {≤, =, ≥} b1
⎪
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn {≤, =, ≥} b2
⎪ ... ⇐⇒
⎪
⎪
⎪
⎪
⎪
⎪ a x + am2 x2 + ... + amn xn {≤, =, ≥} bm
⎩ m1 1
x 1 ≥ 0, . . . , x n ≥ 0
⎧ n
⎪
⎪
⎪ max / min z = c j xj
⎪
⎪
⎪
⎨ j=1
n
⎪
⎪
⎪ aij xj {≤, =, ≥} bi i = 1, m
⎪
⎪
⎪
⎩ j=1
xj ≥ 0 j = 1, n
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 82 / 220
La méthode du simplexe Notions générales
En utilisant la formulation matricielle :
⎧
⎨ max / min z = c T x
Ax {≤, =, ≥} b
⎩
x ≥0
c = (c1 , c2 , ..., cn ) ∈ Rn , b = (b1 , b2 , ..., bm ) ∈ Rm
⎛ ⎞
a11 a12 · · · a1n
⎜ a21 a22 · · · a2n ⎟
⎜ ⎟
A=⎜ . .. .. .. ⎟ matrice de type (m , n)
⎝ .. . . . ⎠
am 1 am 2 · · · amn
n
et c T x = c j xj .
j=1
aij (i = 1, m ; j = 1, n) : coe cients techniques ;
bi (i = 1, m) : seconds membres des contraintes ;
cj (j = 1, n) : coe cients de la fonction économique ;
xj (j = 1, n) : variables de décision (niveaux d'activité).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 83 / 220
La méthode du simplexe Notions générales
2.2 Forme canonique d'un PL
maximisation de la fonction objectif
toutes les contraintes sont des inégalités du type ≤
toutes les variables sont positives
⎧ n
⎪
⎪
⎪ max z = c j xj
⎪
⎪
⎪
⎨ j=1
n
⎪
⎪ aij xj ≤ bi i = 1, m
⎪
⎪
⎪
⎪
⎩ j=1
xj ≥ 0 j = 1, n
Forme matricielle
⎧
⎨ max z = c T x
Ax ≤ b
⎩
x ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 84 / 220
La méthode du simplexe Notions générales
Exemple :
⎧
⎪
⎪ max 6x1 + 7x2 + 8x3
⎪
⎪ x1 + 2x2 + x3 ≤ 100 ⎧
⎪
⎪
⎨ ⎨ max z = c T x
3x1 + 4x2 + 2x3 ≤ 120
(P1 ) ⇐⇒ Ax ≤ b
⎪ 2x1 + 6x2 + 4x3 ≤ 200 ⎩
⎪
⎪ x ≥0
⎪
⎪ x + x3 ≤ 150
⎪
⎩ 1
x 1 , x 2 , x3 ≥ 0
avec
⎛ ⎞ ⎛ ⎞
1 2 1 100 ⎛ ⎞ ⎛ ⎞
⎜ ⎟ ⎜ ⎟ 6 x1
A=⎜ ⎟ ; b=⎜ ⎟ ; c=⎝ ⎠ x = ⎝ x2 ⎠
3 4 2 120
⎝ 2 6 4 ⎠ ⎝ 200 ⎠ 7 ;
8 x3
1 0 1 150
A de type (4 , 3),
m=4 (contraintes) et n=3 (variables de décision).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 85 / 220
La méthode du simplexe Notions générales
2.3 Forme standard d'un PL
maximisation de la fonction objectif
toutes les contraintes sont de type égalités (=)
toutes les variables sont positives
⎧ n
⎪
⎪
⎪ max z = c j xj
⎪
⎪
⎪
⎨ j=1
n
⎪
⎪ aij xj = bi i = 1, m
⎪
⎪
⎪
⎪
⎩ j=1
xj ≥ 0 j = 1, n
Forme matricielle
⎧
⎨ max z = c T x
Ax = b
⎩
x ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 86 / 220
La méthode du simplexe Notions générales
2.4 Passage entre les formes
1 min f ⇐⇒ max − f
Par exemple : minimiser x1 + 2x2 revient à maximiser −x1 − 2x2
car : f (x ∗ )
= min{ f (x) , x ∈ X } ⇐⇒ f (x ∗ )
≤ f (x) , ∀x ∈ X ⇐⇒
−f (x ∗ ) ≥ −f (x), ∀x ∈ X ⇐⇒ −f (x ∗ ) = max{ −f (x) , x ∈ X }
2 ax ≥ b ⇐⇒ −ax ≤ −b
ax ≤ b
3 ax = b ⇐⇒
ax ≥ b
ax + y = b
4 ax ≤ b ⇐⇒ y est dite variable d'écart
y ≥0
ax − y = b
5 ax ≥ b ⇐⇒
y ≥0
6 x ≤ 0 ⇐⇒ −x ≥ 0
x = x+ − x− x + = max(x , 0)
7 x quelconque ⇐⇒ avec
x+ ≥ 0 , x− ≥ 0 x − = max(−x , 0)
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 87 / 220
La méthode du simplexe Notions générales
Propriété
Tout programme linéaire peut être mis sous la forme canonique et sous la
forme standard.
Remarques
1 Le passage entre la forme générale, la forme canonique et la forme
standard se fait moyennant les transformations ci-dessus.
2 La forme canonique est utilisée dans la résolution graphique.
Tandis que la forme standard permet une résolution matricielle et sera
utilisée pour la méthode de simplexe.
Notons aussi que la méthode du simplexe requiert des bi ≥ 0.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 88 / 220
La méthode du simplexe Notions générales
Exemple :
⎧
⎪
⎪ min 5x1 − 3x2
⎪
⎨ x1 − x 2 ≥ 2
⎪
Soit le problème : (P2 )
⎪
2x 1 + 3x 2 ≤ 4
1 + 6x2 = 10
⎪
⎪ −x
⎪
⎩
x1 , x 2 ≥ 0
En introduisant les variables d'écart x3 ≥ 0 et x4 ≥ 0 dans la première et la
deuxième contrainte, on met (P2 ) sous la forme équivalente :
⎧
⎪
⎪ max −5x1 + 3x2
⎪
⎨ 1 − x2 − x3 = 2
⎪ x
(P2 )
⎪
2x1 + 3x2 + x4 = 4
1 + 6x2 = 10
⎪
⎪ −x
⎪
⎩
x 1 , x2 , x3 , x 4 ≥ 0
(P2 ) est la forme standard de (P2 ).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 89 / 220
La méthode du simplexe Bases, variables de base et solution de base
3. Bases, variables de base et solution de base
Soit Ax = b un système d'équations linéaires avec :
A matrice de type (m , n), m ≤ n et rang (A) = m.
Le système est donc sous-déterminé c-à-d le nombre m d'équations est
inférieur au nombre n d'inconnues notées x1 , . . . , xn .
En plus, il existe au moins une sous-matrice de A notée B carrée inversible
de type (m , m) (d'ordre m).
Dé nitions
On appelle base toute sous-matrice carrée B inversible de type
(m , m) extraite de A.
Les variables associées aux colonnes de B sont dites variables de base,
les autres variables hors base.
Par extension, on appellera également base la liste ordonnée des
variables de base ou de leurs indices (notée B).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 90 / 220
La méthode du simplexe Bases, variables de base et solution de base
Exemple :
Soit le système linéaire :
x2 + 2x3 + 2x4 = 1
x 1 + x 2 + 2x 3 + 3x4 = 1
Ce système peut s'écrire Ax =⎛b ⎞
, avec :
x1
⎜ x2 ⎟
A=
0 1 2 2
⎜
x =⎝ ⎟ et b =
1
x3 ⎠
,
1 1 2 3 1
x4
A est de type ( 2 , 4) (2 équations et 4 variables).
1 2
La sous-matrice B= est inversible et rang (A) = 2.
1 3
Ainsi B est une base.
Les variables de base associés à B sont x2 et x4 .
Les variables hors base associés à B sont x1 et x3 .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 91 / 220
La méthode du simplexe Bases, variables de base et solution de base
Remarques
Une base est inversible et donc les variables de base correspondent à
des colonnes linéairement indépendantes de la matrice A.
Par conséquent, on peut avoir plusieurs bases dans une matrice A.
En eet, on peut le remarquer dans l'exemple précédent :
0 1
est aussi une base et correspond alors aux variables de base
1 1
x1 et x2 .
1 2
n'est pas une base (car non inversible).
1 2
Avec les conditions précédentes, le système Ax = b admet une
in nité de solutions.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 92 / 220
La méthode du simplexe Bases, variables de base et solution de base
Le système de l'exemple précédent :
x2 + 2x3 + 2x4 = 1
x 1 + x 2 + 2x 3 + 3x4 = 1
admet une in nité de solutions.
⎛⎞
x1
⎜ x2 ⎟
A=
0 1 2 2
x =⎝ ⎜ ⎟ et b =
1
x3 ⎠
On a : ,
1 1 2 3 1
x4
1 2 − 1 3 −2
B= est une base et B =
1 3 −1 1
Ax = b ⇐⇒ B −1 A x = B −1 b
3 −2 0 1 2 2 −2 1 2 0
B −1 A = =
−1 1 1 1 2 3 1 0 0 1
3 −2 1
B −1 b = =
−1 1 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 93 / 220
La méthode du simplexe Bases, variables de base et solution de base
Donc le système est équivalent à :
⎞ ⎛
x1
−2 1 2 0 ⎜ ⎟
⎜ x2 ⎟ = 1 −2x1 + x2 + 2x3 = 1
⇐⇒
1 0 0 1 ⎝ x3 ⎠ 0 x 1 + x4 = 0
x4
x2 = 1 + 2x1 − 2x3
⇐⇒
x4 = −x1
Le système précédent est équivalent au système de départ Ax = b mais
exprimé dans la base B
En xant des valeurs arbitraires pour x1 et x3 , on obtient les solutions
correspondantes pour x2 et x4 .
En particulier, pour x1 = 0 et x3 = 0, on obtient la solution x2 = 1 et
x4 = 0.
On dit alors que cette solution est la solution de base associée à la base B .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 94 / 220
La méthode du simplexe Bases, variables de base et solution de base
Généralisation :
Soit Ax = b un système d'équations linéaires tel que A matrice de type
(m , n), m ≤ n et rang (A) = m. Soit B une base de A.
Après permutation des colonnes de A de manière à ce que celles de B
soient en premier, on obtient :
A=
P
B N et x=
P xB
xN
où
N est la sous-matrice de A correspondant aux variables hors base,
xB vecteur de Rm formé par les variables de base,
xN vecteur de Rn−m formé par les variables hors base.
et on a :
Ax = b ⇐⇒ BxB + NxN = b ⇐⇒ xB = B −1 b − B −1 NxN
Pour déterminer toutes les solutions du système, on choisit donc
arbitrairement les valeurs de xN (paramètres) et on calcule les valeurs
correspondantes de xB .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 95 / 220
La méthode du simplexe Bases, variables de base et solution de base
Dé nitions
On appelle solution de base (associée à la base B ), la solution
particulière obtenue en prenant xN = 0.
xB est déterminée de façon unique par :
BxB = b ⇐⇒ xB = B −1 b
Une solution de base est dite réalisable si xB ≥ 0 (toutes les variables
de base sont positives), autrement dit : B −1 b ≥ 0.
Remarque :
Dans le cas d'un programme linéaire sous forme standard avec les
contraintes Ax = b , x ≥ 0, une solution de base réalisable correspond
géométriquement à un sommet du polyèdre des contraintes.
En particulier, une solution optimale correspond à une solution de base
réalisable qui maximise la fonction objectif.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 96 / 220
La méthode du simplexe Méthode du simplexe en tableaux
4. Méthode du simplexe en tableaux
4.1 Exemple :
Considérons le problème déjà étudié (Exemple 1, Chapitre 1).
Rappelons le programme linéaire qui modélise ce problème :
⎧
⎪
⎪ max z = 3x1 + 5x2
⎪
⎪
⎨ x1 ≤ 4
(P) 2x2 ≤ 12
⎪
⎪
⎪
⎪ 3x1 + 2x2 ≤ 18
⎩ x ≥ 0 ;x ≥ 0
1 2
où
x1 est le nombre de chassis du produit 1 (chassis en aluminium),
x2 est le nombre de chassis du produit 2 (chassis en bois).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 97 / 220
La méthode du simplexe Méthode du simplexe en tableaux
La forme standard du programme linéaire (P) s'écrit :
⎧
⎪
⎪ max z = 3x1 + 5x2 + 0e1 + 0e2 + 0e3
⎪
⎪
⎨ x1 + e1 + 0e2 + 0e3 = 4
(PS) 2x2 + 0e1 + e2 + 0e3 = 12
⎪
⎪
⎪ 3x1 + 2x2 + 0e1 + 0e2 + e3 = 18
⎪
⎩
x1 ≥ 0 ; x 2 ≥ 0 ; e 1 ≥ 0 ; e 2 ≥ 0 ; e 3 ≥ 0
où ei est la variable d'écart associée à la ième contrainte.
Le système linéaire des contraintes associé à (PS) peut s'écrire :
Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
⎛ ⎞ x1 ⎛ ⎞
⎜ x2 ⎟
1 0 1 0 0
⎜ ⎟ 4
à = ⎝ 0 2 0 1 0 ⎠ ; x̃ = ⎜ ⎟
⎜ e1 ⎟ ; b̃ =
⎝ 12 ⎠
3 2 0 0 1 ⎝ e2 ⎠ 18
e3
z = c̃ T x̃ = 3x1 + 5x2 + 0e1 + 0e2 + 0e3 avec c̃ = (x1 , x2 , 0 , 0 , 0)T
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 98 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Choix de la solution de base réalisable initiale :
⎛ ⎞
1 0 0
Une base initiale est donnée par la matrice : I =⎝ 0 1 0 ⎠
0 0 1
Elle correspond aux variables de base e1 , e2 , e3
et variables hors base x 1 , x2 .
La solution de base réalisable initiale est :
(x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 4 , 12 , 18)
Cela signi e qu'au départ on a :
x1 = 0 ; x2 = 0 ; e1 = 4 ; e2 = 12 ; e3 = 18
Autrement dit : on ne produit rien au départ
et z = 3x1 + 5x2 + 0e1 + 0e2 + 0e3 = 0.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 99 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Tableau initial :
Le premier tableau du simplexe (tableau initial) s'écrit :
Base x1 x2 e1 e2 e3 s.m
e1 1 0 1 0 0 4
e2 0 2 0 1 0 12
e3 3 2 0 0 1 18
−z 3 5 0 0 0 0
Variables de base : e1 , e2 , e3 Variables hors base : x1 , x2
Solution de base : (x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 4 , 12 , 18)
La dernière ligne donne les valeurs marginales (ou taux de substitution )
des variables hors base. Elle correspond à la valeur de −z donc la marge
béné ciaire initiale z = 0.
La solution n'est pas optimale. On recherche donc une solution de base
meilleure : d'où une autre itération.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 100 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Itération du simplexe :
On augmente la fonction objectif en faisant entrer une variable dans la base
prenant la place d'une variable qui va sortir de la base.
Choix de la variable entrante dans la base :
Une augmentation de 1 unité de x1 ferait croître la fonction objectif de 3
Une augmentation de 1 unité de x2 ferait croître la fonction objectif de 5.
On a intérêt à augmenter la valeur de la fonction objectif le plus
rapidement possible donc à augmenter la variable ayant le plus grand
coe cient strictement positif (cas de maximisation) de la dernière ligne :
x2 variable entrante dans la base.
Règle générale pour la variable entrante dans la base :
On sélectionne la variable hors base ayant le plus grand coe cient
strictement positif dans la dernière ligne ( x2 dans notre cas).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 101 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Choix de la variable sortante de la base :
La question qui se pose est : jusqu'à quelle limite doit-on augmenter x2 ?
Une première idée est de pousser x2 le plus loin possible tant que les
variables de base restent positives.
Supposons qu'on augmente x2 en maintenant x1 hors base ( x1 = 0), alors :
⎧
⎪ e1 = 4 ⎧
⎪
⎨ ⎨ e2 = 12 − 2x2 ≥ 0
2x2 + e2 = 12
⇐⇒ e3 = 18 − 2x2 ≥ 0
⎪ 2x + e3 = 18 ⎩
⎪
⎩ 2 x2 ≥ 0
x2 ≥ 0 ; e 1 ≥ 0 ; e 2 ≥ 0 ; e 3 ≥ 0
⎧
⎨ x2 ≤ 12/2 = 6
⇐⇒ x2 ≤ 18/2 = 9 =⇒ 0 ≤ x2 ≤ min{12/2 , / } = 12/2 = 6
18 2
⎩
x2 ≥ 0
Ainsi, la valeur limite que x2 peut prendre est x2 = 6. La deuxième
contrainte sera alors saturée ( e2 = 0) : e2 variable sortante de la base.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 102 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Règle générale pour la variable sortante de la base :
On eectue le rapport des seconds membres des contraintes aux
coe cients strictement positifs correspondants à la variable entrante, puis
on sélectionne la variable de la base ayant le plus petit rapport positif dans
la colonne R (e2 dans notre cas).
Tableau 1
Base x1 x↓2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4/0 = ∞
← e2 0 2 0 1 0 12 12/2 = 6
e3 3 2 0 0 1 18 18/2 = 9
−z 3 5 0 0 0 0
x2 variable entrante dans la base.
e2 variable sortante de la base.
Le coe cient à l'intersection de la colonne de la variable entrante et la
ligne de la variable sortante s'appelle pivot (2 dans notre cas).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 103 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Pour obtenir le tableau 2, on eectue des pivotages.
Règles de calcul :
Les coe cients de la ligne du pivot sont divisés par le pivot.
Les coe cients de la colonne du pivot (sauf le pivot) sont nuls.
Les autres coe cients sont obtenus par la règle :
Cpivot
Nv = Av − ( × Lpivot)
Pivot
Nv : nouvelle valeur
Av : ancienne valeur
Cpivot : colonne du pivot
Lpivot : Ligne du pivot
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 104 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Tableau 1
↓
Base x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4/0 = ∞
← e2 0 2 0 1 0 12 12/2 = 6
e3 3 2 0 0 1 18 18/2 = 9
−z 3 5 0 0 0 0
Tableau 2
↓
Base x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4
x2 0 1 0 1/2 0 6 ∞
← e3 3 0 0 −1 1 6 2
−z 3 0 0 −5/2 0 −30
Variable entrante dans la base : x1 Variable sortante de la base : e3
Pivot : 3
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 105 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Tableau 2
Base
↓
x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4
x2 0 1 0 1/2 0 6 ∞
← e3 3 0 0 −1 1 6 2
−z 3 0 0 −5/2 0 −30
Tableau 3
Base x1 x2 e1 e2 e3 s.m
e1 0 0 1 1/3 −1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 −1/3 1/3 2
−z 0 0 0 −3/2 −1 −36
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 106 / 220
La méthode du simplexe Méthode du simplexe en tableaux
Tous les coe cients de la dernière ligne (coe cients de la fonction
objectif) sont négatifs ou nuls : on ne peut plus augmenter la fonction
objectif. Le tableau 3 est optimal et l'algorithme du simplexe s'arrête.
On a donc : x1∗ = 2 ; x2∗ = 6 et zmax = 36.
Interprétation économique :
L'entreprise doit produire 2 châssis de type 1 (en aluminium) et 6 châssis
de type 2 (en bois) pour réaliser un pro t maximal de 36 UM.
A l'optimum les variables de base sont x1∗ = 2 ; x2∗ = 6 et e1∗ = 2 et les
variables hors base sont e2∗ = e3∗ = 0 .
La première contrainte n'est pas saturée : il reste une capacité disponible
dans l'atelier 1 (sous-emploi) égale à 2 heures par semaine.
La deuxième et la troisième contrainte sont saturées : il ne reste plus de
capacité disponible dans les ateliers 2 et 3 (plein emploi). En eet :
4 − x1∗ = 4 − 2 = 2
12 − 2x2∗ = 12 − 2 × 6 = 0
18 − (3x1∗ + 2x2∗ ) = 18 − (3 × 2 + 2 × 6) = 0.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 107 / 220
La méthode du simplexe Cas général
4.2 Cas général :
Considérons un programme linéaire sous forme standard :
⎧
⎨ max z = c T x
(PS) Ax = b
⎩
x ≥0
où est une A matrice de type (m , n), m ≤ n et rang (A) = m.
Supposons connue une base B telle que la solution de base associée est
réalisable.
Notons :
B = {i1 , . . . , im } : l'ensemble des indices correspondants aux colonnes de B
(et donc aux variables de base),
N = {j1 , ..., jn−m } = {1, ..., n} \ B : l'ensemble des indices hors base,
N : la sous-matrice de A correspondant aux colonnes des indices hors base,
xB : le vecteur de Rm formé par les variables de base (xi , i ∈ B ),
xN : le vecteur de Rn−m formé par les variables hors base (xi , i ∈ N ).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 108 / 220
La méthode du simplexe Cas général
Rappelons que la solution de base associée à B est réalisable si :
xB = B −1 b ≥ 0.
En eectuant un partitionnement suivant les indices de B et ceux de N , on
peut écrire :
xB
Ax = b ⇐⇒ B N =b
xN
⇐⇒ B xB + N xN = b
⇐⇒ xB + B −1 N xN = B −1 b
⇐⇒ xB = B −1 b − B −1 N xN
La fonction objectif peut s'écrire :
z = cT x = c i xi + c i x i = c B xB + c N xN
i∈B i∈N
avec cB = (ci1 , ..., cim ) et cN = (cj1 , ..., cjn−m )
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 109 / 220
La méthode du simplexe Cas général
Donc le PL est équivalent à la forme réduite associée à la base B :
⎧
⎨ max z = cB xB + cN xN
(PR) x + B −1 N xN = B −1 b
⎩ B
xB ≥ 0 , x N ≥ 0
On peut maintenant formuler le problème en réécrivant les contraintes et
l'objectif en fonction des variables hors base :
xB + B −1 N xN = B −1 b ⇐⇒ xB = B −1 b − B −1 N xN =⇒
z = c B x B + c N xN
= cB (B −1 b − B −1 N xN ) + cN xN
= (cN − cB B −1 N)xN + cB B −1 b
z = dN xN + z̄ ⇐⇒ dN xN = z − z̄
avec dN = cN − cB B −1 N ; z̄ = cB B −1 b
les composantes de dN s'appellent coûts réduits des variables hors base.
Ils interviennent de façon déterminante dans la méthode du simplexe.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 110 / 220
La méthode du simplexe Cas général
Ainsi, le problème consiste à maximiser z sachant :
xB + B −1 N xN = B −1 b
d N xN = z − z̄
et xB ≥ 0 , xN ≥ 0.
La solution de base est donnée par : xN = 0 ; xB = b̄ = B −1 b.
Cette solution de base est réalisable signi e que b̄ = B −1 b ≥ 0.
La valeur de la fonction objectif z associée à cette solution est z̄ .
Finalement, le tableau du simplexe associé à la base B est (à une
permutation de colonnes près) de la forme :
Base xB xN s.m
xB Im B 1N
− b̄ = B −1 b
−z 0 dN −z̄
dN = cN − cB B −1 N ; z̄ = cB B −1 b
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 111 / 220
La méthode du simplexe Cas général
Par exemple, le tableau 2 du paragraphe 4.1 donne :
↓
Base x1 x2 e1 e2 e3 s.m
e1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
← e3 3 0 0 −1 1 6
−z 3 0 0 −5/2 0 −30
Base xB xN s.m
xB Im B −1 N b̄ = B −1 b
−z 0 dN −z̄
xB = (e1 , x2 , e3 ): variables de base,
xN = (x1 , e2 ) : variables hors base,
dN = (3 , −5/2) ; b̄ = (4 , 6 , 6),
Solution de base : (x1 , x2 , e1 , e2 , e3 ) = (0 , 6 , 4 , 0 , 6),
Fonction objectif : z̄ = 30.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 112 / 220
La méthode du simplexe Cas général
Remarques :
La forme tableau présente l'avantage de préserver la structure du
programme linéaire. En plus, elle met en évidence les opérations
matricielles (résolution des systèmes linéaires par exemple) mis en
÷uvre durant la résolution.
Les variables de base se distinguent par le fait qu'elles forment une
matrice identité dans le système des contraintes et n'interviennent pas
dans la fonction objectif. les variables hors base sont les variables
restantes et leur coe cients dans la fonction objectif sont représentés
par les coûts réduits (vecteur dN ).
Rappelons que, une fois le choix du pivot établi, le passage d'un
tableau simplexe au tableau suivant s'eectue manuellement en
utilisant les règles de calculs :
Les coe cients de la ligne du pivot sont divisés par le pivot.
Les coe cients de la colonne du pivot (sauf le pivot) sont nuls.
Les autres coe cients sont obtenus par la règle du rectangle.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 113 / 220
La méthode du simplexe Cas général
Dé nition
1 Une solution de base xB associée à la base B est dite non dégénérée
si :
xB = B − 1 b > 0
c-à-d le second membre du système réduit b̄ > 0
autrement dit, si toutes les variables de base sont strictement positives.
Dans le cas contraire, on dit que la solution de base est dégénérée.
2 Un programme linéaire est non dégénéré si toute solution de base
réalisable est non dégénérée.
Théorème (Critère d'optimalité)
Si
d N = c N − c B B −1 N ≤ 0
alors la solution de base réalisable xN = 0 ; xB = b̄ = B −1 b est optimale.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 114 / 220
La méthode du simplexe Cas général
Preuve du Théorème :
Soit x = (x1 , ..., xn ) une solution de base réalisable quelconque et soit
x∗ = (x1∗ , ..., xn∗ ) la solution de base associée à B .
Comme xN ≥ 0 (car x réalisable) et dN ≤ 0 (par hypothèse) on a :
d N xN = d i xi ≤ 0
i∈N
D'où :
z(x1 , ..., xn ) = dN xN + z̄ ≤ z̄ = z(x1∗ , ..., xn∗ ).
Étapes du simplexe (cas général) :
Si le critère d'optimalité ( dN ≤ 0) n'est pas véri é on va procéder soit à
une itération, soit on va découvrir que max z = +∞.
Supposons alors qu'il existe au moins une composante dj de dN telle que
d j > 0, j ∈ N .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 115 / 220
La méthode du simplexe Cas général
Choix de la variable entrante :
Considérons l'indice j ∈N tel que
dj = max{dk ; k ∈ N }
et la colonne d'indice j de la matrice ĀN = B −1 N = (ākj , (1 ≤ k ≤ m).
On a les possibilités suivantes :
1 ākj ≤ 0, ∀ k = 1, ..., m
(Tous les termes de la colonne j de la variable entrante sont ≤ 0).
Dans ce cas l'ensemble réalisable est non borné et max z = +∞
2 Il existe k ∈ {1, ..., m} tel que ākj > 0
Dans ce cas on va procéder à une itération et
xj est la variable entrante dans la base.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 116 / 220
La méthode du simplexe Cas général
Choix de la variable sortante :
On va supposer maintenant que le programme linéaire est non dégénéré.
Soit p l'indice véri ant :
b̄p b̄p
= min{ ; āpj > 0}
āpj āpj
(On fait le rapport des coe cients du s.m du tableau simplexe avec les
coe cients de la colonne j de la variable entrante et on choisit le plus petit)
Dans ce cas, xp est la variable sortante de la base.
Théorème (Convergence de l'algorithme du simplexe)
Supposons que le programme linéaire est non dégénéré et qu'il admette au
moins une solution optimale (avec zmax ni). Alors après un nombre ni
d'itérations, l'algorithme du simplexe va trouver une solution de base
optimale.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 117 / 220
La méthode du simplexe Problèmes particuliers
4.3 Problèmes particuliers :
Dans le paragraphe précédent, nous avons fait les deux hypothèses
suivantes :
1 La connaissance d'une solution de base réalisable initiale.
2 Le programme linéaire est non dégénéré.
En général, ces hypothèses ne sont pas toujours véri ées.
Détermination d'une base réalisable initiale :
Pour déterminer une base initiale réalisable, considérons tout d'abord le cas
où le PL est donné sous la forme canonique :
⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn ≤ b1
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn ≤ b2
(PC ) .
⎪
⎪ .
⎪
⎪
.
⎪
⎪ a x + am2 x2 + ... + amn xn ≤ bm
⎪
⎩ m1 1
x 1 ≥ 0, . . . , x n ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 118 / 220
La méthode du simplexe Problèmes particuliers
En introduisant des variables d'écart (e1 , ..., em ) , nous obtenons le PL sous
forme standard :
⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn + 0e1 + ... + 0en
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn + e1 = b1
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn + e2 = b2
(PS) .
⎪
⎪ .
⎪
⎪
.
⎪
⎪ a x + am2 x2 + ... + amn xn + em = bm
⎪
⎩ m1 1
x1 ≥ 0, . . . , xn ≥ 0, e1 ≥ 0, . . . , em ≥ 0
En posant
à = A Im ; x̃ = (x1 , ..., xn , e1 , ..., em )T ; c̃ = (c1 , ..., cn , 0, ..., 0)T
où Im est la matrice identité d'ordre m.
(PS) s'écrit alors sous la forme matricielle :
⎧
⎨ max z̃ = c̃ T x̃
Ãx̃ = b
⎩
x̃ ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 119 / 220
La méthode du simplexe Problèmes particuliers
Comme Im est inversible on a une solution de base initiale :
B = I m ; N = A ; x B = B − 1 b = b ; xN = x = 0
Si b≥0 alors cette solution est en plus réalisable.
Le problème se pose dans le cas contraire c-à-d celui où il existe au moins
un indice j tel que bj < 0.
Dans ce cas, xB = b, xN = x = 0 est une solution de base mais non
réalisable et il faut procéder à une première étape qui consiste à déterminer
une solution de base réalisable de départ : c'est la phase I de la méthode
du simplexe.
Problème de dégénérescence :
Dans le cas où le PL est dégénéré, on peut avoir :
b̄p b̄p
= min{ ; āpj > 0} = 0
āpj āpj
Alors la fonction objectif z ne varie pas après le changement de base et par
conséquent on peut rencontrer les situations suivantes :
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 120 / 220
La méthode du simplexe Problèmes particuliers
Lors de la détermination de la variable entrante, nous sommes en
présence d'au moins deux variables hors base ayant le même et le plus
élevé coe cient strictement positif dans la dernière ligne.
Lors de la détermination de la variable sortante, nous sommes en
présence d'au moins deux variables de base ayant le même et le plus
petit rapport positif dans la dernière colonne.
il est possible, après un certain nombre d'itérations, de retrouver le
tableau de départ (problème de cyclage).
Plusieurs remèdes au cyclage dans les cas dégénérés sont utilisés, le plus
connu c'est la règle de Bland :
Lorsque plusieurs variables sont susceptibles d'entrer ou de sortir de la
base, on choisit toujours la variable xr ayant le plus petit indice r .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 121 / 220
La méthode du simplexe Problèmes particuliers
Exemples :
T1
Base x1 x2 x3 x4 x 5 x6 s.m R
x5 4 7 0 0 1 4 4 4/7
x4 2 8 0 1 0 3 0 0
x3 -2 9 1 0 0 2 0 0
−z -5 2 0 0 0 5 -3
Variables candidates à enter dans la base : x2
Variables candidates à sortir de la base : x4 et x3 . On choisit donc x3 .
T2
↓
Base x1 x2 x3 e1 e2 e3 s.m R
← e1 1 2 5 1 0 0 4 2
e2 3 4 3 0 1 0 8 2
e3 2 4 1 0 0 1 12 3
−z 2 3 1 0 0 1 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 122 / 220
La méthode du simplexe Problèmes particuliers
T3
↓
Base x1 x2 x3 e1 e2 e3 s.m
e1 1 2 5 1 0 0 3
e2 3 1 3 0 1 0 10
e3 2 8 1 0 0 1 8
−z 3 3 2 0 0 0 0
T4
↓
Base x1 x2 e1 e2 s.m
e1 0 -2 1 -1 20
x1 1 0 0 2,5 3
−z 0 16 0 -3 -32
Tous les coe cients de la colonne de la variable entrante x2 sont négatifs
ou nuls : zmax = +∞
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 123 / 220
La méthode du simplexe Problèmes particuliers
Un autre cas particulier : in nité de solutions optimales
Si à la n des itérations, une variable est hors base avec un coe cient nul
dans la dernière ligne du tableau optimal, alors on a une arête (face,...)
optimale. Les autres sommets optimaux peuvent être obtenus en faisant
rentrer cette variable dans la base. Considérons, par exemple, le tableau
optimal suivant :
Base x1 x2 e1 e2 s.m
x1 1 0 1 1 3
x2 0 1 -1 -2 2
−z 0 0 -1 0 -8
On fait entrer e2 dans la base et x1 sera alors la variable sortante. Ainsi, on
obtient une autre solution optimale :
Base x1 x2 e1 e2 s.m
e2 1 0 1 1 3
x2 2 1 1 0 8
−z 0 0 1 0 -8
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 124 / 220
La méthode du simplexe Simplexe avec minimisation
4.4 Simplexe avec minimisation de l'objectif :
Dans le cas de minimisation de l'objectif, les itérations et l'optimalité de la
méthode du simplexe sont déterminés par les critères suivants :
Critère de la variable entrante : On choisit la variable hors base
ayant le coût réduit le plus négatif.
Critère de la variable sortante : le même que dans le cas de
maximisation, puisque ce critère est lié à la réalisabilité des variables.
Critère d'optimalité : L'algorithme du simplexe s'arrête quand tous
les coûts réduits des variables hors base (coe cients de la dernière
ligne du tableau simplexe) sont tous positifs ou nuls.
Les critères précédents découlent de la propriété suivante :
minimiser z = c1 x1 + ... + cn xn revient à maximiser −z .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 125 / 220
La méthode du simplexe Simplexe avec minimisation
Exemple :
Soit le problème : ⎧
⎪
⎪ min −x1 − 2x2
⎪
⎪
⎨ −3x1 + 2x2 ≤ 2
(PM) −x1 + 2x2 ≤ 4
⎪
⎪
⎪
⎪ x + x2 ≤ 5
⎩ 1
x1 , x2 ≥ 0
En rajoutant les variables d'écart on obtient la forme standard :
⎧
⎪
⎪ min −x1 − 2x2
⎪
⎪
⎨ 3x 1 + 2x2 + e 1 = 2
−
(PMS) −x1 + 2x2 + e2 = 4
⎪
⎪
⎪
⎪ x + x2 + e 3 = 5
⎩ 1
x 1 , x2 , e 1 , e 2 , e 3 ≥ 0
On remarque que tous les termes du second membre (2, 4 et 5) sont
positifs. Dans notre cas, l'obtention d'une solution de base réalisable
initiale est triviale. Elle correspond aux variables de base e1 , e2 , e3 et
variables hors base x1 , x2 .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 126 / 220
La sol tion de base réalisable initiale est
La méthode du simplexe Simplexe avec minimisation
Les contraintes de (PMS) peuvent être représentées par le système :
Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
⎛ ⎞ x1 ⎛ ⎞
−3 2 1 0 0 ⎜ x2 ⎟ 2
⎜ ⎟
à = ⎝ −1 2 0 1 0 ⎠ ; x̃ = ⎜
⎜ e1 ⎟ ; b̃ = b = ⎝ 4 ⎠
⎟
1 1 0 0 1 ⎝ e2 ⎠ 5
e3
z = c̃ T x̃ = −x1 − 2x2 + 0e1 + 0e2 + 0e3 avec c̃ = (x1 , x2 , 0 , 0 , 0)T
⎛ ⎞
1 0 0
Une base initiale est donnée par la matrice identité : I = ⎝ 0 1 0 ⎠
0 0 1
La solution de base réalisable initiale est :
(x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 2 , 4 , 5)
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 127 / 220
La méthode du simplexe Simplexe avec minimisation
Tableau 1
Base x1
↓
x2 e1 e2 e3 s.m R
← e1 -3 2 1 0 0 2 1
e2 -1 2 0 1 0 4 2
e3 1 1 0 0 1 5 5
−z -1 -2 0 0 0 0
x2 variable entrante dans la base.
e1 variable sortante de la base.
Tableau 2
Base
↓
x1 x2 e1 e2 e3 s.m R
x2 -3/2 1 1/2 0 0 1 −2/3
← e2 2 0 -1 1 0 2 1
e3 5/2 0 -1/2 0 1 4 8/5
−z -4 0 1 0 0 2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 128 / 220
La méthode du simplexe Simplexe avec minimisation
Tableau 3
Base x1 x2
↓
e1 e2 e3 s.m R
x2 0 1 -1/4 3/4 0 5/2 10
x1 1 0 -1/2 1/2 0 1 -2
← e3 0 0 3/4 -5/4 1 3/2 2
−z 0 0 -1 2 0 6
Tableau 4
Base x1 x2 e1 e2 e3 s.m
x2 0 1 0 1/3 1/3 3
x1 1 0 0 -1/3 2/3 2
e1 0 0 1 -5/3 4/3 2
−z 0 0 0 1/3 4/3 8
Tous les coe cients de la dernière ligne sont positifs ou nuls : le tableau 4
est optimal et x∗1 = 2 ; x∗2 = 3 ; e∗1 = 2 ; e∗2 = e∗3 = 0 ; z∗ = −8
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 129 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
5. Initialisation de la méthode du simplexe
Jusqu'ici nous avons vu comment trouver une solution de base réalisable
initiale lorsque le programme linéaire de départ est sous forme canonique :
⎧
⎨ max z = c T x
Ax ≤ b
⎩
x ≥0
alors en ajoutant une variable d'écart ei à chaque contrainte pour la
transformer en une égalité, la matrice à qui
correspond
à l'ensemble des
contraintes Ãx = b prend la forme : Ã = A Im
avec x̃ = (x1 , ..., xn , e1 , ..., em )T et Im est la matrice identité d'ordre m.
Le passage en forme standard permet d'avoir une base initiale
B0 = {ei , i = 1...m} facilement.
Si le second membre est positif alors cette base est réalisable et correspond
à l'origine : xN = (x1 , ..., xn ) = 0 et xB = (e1 , ..., em ).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 130 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
Mais dans le cas général on peut avoir les situations suivantes :
L'une des m contraintes possède un second membre bi négatif, alors il
y a violation de la contrainte de positivité pour la variable d'écart
concernée (ei = bi < 0).
Le problème contient déjà des contraintes d'égalité alors ces dernières
n'ont pas besoin de l'adjonction de variables d'écart et il n'existe pas
de sous-matrice identité dans la matrice Ã.
Il est alors nécessaire de mettre en place une procédure pour obtenir une
matrice identité comme matrice de base initiale et qui correspond à une
solution de base initiale réalisable. En général, une telle procédure est basée
sur l'adjonction de variables arti cielles.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 131 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
Méthode du grand M :
Considérons le PL suivant :
⎧
⎪
⎪ max z = x1 + x2
⎨
2x1 + x2 ≥ 4
(P1 )
⎪
⎪ x + 2x2 = 6
⎩ 1
x1 , x 2 ≥ 0
On remarque que les termes du second membre sont tous positifs, mais la
1ère contrainte est de type ≥ et la 2ème contrainte est de type =
On rajoute une variable d'écart e1 à la 1ère contrainte (pour avoir l'égalité).
On rajoute en plus deux variables arti cielles a1 et a2 aux 2 contraintes.
En plus, on transforme la fonction objectif en pondérant les variables
arti cielles avec un coe cient −M où M est un nombre supposé positif et
assez grand.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 132 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
On obtient alors le PL :
⎧
⎪
⎪ max z = x1 + x2 −Ma1 − Ma2
⎨
2 x 1 + x2 − e 1 + a 1 = 4
⎪ x 1 + 2x2 + a 2 = 6
⎪
⎩
x1 , x2 , e 1 , a 1 , a 2 ≥ 0
qui est sous forme standard.
On remarque que les contraintes du dernier problème peuvent s'écrire :
Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
x1
⎜ ⎟
à =
2 1 −1 1 0 ⎜
; x̃ = ⎜
x2 ⎟
⎟ ; b̃ = b = 4
1 2 0 0 1 ⎜
⎝
e1
a1
⎟
⎠ 6
a2
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 133 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
La solution de base initiale est donnée par :
Variables de base : a1 = 4 ; a2 = 6
Variables hors base : x1 = x2 = e1 = 0
Pour établir le premier tableau du simplexe, il faut maintenant exprimer les
variables de base en fonction des variables hors base.
2x1 + x2 − e1 + a1 = 4 ⇒ a1 = 4 − 2x1 − x2 + e1
x 1 + 2x 2 + a 2 = 6 a 2 = 6 − x 1 − 2x 2
La fonction objectif devient alors :
z = x1 + x2 −Ma1 − Ma2
= x1 + x2 − M(4 − 2x1 − x2 + e1 ) − M(6 − x1 − 2x2 )
z = (3M + 1)x1 + (3M + 1)x2 − Me1 − 10M
Notons aussi que : si x 1 = x2 = e 1 = 0 alors z = z̄ = −10M .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 134 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
Nous pouvons maintenant démarrer le simplexe avec le tableau suivant :
Tableau 1
Base ↓
x1 x2 e1 a1 a2s.m R
← a1 2 1 -1 1 0 4 2
a2 1 2 0 0 1 6 6
−z 3M+1 3M+1 -M 0 0 10 M
x1 et x2 candidates à entrer dans la base. En appliquant la règle de Bland,
x1 entrante. a1 sort de la base.
Tableau 2
Base x1 ↓
x2 e1 a1 a2 s.m R
x1 1 1/2 -1/2 1/2 0 2 4
← a2 0 3/2 1/2 -1/2 1 4 8/3
−z 0 (3M+1)/2 (M+1)/2 -(3M+1)/2 0 -2 + 4M
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 135 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
Tableau 3
Base x1 x2
↓
e1 a1 a2 s.m R
x1 1 0 -2/3 2/3 -1/3 2/3 -1
← x2 0 1 1/3 -1/3 2/3 8/3 8
−z 0 0 1/3 -M-1/3 -M-1/3 -10/3
Tableau 4
Base x1 x2 e1 a1 a2 s.m
x1 1 2 0 0 1 6
e1 0 3 1 -1 2 8
−z 0 -1 0 -M -M-1 -6
Le tableau 4 est optimal et x1∗ = 6 ; x2∗ = 0 ; e1∗ = 8 ; zmax = 6.
On remarque que chaque variable arti cielle (a1 et a2 ) a été mise hors base
de telle sorte que leurs valeurs sont nulles dans le tableau optimal.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 136 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
En général, la méthode du grand M ( big M ,méthode M) consiste à :
Introduire des variables arti cielles ai , (i = 1, ..., p) dans les
contraintes qui posent un problème pour la réalisabilité de la base
initiale.
m
Remplacer la fonction objectif par z = max c T x − M ai
i=1
où M est une constante positive assez grande.
En pratique, on n'est pas obligé de donner une valeur à M.
Chaque fois que M est comparé à un nombre, il sera toujours
considéré comme plus grand.
Si la méthode du simplexe se termine avec une solution (x ∗ , a∗ ) telle
que a∗ = (a1∗ , ..., ap∗ ) = 0, alors x ∗ est une solution optimale du
problème de départ.
Si la méthode du simplexe se termine avec une solution (x ∗ , a∗ ) telle
que a∗ = 0 (c-à-d qu'au moins une variable arti cielle est encore dans
la base dans le tableau optimal), alors le problème est non réalisable.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 137 / 220
La méthode du simplexe Initialisation de la méthode du simplexe
Chapitre 4 :
Résolution des programmes linéaires
La dualité
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 138 / 220
Dualité Exemple introductif
1. Exemple introductif
Une entreprise E1 fabrique les produits P1 et P2. Elle utilise les matières
premières M1, M2 et M3, à raison de :
2 tonnes de M1, 1 tonne de M2 et 3 tonnes de M3
par unité produite de P1,
1 tonne de M1, 3 tonnes de M2 et 4 tonnes de M3
par unité produite de P2.
Elle dispose de :
50 tonnes de M1, 25 tonnes de M2 et 60 tonnes de M3.
Le béné ce net est de 5000 UM par unité de P1 et de 2000 UM par unité
de P2.
Le problème que se pose l'entreprise est le suivant :
Quelle quantité de chacun des deux produits P1 et P2 l'entreprise doit-elle
fabriquer pour que le béné ce soit maximal ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 139 / 220
Dualité Exemple introductif
Produit P1 Produit P2 Disponibilité
Quantité de m.p M1 (tonnes) 2 1 50
Quantité de m.p M2 (tonnes) 1 3 25
Quantité de m.p M3 (tonnes) 3 4 60
Prix unitaire (UM) 5000 2000
Le problème de l'entreprise E1 se modélise par le programme linéaire :
⎧
⎪
⎪ max z = 5000x1 + 2000x2
⎪
⎪
⎪
⎨ 2x1 + x2 ≤ 50
⎪ Quantité de m.p M1
(P) x1 + 3x2 ≤ 25 Quantité de m.p M2
⎪
⎪ 3x1 + 4x2 ≤ 60
⎪
⎪ Quantité de m.p M3
⎪
⎪
⎩
x 1 ≥ 0 ; x2 ≥ 0
x1 : quantité de produits P1 fabriqués
x2 : quantité de produits P2 fabriqués
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 140 / 220
Dualité Exemple introductif
Supposons qu'une autre entreprise E2, en rupture de stock, désire racheter
les matières premières (M1, M2 et M3) de l'entreprise E1. Le problème
qu'elle va se poser et le suivant :
Quel doit être le prix unitaire minimum d'achat y1 , y2 et y3 de chaque
matière première, pour que :
la valeur totale des m.p consommées par chaque produit P1 et P2 soit
supérieure ou égale à leurs prix unitaires respectifs, c1 = 5000 UM et
c2 = 2000 UM (pour que cela reste intéressant pour l'entreprise E1),
le prix total d'achat des matières premières disponibles soit minimum ?
Ce deuxième problème peut se mettre sous la forme :
⎧
⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨
(D)
2y1 + y2 + 3y3 ≥ 5000 contrainte produit P1
⎪
⎪ y1 + 3y2 + 4y3 ≥ 2000 contrainte produit P2
⎪
⎩
y 1 ; y2 ; y 3 ≥ 0
yi : prix unitaire d'achat de la m.p Mi (i = 1, 2, 3)
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 141 / 220
Dualité Exemple introductif
Le problème (D) est appelé problème dual de (P).
Le problème (P) est appelé problème primal.
Remarque
Comparons les deux problèmes, primal (P) et dual (D) :
⎧
⎪
⎪ max z = 5000x1 + 2000x2
⎪
⎪
⎪
⎨ 2x 1 + x2 ≤ 50
(P) x1 + 3x 2 ≤ 25
⎪
⎪
⎪
⎪ 3x 1 + 4x 2 ≤ 60
⎪
⎩
x1 , x2 ≥0
⎧
⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨
2y1 + y2 + 3y 3 ≥ 5000
(D)
⎪
⎪ y1 + 3y 2 + 4y 3 ≥ 2000
⎪
⎩
y1 , y2 , y3 ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 142 / 220
Dualité Exemple introductif
Les coe cients de la fonction objectif w de (D) correspondent aux
coe cients du second membre de (P).
De même, Les coe cients de la fonction objectif z de (P) correspondent
aux coe cients du second membre de (D).
Si nous désignons par :
A, b et c respectivement la matrice des contraintes, le second membre et le
vecteur des coûts du problème (P),
A , b et c respectivement la matrice des contraintes, le second membre et
le vecteur des coûts du problème (D),
alors on a :
⎛ ⎞ ⎛ ⎞
2 1 50
5000
A = ⎝ 1 3 ⎠ ; b = ⎝ 25 ⎠ ; c =
2000
3 4 60
⎛ ⎞
50
2 1 3 5000
A = = AT ; b = = c ; c = ⎝ 25 ⎠ = b
1 3 4 2000
60
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 143 / 220
Dualité Exemple introductif
Le problème primal (P) et son dual (D) sont liés par les relations suivantes :
Le problème (P) contient 2 variables (x1 et x2 ) et 3 contraintes.
Le problème (D) contient 3 variables (y1 , y2 et y3 ) et 2 contraintes.
On en conclut que le nombre de variables de (P) est égal au nombre
de contraintes de (D) et réciproquement, le nombre de variables de
(D) est égal au nombre de contraintes de (P).
On peut véri er facilement que le dual de (D) est le problème (P).
Le problème (P) est un problème de maximisation. Tandis que (D) est
un problème de minimisation.
Le minimum wmin atteint par le problème (D) est égal au maximum
zmax du problème (P).
Cela signi e dans notre cas que le prix d'achat minimal des matières
premières par l'entreprise E2 est égal au pro t maximal que peut en
tirer l'entreprise E1 en vendant ces matières premières.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 144 / 220
Dualité Formulation générale du problème dual
2. Formulation générale du problème dual
Formulation algébrique :
Soit un programme linéaire sous forme canonique :
⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn ≤ b1
⎪
⎪
⎪
⎨ a x + a x + ... + a x ≤ b
21 1 22 2 2n n 2
(P)
.
⎪ .
⎪
⎪
⎪ .
⎪
⎪
⎪
⎪ a x + am2 x2 + ... + amn xn ≤ bm
⎪
⎩ m1 1
x 1 ≥ 0, . . . , x n ≥ 0
n variables x1 , x2 ,..., xn et m contraintes.
Coe cients du second membre : b1 , b2 ,..., bm .
Coe cients (coûts) de la fonction objectif : c1 , c2 ,..., cn
Matrice des contraintes A de type (m, n) (m lignes et n colonnes).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 145 / 220
Dualité Formulation générale du problème dual
Le problème dual de (P) est dé ni par :
⎧
⎪
⎪ min w = b1 y1 + b2 y2 + ... + bm ym
⎪
⎪
⎪
⎪ a11 y1 + a21 y2 + ... + am1 ym ≥ c1
⎪
⎪
⎪
⎨ a y + a y + ... + a y ≥ c
12 1 22 2 m2 m 2
(D)
.
⎪ .
⎪
⎪
⎪ .
⎪
⎪
⎪
⎪ a y + am2 y2 + ... + amn ym ≥ cn
⎪
⎩ 1n 1
y 1 ≥ 0, . . . , y m ≥ 0
m variables y1 , y2 ,..., ym et n contraintes.
Coe cients du second membre : c1 , c2 ,..., cn .
Coe cients (coûts) de la fonction objectif : b1 , b2 ,..., bm
Matrice des contraintes : A = AT de type (n, m) (n lignes et m colonnes).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 146 / 220
Dualité Formulation générale du problème dual
Formulation matricielle :
⎧ ⎧
⎨ max z = c T x ⎨ min w = b T y
(P) Ax ≤ b (D) AT y ≥ c
⎩ ⎩
x ≥0 y ≥0
Exemples :
⎧
⎪
⎪ max z = x1 + 3x 2
⎪
⎪
⎪
⎨ x1 + x2 ≤ 14
(P1 ) − 2x 1 + 3x2 ≤ 12
⎪
⎪
⎪
⎪ 2x 1 − x2 ≤ 12
⎪
⎩
x1 , x2 ≥0
⎧
⎪
⎪ min w = 14y1 + 12y2 + 12y3
⎪
⎨
y1 − 2y 2 + 2y 3 ≥ 1
(D1 )
⎪
⎪ y1 + 3y 2 − y3 ≥ 3
⎪
⎩
y1 , y2 , y3 ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 147 / 220
Dualité Formulation générale du problème dual
⎧ ⎧
⎪
⎪ min z = −2x1 + 9x 2 ⎪
⎪ min z = − 2x 1 + 9x 2
⎪
⎪ ⎪
⎪
⎪
⎨ 3x 1 + x2 ≥ 10 ⎪
⎨ 3x 1 + x2 ≥ 10
(P2 ) 4 x1 − 3x 2 ≤ 8 ⇐⇒ − 4x 1 + 3x 2 ≥ −8
⎪
⎪ ⎪
⎪
⎪
⎪ x1 − x2 ≤ 6 ⎪
⎪ −x1 + x2 ≥ −6
⎪
⎩ ⎪
⎩
x1 , x2 ≥0 x1 , x2 ≥0
Le dual de (P2 ) est :
⎧
⎪
⎪ max w = 10y1 − 8y 2 − 6y 3
⎨
3y1 − 4y 2 − y3 ≤ −2
(D2 )
⎪
⎪ y + 3y 2 + y3 ≤ 9
⎩ 1
y1 , y2 , y3 ≥0
Question : Dual de (D2) ?
⎧
⎪
⎪ min z = − 2u 1 + 9u 2
⎪
⎪
⎨ 3u1 + u2 ≥ 10
(D̄2 ) −4u1 + 3u2 ≥ −8 Le dual du dual de (P2 ) = (P2 ).
⎪
⎪
⎪
⎪ −u1 + u2 ≥ −6
⎩
u1 , u2 ≥0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 148 / 220
Dualité Correspondances entre le primal et le dual
3. Correspondances entre le primal et le dual
Problème Primal Problème Dual
maximisation minimisation
second membre des contraintes coe cient de la fonction objectif
coe cient de la fonction objectif second membre des contraintes
m contraintes m variables de décision
n variables de décision n contraintes
i ème contrainte de type ≤ i ème variable ≥ 0
j ème variable ≥ 0 j ème contrainte de type ≥
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 149 / 220
Dualité Théorème de dualité
4. Théorème de dualité
Avec les notations du paragraphe 2, on a les résultats suivants :
Théorème 1 (Dualité forte)
Le problème primal (P) admet une solution optimale x ∗ si et seulement si le
problème dual (D) admet une solution optimale y ∗ , et dans ce cas, on a :
c T x ∗ = b T y ∗ autrement dit z ∗ = w ∗ .
Théorème 2 (conditions de complémentarité)
Soient x une solution réalisable du problème primal (P) et y une solution
réalisable du problème dual (D). Alors x et y sont optimales ssi :
n
yi bi − aij xj = 0, i = 1, ..., m (1)
j=1
m
yi aij − cj xj = 0, j = 1, ..., n (2)
i=1
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 150 / 220
Dualité Théorème de dualité
Par exemple :
⎧
⎪
⎪ max z = 5000x1 + 2000x2 ⎧
⎪
⎪
⎪ ⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨ 2x1 + x2 ≤ 50 ⎪
⎨
2y1 + y2 + 3y3 ≥ 5000
(P) x1 + 3x2 ≤ 25 (D)
⎪
⎪ ⎪
⎪ y 1 + 3y2 + 4y3 ≥ 2000
⎪
⎪
⎪ 3x1 + 4x2 ≤ 60 ⎪
⎩
⎪
⎩ x ≥0; x ≥0 y 1 , y2 , y3 ≥ 0
1 2
Si x = (x1 , x2 ) réalisable pour P et y = (y1 , y2 , y3 ) réalisable pour D ,
alors x et y solutions optimales ssi :
y1 (50 − 2x1 − x2 ) = 0 ; y2 (25 − x1 − 3x2 ) = 0 ; y3 (60 − 3x1 − 4x2 ) = 0
(2y1 + y2 + 3y3 − 5000) x1 = 0 ; (y1 + 3y2 + 4y3 − 2000) x2 = 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 151 / 220
Dualité Théorème de dualité
Une interprétation économique du théorème 1 a été donnée dans le
paragraphe 2 sur l'exemple introductif.
Les problèmes primal et dual peuvent s'écrire :
⎧ n ⎧
⎪
⎪ ⎪ m
⎪
⎪ max z = c j xj ⎪
⎪ min w = b i yi
⎪
⎪ ⎪
⎪
⎪
⎨ j=1 ⎪
⎨ i=1
n m
(P) (D)
⎪
⎪ aij xj ≤ bi (i = 1, ..., m) ⎪
⎪ aij yi ≥ cj (j = 1, n)
⎪
⎪ ⎪
⎪
⎪
⎪ j= 1 ⎪
⎪ i=1
⎪
⎩ x ≥ 0 (j = 1, ..., n) ⎩
j yi ≥ 0 (i = 1, m)
Soient x ∗ une solution optimale de (P) et y ∗ une solution optimale de (D).
D'après le théorème 2, on a :
n
yi∗ bi − aij xj∗ = 0, i = 1, ..., m (3)
j=1
m
yi∗ aij − cj xj∗ = 0, j = 1, ..., n (4)
i=1
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 152 / 220
Dualité Théorème de dualité
Conséquences :
Si la i ème contrainte du problème primal (P) est non saturée alors
n
bi − aij xj∗ = 0
j=1
et la relation (3) entraîne que yi∗ = 0.
Si la j ème contrainte du problème dual (D) est non saturée alors
m
yi∗ aij − cj = 0
i=1
et la relation (4) entraîne que xj∗ = 0.
Si yi∗ > 0 alors (3) ⇒ la i ème contrainte de (P) est saturée.
Si xj∗ > 0 alors (4) ⇒ la j ème contrainte de (D) est saturée.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 153 / 220
Dualité Interprétation économique des variables duales
5. Interprétation économique des variables duales
Considérons le problème de production suivant :
Une entreprise fabrique 2 produits P1 et P2. Soient x1 et x2 leurs quantités
respectives.
Leurs marges respectives sont de 4 UM et 3 UM.
Pour produire une unité du produit P1 on utilise 2 unités de matière
première et 5 heures de travail, tandis que pour une unité de P2 on a
besoin de 1 unité de matière première et de 6 heures de travail.
Le stock est de 3 unités et le nombre d'heures de travail par jour est de 11h.
Ce problème peut être modéliser par le programme linéaire suivant :
⎧
⎪
⎪ max z = 4x1 + 3x2
⎪
⎨
(P)
2x 1 + x 2 ≤ 3 Quantité de m.p
⎪
⎪
⎪
5x1 + 6x2 ≤ 11 Nombre d'heures de travail/jour
⎩
x 1 ≥ 0 ; x2 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 154 / 220
Dualité Interprétation économique des variables duales
Le chef d'entreprise voudrait savoir ce que lui rapporterait le fait que son
atelier soit ouvert une heure de plus par jour. Autrement dit, il voudrait
connaître l'augmentation de sa marge béné ciaire si le deuxième coe cient
du second membre passait de 11 à 12. On obtient alors un deuxième P.L :
⎧
⎪
⎪ max z = 4x1 + 3x2
⎪
⎨
(P )
2x1 + x2 ≤ 3 (Quantité de m.p)
⎪
⎪
⎪
5 x 1 + 6 x 2 ≤ 12 (Nombre d'heures de travail/jour)
⎩
x 1 ≥ 0 ; x2 ≥ 0
La solution optimale de (P) est : A = (1, 1) et zmax = 7 UM.
La solution optimale de (P ) est : A = (6/7, 9/7) et zmax
= 51/7 UM.
L'augmentation de l'objectif est de : Δz = 51/7 − 7 = 2/7.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 155 / 220
Dualité Interprétation économique des variables duales
D'autre part, le dual de (P) s'écrit :
⎧
⎪
⎪ min w = 3y1 + 11y2
⎪
⎨
(D)
2y1 + 5y2 ≥ 4
⎪
⎪ y 1 + 6y2 ≥ 3
⎪
⎩
y1 ≥ 0 ; y 2 ≥ 0
Le problème dual (D) a pour solution optimale : (y1∗ , y2∗ ) = (9/7, 2/7).
Donc y2∗ représente l'augmentation de l'objectif si on augmente le nombre
d'heures de travail/jour de 1 unité. Si on avait augmenté la capacité de
stockage d'une unité (c-à-d de 3 à 4) sans augmenter le nombre d'heures,
on aurait pu constater une augmentation de l'objectif égale à 9/7.
En général on a le résultat suivant :
Si on augmente la i ème composante du second membre du problème
primal (bi ) d'une unité, alors la fonction objectif augmentera d'une
quantité égale à la i ème variable duale optimale (yi∗ ).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 156 / 220
Dualité Interprétation économique des variables duales
Remarques
Les valeurs des variables duales yi sont appelées coûts marginaux ou
valeurs marginales.
Si une contrainte d'indice i est non saturée, alors les relations de
complémentarité entraînent que yi∗ = 0, c-à-d le coût marginal
d'indice i est nul. Donc on n'a pas intérêt à augmenter la capacité si
on n'a pas utilisé toutes les ressources.
Si le coût marginal d'indice i est non nul c-à-d yi∗ = 0, alors la
contrainte d'indice i est saturée ; cela signi e que toutes les ressources
ont été utilisées, donc une augmentation de la capacité permettra
d'augmenter le béné ce.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 157 / 220
Passage du tableau optimal primal au tableau optimal dual et vice versa
Primal Dual
La valeur optimale de la fonction objectif z = La valeur optimale de la fonction objectif w
Colonne s.m des variables de base associées
Coûts marginaux des variables hors base Signe opposé
(Valeurs optimales des variables de base associées)
Colonne second membre Signe opposé Coûts marginaux
La variable d’écart tj hors base (tj = 0)
La variable de décision xj en base (xj > 0)
(Contrainte d’indice j saturée)
La variable d’écart tj en base (tj > 0)
La variable de décision xj hors base (xj = 0)
(Contrainte d’indice j non saturée)
La variable d’écart ei en base (ei > 0)
La variable de décision yi hors base (yi = 0)
(Contrainte d’indice i non saturée)
La variable d’écart ei hors base (ei = 0)
La variable de décision yi en base (yi > 0)
(Contrainte d’indice i saturée)
Ligne xj en base Signe opposé Colonne tj hors base
Ligne ei en base Signe opposé Colonne yi hors base
Colonne xj hors base Signe opposé Ligne tj en base
Colonne ei hors base Signe opposé Ligne yi en base
Dualité Exercice d'application
Exercice d'application :
Une entreprise fabrique les produits P1 et P2. Elle utilise les matières
premières M1, M2 et M3. Les quantités (en tonnes) de chaque matière
première par unité de produit fabriqué, les capacités disponibles (tonnes)
ainsi que les marges unitaires sont rapportées dans le tableau ci-dessous :
Produit P1 Produit P2 Disponibilité
Quantité de m.p M1 1 3 96
Quantité de m.p M2 1 1 40
Quantité de m.p M3 7 4 238
Prix unitaire (UM) 15 25
1 Formuler un P.L (P) aidant l'entreprise à maximiser son chire
d'aaires et résoudre (P) par l'algorithme du simplexe.
2 Donner le P.L dual (D) et ses valeurs optimales ( y1∗ , y2∗ , y3∗ , w ∗ ).
3 Si la fabrique pouvait augmenter la quantité de matière première M1
ou M2, dans laquelle serait-il conseillé d'investir en premier ?
4 Établir le tableau optimal dual.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 159 / 220
Dualité Exercice d'application
Exercice d'application - corrigé :
1)
Variables de décision :
x1 : quantité de produits P1 fabriqués
x2 : quantité de produits P2 fabriqués
Programme linéaire :
⎧
⎪
⎪ max z = 15x1 + 25x2
⎪
⎪
⎪
⎪
⎨ x1 + 3x2 ≤ 96 Contrainte quantité de m.p M1
(P) x1 + x2 ≤ 40 Contrainte quantité de m.p M2
⎪
⎪
⎪ 7x1 + 4x2 ≤ 238
⎪
⎪
Contrainte quantité de m.p M3
⎪
⎩
x1 ≥ 0 ; x2 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 160 / 220
Dualité Exercice d'application
Forme standard du problème primal :
⎧
⎪
⎪ max z = 15x1 + 25x2
⎪
⎪
⎨ x1 + 3x2 + e1 = 96
(P.S) x1 + x2 + e2 = 40
⎪
⎪
⎪ 7x + 4x2 + e3 = 238
⎪
⎩ 1
x 1 , x2 , x3 , e 1 , e 2 , e 3 ≥ 0
Tableau 1
↓
Base x1 x2 e1 e2 e3 s.m R
← e1 1 3 1 0 0 96 / = 32
96 3
e2 1 1 0 1 0 40 / = 40
40 1
e3 7 4 0 0 1 238 238/4 = 59, 5
−z 15 25 0 0 0 0
Variable entrante : x2 .
Variable sortante : e1 .
Pivot : 3
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 161 / 220
Dualité Exercice d'application
Tableau 2
↓
Base x1 x2 e1 e2 e3 s.m R
x2 /
1 3 1 / 1 3 0 0 32 96
← e2 2/3 0 −1/3 1 0 8 12
e3 /
17 3 0 −4/3 0 1 110 238 4/ = 19, 4
−z 20/3 0 −25/3 0 0 -800
Variable entrante : x1 ; Variable sortante : e2 ; Pivot : /
2 3
Tableau 3
Base x1 x2 e1 e2 e3 s.m
x2 0 1 /1 2 −1/2 0 28
x1 1 0 −1/2 3/2 0 12
e3 0 0 3/2 −17/2 1 42
−z 0 0 −5 −10 0 −880
Le tableau 3 est optimal car tous les coe cients de la dernière ligne −z
sont négatifs ou nuls.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 162 / 220
Dualité Exercice d'application
x1∗ = 12 ; x2∗ = 28 ; e1∗ = e2∗ = 0 ; e3∗ = 42 ; z ∗ = 880.
L'entreprise doit fabriquer 12 produits P1 et 28 produits P2 pour réaliser un
pro t maximal de 880 UM.
2) ⎧
⎪
⎪ min w = 96y1 + 40y2 + 238y3
⎪
⎨
y1 + y2 + 7y3 ≥ 15 contrainte produit P1
(D)
⎪
⎪ 3 y 1 + y 2 + 4y 3 ≥ 25 contrainte produit P2
⎪
⎩
y 1 ; y2 ; y3 ≥ 0
yi : prix unitaire d'achat de la m.p Mi (i = 1, 2, 3)
D'après la ligne −z du tableau 3, les coûts marginaux de e1 , e2 et e3 sont
respectivement : −5, −10 et 0. Donc
y1∗ = 5 ; y2∗ = 10 ; y3∗ = 0 et w ∗ = z ∗ = 880
(Voir passage du tableau optimal primal au tableau optimal dual).
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 163 / 220
Dualité Exercice d'application
3)
On a y1∗ = 5 et y2∗ = 10, donc une augmentation de la quantité de la m.p
M1 (resp. M2 ) d'une tonne va entraîner une amélioration du chire
d'aaires de 5 UM (resp. 10 UM). Ainsi l'entreprise a intérêt à investir
dans la quantité de la m.p M2 en premier.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 164 / 220
Dualité Exercice d'application
4) Il faut appliquer les règles de passage du tableau optimal primal au
tableau optimal dual.
La dernière ligne du tableau 3 donne :
w ∗ = 880 ; y1∗ = 5 ; y2∗ = 10 ; y3∗ = 0 ; t1∗ = 0 ; t2∗ = 0
(t1 et t2 sont les variables d'écart associées au problème dual) ;
Le s.m du tableau optimal dual est donné par la dernière ligne du tableau
optimal primal avec un signe opposé.
De même, la dernière ligne du tableau optimal dual est déduite du s.m du
tableau optimal primal avec un signe opposé.
On peut faire les correspondances suivantes :
x ←→ t
i i y ←→ e
i i
Si une variable est dans la base son correspondant est hors base :
e1 et e2 sont hors base dans le primal donc leurs correspondants y1 et y2
sont dans la base pour le dual.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 165 / 220
Dualité Exercice d'application
case (variable1, variable2) = - (case correspondant1, correspondant 2).
Exemples :
case (y1 ,y3 ) = - case (e1 ,e3 )= -3/2 case (y1 ,t1 ) = - case (e1 ,x1 ) = 1/2
Tableau optimal primal
Base x1 x2 e1 e2 e3 s.m
x2 0 1 1/2 −1/2 0 28
x1 1 0 −1/2 3/2 0 12
e3 0 0 3/2 −17/2 1 42
−z 0 0 −5 −10 0 −880
Tableau optimal dual
Base y1 y2 y3 t1 t2 s.m
y1 1 0 -3/2 1/2 -1/2 5
y2 0 1 17/2 -3/2 1/2 10
−w 0 0 -42 -12 -28 -880
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 166 / 220
Analyse de sensibilité
Chapitre 5 :
Résolution des programmes linéaires
Analyse de sensibilité
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 167 / 220
Analyse de sensibilité
Dans la pratique, on n'est jamais sûr des nombres qui dé nissent les
contraintes. Par exemple, le prix de gasoil serait-il à 7, 81DH dans un mois,
faut-il vraiment 3H30 pour faire un Casablanca-Tanger malgré les travaux
au niveau de la rocade de Rabat ? etc.
Loin de nous l'idée de traiter les nombres qui dé nissent les contraintes
comme le résultat d'aléas : il n'est pas question ici de présenter une théorie
de la programmation linéaire à coe cients aléatoires.
Néanmoins, on peut essayer d'envisager la variation de quelques nombres
qui dé nissent les contraintes ou l'expression de la fonction à maximiser
(fonction objectif) et essayer de relier ces variations à la variation de la
solution optimale : avec 30 centimes de plus au prix du gasoil, dans quelles
proportions vais-je baisser mon béné ce ! sous entendu : combien suis-je
prêt à payer ces 30 centimes supplémentaires ? En donnant 15mn de pause
supplémentaire tous les deux heures de route aux transporteurs, de
combien va varier ma marge ?
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 168 / 220
Analyse de sensibilité
Notons que nous avons déjà abordé de tels types de problèmes dans le
second chapitre consacré à la méthode graphique. Nous avons vu dans
quelle mesure le béné ce pouvait augmenter lorsqu'on faisait varier une
contrainte en remplissant de soja la cabine du capitaine du bateau.
Les techniques qui permettent d'analyser ces phénomènes forment ce que
l'on appelle l'analyse de sensibilité, sensibilité aux contraintes, sensibilité
aux paramètres qui dé nissent la fonction objectif. Nous verrons qu'elles
nous permettront de résoudre un autre type de problèmes de
programmation linéaire.
Pour illustrer notre propos, nous partirons d'un exemple simple.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 169 / 220
Analyse de sensibilité
Exemple :
Un euriste dispose d'un stock de roses, d'un stock d'÷illets et d'un stock
d'orchidées. Il peut confectionner avec ces eurs trois types de bouquets
qui ont un grand succès auprès de la clientèle : il sait qu'il pourra vendre
dans la journée toute quantité de bouquets qu'il aura préparée. Le tableau
suivant donne tous les renseignements utiles :
Type de bouquet stock
Type de eur bouquet N1 bouquet N2 bouquet N3 disponible
roses 2 3 2 90
÷illets 1 2 1 81
orchidées 4 3 1 120
Prix 8UM 5UM 6UM
Le problème du euriste est de savoir comment choisir les nombres de
bouquets de chaque type de manière à maximiser sa recette totale. Pour
résoudre ce problème, nous savons qu'il faut commencer par le mettre en
équations .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 170 / 220
Analyse de sensibilité
On notera alors :
x1 le nombre de bouquets N 1
x2 le nombre de bouquets N 2
x3 le nombre de bouquets N 3
Z la recette totale
Le problème du euriste s'écrit sous la forme suivante :
⎧
⎪
⎪ max z = 8x1 + 5x2 + 6x3
⎪
⎪
⎨ (e1 ) roses 2x1 + 3x2 + 2x3 ≤ 90
(e2 ) ÷illets x1 + 2x2 + x3 ≤ 81
⎪
⎪
⎪ (e3 )
⎪ orchidées 4 x1 + 3x2 + x 3 ≤ 120
⎩
x1 , x2 , x3 ≥ 0
Dans cette écriture, nous avons mis entre parenthèses les noms des
variables d'écart que nous allons utiliser dans la forme standard .
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 171 / 220
Analyse de sensibilité
Ce problème s'écrit, sous sa forme standard :
⎧
⎪
⎪ max z = 8x1 + 5x2 + 6x3
⎪
⎨ (e1 )roses
⎪ 2x1 + 3x2 + 2x3 + e1 = 90
(e2 )÷illets x 1 + 2x 2 + x 3 + e 2 = 81
⎪
⎪
⎪
⎪ (e )orchidées 4x1 + 3x2 + x3 + e3 = 120
⎩ 3
x1 , x2 , x3 , e1 , e2 , e3 ≥ 0
Ce qui nous conduit au premier tableau de la méthode simplexe :
Tableau 1
↓
Base x1 x2 x3 e1 e2 e3 s.m R
e1 2 3 2 1 0 0 90 45
e2 1 2 1 0 1 0 81 81
← e3 4 3 1 0 0 1 120 30
−Z 8 5 6 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 172 / 220
Analyse de sensibilité
Tableau 2
Base x1 x2 x3 e1 e2 e3 s.m R
e1 0 3/2 3/2 1 0 −1/2 30 20
e2 0 5/4 3/4 0 1 −1/4 51 68
x1 1 3/4 1/4 0 0 1/4 30 120
−Z 0 −1 4 0 0 −2 −240
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 −5 0 −8/3 0 −2/3 −320
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 173 / 220
Analyse de sensibilité
Ce dernier tableau donne la solution du problème du euriste :
Z = 320; x1 = 25; x2 = 0; x3 = 20; e1 = 0; e2 = 36; e3 = 0.
Ce qui signi e que le euriste devra composer :
25 bouquets N1 (x1 = 25)
0 bouquets N2 (x2 = 0)
20 bouquets N3 (x3 = 20)
Il utilisera toutes ses roses (e1 = 0)
Il lui restera 36 ÷illets . (e2 = 36)
Il utilisera toutes ses orchidées (e3 = 0)
Sa recette sera de 320 (Z = 320)
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 174 / 220
Analyse de sensibilité Variation des bornes des contraintes
1. Variation des bornes des contraintes
Supposons maintenant qu'un incident vous ait fait perdre la dernière
colonne du tableau : vous vous trouvez maintenant devant le tableau :
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 − 1/ 3 A
e2 0 1/2 0 −1/2 1 0 B
x1 1 1/2 0 −1/6 0 1/3 C
−Z 0 −5 0 −8/3 0 − 2/ 3 D
Vous devez recalculer les nombres A,B,C,D.
Pour répondre à ce problème, il faut se souvenir que le dernier tableau a
été obtenu à partir du premier en appliquant la méthode du pivot. Ces deux
tableaux représentent donc deux systèmes d'équations équivalents, c-à-d
que toute solution de l'un des systèmes est solution de l'autre.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 175 / 220
Analyse de sensibilité Variation des bornes des contraintes
Écrivons ces systèmes :
⎧
⎪
⎪ Z − 8x1 − 5x2 − 6x3 = 0
⎪
⎪
⎨ 2x1 + 3x2 + 2x3 + e1 = 90
(P) x 1 + 2x2 + x 3 + e 2 = 81
⎪
⎪
⎪
⎪ 4x + 3x2 + x3 + e3 = 120
⎩ 1
x1 ≥ 0 ; x 2 ≥ 0 ; x 3 ≥ 0
⇐⇒
⎧
⎪
⎪ Z + 5x2 + 8/3e1 + 2/3e3 = D
⎪
⎪
⎨ x2 + x3 + 2/3e1 − 1/3e3 = A
(P ) 1/2x2 − 1/2e1 + e2 = B
⎪
⎪
⎪
⎪ x − 1/2x2 − 1/6e1 + 1/3e3 = C
⎩ 1
x 1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
Toute solution de l'un est aussi solution de l'autre. Nous connaissons une
solution particulière du premier système "la solution de base" :
x1 = 0; x2 = 0; x3 = 0; e1 = 90; e2 = 81; e3 = 120.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 176 / 220
Analyse de sensibilité Variation des bornes des contraintes
Cette solution doit aussi être solution de second système : en remplaçant,
on trouve :
⎧ ⎧
⎪
⎪ 0 + 5 × 0 + 8/3 × 90 + 2/3 × 120 = D ⎪
⎪ D = 320
⎨ ⎨
0 + 0 + 2/3 × 90 − 1/3 × 120 = A A = 20
(P ) ⇔
⎪
⎪ 1 / 2 × 0 − 1/2 × 90 + 81 = B ⎪
⎪ B = 36
⎩ ⎩
0 − 1/2 × 0 − 1/6 × 90 + 1/3 × 120 = C C = 25
Ainsi, on peut retrouver une partie des valeurs numériques du tableau nal
en prenant en compte le fait que les tableaux initiaux et naux représentent
des systèmes d'équations équivalents.
Cette technique permet de retrouver une partie de ses calculs si une tache
inopportune est venue brouiller les résultats.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 177 / 220
Analyse de sensibilité Variation des bornes des contraintes
Supposons maintenant que le tableau initial soit légèrement modi é : ce ne
sont plus ⎧ ⎧
⎨ 90 roses ⎨ 84 roses
81 ÷illets Mais 72 ÷illets
⎩ ⎩
120 orchidées 120 orchidées
Le problème du euriste est modi é et devient :
⎧
⎪
⎪ max z = 8x1 + 5x2 + 6x3
⎪
⎪
⎨ (e1 )roses 2x1 + 3x2 + 2x3 + e1 = 84
(e2 )÷illets x 1 + 2x 2 + x 3 + e 2 = 72 avec
⎪
⎪
⎪
⎪ (e )orchidées 4 x 1 + 3x2 + x 3 + e 3 = 120
⎩ 3
x1 , x 2 , x 3 , e 1 , e 2 , e 3 ≥ 0
Tableau 1
Base x1 x2 x3 e1 e2 e3 s.m
e1 2 3 2 1 0 0 84
e2 1 2 1 0 1 0 72
e3 4 3 1 0 0 1 120
−Z 8 5 6 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 178 / 220
Analyse de sensibilité Variation des bornes des contraintes
Supposons que l'on applique à ce tableau exactement les mêmes calculs
que lors du traitement précédent : on va retrouver à peu près le même
tableau nal que précédemment : seule la dernière colonne sera diérente :
le dernier tableau de calculs sera donc de la forme :
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 − 1/ 3 A
e2 0 1/2 0 −1/2 1 0 B
x1 1 1/2 0 −1/6 0 1/3 C
−Z 0 −5 0 −8/3 0 − 2/ 3 D
où il ne nous reste plus qu'à calculer les nombres A,B,C,D. On procédera
exactement de la même façon, en disant qu'une solution particulière du
système représenté par ce tableau est :
x1 = 0; x2 = 0; x3 = 0; e1 = 84; e2 = 72; e3 = 120.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 179 / 220
Analyse de sensibilité Variation des bornes des contraintes
ce qui nous conduit à la solution :
⎧ ⎧
⎪
⎪ 0 + 5 × 0 + 8/3 × 84 + 2/3 × 120 = D ⎪
⎪ D = 304
⎨ ⎨
0 + 0 + 2/3 × 84 − 1/3 × 120 = A A = 16
(P ) ⇔
⎪
⎪ 1 / 2 × 0 − 1/2 × 84 + 72 = B ⎪
⎪ B = 30
⎩ ⎩
0 − 1/2 × 0 − 1/6 × 84 + 1/3 × 120 = C C = 26
Ce qui signi e que le euriste devra composer :
26 bouquets N1 (x1 = 26)
0 bouquets N2 (x2 = 0)
16 bouquets N3 (x3 = 16)
Il utilisera toutes ses roses (e1 = 0)
Il lui restera 30 ÷illets . (e2 = 30)
Il utilisera toutes ses orchidées (e3 = 0)
Sa recette sera de 304 (Z = 304)
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 180 / 220
Analyse de sensibilité Variation des bornes des contraintes
Supposons
⎧ maintenant que l'on parte d'un stock⎧
⎨ 162 roses ⎨ 90 roses
30 ÷illets plutôt que 81 ÷illets
⎩ ⎩
207 orchidées 120 orchidées
Le problème du euriste devient :
⎧
⎪
⎪ max z = 8x1 + 5x2 + 6x3
⎪
⎪
⎨ (e1 )roses 2x1 + 3x2 + 2x3 + e1 = 162
(e2 )÷illets x 1 + 2x 2 + x 3 + e 2 = 30 avec
⎪
⎪
⎪
⎪ (e )orchidées 4 x 1 + 3x2 + x 3 + e 3 = 207
⎩ 3
x1 , x2 , x3 , e1 , e2 , e3 ≥ 0
Tableau 1
Base x1 x2 x3 e1 e2 e3 s.m
e1 2 3 2 1 0 0 162
e2 1 2 1 0 1 0 30
e3 4 3 1 0 0 1 207
−Z 8 5 6 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 181 / 220
Analyse de sensibilité Variation des bornes des contraintes
En appliquant les mêmes raisonnements que précédemment, on obtiendra
⎧ ⎧
⎪
⎪ 0 + 5 × 0 + 8/3 × 162 + 2/3 × 207 = D ⎪
⎪ D = 570
⎨ ⎨
0 + 0 + 2/3 × 162 − 1/3 × 207 = A A = 39
(P ) ⇔
⎪
⎪ 1/2 × 0 − 1/2 × 162 + 30 = B ⎪
⎪ B = −51
⎩ ⎩
0 − 1/2 × 0 − 1/6 × 162 + 1/3 × 207 = C C = 42
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 39
e2 0 1/2 0 −1/2 1 0 -51
x1 1 1/2 0 −1/6 0 1/3 42
−Z 0 −5 0 −8/3 0 −2/3 570
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 182 / 220
Analyse de sensibilité Variation des bornes des contraintes
On trouve alors ce qu'il fallait éviter à tout prix : des valeurs négatives dans
la dernière colonne du tableau du simplexe. La solution correspondante
n'est pas à considérer car elle n'est pas réalisable.
Moralité
On peut, avec la technique précédente, mesurer ce qui se passe avec une
petite variation des contraintes et non pas de grandes variations. En
tout état de cause, il faudra toujours véri er si la colonne de droite du
tableau ne comprend que des nombres positifs pour conclure que la
technique de raccourci a bien fonctionné.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 183 / 220
Analyse de sensibilité Variation de l'objectif
2. Variation de l'objectif
Supposons maintenant qu'une tache d'encre nous ait fait perdre la dernière
ligne du tableau. On se retrouve devant le tableau suivant
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 − 1/ 3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z A B C D E F G
Nous savons déjà que la dernière ligne comportera des zéros dans les
colonnes associées aux variables de base x1 , x3 , et e2 , c-à-d :
A = C = E = 0.
Par contre, les nombres B,D,F,G associés aux variables hors base et au
second membre sont inconnus. Nous allons alors utiliser une astuce un peu
diérente que la précédente. On considère comme si on a oublié
d'appliquer le pivot sur la dernière ligne du tableau.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 184 / 220
Analyse de sensibilité Variation de l'objectif
Cependant, les systèmes d'équations représentés par le premier tableau et
le dernier sont équivalents.
Il ne reste plus qu'à transformer le dernier tableau pour faire apparaître,
dans la dernière ligne, un 0 dans la colonne de la variable x1 (premier pivot)
ainsi qu'un 0 dans la colonne de la variable x3 (deuxième pivot).
Complétons le tableau par la ligne que nous voulons obtenir :
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/ 3 25
−Z 8 5 6 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 185 / 220
Analyse de sensibilité Variation de l'objectif
Tableau 3'
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 1 6 4/3 0 −8/3 −200
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 −5 0 −8/3 0 −2/3 −320
Il apparaît ainsi, qu'il est relativement simple de reconstituer la dernière
ligne du tableau.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 186 / 220
Analyse de sensibilité Variation de l'objectif
Reprenons l'histoire de notre euriste et supposons que les prix des
bouquets varient légèrement, mais qu'il peut toujours en vendre n'importe
quelle quantité aux nouveaux prix :
⎧
⎨ le prix du bouquet de type 1 passe de 8 UM à 9
le prix du bouquet de type 2 passe de 5 UM à 6
⎩
le prix du bouquet de type 3 passe de 6 UM à 5
Le
⎧ problème de notre euriste devient :
⎪
⎪ max z = 9x1 + 6x2 + 5x3
⎪
⎨ (e1 ) roses
⎪ 2x1 + 3x2 + 2x3 ≤ 90
(e2 ) ÷illets x1 + 2x2 + x3 ≤ 81
⎪
⎪
⎪
⎪ (e ) orchidées 4x1 + 3x2 + x3 ≤ 120
⎩ 3
x1 , x2 , x3 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 187 / 220
Analyse de sensibilité Variation de l'objectif
Le premier tableau du simplexe devient :
Tableau 1
Base x3 e1 e2 e3 s.m
x1 x2
e1 2
3 2 1 0 0 90
e2 1
2 1 0 1 0 81
e34 3 1 0 0 1 120
−Z9 6 5 0 0 0 0
Si nous appliquons sans ré échir les mêmes opérations sur ce tableau que
celles que nous avons appliquées dans la première partie, nous allons
construire progressivement un tableau de la forme :
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/ 3 25
−Z 9 6 5 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 188 / 220
Analyse de sensibilité Variation de l'objectif
Tableau 3'
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 3/2 5 3/2 0 −3 −225
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 −7/2 0 −11/6 0 −4/3 −325
Il apparaît ainsi, qu'il est relativement simple de reconstituer la dernière
ligne du tableau.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 189 / 220
Analyse de sensibilité Variation de l'objectif
Ainsi, on peut résoudre pratiquement sans calculs le nouveau problème
du euriste : il devra composer :
25 bouquets N1 (x1 = 25)
0 bouquets N2 (x2 = 0)
20 bouquets N3 (x3 = 20)
Il utilisera toutes ses roses (e1 = 0)
Il lui restera 36 ÷illets . (e2 = 36)
Il utilisera toutes ses orchidées (e3 = 0)
Sa recette sera de 325 (Z = 325)
Comme dans la partie précédente, cette méthode n'est pas valable pour
tous les systèmes de prix de vente des bouquets : il est faux de penser que
quels que soient les prix des bouquets il est optimal de composer 25
bouquets N1, 20 bouquets N3 et aucun bouquets N2.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 190 / 220
Analyse de sensibilité Variation de l'objectif
par exemple,
⎧ si
⎨ le prix du bouquet de type 1 passe de 8 UM à 8
⎩
le prix du bouquet de type 2 passe de 5 UM à 7
le prix du bouquet de type 3 passe de 6 UM à 10
Le problème de notre euriste devient :
⎧
⎪
⎪ max z = 8x1 + 7x2 + 10x3
⎪
⎨ (e1 ) roses
⎪ 2x1 + 3x2 + 2x3 ≤ 90
(e2 ) ÷illets x1 + 2x2 + x3 ≤ 81
⎪
⎪
⎪
⎪ (e ) orchidées 4x1 + 3x2 + x3 ≤ 120
⎩ 3
x 1 , x2 , x3 ≥ 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 191 / 220
Analyse de sensibilité Variation de l'objectif
Le premier tableau du simplexe devient :
Tableau 1
Base x2 x3 e1 e2 e3 s.m
x1
e12 3 2 1 0 0 90
e21 2 1 0 1 0 81
e34 3 1 0 0 1 120
−Z8 7 10 0 0 0 0
Si nous appliquons sans ré échir les mêmes opérations sur ce tableau que
celles que nous avons appliquées dans la première partie, nous allons
construire progressivement un tableau de la forme :
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 11 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 8 7 10 0 0 0 0
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 192 / 220
Analyse de sensibilité Variation de l'objectif
Tableau 3'
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 3 10 4/3 0 −8/3 −200
Tableau 3
Base x1 x2 x3 e1 e2 e3 s.m
x3 0 1 1 2/3 0 −1/3 20
e2 0 1/2 0 −1/2 1 0 36
x1 1 1/2 0 −1/6 0 1/3 25
−Z 0 −7 0 −16/3 0 2/3 −325
Il apparaît que ce tableau n'est pas optimal. Il est clair que la procédure
de raccourci que nous avons adopté n'est pas e cace dans ce cas.
EL BOUANANI (Département SMAEG ) RO - L3 Économie et Gestion 2018/2019 193 / 220
Vous aimerez peut-être aussi
- Pr. BENMLIH Rech. Opérationnelle 2022-23Pas encore d'évaluationPr. BENMLIH Rech. Opérationnelle 2022-2343 pages
- Optimisation de Menu par Programmation LinéairePas encore d'évaluationOptimisation de Menu par Programmation Linéaire50 pages
- Cours de Recherche Opérationnelle Ed 2012Pas encore d'évaluationCours de Recherche Opérationnelle Ed 201260 pages
- Coût de production et planification des commandesPas encore d'évaluationCoût de production et planification des commandes3 pages
- Optimisation et Ordonnancement en Recherche OpérationnellePas encore d'évaluationOptimisation et Ordonnancement en Recherche Opérationnelle4 pages
- Gestion Approvisionnement et StocksPas encore d'évaluationGestion Approvisionnement et Stocks8 pages
- Recherche Op Chap 1 - S6 - Youb Manal PDFPas encore d'évaluationRecherche Op Chap 1 - S6 - Youb Manal PDF24 pages
- Définition de la dualité en optimisationPas encore d'évaluationDéfinition de la dualité en optimisation9 pages
- Exercices de Recherche OpérationnellePas encore d'évaluationExercices de Recherche Opérationnelle4 pages
- Coût de Production et Distribution des Marinières et Pantalons JEANSPas encore d'évaluationCoût de Production et Distribution des Marinières et Pantalons JEANS4 pages
- Introduction à Prélude 7 ERP pour PicasoPas encore d'évaluationIntroduction à Prélude 7 ERP pour Picaso48 pages
- Budget Approvisionnement Et Stock Exo CorrigéPas encore d'évaluationBudget Approvisionnement Et Stock Exo Corrigé3 pages
- Travaux Diriges Ro 24 - 25 Serie 2 Avec Solution 2024 - 2025Pas encore d'évaluationTravaux Diriges Ro 24 - 25 Serie 2 Avec Solution 2024 - 20255 pages
- Chapitre3 Méthodes D'ordonnancement Ou de Gestion Des Projets - PPT (Enregistrement Automatique)Pas encore d'évaluationChapitre3 Méthodes D'ordonnancement Ou de Gestion Des Projets - PPT (Enregistrement Automatique)30 pages
- Analyse de Sensibilité en Recherche OpérationnellePas encore d'évaluationAnalyse de Sensibilité en Recherche Opérationnelle13 pages
- Calcul des fours et machines nécessairesPas encore d'évaluationCalcul des fours et machines nécessaires20 pages
- Manuel de Recherche Opérationnelle 2021Pas encore d'évaluationManuel de Recherche Opérationnelle 202191 pages
- Programmation linéaire : Maximisation des profits100% (1)Programmation linéaire : Maximisation des profits2 pages
- Introduction à la Programmation LinéairePas encore d'évaluationIntroduction à la Programmation Linéaire46 pages
- Gestion efficace des stocks et approvisionnements100% (1)Gestion efficace des stocks et approvisionnements2 pages
- Chap3 - PL Résolution Graphique 2021 PDFPas encore d'évaluationChap3 - PL Résolution Graphique 2021 PDF41 pages
- Prévisions des ventes et saisonnalitéPas encore d'évaluationPrévisions des ventes et saisonnalité24 pages
- Phase I de l'algorithme du simplexePas encore d'évaluationPhase I de l'algorithme du simplexe18 pages
- Recherche Opérationnelle: Cours de Licence D Economie Et de GestionPas encore d'évaluationRecherche Opérationnelle: Cours de Licence D Economie Et de Gestion176 pages
- Techniques de Vente Négociation LP CIPas encore d'évaluationTechniques de Vente Négociation LP CI115 pages
- Définition et Méthodologie du MémoirePas encore d'évaluationDéfinition et Méthodologie du Mémoire33 pages
- Guide Methodes Langue Arabe FINAL Decembre2019Pas encore d'évaluationGuide Methodes Langue Arabe FINAL Decembre201938 pages
- Bulletin de paie fonctionnaire KinshasaPas encore d'évaluationBulletin de paie fonctionnaire Kinshasa1 page
- Rapport de Stage de Parasitologie L1 BiomedPas encore d'évaluationRapport de Stage de Parasitologie L1 Biomed21 pages
- Correction D'examen Fiscalité Session Ordinaire 2019-2020 Prof ElmadiPas encore d'évaluationCorrection D'examen Fiscalité Session Ordinaire 2019-2020 Prof Elmadi3 pages
- Liste Doublement Chaînée CirculairePas encore d'évaluationListe Doublement Chaînée Circulaire6 pages
- Rob Grice (Ascap) Conductor Score: B B B B BPas encore d'évaluationRob Grice (Ascap) Conductor Score: B B B B B6 pages
- ACFrOgAonHv0CTpjFaSyrL4i14LD8iuD - 3d-LXq4xNaW8-RYp4T9s - vKkmdi2yht3eKgeF6TJ1o5BNQDuKAnSLG7xE66FozEylMDYtnuGQQuTyE4FoxYKle-DyFNiDtVFr6zB7uXSAbQr4RJDd8 - CopiePas encore d'évaluationACFrOgAonHv0CTpjFaSyrL4i14LD8iuD - 3d-LXq4xNaW8-RYp4T9s - vKkmdi2yht3eKgeF6TJ1o5BNQDuKAnSLG7xE66FozEylMDYtnuGQQuTyE4FoxYKle-DyFNiDtVFr6zB7uXSAbQr4RJDd8 - Copie2 pages
- Cours de Marketing Canaux de Distribution Chapitre 9 PDFPas encore d'évaluationCours de Marketing Canaux de Distribution Chapitre 9 PDF5 pages
- Aircom Catalogue Compresseurs 19-11-2021Pas encore d'évaluationAircom Catalogue Compresseurs 19-11-202128 pages
- Homogénéisation des Matériaux SandwichPas encore d'évaluationHomogénéisation des Matériaux Sandwich8 pages
- Guide de Sélection Des Variétés Fruitières en ABPas encore d'évaluationGuide de Sélection Des Variétés Fruitières en AB16 pages
- Le Voyage Du Pelerin Musique - YouTubePas encore d'évaluationLe Voyage Du Pelerin Musique - YouTube1 page
- Examen BTS 2019 : Comptabilité AgropastoralePas encore d'évaluationExamen BTS 2019 : Comptabilité Agropastorale2 pages
