Recherche Opérationnelle: Cours de Licence D Economie Et de Gestion [PDF]
Recherche opérationnelle Cours de Licence d Economie et de Gestion Appliquées à l'Économie et à la Gestion FSJES Gueli
12 0 2MB
![Recherche Opérationnelle: Cours de Licence D Economie Et de Gestion [PDF]](https://vdoc.tips/img/200x200/div-class2qs3tf-truncatedtext-modulewrapperfg1km9p-classtruncatedtext-modulelineclamped85ulhh-style-max-lines5recherche-operationnelle-cours-de-licence-d-economie-et-de-gestion-p-div.jpg)
- Author / Uploaded
- Biig Med
Datei wird geladen, bitte warten...
Zitiervorschau
Recherche opérationnelle
Cours de Licence d Economie et de Gestion Appliquées à l'Économie et à la Gestion
FSJES Guelimim
2020/2021
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 1 / 192
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é
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 2 / 192
Programmes linéaires et modélisation
Chapitre 1 : Programmes linéaires et modélisation
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 3 / 192
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).
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 4 / 192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 5 / 192
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).
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 6 / 192
Programmes linéaires et modélisation
Introduction
Etapes d'un processus de RO Détecter et comprendre le problème I I
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 I I
Choix d'un algorithme (Simplexe par ex.) Utilisation des logiciels spécialisés (Excel, Lindo,...)
Validation du modèle et des résultats : I I
le modèle développé est-il conforme à la réalité ? les résultats sont-ils valides et satisfaisantes ?
Prise de décision
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 7 / 192
Programmes linéaires et modélisation
Introduction
Etapes d'un processus de RO
Problème réel
Modélisation
Problème mathématique
Algorithme Solution
Prise de décision
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 8 / 192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 9 / 192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 10 /
192
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
(châssis aluminium)
(châssis bois)
(heures/produit)
(heures/produit)
Atelier 1
1
0
4
Atelier 2
0
2
12
3
2
18
3 UM
5 UM
Atelier 3 Marge
Capacité disponible (heures/semaine)
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 ?
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 11 /
192
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
économique)
fonction
s'exprime comme suit : max
FSJES GUELIMIM
z = 3x1 + 5x2
RO - S5 Économie et Gestion
2020/2021 12 /
192
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
3 x1
+ 2x2 ≤ 18
D'autre part, les quantités produites ne peuvent être négatives. Mathématiquement :
x1 ≥ 0, x2 ≥ 0
Finalement, le problème peut être formulé en programme linéaire :
max z = 3x1 + 5x2 x1 ≤ 4 2x2 ≤ 12 (P1 ) 3x1 + 2x2 ≤ 18 x ≥0; x ≥0 1 2 FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 13 /
192
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 10
4 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 ?
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 14 /
192
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
FSJES GUELIMIM
z = 700x1 + 500x2
RO - S5 Économie et Gestion
2020/2021 15 /
192
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, 3x1
+ 0, 25x2 ≥ 125 104
Contrainte de gazole :
0, 4x1
+ 0, 25x2 ≥ 135 104
Contrainte de oul :
0, 3x1
+ 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 FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 16 /
192
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 a21 x1 + a22 x2 + ... + a2n xn
≤, =, ≥ ≤, =, ≥
b1 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 FSJES GUELIMIM
RO - S5 Économie et Gestion
(connues). 2020/2021 17 /
192
Programmes linéaires et modélisation
Formulation générale
Formulation matricielle Posons :
x = (x1 , x2 , ..., xn ) où
x1 , x2 , ..., xn
vecteur de
Rn
sont les variables de décision.
c = (c1 , c2 , ..., cn ) ∈ Rn et b a11 a12 · · · a21 a22 · · · A= . . .. . .. . . am1 am2 · · ·
= (b1 , b2 , ..., bm ) ∈ Rm a1n a2n (matrice de . . . amn
c T x =< c, x >= c1 x1 + ... + cn xn
type (m
(produit scalaire dans
× n))
Rn ).
Alors, le programme linéaire peut s'écrire sous la forme :
min / max z = c T x Ax ≤, =, ≥ b (PL) x ≥0 FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 18 /
192
Programmes linéaires et modélisation
Formulation générale
Terminologie Solution réalisable (solution admissible) :
x = (x1 , x2 , ..., xn ) contraintes c-à-d
est une solution réalisable si
Ax {≤, =, ≥} b
et
x
satisfait toutes les
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
Rn (voir chapitre 2). FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 19 /
192
de
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 : Quantités de poisson
FSJES GUELIMIM
Thon
Morue
Sardine
900Kg
800Kg
700Kg
RO - S5 Économie et Gestion
2020/2021 31 /
192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 32 /
192
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
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 33 /
192
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
FSJES GUELIMIM
⇒
la proposition 1.
RO - S5 Économie et Gestion
2020/2021 34 /
192
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 x1 ≥ 0, x2 ≥ 0
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 35 /
192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 36 /
192
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.
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 37 /
192
Programmes linéaires et modélisation
1
Formulation générale
la proportion de chambres n'étant équipée que d'une douche ne doit pas dépasser 25% : 1
3
1
3
1
4
4
4
4
4
x1 + x3 ≤ (x1 + x2 + x3 + x4 ) ⇔ x1 − x2 + x3 − x4 ≤ 0 2
seulement 50% des chambres pourraient contenir 3 couchages : 1
1
1
1
1
2
2
2
2
2
x3 + x4 ≤ (x1 + x2 + x3 + x4 ) ⇔ − x1 − x2 + x3 + x4 ≤ 0 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
4
+ 2x2 + 3x3 + 3x4 = 100 x1 , x2 , x3 , x4 ≥ 0
5
La fonction objectif :
Max Z = 250x1 + 300x2 + 400x3 + 450x4 FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 38 /
192
Programmes linéaires et modélisation
3
Formulation générale
1
3
1
4 1
4 1
4 1
x1 − x2 + x3 − x4 ≤
0
− x1 − x2 + x3 + x4 ≤
0
4 1 2
2x1
2
+
2 2x2 + 3x3
2 + 3x4
= x1 , x2 , x3 , x4 ≥
100 0
Max Z = 250x1 + 300x2 + 400x3 + 450x4
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 39 /
192
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 ?
FSJES GUELIMIM
RO - S5 Économie et Gestion
2020/2021 40 /
192
Résolution des programmes linéaires : Méthode graphique
Chapitre 2 : Résolution des programmes linéaires Méthode graphique
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 41 /
192
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). FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 42 /
192
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)
(heures/produit)
(heures/produit)
Atelier 1
1
0
4
Atelier 2
0
2
12
Atelier 3
3
2
18
3 UM
5 UM
Marge
disponible (heures/semaine)
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 ?
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 43 /
192
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 2x2 ≤ 12 (P1 ) 3 x1 + 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 satisfaisant les inégalités de
Graphiquement une inégalité telle que 3x1 demi-plan limité par la droite d'équation : FSJES Guelimim
(x1 , x2 )
(P1 ) . + 2x2 ≤ 18 correspond 3x1 + 2x2 = 18.
RO - S5 Économie et Gestion
2020/2021 44 /
à un
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Maximisation
Lorsque l'on fait l'intersection des cinq demi-plans correspondant aux cinq inégalités :
x1 2 x2 3x1 + 2x2 x 1 x2
≤ ≤ ≤ ≥ ≥
4 12 18 0 0
(1) (2) (3) (4) (5)
on obtient le polyèdre de la gure ci-dessous.
Représentation de l'objectif :
z = k. parallèles ∆k d'équation
On va considérer des valeurs successives de l'objectif : Ce qui correspond graphiquement à des droites 3x1
:
+ 5x2 = k
Les points d'une de ces droites sont donc le lieu de tous les points donnant la même valeur du pro t, d'où le nom de
d'isopro t)
droites d'isovaleur
(ou
droites
de la fonction objectif.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 45 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Maximisation
Représentation graphique de la région admissible
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 46 /
192
Résolution des programmes linéaires : Méthode graphique
On a 3x1
+ 5x2 = k ⇒ x2 = ∆k
Donc les droites
−3
La droite
d'isovaleur
points
et
La droite
∆15 ,
x1 +
k 5
.
ont la même pente (coe cient directeur)
Prenons par exemple les valeurs
∆0 (0, 0)
5
Méthode Graphique : Maximisation
k = 0 , k = 15
k = 0,
c-à-d : 3x1
et
p=−
3 5
k = 30 .
+ 5x2 = 0 ,
passe par les
(5, −3).
c-à-d : 3x1
+ 5x2 = 15 ,
passe par les points
(5, 0)
et
(0, 3). Tandis que La droite
(10, 0)
et
∆30 ,
c-à-d : 3x1
+ 5x2 = 30 ,
passe par les points
(0, 6).
On obtient donc des droites parallèles qui montent vers le haut si
k
augmente. Ainsi, on conclut que pour maximiser
z,
il faut prendre la droite d'isovaleur
la plus élevée. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 47 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Maximisation
Détermination du point optimal : On cherche le point de la région admissible qui maximise la fonction objectif
z = 3x1 + 5x2 .
Ce point sera déterminé graphiquement en tenant compte des deux conditions suivantes : Il sera situé sur la droite qui donne le pro t le plus grand, donc la droite d'isopro t la plus élevée. Il faut se restreindre à la région admissible.
Conclusion : Pour maximiser l'objectif, il faut prendre la droite d'isovaleur la plus élevée (qui donne la plus grande valeur à l'objectif ) et qui touche encore la région admissible. Le point de contact est un point optimal.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 48 /
192
Résolution des programmes linéaires : Méthode graphique
Le point optimal
D2 : x 2 = 6 x∗
et
Méthode Graphique : Maximisation
x ∗ = (x1∗ , x2∗ ) se trouve D3 : 3x1 + 2x2 = 18.
véri e donc :
à l'intersection des deux droites
x2 = 6 3x1 + 2x2 = 18
D'où
x ∗ = (2 , 6) et la valeur maximale de la fonction objectif est :
z ∗ = 3x1∗ + 5x2∗ = 36
Remarque : Pour un calcul exact de la solution optimale, il faut commencer tout d'abord par déterminer les droites (contraintes) qui se rencontrent au point optimal, et ensuite résoudre le système d'équations relatives à ces droites.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 49 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Maximisation
Représentation graphique de la solution optimale
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 50 /
192
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 FSJES Guelimim
par semaine).
RO - S5 Économie et Gestion
2020/2021 51 /
192
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 ?
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 52 /
192
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 + 3x2 ≥ 180
6x1 En plus,
x1
positivité : FSJES Guelimim
x2 , étant des nombres, x1 ≥ 0 et x2 ≥ 0.
et
véri ent la contrainte de
RO - S5 Économie et Gestion
2020/2021 53 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Fonction objectif : Pour minimiser le coût de production de la compagnie, on doit minimiser la fonction objectif :
z = 1000x1 + 1000x2
Le programme linéaire qui modélise ce problème s'écrit donc :
min z = 1000x1 + 1000x2 x1 + 2x2 ≥ 90 x1 + 4x2 ≥ 120 6x + 3x2 ≥ 180 1 x1 ≥ 0 ; x2 ≥ 0 2.2 Résolution graphique La région admissible est un polyèdre non borné qui a pour sommets les points (voir gure ci-dessous) :
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 54 /
192
Résolution des programmes linéaires : Méthode graphique
A (0 ;
1
Méthode Graphique : Minimisation
60) : intersection de la droite
D3
d'équation 6x1
+ 3x2 = 180
x2 ; B (10 ; 40) : intersection des deux droites D3 et (D1 : x1 + 2x2 = 90) ; C (60 ; 15) : intersection des deux droites D1 et (D2 : x1 + 4x2 = 120) ; D (120 ; 0) : intersection de la droite D2 avec l'axe x1 .
avec l'axe 2 3 4
La fonction objectif étant la même pente égale à
z = 1000x1 + 1000x2 ,
−1.
les droites d'isovaleur ont
On remarque sur la gure que celle qui réalise
le coût minimal est la droite passant par le sommet l'intersection des droites
D1 et D3 , ses coordonnées x1 + 2x2 = 90 6x1 + 3x2 = 180
B.
Ce dernier étant
véri ent le système :
D'où
x ∗ = (10 ;
40)
et la valeur minimale de la fonction objectif est :
z ∗ = 1000x1∗ + 1000x2∗ = 50000 FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 55 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Graphique exemple 2
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 56 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
2.3 Interprétation économique On a
x ∗ = (10 ;
40) et
z ∗ = 50000,
donc il faut 10 jours de travail dans la
mine A et 40 jours de travail dans la mine B à la compagnie pour un coût de production minimal de 50000 UM. A l'optimum, la première contrainte et la troisième contrainte sont saturées mais la deuxième contrainte ne l'est pas :
∗ x1 + 2x2∗ = 10 + (2 × 40) = 90 x ∗ + 4x2∗ = 10 + (4 × 40) = 170 > 120 1∗ ∗ 6x1 + 3x2 = (6 × 10) + (3 × 40) = 180 Pour minimiser le coût de production, la compagnie devra utiliser toutes les quantités de charbon de qualités supérieure et inférieure, et il lui restera un stock de charbon de qualité moyenne égal à 170
FSJES Guelimim
RO - S5 Économie et Gestion
− 120 = 50
tonnes.
2020/2021 57 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
3. Cas particuliers 3.1 Région admissible bornée - une in nité de solutions optimales : Dans l'exemple 1, la solution optimale est unique et correspond à un sommet (optimal) de la région admissible (bornée). En général, il existe des cas où tout un côté (segment) de la région admissible est optimal. En eet, supposons que l'on aie, sous les mêmes contraintes, un objectif de la forme : max z
0
= 3x1 + 2x2
Il est facile, dans ce cas, de voir que les droites d'isovaleur de l'objectif seraient toutes parallèles à la droite 3x1
D3
d'équation :
+ 2x2 = 18
On en déduit (voir gure ci-dessous) que tout le segment joignant le sommet comme
(2, 6) au sommet (4, 3) est optimal. Dans ce cas, on pourra choisir solution optimale celle qui correspond au sommet (2, 6) ou (4, 3).
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 58 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Région admissible bornée - in nité de solutions
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 59 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
3.2 Région admissible non bornée - in nité de solutions : Dans l'exemple 2, la région admissible est un polyèdre non bornée et la solution optimale est unique et atteinte en un sommet du polyèdre. Supposons maintenant que l'on aie à minimiser la fonction objectif
z 0 = 2x1 + 4x2
avec les mêmes contraintes.
Nous aurons alors le nouveau PL :
0 min z = 2x1 + 4x2 x1 + 2x2 ≥ 90 x1 + 4x2 ≥ 120 6x1 + 3x2 ≥ 180 x1 ≥ 0 ; x2 ≥ 0 Les droites d'isovaleur seront toutes parallèles à la droite
x1 + 2x2 = 90.
par le segment joignant les points
FSJES Guelimim
D1
d'équation
Par suite, nous aurons une in nité de solutions représentées
B (10 ;
40) et
RO - S5 Économie et Gestion
C (60 ;
15).
2020/2021 60 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Problème non borné - in nité de solutions
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 61 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
3.3 Région admissible non bornée - solution optimale in nie : Considérons le programme linéaire suivant :
z = x1 + x2 + 3x2 ≥ 6 2x + x2 ≥ 4 1 x1 ≥ 0 ; x2 ≥ 0 En donnant à
x1
et
x2
max 2x1
des valeurs assez grandes les contraintes seront
toujours véri ées. La valeur de la fonction objectif indé niment. Par conséquent,
z
peut être augmentée
z = +∞.
Graphiquement, on remarque sur la gure ci-dessous que la région admissible n'est pas bornée et que les droites d'isovaleur peuvent être déplacées à l'in nie en conservant toujours une intersection avec la région admissible : le programme linéaire possède une solution optimale in nie (aucune solution optimale nie) .
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 62 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Région admissible non bornée - solution in nie
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 63 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
3.4 Région admissible vide - aucune solution : Considérons maintenant le programme linéaire :
z = 2x1 + 3x2 x1 + x2 ≤ 1 x − x2 ≥ 2 1 x1 ≥ 0 ; x2 ≥ 0 max
Sur la gure ci-dessous, nous remarquons que la région admissible est vide et par suite le programme linéaire n'admet aucune solution optimale. Algébriquement, d'après le système des contraintes, on a :
x1 + x2 ≤ 1 x1 − x2 ≥ 2 x1 ≥ 0 ; x2 ≥ 0
x1 + x2 ≤ 1 −x1 + x2 ≤ −2 =⇒ ⇐⇒ x1 ≥ 0 ; x2 ≥ 0
ce qui contredit la contrainte
x2 ≥ 0.
2x2
≤ −1
Et par conséquent, l'ensemble des
solutions réalisables est vide. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 64 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
Région admissible vide (pas de solution)
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 65 /
192
Résolution des programmes linéaires : Méthode graphique
Méthode Graphique : Minimisation
En résumé : L'ensemble réalisable (ou région admissible) d'un programme linéaire est toujours un polyèdre de vide
−→
Rn
(intersection de demi-espaces) qui peut être :
pas de solution
non vide et bornée I I
solution optimale unique −→ sommet optimal unique du polyèdre in nité de solutions optimales −→ côté optimal du polyèdre, tous les points de ce côté sont des solutions optimales
non vide et non bornée I
solution optimale unique −→ sommet optimal unique
I
in nité de solutions optimales −→ côté optimal du polyèdre
I
aucune solution optimale nie (z = ∞)
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 66 /
192
Résolution des programmes linéaires : Méthode graphique
Astuce
Chapitre 3 : Résolution des programmes linéaires La méthode du simplexe
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 79 /
192
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 : I I
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 et itérative pour résoudre des problèmes linéaires de grande taille : I
I
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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 80 /
192
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 a 11 x1 + a12 x2 + ... + a1n xn {≤, =, ≥} b1 a21 x1 + a22 x2 + ... + a2n xn {≤, =, ≥} b2 .
. . a x + am2 x2 + ... + amn xn {≤, =, ≥} bm m1 1 x1 ≥ 0, . . . , xn ≥ 0 n X max / min z = cj xj j=1 n X aij xj {≤, =, ≥} bi i = 1, m j=1 xj ≥ 0 j = 1, n FSJES Guelimim
RO - S5 Économie et Gestion
⇐⇒
2020/2021 81 /
192
La méthode du simplexe
Notions générales
En utilisant la formulation matricielle :
z = cT x Ax {≤, =, ≥} b x ≥0
c = (c1 , c2 , ..., cn ) ∈ Rn , a11 a12 a21 a22 A= . . . .. . am1 am2 T et c x
=
n X
cj xj
max / min
b = (b1 , b2 , ..., bm ) ∈ Rm · · · a1n · · · a2n matrice . .. . . . · · · amn
de type (m ,
n)
.
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é). FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 82 /
192
La méthode du simplexe
2.2
Notions générales
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
max
n X
z=
n X
cj xj
j=1
aij xj ≤ bi
i = 1, m
j=1
xj ≥ 0
j = 1, n
Forme matricielle
z = cT x Ax ≤ b x ≥0
FSJES Guelimim
max
RO - S5 Économie et Gestion
2020/2021 83 /
192
La méthode du simplexe
Notions générales
Exemple :
(P1 )
max 6x1 + 7x2 + 8x3 x1 + 2x2 + x3 ≤ 100 3x1 + 4x2 + 2x3 ≤ 120 2x1 + 6x2 + 4x3 ≤ 200 x1 + x3 ≤ 150 x1 , x2 , x3 ≥ 0
z = cT x Ax ≤ b ⇐⇒ x ≥0
max
avec
A= A
1
2
1
3
4
2
2
6
4
1
0
1
de type
m=4
; b=
100 120 200
; c =
150
6
7
8
;
x1 x = x2 x3
(4 , 3),
(contraintes) et
FSJES Guelimim
n=3
(variables de décision).
RO - S5 Économie et Gestion
2020/2021 84 /
192
La méthode du simplexe
2.3
Notions générales
Forme standard d'un PL maximisation de la fonction objectif toutes les contraintes sont de type égalités
(=)
toutes les variables sont positives
max
n X
z=
n X
cj xj
j=1
aij xj = bi
i = 1, m
j=1
xj ≥ 0
j = 1, n
Forme matricielle
z = cT x Ax = b x ≥0
FSJES Guelimim
max
RO - S5 Économie et Gestion
2020/2021 85 /
192
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
3
4
5
6
ax ≥ b ⇐⇒ −ax ≤ −b ax ≤ b ax = b ⇐⇒ ax ≥ b ax + y = b ax ≤ b ⇐⇒ y ≥0 ax − y = b ax ≥ b ⇐⇒ y ≥0
est dite variable d'écart
x ≤ 0 ⇐⇒ −x ≥ 0
7
y
x
quelconque
FSJES Guelimim
⇐⇒
x = x+ − x− x+ ≥ 0 , x− ≥ 0 RO - S5 Économie et Gestion
avec
x + = max(x , 0) x − = max(−x , 0) 2020/2021 86 /
192
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
FSJES Guelimim
RO - S5 Économie et Gestion
bi ≥ 0.
2020/2021 87 /
192
La méthode du simplexe
Notions générales
Exemple :
Soit le problème :
min 5x1 − 3x2 x1 − x2 ≥ 2 2x1 + 3x2 ≤ 4 (P2 ) −x1 + 6x2 = 10 x1 , x2 ≥ 0
En introduisant les variables d'écart
x3 ≥ 0
et
x4 ≥ 0
dans la première et la
(P2 ) sous la forme équivalente max −5x1 + 3x2 x1 − x2 − x3 = 2 2x1 + 3x2 + x4 = 4 (P20 ) −x1 + 6x2 = 10 x1 , x2 , x3 , x4 ≥ 0
deuxième contrainte, on met
(P20 )
est la forme standard de
FSJES Guelimim
:
(P2 ).
RO - S5 Économie et Gestion
2020/2021 88 /
192
La méthode du simplexe
Bases, variables de base et solution de base
3. Bases, variables de base et solution de base Soit
A
Ax = b
un système d'équations linéaires avec :
matrice de type
(m , n), m ≤ n
Le système est donc inférieur au nombre
et
sous-déterminé n
rang (A) = m.
c-à-d le nombre
d'inconnues notées
En plus, il existe au moins une sous-matrice de de type
(m , m)
(d'ordre
m
d'équations est
x1 , . . . , xn . A
notée
B
B
inversible de type
carrée inversible
m).
Dé nitions On appelle base toute sous-matrice carrée
(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 FSJES Guelimim
RO - S5 Économie et Gestion
B ). 2020/2021 89 /
192
La méthode du simplexe
Bases, variables de base et solution de base
Exemple : Soit le système linéaire :
x2 + 2x3 + 2x4 = 1 x1 + x2 + 2x3 + 3x4 = 1
Ce système peut s'écrire
A=
A
0
1
2
2
1
1
2
3
est de type
(2 , 4 )
,
Ainsi
B
, avec : x1 x2 x = et b = x3 x4
1
1
(2 équations et 4 variables).
La sous-matrice
Ax =b
B=
1
2
1
3
est inversible et
rang (A) = 2.
est une base.
Les variables de base associés à
B
Les variables hors base associés à FSJES Guelimim
x2 et x4 . B sont x1 et x3 . sont
RO - S5 Économie et Gestion
2020/2021 90 /
192
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
1
1
1
2
1
2
est aussi une base et correspond alors aux variables de base
x1
et
x2 .
n'est pas une base (car non inversible).
Avec les conditions précédentes, le système
Ax = b
admet une
in nité de solutions.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 91 /
192
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 x1 + x2 + 2x3 + 3x4 = 1
admet une in nité de solutions.
On a :
B=
A=
1
2
1
3
0
1
2
2
1
1
2
3
,
est une base et
x1 x2 et b = x = x3 x4 3 −2 − 1 B = −1 1
Ax = b ⇐⇒ B −1 A x = B −1 b 3 −2 0 1 2 − 1 B A= −1 1 1 1 2 3 −2 1 B −1 b = = −1 1 0 FSJES Guelimim
2 3
=
RO - S5 Économie et Gestion
1
1
−2
1
2
0
1
0
0
1
2020/2021 92 /
192
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 = x3 1 0 0 1 x4 x2 = 1 + 2x1 − 2x3 ⇐⇒ x4 = −x1
1
⇐⇒
0
−2x1 + x2 + 2x3 = 1 x1 + x4 = 0
Le système précédent est équivalent au système de départ exprimé dans la base
En xant des valeurs arbitraires pour correspondantes pour En particulier, pour
Ax = b
mais
B x2
et
x1 = 0
x1
et
x3 ,
on obtient les solutions
x4 . 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
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 93 /
192
B.
La méthode du simplexe
Bases, variables de base et solution de base
Généralisation :
Ax = b un système d'équations linéaires tel que A matrice (m , n), m ≤ n et rang (A) = m. Soit B une base de A.
Soit
Après permutation des colonnes de
A
de type
B
de manière à ce que celles de
soient en premier, on obtient :
P
A=
B N
et
P
x=
xB xN
où
N est la sous-matrice de A correspondant aux variables xB vecteur de Rm formé par les variables de base, xN vecteur de Rn−m formé par les variables hors base.
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 correspondantes de FSJES Guelimim
xN
(paramètres) et on calcule les valeurs
xB . RO - S5 Économie et Gestion
2020/2021 94 /
192
La méthode du simplexe
Bases, variables de base et solution de base
Dé nitions On appelle solution de base (associée à la base particulière obtenue en prenant
xB
B ),
la solution
xN = 0.
est déterminée de façon unique par :
BxB = b ⇐⇒ xB = B −1 b xB ≥ 0 (toutes B −1 b ≥ 0.
Une solution de base est dite réalisable si de base sont positives), autrement dit :
les variables
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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 95 /
192
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 2x2 ≤ 12 (P) 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).
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 96 /
192
La méthode du simplexe
Méthode du simplexe en tableaux
(P) s'écrit max z = 3x1 + 5x2 + 0e1 + 0e2 + 0e3 x1 + e1 + 0e2 + 0e3 = 4 2x2 + 0e1 + e2 + 0e3 = 12 (PS) 3x1 + 2x2 + 0e1 + 0e2 + e3 = 18 x1 ≥ 0 ; x2 ≥ 0 ; e1 ≥ 0 ; e2 ≥ 0 ; e3 ≥ 0 La forme standard du programme linéaire
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˜ A˜ x˜ ≥ 0 x1 x2 1 0 1 0 0 4 ˜ 12 A˜ = 0 2 0 1 0 ; x˜ = e1 ; b = 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
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 97 /
192
La méthode du simplexe
Méthode du simplexe en tableaux
Choix de la solution de base réalisable initiale :
Une base initiale est donnée par la matrice :
Elle correspond aux variables de base et variables hors base
1
0
0
I =
0
1
0
0
0
1
e1 , e2 , e3
x1 , 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.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 98 /
192
La méthode du simplexe
Méthode du simplexe en tableaux
Tableau initial : Le premier tableau du simplexe (tableau initial) s'écrit :
Variables de base : Solution de base :
Base
x1
x2
e1
e2
e3
s.m
e1 e2 e3 −z
1
0
1
0
0
4
0
2
0
1
0
12
3
2
0
0
1
18
3
5
0
0
0
0
e1 , e2 , e3 Variables hors base : x1 , x2 (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 béné ciaire initiale
−z
donc la marge
z = 0.
La solution n'est pas optimale. On recherche donc une solution de base meilleure : d'où une autre itération. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 99 /
192
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). FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 100 /
192
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 Une première idée est de pousser
x2
x2 ?
le plus loin possible tant que les
variables de base restent positives. Supposons qu'on augmente
x2
en maintenant
e1 = 4 2x2 + e2 = 12 2x + e3 = 18 2 x2 ≥ 0 ; e1 ≥ 0 ; e2 ≥ 0 ; e3 ≥ 0
x1
hors base (
Ainsi, la valeur limite que
x2
peut prendre est
FSJES Guelimim
= 0)
:
alors :
e2 = 12 − 2x2 ≥ 0 e3 = 18 − 2x2 ≥ 0 ⇐⇒ x2 ≥ 0
x2 ≤ 12/2 = 6 x2 ≤ 18/2 = 9 =⇒ 0 ≤ x2 ≤ min{12/2 , ⇐⇒ x2 ≥ 0 contrainte sera alors saturée (e2
x1 = 0),
e2
x2 = 6.
18/2}
= 12/2 = 6
La deuxième
variable sortante de la base.
RO - S5 Économie et Gestion
2020/2021 101 /
192
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 ↓
s.m
Base
x1
x2
e1
e2
e3
e1 ← e2 e3 −z
1
0
1
0
0
4
0
2
0
1
0
12
3
2
0
0
1
18
3
5
0
0
0
0
x2
variable entrante dans la base.
e2
variable sortante de la base.
R
=∞ =6 18/2 = 9
4 /0
12/2
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). FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 102 /
192
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 :
Nv = Av − (
Cpivot × Lpivot) Pivot
Nv : nouvelle valeur Av : ancienne valeur Cpivot : colonne du pivot Lpivot : Ligne du pivot
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 103 /
192
La méthode du simplexe
Méthode du simplexe en tableaux
Tableau 1 ↓
Base
x1
x2
e1
e2
e3
s.m
e1 ← e2 e3 −z
1
0
1
0
0
4
0
2
0
1
0
12
3
2
0
0
1
18
3
5
0
0
0
0
R
=∞ 12/2 = 6 18/2 = 9
4 /0
Tableau 2 ↓
Base
x1
x2
e1
e2
e3
s.m
R
e1 x2 ← e3 −z
1
0
1
0
0
4
4
0
1
0
1/2
0
6
∞
3
0
0
6
2
0
0
−1 −5/2
1
3
0
−30
Variable entrante dans la base :
x1
Variable sortante de la base :
e3
Pivot : 3 FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 104 /
192
La méthode du simplexe
Méthode du simplexe en tableaux
Tableau 2 ↓
Base
x1
x2
e1
e2
e3
s.m
R
e1 x2 ← e3 −z
1
0
1
0
0
4
4
0
1
0
1/2
0
6
∞
3
0
0
1
6
2
3
0
0
−1 −5/2
0
−30
Tableau 3
FSJES Guelimim
Base
x1
x2
e1
e2
e1 x2 x1 −z
0
0
1
1/3
0
1
0
1
0
0
0
0
0
1/2 −1/3 −3/2
RO - S5 Économie et Gestion
e3 −1/3
s.m 2
0
6
1/3
2
−1
−36 2020/2021 105 /
192
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
∗ variables hors base sont e2
=
e∗ 3
=0
x1∗ = 2 ; x2∗ = 6
et
e1∗ = 2
et les
.
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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 106 /
192
La méthode du simplexe
Cas général
4.2 Cas général : Considérons un programme linéaire sous forme standard :
z = cT x Ax = b (PS) x ≥0
où est une
A
matrice de type
Supposons connue une base
max
(m , n), m ≤ n
B
et
rang (A) = m.
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 N
: la sous-matrice de
A
: l'ensemble des indices hors base,
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 ∈ FSJES Guelimim
RO - S5 Économie et Gestion
N ).
2020/2021 107 /
192
La méthode du simplexe
Cas général
Rappelons que la solution de base associée à
xB = B −1 b ≥ 0.
B
est réalisable si :
En eectuant un partitionnement suivant les indices de
B
et ceux de
N,
peut écrire :
⇐⇒ ⇐⇒
xB + B −1 N xN = B −1 b
⇐⇒
xB = B −1 b − B −1 N xN
⇐⇒
Ax = b
xB B N xN B xB + N xN = b
=b
La fonction objectif peut s'écrire :
z = cT x =
X i∈B
avec
cB = (ci , ..., cim )
FSJES Guelimim
1
et
ci xi +
X
ci xi = cB xB + cN xN
i∈N
cN = (cj , ..., cjn−m ) 1
RO - S5 Économie et Gestion
2020/2021 108 /
192
on
La méthode du simplexe
Cas général
Donc le PL est équivalent à la forme réduite associée à la base
(PR)
B
:
z = cB xB + cN xN xB + B −1 N xN = B −1 b xB ≥ 0 , xN ≥ 0 max
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 z
= B −1 b ⇐⇒ xB = B −1 b − B −1 N xN =⇒ = cB xB + cN xN = cB (B −1 b − B −1 N xN ) + cN xN = (cN − cB B −1 N)xN + cB B −1 b
z avec
= dN xN + z¯
dN = cN − cB B −1 N
les composantes de
dN
;
⇐⇒ dN xN = z − z¯
z¯ = cB B −1 b
s'appellent coûts réduits des variables hors base.
Ils interviennent de façon déterminante dans la méthode du simplexe. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 109 /
192
La méthode du simplexe
Cas général
Ainsi, le problème consiste à maximiser z sachant :
et
xB + B −1 N xN
= B −1 b
dN x N
= z − z¯
xB ≥ 0 , xN ≥ 0.
La solution de base est donnée par : Cette solution de base est réalisable La valeur de la fonction objectif
z
xN = 0 ; xB = b¯ = B −1 b . ¯ = B −1 b ≥ 0. signi e que b
associée à cette solution est
Finalement, le tableau du simplexe associé à la base
B
z¯.
est (à une
permutation de colonnes près) de la forme : Base
xB −z
xB Im
xN − B 1N
0
dN
s.m
b¯ = B −1 b −¯ z
dN = cN − cB B −1 N ; z¯ = cB B −1 b FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 110 /
192
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 x2 ← e3 −z
1
0
1
0
0
4
0
1
0
1/2
0
6
3
0
0
1
6
3
0
0
−1 −5/2
0
−30
Base
xB −z xB = (e1 , x2 , e3 ) xN = (x1 , e2 )
xB Im
xN
s.m
B −1 N
0
dN
b¯ = B −1 b −¯ z
: variables de base,
: variables hors base,
dN = (3 , −5/2) ; b¯ = (4 , 6 , 6), Solution de base : Fonction objectif : FSJES Guelimim
(x1 , x2 , e1 , e2 , e3 ) = (0 , 6 , 4 , 0 , 6), z¯ = 30. RO - S5 Économie et Gestion
2020/2021 111 /
192
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 : I I I
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.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 112 /
192
La méthode du simplexe
Cas général
Dé nition 1
Une solution de base si :
xB
associée à la base
B
est dite non dégénérée
x B = 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
dN = cN − cB B −1 N ≤ 0
alors la solution de base réalisable FSJES Guelimim
xN = 0 ; xB = b¯ = B −1 b
RO - S5 Économie et Gestion
est optimale.
2020/2021 113 /
192
La méthode du simplexe
Cas général
Preuve du Théorème :
x = (x1 , ..., xn ) une solution de base réalisable = (x1∗ , ..., xn∗ ) la solution de base associée à B .
Soit
x∗
Comme
xN ≥ 0
(car
x
dN ≤ 0 (par X dN xN = di xi ≤ 0
réalisable) et
quelconque et soit
hypothèse) on a :
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
dj > 0 , j ∈ N . FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 114 /
192
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
A¯N = B −1 N = (¯ akj , (1 ≤ k ≤ m).
On a les possibilités suivantes : 1
a¯kj ≤ 0, ∀ k = 1, ..., m (Tous les termes de la colonne
j
de la variable entrante sont
Dans ce cas l'ensemble réalisable est non borné et max 2
Il existe
k ∈ {1, ..., m}
tel que
≤ 0).
z = +∞
a¯kj > 0
Dans ce cas on va procéder à une itération et
xj FSJES Guelimim
est la variable entrante dans la base. RO - S5 Économie et Gestion
2020/2021 115 /
192
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{ ; a¯pj > 0} a¯pj a¯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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 116 /
192
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 :
(PC )
FSJES Guelimim
max 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 x1 ≥ 0, . . . , xn ≥ 0 RO - S5 Économie et Gestion
2020/2021 117 /
192
La méthode du simplexe
En introduisant des variables d'écart
Problèmes particuliers
(e1 , ..., em ) ,
nous obtenons le PL sous
forme standard :
(PS)
max z = c1 x1 + c2 x2 + ... + cn xn + 0e1 + ... + 0en a 11 x1 + a12 x2 + ... + a1n xn + e1 = b1 a21 x1 + a22 x2 + ... + a2n xn + e2 = b2 .
. . a x + am2 x2 + ... + amn xn + em = bm m1 1 x1 ≥ 0, . . . , xn ≥ 0, e1 ≥ 0, . . . , em ≥ 0
En posant
A˜ = où
Im
A Im
; x˜ = (x1 , ..., xn , e1 , ..., em )T ; c˜ = (c1 , ..., cn , 0, ..., 0)T
est la matrice identité d'ordre
m.
(PS) s'écrit alors sous la forme matricielle :
z˜ = c˜T x˜ ˜x = b A˜ x˜ ≥ 0
FSJES Guelimim
max
RO - S5 Économie et Gestion
2020/2021 118 /
192
La méthode du simplexe
Comme
Im
Problèmes particuliers
est inversible on a une solution de base initiale :
B = Im ; N = A ; xB = 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
Dans ce cas,
bj < 0.
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{ ; a¯pj > 0} = 0 a¯pj a¯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 : FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 119 /
192
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
FSJES Guelimim
xr
ayant le plus petit indice
RO - S5 Économie et Gestion
r.
2020/2021 120 /
192
La méthode du simplexe
Problèmes particuliers
Exemples : T1 Base
x1
x2
x3
x4
x5
x6
s.m
R
x5 x4 x3 −z
4
7
0
0
1
4
4
4/7
2
8
0
1
0
3
0
0
- 2
9
1
0
0
2
0
0
-5
2
0
0
0
5
-3
Variables candidates à enter dans la base : Variables candidates à sortir de la base :
x2
x4
et
x3 .
On choisit donc
x3 .
T2
FSJES Guelimim
↓
Base
x1
x2
x3
e1
e2
e3
s.m
R
← e1 e2 e3 −z
1
2
5
1
0
0
4
2
3
4
3
0
1
0
8
2
2
4
1
0
0
1
12
3
2
3
1
0
0
1
0
RO - S5 Économie et Gestion
2020/2021 121 /
192
La méthode du simplexe
Problèmes particuliers
T3 ↓
Base
x1
x2
x3
e1
e2
e3
e1 e2 e3 −z
1
2
5
1
0
0
3
3
1
3
0
1
0
10
2
8
1
0
0
1
8
3
3
2
0
0
0
0
s.m
T4 ↓
Base
x1
x2
e1
e2
s.m
e1 x1 −z
0
-2
1
-1
20
1
0
0
2,5
3
0
16
0
-3
-32
Tous les coe cients de la colonne de la variable entrante ou nuls :
x2
sont négatifs
zmax = +∞
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 122 /
192
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 :
On fait entrer
e2
Base
x1
x2
e1
e2
s.m
x1 x2 −z
1
0
1
1
3
0
1
-1
-2
2
0
0
-1
0
-8
dans la base et
x1
sera alors la variable sortante. Ainsi, on
obtient une autre solution optimale :
FSJES Guelimim
Base
x1
x2
e1
e2
s.m
e2 x2 −z
1
0
1
1
3
2
1
1
0
8
0
0
1
0
-8
RO - S5 Économie et Gestion
2020/2021 123 /
192
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
FSJES Guelimim
revient à maximiser
RO - S5 Économie et Gestion
−z
.
2020/2021 124 /
192
La méthode du simplexe
Simplexe avec minimisation
Exemple : Soit le problème :
min −x1 − 2x2 −3x1 + 2x2 ≤ 2 −x1 + 2x2 ≤ 4 (PM) x + x2 ≤ 5 1 x1 , x2 ≥ 0 En rajoutant les variables d'écart on obtient la forme standard :
min −x1 − 2x2 −3x1 + 2x2 + e1 = 2 −x1 + 2x2 + e2 = 4 (PMS) x + x2 + e3 = 5 1 x1 , x2 , e1 , e2 , e3 ≥ 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 variables hors base FSJES Guelimim
e1 , e2 , e3
et
x1 , x2 . RO - S5 Économie et Gestion
2020/2021 125 /
192
La méthode du simplexe
Les contraintes de
(PMS)
peuvent être représentées par le système :
˜x = b˜ A˜ x˜ ≥ 0
−3 ˜ −1 A= 1
2
1
0
0
2
0
1
0
1
0
0
1
Simplexe avec minimisation
; x˜ =
x1 x2 e1 e2 e3
z = c˜T x˜ = −x1 − 2x2 + 0e1 + 0e2 + 0e3
; b˜ = b = avec
2
4
5
c˜ = (x1 , x2 , 0 , 0 , 0)T
Une base initiale est donnée par la matrice identité :
I =
1
0
0
0
1
0
0
0
1
La solution de base réalisable initiale est :
(x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 2 , 4 , 5) FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 126 /
192
La méthode du simplexe
Simplexe avec minimisation
Tableau 1 ↓
Base
x1
x2
e1
e2
e3
s.m
R
← e1 e2 e3 −z
-3
2
1
0
0
2
1
-1
2
0
1
0
4
2
1
1
0
0
1
5
5
-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 ← e2 e3 −z
-3/2
1
1/2
0
0
1
−2/3
2
0
-1
1
0
2
1
5/2
0
-1/2
0
1
4
8/5
-4
0
1
0
0
2
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 127 /
192
La méthode du simplexe
Simplexe avec minimisation
Tableau 3 ↓
Base
x1
x2
e1
e2
e3
s.m
R
x2 x1 ← e3
0
1
-1/4
3/4
0
5/2
10
1
0
-1/2
1/2
0
1
-2
0
0
3/4
-5/4
1
3/2
2
−z
0
0
-1
2
0
6
Tableau 4
e2
e3
s.m
0
1/3
1/3
3
0
-1/3
2/3
2
0
1
-5/3
4/3
2
0
0
1/3
4/3
8
Base
x1
x2
e1
x2 x1 e1 −z
0
1
1
0
0 0
Tous les coe cients de la dernière ligne sont positifs ou nuls : le tableau 4 est optimal et FSJES Guelimim
x∗ 1
=2;
x∗ 2
=3;
e∗ 1
=2;
e∗ 2
RO - S5 Économie et Gestion
= e∗3 = 0 ;
z∗
= −8
2020/2021 128 /
192
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 :
z = cT x Ax ≤ b x ≥0
max
ei à chaque contrainte pour la ˜ qui correspond à l'ensemble transformer en une égalité, la matrice A ˜ ˜ A Im contraintes Ax = b prend la forme : A =
alors en ajoutant une variable d'écart
avec
x˜ = (x1 , ..., xn , e1 , ..., em )T
et
Im
des
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
FSJES Guelimim
et
xB = (e1 , ..., em ).
RO - S5 Économie et Gestion
2020/2021 129 /
192
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
A˜.
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.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 130 /
192
La méthode du simplexe
Initialisation de la méthode du simplexe
Méthode du grand M : Considérons le PL suivant :
z = x1 + x2 + x2 ≥ 4 (P1 ) x + 2x2 = 6 1 x1 , x2 ≥ 0 max 2x1
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.
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 131 /
192
La méthode du simplexe
Initialisation de la méthode du simplexe
On obtient alors le PL :
z = x1 + x2 −Ma1 − Ma2 + x2 − e1 + a1 = 4 x + 2x2 + a2 = 6 1 x1 , x2 , e1 , a1 , a2 ≥ 0 max 2x1
qui est sous forme standard. On remarque que les contraintes du dernier problème peuvent s'écrire :
˜x = b˜ A˜ x˜ ≥ 0
A˜ =
2
1
−1
1
0
1
2
0
0
1
FSJES Guelimim
; x˜ =
x1 x2 e1 a1 a2
; b˜ = b =
RO - S5 Économie et Gestion
4
6
2020/2021 132 /
192
La méthode du simplexe
Initialisation de la méthode du simplexe
La solution de base initiale est donnée par : Variables de base : Variables hors base :
a1 = 4 ; a2 = 6 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.
+ x2 − e1 + a1 = 4 x1 + 2x2 + a2 = 6 2x1
⇒
a1 = 4 − 2x1 − x2 + e1 a2 = 6 − x1 − 2x2
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
FSJES Guelimim
x1 = x2 = e1 = 0
alors
RO - S5 Économie et Gestion
z = z¯ = −10M . 2020/2021 133 /
192
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
x1 x1
et
x2
↓
Base
x1
x2
e1
a1
a2
s.m
R
← a1 a2 −z
2
1
-1
1
0
4
2
1
2
0
0
1
6
6
3M+1
3M+1
-M
0
0
10 M
candidates à entrer dans la base. En appliquant la règle de Bland,
entrante.
a1
sort de la base.
Tableau 2 Base
x1
x1 ← a2 −z
↓
a1
a2
s.m
-1/2
1/2
0
2
4
1/2
-1/2
1
4
8/3
(M+1)/2
-(3M+1)/2
0
-2 + 4M
x2
e1
1
1/2
0
3/2
0
(3M+1)/2
FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 134 /
R
192
La méthode du simplexe
Initialisation de la méthode du simplexe
Tableau 3 ↓
a1
a2
s.m
R
-2/3
2/3
-1/3
2/3
-1
1/3
-1/3
2/3
8/3
8
1/3
-M-1/3
-M-1/3
-10/3
Base
x1
x2
e1
x1 ← x2
1
0
0
1
−z
0
0
Tableau 4
a1
a2
s.m
0
0
1
6
1
-1
2
8
0
-M
-M-1
-6
Base
x1
x2
e1
x1 e1 −z
1
2
0
3
0
-1
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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 135 /
192
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. Remplacer la fonction objectif par où
M
z=
T max c x
−M
m X
ai
i=1 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 que
a∗ =
(a1∗ , ..., ap∗ )
=
(x ∗ , a∗ )
telle
∗ 0, alors x est une solution optimale du
problème de départ. Si la méthode du simplexe se termine avec une solution
∗ que a
6= 0
(x ∗ , a∗ )
telle
(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. FSJES Guelimim
RO - S5 Économie et Gestion
2020/2021 136 /
192
La méthode du simplexe
Initialisation de la méthode du simplexe
Chapitre 4 : Résolution des programmes linéaires La dualité
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
137 / 192
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 ? (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
138 / 192
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
3
4
60
5000
2000
Quantité de m.p M3 (tonnes) Prix unitaire (UM)
Le problème de l'entreprise E1 se modélise par le programme linéaire :
max z = 5000x1 + 2000x2 Quantité de m.p M1 2x1 + x2 ≤ 50 x1 + 3x2 ≤ 25 Quantité de m.p M2 (P) 3 x + 4 x ≤ 60 Quantité de m.p M3 1 2 x1 ≥ 0 ; x2 ≥ 0 x1
: quantité de produits P1 fabriqués
x2
: quantité de produits P2 fabriqués
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
139 / 192
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,
c2 = 2000
c1 = 5000
UM et
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 :
(D)
yi
min
w = 50y1 + 25y2 + 60y3
+ y2 + 3y3 ≥ 5000 y1 + 3y2 + 4y3 ≥ 2000 y1 ; y2 ; y3 ≥ 0 2y1
: prix unitaire d'achat de la m.p Mi (Département SMAEG )
contrainte produit P1 contrainte produit P2
(i
= 1, 2, 3)
RO - S6 Économie et Gestion
2015/2016
140 / 192
Dualité
Exemple introductif
Le problème
(D)
est appelé problème dual de
Le problème
(P)
est appelé problème primal.
(P).
Remarque Comparons les deux problèmes, primal
max z 2x1 x1 (P) 3x1 x1
(D)
min 2y1
y1 y1
(Département SMAEG )
w
=
=
(P)
5000x1
et dual
(D)
:
+
2000x2
+ x2 + 3x2 + 4x2
≤ ≤ ≤
50
,
≥0
x2 50y1
25 60
+
25y2
+
60y3
+ y2 + 3y2
+ +
3y3
5000
4y3
≥ ≥
,
,
y3
≥0
y2
RO - S6 Économie et Gestion
2000
2015/2016
141 / 192
Dualité
w (P).
Les coe cients de la fonction objectif coe cients du second membre de
Exemple introductif
de
(D)
De même, Les coe cients de la fonction objectif aux coe cients du second membre de
correspondent aux
z
de
(P)
correspondent
(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
A0 ,
b 0 et
(P),
c 0 respectivement la matrice des contraintes, le second membre et
le vecteur des coûts du problème
(D),
alors on a :
A=
A0 =
2
1
3
1
3
4
2
1
1
3
; b=
3
4
(Département SMAEG )
50
25
; c=
60
= AT ; b 0 =
5000
2000
RO - S6 Économie et Gestion
5000
2000
50
= c ; c0 =
25
=b
60 2015/2016
142 / 192
Dualité
Le problème primal
Exemple introductif
(P) et son dual (D) sont liés par les relations suivantes :
Le problème
(P)
contient 2 variables (x1 et
Le problème
(D)
contient 3 variables (y1 ,
x2 )
y2
On en conclut que le nombre de variables de
(D)
de contraintes de
(D)
et
et 2 contraintes.
est égal au nombre
et réciproquement, le nombre de variables de
(P).
On peut véri er facilement que le dual de
(D)
(P)
y3 )
(P)
est égal au nombre de contraintes de
Le problème
et 3 contraintes.
est le problème
(P).
est un problème de maximisation. Tandis que
(D)
est
un problème de minimisation. Le minimum
zmax
wmin
du problème
atteint par le problème
(D)
est égal au maximum
(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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
143 / 192
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 x1 ≥ 0, . . . , xn ≥ 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 : Matrice des contraintes (Département SMAEG )
A
de type
(m, n)
c1 , c2 ,..., cn
(m lignes et n colonnes).
RO - S6 Économie et Gestion
2015/2016
144 / 192
Dualité
Formulation générale du problème dual
(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) . . . a1n y1 + am2 y2 + ... + amn ym ≥ cn y1 ≥ 0, . . . , ym ≥ 0
Le problème dual de
m
variables
y1 , y2 ,..., ym
et
n
contraintes.
Coe cients du second membre :
c1 , c2 ,..., cn .
Coe cients (coûts) de la fonction objectif : Matrice des contraintes :
(Département SMAEG )
A0 = AT
de type
b1 , b2 ,..., bm
(n, m)
RO - S6 Économie et Gestion
(n lignes et m colonnes).
2015/2016
145 / 192
Dualité
Formulation générale du problème dual
Formulation matricielle : T max z = c x
(P)
Ax ≤ b x ≥0
(D)
w = bT y ≥ c
min
y ≥0
AT y
Exemples :
max z = + x1 −2x1 + (P1 ) 2x1 − x1 , min w = 14y1 y1 − 2y2 (D1 ) y1 + 3y2 y1 , y2 (Département SMAEG )
x1
+
x2 ≤ 3x2 ≤ x2 ≤ x2
≥0
+
12y2
3x2 14 12 12
+
12y3
+ 2y3 − y3
≥ ≥
1
,
≥0
y3
RO - S6 Économie et Gestion
3
2015/2016
146 / 192
Dualité
min z 3x1 4x1 (P2 ) x1 x1 Le dual de
= −2x1 + + x2 − 3x2 − x2
≥ ≤ ≤
,
≥0
(P2 )
x2
10 8 6
min z 3x1 −4x1 ⇐⇒ −x1 x1
= −2x1 +
9x2
+ x2 + 3x2 + x2
≥ ≥ ≥
,
≥0
x2
10
−8 −6
est :
(D2 )
max
w
3y1 y 1 y1
Question : Dual de
min z 3u1 −4u1 (D¯2 ) −u 1 u1
9x2
Formulation générale du problème dual
= + + + ,
(Département SMAEG )
= 10y1 − 4y2 + 3y2 , y2
− 8y2 − y3 + y3 , y3
− 6y3 ≤ −2 ≤ 9 ≥0
(D2 ) ?
−2u1 u2 3u2 u2 u2
+ 9u2 ≥ 10 ≥ −8 ≥ −6 ≥0
Le dual du dual de
RO - S6 Économie et Gestion
(P2 )
=
2015/2016
(P2 ).
147 / 192
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
j ème
variable
(Département SMAEG )
≥0
i ème
≤ j ème
variable
≥0
contrainte de type
RO - S6 Économie et Gestion
≥
2015/2016
148 / 192
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 ∗ = bT 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
une solution
et
y
=
0
,
i = 1, ..., m
(1)
yi aij − cj xj
=
0
,
j = 1, ..., n
(2)
yi bi − m X
y
x
réalisable du problème dual (D). Alors
n X
aij xj
sont optimales ssi :
j=1
i=1 (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
149 / 192
Dualité
Théorème de dualité
Par exemple :
max z = 5000x1 + 2000x2 2x1 + x2 ≤ 50 (P) x1 + 3x2 ≤ 25 3x1 + 4x2 ≤ 60 x ≥0; x ≥0 1 2 Si
(D)
min
w = 50y1 + 25y2 + 60y3
2y1 + y2 + 3y3 ≥ 5000 y 1 + 3y2 + 4y3 ≥ 2000 y1 , y2 , y3 ≥ 0
x = (x1 , x2 ) réalisable pour P et y = (y1 , y2 , y3 ) x et y solutions optimales ssi :
réalisable pour
D,
alors
y1 (50 − 2x1 − x2 ) = 0 ; y2 (25 − x1 − 3x2 ) = 0 ; y3 (60 − 3x1 − 4x2 ) = 0 (2y1 + y2 + 3y3 − 5000) x1 = 0 ;
(Département SMAEG )
(y1 + 3y2 + 4y3 − 2000) x2 = 0
RO - S6 Économie et Gestion
2015/2016
150 / 192
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 :
(P)
max
n X
z=
n X
cj xj
j=1
(D)
aij xj ≤ bi (i = 1, ..., m) j= 1 x ≥ 0 (j = 1, ..., n) j
Soient
x∗
une solution optimale de
(P)
et
y∗
min
m X
w=
m X
bi yi
i=1
aij yi ≥ cj
(j = 1, n)
i=1
yi ≥ 0 (i = 1, m)
une solution optimale de
(D).
D'après le théorème 2, on a :
n X yi∗ bi − aij xj∗ = m X
0
,
i = 1, ..., m
(3)
0
,
j = 1, ..., n
(4)
j=1
yi∗ aij − cj xj∗ =
i=1 (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
151 / 192
Dualité
Théorème de dualité
Conséquences : Si la
i ème
contrainte du problème primal (P) est non saturée alors
bi −
n X
aij xj∗ 6= 0
j=1
yi∗ = 0.
et la relation (3) entraîne que Si la
j ème
contrainte du problème dual (D) est non saturée alors
m X
yi∗ aij − cj 6= 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.
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
152 / 192
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 :
(P)
max
z = 4x1 + 3x2
+ x2 ≤ 3 5x1 + 6x2 ≤ 11 x1 ≥ 0 ; x2 ≥ 0 2x1
(Département SMAEG )
Quantité de m.p Nombre d'heures de travail/jour
RO - S6 Économie et Gestion
2015/2016
153 / 192
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 :
(P 0 )
max
z = 4x1 + 3x2
+ x2 ≤ 3 5x1 + 6x2 ≤ 12 x1 ≥ 0 ; x2 ≥ 0 2x1
La solution optimale de
(P)
(Quantité de m.p) (Nombre d'heures de travail/jour)
est :
0 La solution optimale de (P ) est :
A = (1, 1) A0
L'augmentation de l'objectif est de :
(Département SMAEG )
et
zmax = 7
= (6/7, 9/7)
UM.
0 et zmax
= 51/7
UM.
∆z = 51/7 − 7 = 2/7.
RO - S6 Économie et Gestion
2015/2016
154 / 192
Dualité
Interprétation économique des variables duales
(P) s'écrit : min w = 3y1 + 11y2 2y1 + 5y2 ≥ 4 (D) y1 + 6y2 ≥ 3 y1 ≥ 0 ; y2 ≥ 0
D'autre part, le dual de
Le problème dual (D) a pour solution optimale : Donc
y2∗
(y1∗ , y2∗ ) = (9/7, 2/7).
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∗ ). (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
155 / 192
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 d'indice
i
yi∗ = 0,
c-à-d le coût marginal
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 contrainte d'indice
i
i
est non nul c-à-d
yi∗ 6= 0,
alors la
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.
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
156 / 192
Passage du tableau optimal primal au tableau optimal dual et vice versa Primal La valeur optimale de la fonction objectif z
Dual =
La valeur optimale de la fonction objectif w
Coûts marginaux des variables hors base
Signe opposé
Colonne s.m des variables de base associées (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) (Contrainte d’indice j saturée) La variable d’écart tj en base (tj > 0) (Contrainte d’indice j non saturée)
La variable de décision xj en base (xj > 0) La variable de décision xj hors base (xj = 0) La variable d’écart ei en base (ei > 0) (Contrainte d’indice i non saturée) La variable d’écart ei hors base (ei = 0) (Contrainte d’indice i saturée)
La variable de décision yi hors base (yi = 0) La variable de décision yi en base (yi > 0)
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
15
25
Prix unitaire (UM) 1
Formuler un P.L (P) aidant l'entreprise à maximiser son chire d'aaires et résoudre (P) par l'algorithme du simplexe.
2 3
∗
Donner le P.L dual (D) et ses valeurs optimales (y1 ,
y2∗ , y3∗ , w ∗ ).
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
158 / 192
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 Contrainte quantité de m.p M1 x1 + 3x2 ≤ 96 x1 + x2 ≤ 40 Contrainte quantité de m.p M2 (P) 7 x + 4 x ≤ 238 Contrainte quantité de m.p M3 1 2 x1 ≥ 0 ; x2 ≥ 0
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
159 / 192
Dualité
Exercice d'application
Forme standard du problème primal :
(P.S)
max z = 15x1 + 25x2 x1 + 3x2 + e1 = 96 x1 + x2 + e2 = 40 7x1 + 4x2 + e3 = 238 x1 , x2 , x3 , e1 , e2 , e3 ≥ 0 Tableau 1 ↓
Base
x1
x2
e1
e2
e3
s.m
← e1 e2 e3 −z
1
3
1
0
0
96
1
1
0
1
0
40
7
4
0
0
1
238
15
25
0
0
0
0
Variable entrante :
x2 .
Variable sortante :
e1 .
R 96/3
= 32 = 40 238/4 = 59, 5 40/1
Pivot : 3 (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
160 / 192
Dualité
Exercice d'application
Tableau 2 Base
e1 ← e2 e3 −z
↓
x1 1/3
x2
2/3
0
17/3
0
20/3
0
Variable entrante :
1
x1
e1 1/3 −1/3 −4/3 −25/3
e2
e3
s.m
R
0
0
32
96
1
0
8
12
0
1
110
0
0
-800
; Variable sortante :
e2
238/4
= 19, 4
; Pivot : 2/3
Tableau 3 Base
x1
x2
x2 x1 e3 −z
0
1
1
0
0
0
0
0
e1 1 /2 −1/2 3 /2 −5
e2 −1/2 3/2 −17/2 −10
e3
s.m
0
28
0
12
1
42
0
−880
Le tableau 3 est optimal car tous les coe cients de la dernière ligne
−z
sont négatifs ou nuls. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
161 / 192
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)
(D)
yi
min
w = 96y1 + 40y2 + 238y3
y1 + y2 + 7y3 ≥ 15 3y1 + y2 + 4y3 ≥ 25 y1 ; y2 ; y3 ≥ 0
: prix unitaire d'achat de la m.p Mi
D'après la ligne
contrainte produit P1 contrainte produit P2
(i
= 1, 2, 3)
−z du tableau 3, les coûts −5, −10 et 0. Donc
marginaux de
e1 , e2
et
e3
sont
respectivement :
y1∗ = 5 ; y2∗ = 10 ; y3∗ = 0
et
w ∗ = z ∗ = 880
(Voir passage du tableau optimal primal au tableau optimal dual).
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
162 / 192
Dualité
Exercice d'application
3)
y1∗ = 5 et y2∗ = 10, donc une augmentation de la quantité de M1 (resp. M2 ) d'une tonne va entraîner une amélioration du chire
On a
la m.p
d'aaires de 5 UM (resp. 10 UM). Ainsi l'entreprise a intérêt à investir dans la quantité de la m.p
(Département SMAEG )
M2
en premier.
RO - S6 Économie et Gestion
2015/2016
163 / 192
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 :
xi
←→ ti
yi
←→ ei
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
164 / 192
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
x2 x1 e3 −z
0
1
1 /2
1
0
0
0
0
0
−1/2 3 /2 −5
e2 −1/2 3/2 −17/2 −10
e3
s.m
0
28
0
12
1
42
0
−880
Tableau optimal dual Base
y1
y2
y3
t1
t2
s.m
y1 y2 −w
1
0
-3/2
1/2
-1/2
5
0
1
17/2
-3/2
1/2
10
0
0
-42
-12
-28
-880
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
165 / 192
Analyse de sensibilité
Chapitre 5 : Résolution des programmes linéaires Analyse de sensibilité
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
166 / 192
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 ?
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
167 / 192
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.
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
168 / 192
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 Type de eur
stock
bouquet N1
bouquet N2
bouquet N3
disponible
roses
2
3
2
90
÷illets
1
2
1
81
orchidées
4
3
1
120
8UM
5UM
6UM
Prix
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 . (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
169 / 192
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 :
(e1 ) (e2 ) (e ) 3
z = 8x1 + 5x2 + 6x3 2x1 + 3x2 + 2x3 ≤ 90 x1 + 2x2 + x3 ≤ 81 4x1 + 3x2 + x3 ≤ 120 x1 , x2 , x3 ≥ 0 max
roses ÷illets orchidées
Dans cette écriture, nous avons mis entre parenthèses les noms des variables d'écart que nous allons utiliser dans la forme standard .
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
170 / 192
Analyse de sensibilité
Ce problème s'écrit, sous sa forme standard :
max z = 8x1 + 5x2 + 6x3 2x1 + 3x2 + 2x3 + e1 = 90 (e1 )roses (e2 )÷illets x1 + 2x2 + x3 + e2 = 81 (e ) orchidées 4 x + 3 x + x + e = 120 3 1 2 3 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 e2 ← e3 −Z
2
3
2
1
0
0
90
45
1
2
1
0
1
0
81
81
4
3
1
0
0
1
120
30
8
5
6
0
0
0
0
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
171 / 192
Analyse de sensibilité
Tableau 2 Base
x1
e1 e2 x1 −Z
0
x2 3/2 5/4 3/4 −1
0 1 0
x3
e1
e2
3/2
1
0
3/4
0
1
1/4
0
0
4
0
0
e3 −1/2 −1/4 1/4 −2
s.m
R
30
20
51
68
30
120
−240
Tableau 3 Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
0
1/2
0
1
1/2
0
0
−5
0
−1/2 −1/6 −8/3
(Département SMAEG )
e3 −1/3
s.m
1
0
36
0
1/3
25
0
−2/3
−320
RO - S6 Économie et Gestion
20
2015/2016
172 / 192
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 0 bouquets N2 (x2
= 25)
= 0)
20 bouquets N3 (x3
= 20)
Il utilisera toutes ses roses (e1 Il lui restera 36 ÷illets . (e2
= 0)
= 36)
Il utilisera toutes ses orchidées (e3 Sa recette sera de 320 (Z
(Département SMAEG )
= 0)
= 320)
RO - S6 Économie et Gestion
2015/2016
173 / 192
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
x3 e2 x1 −Z
0
1
1
0
1/2
0
1
1/2
0
0
−5
0
e1 2/3 −1/2 −1/6 −8/3
e2
s.m
0
e3 −1/3
1
0
B
0
1/3 −2/3
D
0
A
C
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
174 / 192
Analyse de sensibilité
Variation des bornes des contraintes
Écrivons ces systèmes :
Z − 8x1 − 5x2 − 6x3 2x1 + 3x2 + 2x3 + e1 x1 + 2x2 + x3 + e2 (P) 4 x + 3x2 + x3 + e3 1 x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
= = = =
0 90 81 120
⇐⇒ Z + 5x2 + 8/3e1 + 2/3e3 x 2 + x3 + 2/3e1 − 1/3e3 0 1/2x2 − 1/2e1 + e2 (P ) x − 1/2x2 − 1/6e1 + 1/3e3 1 x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0
= = = =
D A B C
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
175 / 192
Analyse de sensibilité
Variation des bornes des contraintes
Cette solution doit aussi être solution de second système : en remplaçant, on trouve :
+ 5 × 0 + 8/3 × 90 + 2/3 × 120 0 + 0 + 2/3 × 90 − 1/3 × 120 (P 0 ) 1/2 × 0 − 1/2 × 90 + 81 0 − 1/2 × 0 − 1/6 × 90 + 1/3 × 120 0
= = = =
D D A A ⇔ B B C C
= = = =
320 20 36 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.
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
176 / 192
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
81
÷illets
84
roses
72
÷illets
120
120
orchidées
max z = 8x1 + 5x2 + 6x3 2x1 + 3x2 + 2x3 + e1 = 84 (e1 )roses (e2 )÷illets x1 + 2x2 + x3 + e2 = 72 (e )orchidées 4x1 + 3x2 + x3 + e3 = 120 3 x1 , x2 , x3 , e1 , e2 , e3 ≥ 0
avec
Mais
orchidées
Le problème du euriste est modi é et devient :
Tableau 1 Base
x1
x2
x3
e1
e2
e3
s.m
e1 e2 e3 −Z
2
3
2
1
0
0
84
1
2
1
0
1
0
72
4
3
1
0
0
1
120
8
5
6
0
0
0
0
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
177 / 192
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
x3 e2 x1 −Z
0
1
1
2/3
0
e3 −1/3
s.m
0
1/2
0
1
1/2
0
0
−5
0
−1/2 −1/6 −8/3
1
0
B
0
1/3
C
0
−2/3
D
A
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
178 / 192
Analyse de sensibilité
Variation des bornes des contraintes
ce qui nous conduit à la solution :
+ 5 × 0 + 8/3 × 84 + 2/3 × 120 0 + 0 + 2/3 × 84 − 1/3 × 120 (P 0 ) 1/2 × 0 − 1/2 × 84 + 72 0 − 1/2 × 0 − 1/6 × 84 + 1/3 × 120 0
= = = =
D D A A ⇔ B B C C
= = = =
304 16 30 26
Ce qui signi e que le euriste devra composer : 26 bouquets N1 (x1 0 bouquets N2 (x2
= 26)
= 0)
16 bouquets N3 (x3
= 16)
Il utilisera toutes ses roses (e1 Il lui restera 30 ÷illets . (e2
= 0)
= 30)
Il utilisera toutes ses orchidées (e3 Sa recette sera de 304 (Z
(Département SMAEG )
= 0)
= 304)
RO - S6 Économie et Gestion
2015/2016
179 / 192
Analyse de sensibilité
Variation des bornes des contraintes
Supposons maintenant que l'on parte d'un stock 162 roses 30
207
÷illets
plutôt que
orchidées
90
roses
81
÷illets
120
orchidées
Le problème du euriste devient :
max z = 8x1 + 5x2 + 6x3 2x1 + 3x2 + 2x3 + e1 = 162 (e1 )roses (e2 )÷illets x1 + 2x2 + x3 + e2 = 30 (e )orchidées 4x1 + 3x2 + x3 + e3 = 207 3 x1 , x2 , x3 , e1 , e2 , e3 ≥ 0
avec
Tableau 1 Base
x1
x2
x3
e1
e2
e3
s.m
e1 e2 e3 −Z
2
3
2
1
0
0
162
1
2
1
0
1
0
30
4
3
1
0
0
1
207
8
5
6
0
0
0
0
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
180 / 192
Analyse de sensibilité
Variation des bornes des contraintes
En appliquant les mêmes raisonnements que précédemment, on obtiendra
+ 5 × 0 + 8/3 × 162 + 2/3 × 207 0 + 0 + 2/3 × 162 − 1/3 × 207 (P 0 ) 1/2 × 0 − 1/2 × 162 + 30 0 − 1/2 × 0 − 1/6 × 162 + 1/3 × 207 0
= = = =
D D = 570 A A = 39 ⇔ B B = −51 C C = 42
Tableau 3 Base
x1
x3 e2 x1 −Z
(Département SMAEG )
x2
x3
0
1
1
0
1/2
0
1
1/2
0
0
−5
0
e1 2/3 −1/2 −1/6 −8/3
e2
s.m
0
e3 −1/3
1
0
-51
0
1/3 −2/3
570
0
RO - S6 Économie et Gestion
39
42
2015/2016
181 / 192
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é.
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
182 / 192
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
x3 e2 x1 −Z
e2
0
e1 2/3 −1/2 −1/6
0
1
1
0
1/2
0
1
1/2
A
B
s.m
0
e3 −1/3
1
0
36
C
D
0
1/3
25
E
F
G
20
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
183 / 192
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 ainsi qu'un 0 dans la colonne de la variable
x3
x1
(premier pivot)
(deuxième pivot).
Complétons le tableau par la ligne que nous voulons obtenir :
Tableau 3 Base
x1
x3 e2 x1 −Z
(Département SMAEG )
x2
x3
e2
0
e1 2 /3 −1/2 −1/6
0
1
1
0
1/2
0
1
1/2
8
5
s.m
0
e3 −1/3
1
0
36
6
0
0
1 /3
25
0
0
0
RO - S6 Économie et Gestion
20
2015/2016
184 / 192
Analyse de sensibilité
Variation de l'objectif
Tableau 3' Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
e3 −1/3
s.m
0
1 /2
0
1
1 /2
0
0
1
6
−1/2 −1/6 4/3
1
0
36
0
1/3
25
0
−8/3
−200
e3 −1/3
s.m
20
Tableau 3 Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
0
1/2
0
0
36
1/2
0
0
1/3
25
0
−5
0
−1/2 −1/6 −8/3
1
1
0
−2/3
−320
20
Il apparaît ainsi, qu'il est relativement simple de reconstituer la dernière ligne du tableau. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
185 / 192
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 3 passe de 6 UM à 5
le prix du bouquet de type 2 passe de 5 UM à 6
Le problème de notre euriste devient :
(e1 ) (e2 ) (e3 )
z = 9x1 + 6x2 + 5x3 2x1 + 3x2 + 2x3 ≤ 90 x1 + 2x2 + x3 ≤ 81 4x1 + 3x2 + x3 ≤ 120 x1 , x2 , x3 ≥ 0 max
roses ÷illets orchidées
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
186 / 192
Analyse de sensibilité
Variation de l'objectif
Le premier tableau du simplexe devient :
Tableau 1 Base
x1
x2
x3
e1
e2
e3
s.m
e1 e2 e3 −Z
2
3
2
1
0
0
90
1
2
1
0
1
0
81
4
3
1
0
0
1
120
9
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
0
1
1
2 /3
0
e3 −1/3
s.m
x3 e2 x1 −Z
0
1/2
0
1
0
36
1
1/2
0
−1/2 −1/6
0
1 /3
25
9
6
5
0
0
0
0
(Département SMAEG )
RO - S6 Économie et Gestion
20
2015/2016
187 / 192
Analyse de sensibilité
Variation de l'objectif
Tableau 3' Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
e3 −1/3
s.m
0
1 /2
0
1
1 /2
0
0
3 /2
5
−1/2 −1/6 3/2
1
0
36
0
1/3
25
0
−3
−225
20
Tableau 3 Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
e3 −1/3
s.m
0
1/2
0
1
1/2
0
0
−7/2
0
−1/2 −1/6 −11/6
1
0
36
0
1/3
25
0
−4/3
−325
20
Il apparaît ainsi, qu'il est relativement simple de reconstituer la dernière ligne du tableau. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
188 / 192
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 0 bouquets N2 (x2
= 25)
= 0)
20 bouquets N3 (x3
= 20)
Il utilisera toutes ses roses (e1 Il lui restera 36 ÷illets . (e2
= 0)
= 36)
Il utilisera toutes ses orchidées (e3 Sa recette sera de 325 (Z
= 0)
= 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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
189 / 192
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 3 passe de 6 UM à 10
le prix du bouquet de type 2 passe de 5 UM à 7
Le problème de notre euriste devient :
(e1 ) (e2 ) (e3 )
z = 8x1 + 7x2 + 10x3 2x1 + 3x2 + 2x3 ≤ 90 x1 + 2x2 + x3 ≤ 81 4x1 + 3x2 + x3 ≤ 120 x1 , x2 , x3 ≥ 0 max
roses ÷illets orchidées
(Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
190 / 192
Analyse de sensibilité
Variation de l'objectif
Le premier tableau du simplexe devient :
Tableau 1 Base
x1
x2
x3
e1
e2
e3
s.m
e1 e2 e3 −Z
2
3
2
1
0
0
90
1
2
1
0
1
0
81
4
3
1
0
0
1
120
8
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
x3 e2 x1 −Z
0
1
1
2 /3
0
(Département SMAEG )
e3 −1/3
s.m 20
0
1 /2
0
0
36
1 /2
0
−1/2 −1/6
1
1
0
1/3
25
8
7
10
0
0
0
0
RO - S6 Économie et Gestion
2015/2016
191 / 192
Analyse de sensibilité
Variation de l'objectif
Tableau 3' Base
x1
x2
x3
x3 e2 x1 −Z
0
1
1
0
1 /2
0
1
1 /2
0
0
3
10
e1 2/3 −1/2 −1/6 4/3
e2
s.m
0
e3 −1/3
1
0
36
0
1/3 −8/3
−200
0
20
25
Tableau 3 Base
x1
x2
x3
e1
e2
x3 e2 x1 −Z
0
1
1
2/3
0
e3 −1/3
s.m
0
1/2
0
1
1/2
0
0
−7
0
−1/2 −1/6 −16/3
1
0
36
0
1 /3
25
0
2 /3
−325
20
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. (Département SMAEG )
RO - S6 Économie et Gestion
2015/2016
192 / 192
Chapter 1 Programmes linéaires et modélisation
1.1
Introduction
Définition 1.1. La recherche opérationnelle est un ensemble de méthodes scientifiques 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 scientifique à des problèmes organisationnels complexes (problèmes de gestion par exemple).
Exemple 1.1. • Comment aller le plus vite de Casablanca à Rabat en voiture ? • Comment investir ses 10000 Dh d’économie de sorte à maximiser le profit obtenu après deux ans ? • Comment ordonnancer les tâches d’un projet en fonction de la main d’?uvre, tout en minimisant sa durée ? • Trouver un plus court chemin entre deux villes. • Emplois du temps : Planifier l’horaire des cours ou des examens, en tenant compte des différentes ressources (étudiants, professeurs,locaux,...) • Définir le nombre du personnel dans une gare de trains ou une banque suivant la fréquence de la clientèle.
3
Remarque 1.1. En conclusion, la recherche opérationnelle, face à un problème pratique de décision, cherche à : • faire le mieux : coût minimal, meilleur profit, 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 " les mathématiques (modélisation), l’informatique (algorithmique) et l’économie (gestion, stratégie).
1.1.1
Etapes d’un processus de RO
1. 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...) 2. Traduire le problème réel sous forme de modèle mathématique (programme linéaire par ex.) 3. Résolution du modèle: • Choix d’un algorithme (Simplexe par ex.) • Utilisation des logiciels spécialisés (Excel, Lindo,...) 4. 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 ? 5. Prise de décision
4
1.1.2
La programmation linéaire
Définition 1.2. 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 à diffé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écifique comme la maximisation des bénéfices ou la minimisation des coûts.
1.2
Exemples de programmes linéaires
Exemple 1.2. 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. 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 : Atelier 1 Atelier 2 Atelier 3 Marge
Prod1 (châssis alum)(h/prod) 1 0 3 3UM
Prod2 (châssis bois)(h/prod) 0 2 2 5UM
La question qui se pose est la suivante : combien faut-il produire de châssis de chaque type par semaine pour maximiser le profit net ? 1. Identification 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 5
Capacité disponible (h/s 4 12 18
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 profit 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 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 :x1 ≥ 0; x2 ≥ 0 Finalement, le problème peut être formulé en programme linéaire : max z = 3x1 + 5x2 x1 ≤ 4 2x2 ≤ 12 (P1) 3x + 2x2 ≤ 18 1 x1 ≥ 0; x2 ≥ 0
6
Exemple 1.3. Une rafinerie achète deux types de pétroles bruts dont elle retire de l’essence, du gazole et du fioul dans les pourcentages Produits finis Brut 1 Brut 2 Essence 30 25 suivants : Gazole 40 25 fioul 30 50 La raffinerie doit satisfaire à la demande de : 125 104 tonnes d’essence, 135 104 tonnes de gazole et 180 104 tonnes de fioul 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 ?
• Fixation de l’ objectif : Fixation de l’ objectif : minimisation du coût minz = 700x1 + 500x2 • Mise en équations des contraintes économiques : les variables x1 et x2 vérient 3 contraintes : Contrainte d’essence : 0, 3x1 + 0, 25x2 ≥ 125104 Contrainte de gazole :0, 4x1 + 0, 25x2 ≥ 135104 Contrainte de fioul : 0, 3x1 + 0, 5x2 ≥ 180104 Restriction des signes : contrainte de positivité x1 , x2 ≥ 0 • Modélisation mathématique min z = 700x1 + 500x2 0, 3x1 + 0, 25x2 ≥ 125104 0, 4x1 + 0, 25x2 ≥ 135104 0, 3x1 + 0, 5x2 ≥ 180104 x1 ≥ 0; x2 ≥ 0
7
1.3
Formulation générale d’un PL
– Fonction objectif (économique) :
max (oumin)z = c1 x1 + c2 x2 + · · · + cn xn – Contraintes : a11 x1 + a12 x2 + . . . + a1n xn a21 x1 + a22 x2 + . . . + a2n xn .. .
≤, =, ≥ b1 ≤, =, ≥ b2
am1 x1 + am2 x2 + . . . + amn xn ≤, =, ≥ bm – Contraintes de positivité (non négativité) :
xj ≥ 0
∀ j = 1; · · · ; n
Avec, x j : variables de décision (inconnues) ai,j ; bi ; c j : paramètres du programme linéaire (connues).
1.4
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 × . . . . . . am1 am2 · · · amn n)) 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
8
1.5
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). Remarque 1.2. · Plusieurs solutions optimales sont possibles. · Géométriquement, la région admissible correspond à un polyèdre de Rn (voir chapitre 2 ).
9