Cours RO Aazab PDF 2020-2021

Semestre 7 La recherche opérationnelle Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Présentation du syllabus 1. Pré-requis Algèbre linéaire, calcul matriciel et statistique 2. Objectif du cours Ce cours rep...

Semestre 7 La recherche opérationnelle Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Présentation du syllabus 1. Pré-requis Algèbre linéaire, calcul matriciel et statistique 2. Objectif du cours Ce cours représente une introduction à la recherche opérationnelle et ses applications dans le domaine de l’industrie, du transport, de la finance et de la gestion. L’objectif général de ce cours est de mettre à la disposition des encgistes les outils nécessaires à la modélisation et à la résolution des problèmes du monde réel en exploitant des méthodes et techniques mathématiques et numériques de résolution de problèmes d’optimisation et leurs applications en sciences de gestion. ENCG AGADIR 2020-2021 2  Présentation du syllabus Compétences générales visées Le cours de la recherche opérationnelle vise à développer chez les étudiants les qualités suivantes : Développer une démarche scientifique complète de RO ; Formuler et modéliser les problèmes quotidiens de gestion ; Proposer des méthodes d'optimisation ou d'aide à la décision adaptées au contexte ; Exploiter les différentes techniques d’optimisation à la résolution des problèmes. ENCG AGADIR 2020-2021 3  Présentation du syllabus Moyens pédagogiques Manuels pédagogiques de base disponible sous format pdf : Robert Faure, Précis de recherche opérationnelle Méthodes et exercices d’application, Dunod, Paris, 2014.  Notes de cours pour chaque séance ; Apprentissage en hybride (en présentiel et en distanciel) ; Utilisation du vidéo projecteur et du tableau blanc ainsi que d’autres outils d’apprentissage à distance ; Des séries d’exercices sont données aux étudiants avant de les corriger. ENCG AGADIR 2020-2021 4  Présentation du syllabus Plan du cours : Chapitre 1: La Programmation Linéaire Formulation des programmes linéaires Méthode de résolution graphique Méthode de résolution algébrique : Algorithme du simplexe Problème de dualité en programmation linéaire Aspect matriciel de la programmation linéaire Chapitre 2 : Introduction à la théorie des graphes Éléments de théorie des graphes Décomposition des graphes Problèmes d'ordonnancement Introduction Modélisation par un graphe orienté Construction et résolution du diagramme de PERT Diagramme Gantt Problème du plus court chemin Définition du problème de plus court chemin dans un graphe Algorithmes de résolution ENCG AGADIR 2020-2021 5  Présentation du syllabus Évaluation Travaux à rendre 30% Participation & Assiduité 20 % Examen final 50 % TOTAL 100% ENCG AGADIR 2020-2021 6  Introduction générale Définitions de la Recherche Opérationnelle : La RO peut se définir comme « la mise en œuvre de méthodes scientifiques, essentiellement mathématiques, en vue de prendre la meilleure décision possible. » Association Française de Recherche Opérationnelle et d'Aide à la Décision (2011) La RO peut se définir comme «la science de la bonne gestion. C’est un ensemble des domaines scientifiques traitant des questions d’ordre décisionnel ou d’optimisation de systèmes complexes.» La Fédération Européenne de Recherche Opérationnelle Exemples : chercher un itinéraire sur une carte, ordonnancement des tâches, la décision stratégique en finance … ENCG AGADIR 2020-2021 7  Introduction générale Histoire : les problèmes de RO remontent au XVIème siècle (Blaise Pascal, Euler,...) avec les jeux en Mathématiques. Origine de la méthode : Domaine militaire (l'implantation optimale de radars de surveillance durant la 2ème guerre mondiale) Domaine d’application : La gestion de projets : problèmes d'ordonnancement et de planification de projets, problèmes de logistique et de transport et problèmes d'emploi du temps... L’industrie manufacturière : plans de productions (ordonnancement ), problèmes de découpe (optimisation des ressources), optimisation du conditionnement et la livraison… La finance : les problèmes de financement et d'investissement (maximiser le profit et/ou minimiser les coûts)… … ENCG AGADIR 2020-2021 8  Introduction générale Étapes générales d’un problème de RO Étape 1: observation, collecte des données et formulation du problème. Étape 2 : construction d’un modèle scientifique (formulation mathématique). Étape 3 : résoudre le problème en testant le modèle développer en donnant une solution optimale. ENCG AGADIR 2020-2021 9  Chapitre 1 : la programmation linéaire Définition En mathématiques, les problèmes de programmation linéaire (PL) est la recherche de l’optimum (minimum ou maximum) d’une fonction d’objectif linéaire liées par des équations ou inéquations linéaires appelées contraintes. La fonction d’objectif On appelle fonction d’objectif, ou fonction économique, d’un problème d’optimisation le critère de choix entre les diverses solutions possibles. Les contraintes On appelle contraintes du problème toutes les relations limitant le choix des valeurs possibles des variables. Ce sont des restrictions de nature techniques, économiques ou logiques. 1- Formulation mathématique d’un programme linéaire La forme générale d’un problème linéaire : M ax ou M inZ  c1 x1  c2 x2 ...  cn xn Sous contraintes : a11x1  a12x 2 ...  a1n x n , ,  b1 a x  a x ...  a x , ,  b  21 1 22 2 2n n 2 a 31x1  a 32x 3 ...  a 3n x n , ,  b3  ...  a m1 x1  a m2 x 2 ...  a mn x n , ,  bm   x j  0 ; j  1,2,..., n contraintes de non négativité   1- Formulation mathématique d’un programme linéaire La forme générale d’un problème linéaire : Z : la fonction économique (fonction d’objectif); c1, c2, …, cn : les coefficients des variables de la fonction Z x1, x2, …, xn : les variables inconnues du modèle; a11, a12, …, amn : les coefficients des variables pour les contraintes du modèle; b1, b2, …, bm : les quantités disponibles de chaque ressource. 1- Formulation mathématique d’un programme linéaire La forme matricielle d’un problème linéaire : M ax ou M inZ  CX Sous contraintes : AX , ,  B avec :  x1  a a. a  b1  x   11 12 1n  b  X  2 .     ; C  c1 c2. cn ; A ....    ; B  2 .         xn   am1 am 2. amn  bm  Étapes de construction d’un programme linéaire : 1- identifier les variables associées au problème ; 2- formuler les contraintes qui délimitent les valeurs que peuvent prendre les variables ; 3- Formuler la fonction économique linéaire qui mesure l’efficacité des variables. Exemple d’application (1) Soit une firme produisant deux biens A et du B avec trois types de matières premières M1, M2 et M3, selon le tableau suivant : A B Stocks M1 2 1 8 M2 1 2 7 M3 0 1 3 Gain / unité 4 5 Formuler le modèle linéaire qui permet de déterminer les quantités à produire pour maximiser le gain par unité Exemple d’application (1) Solution : 1- identification des variables : Les variables sont les quantités x1 et x2 des biens fabriqués A et B. 2- formulation des contraintes : Quelques soient les quantités produites des deux biens, il ne faut pas dépasser les quantités de matières premières disponibles dans les stocks  2 x1  x2  8 pour M 1   Contraintes techniques    x1  2 x2  7 pour M 2   Ou de capacité :   x2  3 pour M 3    x1  0 Contraintes de non   x2  0 négativité Exemple d’application (1) Solution : 3- identification de la fonction d’objectif (fonction économique) : L’objectif de cette firme est de maximiser la fonction Z qui représente le gain : Le gain du bien A est de 4x1 Le gain du bien A est de 5x2 Donc Z= 4x1 + 5x2 Exemple d’application (1) Solution : Programme linéaire est de : Max Z  4 x1  5 x2 2 x1  x2  8 x  2x  7   1 2 SC :  x2  3 x  0  1   x2  0  Exemple d’application (2) Une entreprise peut utiliser 2 usines pour fabriquer un certain produit. La capacité de fabrication de chaque usine en temps régulier est la suivante : Usines Capacités en unités Coût unitaire U1 1800 7 U2 2200 6 L’entreprise alimente 3 entrepôts dont les capacités maximales de stockage : Entrepôts Capacité de stockage en unités E1 1500 E2 2000 E3 1800 Question : Les coûts unitaires de transport sont : Formuler le modèle Entrepôts linéaire qui permet de Usines E1 E2 E3 déterminer les quantités à U1 6 4 7 fabriquer pour minimiser U2 5 3 2 les coûts de fabrication et du transport. Exemple d’application (2) Solution : 1- identification des variables : Nous avons 2 usines pour produire des quantités d’un bien destinées à être stockées dans 3 entrepôts. Donc, xij est la quantité en unités expédiées par l’usine i à l’entrepôt j. avec i=1,2 et j=1,2,3. 2- formulation des contraintes : Contraintes relatives à la capacité de production des usines :  x11  x12  x13  1800 pour U1   x21  x22  x23  2200 pour U2 Contraintes relatives à la capacité de stockage des entrepôts :  x11  x21  1500 pour E1   x12  x22  2000 pour E2  x  x  1800 pour E3  13 23  Exemple d’application (2) Solution : Contraintes de non négativité : x11, x12 , x13, x21, x22 , x23  0 3- identification de la fonction d’objectif (fonction économique) : L’objectif de cette firme est de minimiser la fonction Z qui représente le coût du transport et de fabrication : Coût du transport : 6 x11  4 x12  7 x13  5x21  3x22  2 x23 Coût de fabrication : 7x11  x12  x13   6x21  x22  x23  La fonction Z : 6 x11  4 x12  7 x13  5x21  3x22  2 x23  7x11  x12  x13   6x21  x22  x23   Exemple d’application (3) Solution : Programme linéaire est de : Min Z  6 x11  4 x12  7 x13  5 x21  3x22  2 x23  7x11  x12  x13   6x21  x22  x23   x11  x12  x13  1800  x  x  x  2200  21 22 23  x11  x21  1500 SC :   x12  x22  2000  x13  x23  1800   x11, x12 , x13 , x21, x22 , x23  0 Merci de votre attention ENCG AGADIR 2020-2021 23  Semestre 7 La recherche opérationnelle Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1 EXERCICE 1 Un producteur artisanal fabrique des articles de poterie et des articles d’émaux sur cuivre. Sachant que : - Il faut 1 heure de temps de fabrication pour une poterie et 4 heures pour un émail, la charge de travail pour les émaux ne doit pas dépasser celle de la poterie de plus de 160 heures. - La production d’articles de poterie ne doit pas excéder de plus de 30 unités la production d’émaux. - Le nombre total d’articles fabriqués ne doit pas être supérieur à 80 unités par jour. -Le bénéfice est de 20 DH pour une poterie et de 60 DH pour les émaux sur cuivre. TAF : Modéliser le problème du plan de travail journalier optimal de cette entreprise sous forme d’un programme linéaire. ENCG AGADIR 2020-2021 2 EXERCICE 1 : Solution 1- identification des variables : Soient : x : le nombre d’articles de poterie; y : le nombre d’articles d’émaux sur cuivre; Z : le bénéfice généré par cette fabrication. 2- formulation des contraintes : La charge de travail pour les émaux ne doit pas dépasser celle de la poterie de plus de 160 heures, soit : 4 y  x  160 La production d’articles de poterie ne doit pas excéder de plus de 30 unités la production d’émaux, soit : x  y  30 Le nombre d’articles fabriqués ne doit pas excéder 80 unités par jour, soit : x  y  80 ENCG AGADIR 2020-2021 3 EXERCICE 1 : Solution Contraintes de non négativité : x0 ; y0 3- identification de la fonction d’objectif (fonction économique) : L’objectif ici est d’avoir un bénéfice global maximum sachant que le bénéfice est de 20 DH pour une poterie et de 60 DH pour un émail. Il s’agit donc de maximiser la fonction : Z  20 x  60 y ENCG AGADIR 2020-2021 4 EXERCICE 1 : Solution Programme linéaire est de : Max Z  20 x  60 y 4 y  x  160  x  y  30   SC :  x  y  80 x  0   y  0 EXERCICE 2 Un atelier peut fabriquer trois types d’articles : - l’article A1 à la cadence de 40 objets à l’heure ; - l’article A2 à la cadence de 65 objets à l’heure ; - l’article A3 à la cadence de 26 objets à l’heure. Mais A1 rapporte net 30 DH, A2 20 DH et A3 40 DH. D’autre part, on dispose d’une machine unique pour fabriquer ces trois articles avec une capacité de 160 heures par mois. La capacité d’absorption du marché étant limité, on ne peut écouler par mois, plus de 6000 objets de type A1, ni plus de 6500 objets de type A2, ni plus de 2000 objets de type A3. TAF : Formuler le programme linéaire ENCG AGADIR 2020-2021 6 EXERCICE 2 : Solution 1- identification des variables : Soient : x1 : le nombre d’objets de l’article A1 ; x2 : le nombre d’objets de l’article A2; x3 : le nombre d’objets de l’article A3; Z : le bénéfice net généré par cette fabrication. 2- formulation des contraintes : Contraintes du marché, soit : x1  6000 x2  6500 x3  2000 Contrainte de capacité de production x1 x2 x3 Inéquation    160 13x18x2  20 x3  83200 40 160 26 simplifiée ENCG AGADIR 2020-2021 7 EXERCICE 2 : Solution Contraintes de non négativité : x1  0 ; x2  0; x3  0 3- identification de la fonction d’objectif (fonction économique) : L’objectif est d’avoir un bénéfice net global maximum, alors : Z  30 x1  20 x2  40 x3 ENCG AGADIR 2020-2021 8 EXERCICE 2 : Solution Programme linéaire est de : Max Z  30 x1  20 x2  40 x3  x1  6000  x  6500  2  x3  2000  SC : 13 x1 8 x2  20 x3  83200 x  0  1  x2  0   x3  0 EXERCICE 3 Une entreprise fabrique des pièces en inox, de trois types A, B et C; elles sont fabriquées par lot de 50 dans un grand atelier où sont rassemblées deux machines de découpe de l’inox, une emboutisseuse et deux polisseuses ; chaque machine fonctionne 120 heures par mois. Les caractéristiques de fabrication sont rassemblées dans le tableau suivant : Coût horaire Lot A Lot B Lot C Découpe 20 DH 1h 1,5h 1,5h Emboutissage 30 DH 0,5h 1h Polissage 40 DH 2h 1h 1h Inox (mat. première) 50 DH 85 DH 68 DH Prix de vente 200 DH 200 DH 210 DH TAF : Formuler le programme linéaire ENCG AGADIR 2020-2021 10 EXERCICE 3 : Solution 1- identification des variables : Soient : x : le nombre de lots de pièces de type A ; y : le nombre de lots de pièces de type B ; z : le nombre de lots de pièces de type C; Z : le bénéfice net généré par cette fabrication. 2- formulation des contraintes : Contraintes de production, soit : Découpe : x  1,5 y  1,5 z  2 120  240 Emboutissage : 0,5 x  z  120 Polissage : 2 x  y  z  2 120  240 Contraintes de non négativité : x  0 ; y  0; z  0 ENCG AGADIR 2020-2021 11 EXERCICE 3 : Solution 3- identification de la fonction d’objectif (fonction économique) : Nous avons des coûts et des ventes, l’objectif alors est de maximiser le bénéfice net mensuel qui est égal aux ventes moins les coûts. Pour les ventes : 200 x  200 y  210 z ENCG AGADIR 2020-2021 12 EXERCICE 3 : Solution 3- identification de la fonction d’objectif (fonction économique) : Pour les coûts : Coût de MP : 50 x  85 y  68z Coût heures découpe: 20  x  1,5 y  1,5z   20 x  30 y  30 z Coût heures emboutissage: 30  0,5x  1z   15x  30 z Coût heures polissage: 40  2 x  y  z   80 x  40 y  40 z ENCG AGADIR 2020-2021 13 EXERCICE 3 : Solution 3- identification de la fonction d’objectif (fonction économique) : Coût total: 165x  155 y  168z L’expression du bénéfice total est alors : Z = Ventes – Coût total Z  200 x  200 y  210 z   165 x  155 y  168 z   35 x  45 y  42 z ENCG AGADIR 2020-2021 14 EXERCICE 2 : Solution Programme linéaire est de : Max Z  35 x  45 y  42 z  x  1,5 y  1,5 z  240 0,5 x  z  120   2 x  y  z  240 SC :  x  0 y  0   z  0 Merci de votre attention ENCG AGADIR 2020-2021 16  Semestre 7 La recherche opérationnelle Résolution d’un pRogRamme linéaiRe Méthode géométrique Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1 Plan : Introduction Rappel de géométrie analytique La solution optimale Applications : Cas d’une seule solution possible Cas de solutions multiples Cas des problèmes à solution infinie Cas des problèmes à aucune solution possible ENCG AGADIR 2020-2021 2 Introduction La méthode géométrique ou graphique n'est pas utilisée en pratique, par contre, elle permet de visualiser certains concepts qui seront très utiles lors du développement de la méthode du simplexe. Dans le cas de la méthode géométrique, les problèmes portent sur les modèles à deux variables. La géométrie des problèmes à deux variables permet une meilleur compréhension des situations qui peuvent se présenter pour des modèles à n variables ENCG AGADIR 2020-2021 3 Rappel de géométrie analytique Une contrainte à deux variables a la forme : a11x1  a12 x2 , ,  b1 Donc pour la résolution géométrique d’un modèle linéaire à deux variables, nous nous intéresserons au plan x1x2 dont x1 constitue l’axe des abscisses et x2 constitue l’axe des ordonnées. Ensuite, on détermine l’ensemble des points (x1,x2) dont les coordonnées satisfont les contraintes d’un problème de programmation linéaire. On représente l’équation de la droite x2=ax1 + b (a est la pente de la droite et b est l’ordonnée à l’origine). ENCG AGADIR 2020-2021 4 L’inéquation x2≤ ax1 + b représente un demi-plan fermé composé de tous les points sur et sous la droite x2=ax1 + b. x2 x2 x1 x1 x2 ≤ ax1 + b x2 ≤ ax1 + b a > 0; b >0 a < 0; b >0 ENCG AGADIR 2020-2021 5 L’inéquation x2≥ ax1 + b représente un demi-plan fermé composé de tous les points sur et sous la droite x2=ax1 + b. x2 x2 x1 x1 x2 ≥ ax1 + b x2 ≥ ax1 + b a > 0; b >0 a < 0; b >0 ENCG AGADIR 2020-2021 6 L’inéquation x1 = α représente une droite parallèle à l’axe x2 x2 x2 α x1 α x1 x1 ≤ α x1 ≥ α ENCG AGADIR 2020-2021 7 L’inéquation x2 = β représente une droite parallèle à l’axe x1 x2 x2 β β x1 x1 x2 ≤ β x2 ≥ β ENCG AGADIR 2020-2021 8 La solution optimale La recherche de l’optimum d’un programme linéaire consiste d’abord à déterminer les solutions satisfont (solutions réalisables) aux contraintes du programme. Ces solutions forment un ensemble convexe. La solution qui optimise la fonction économique est un point extrême de cet ensemble convexe. Ce point extrême est nécessairement sur la frontière de l’ensemble convexe. ENCG AGADIR 2020-2021 9 Application 1 : Résoudre le programme linéaire suivant (méthode graphique) Max Z  x1  2 x2 2 x1  x2  4 x  x  8   1 2 SC :  x1  x2  4 x  5  1   x1  0; x2  0 Solution: Solution: (Une seule solution possible) Valeur de la fonction Point Coordonnée X1 Coordonnée X2 économique (Z) B 2 0 2 H 5 0 5 A 0 4 8 F 5 3 11 E 2 6 14 O 0 0 Hors solutions réalisables C 0 8 Hors solutions réalisables D 8 0 Hors solutions réalisables G 5 9 Hors solutions réalisables Le point extrême qui optimise la fonction économique est x1=2; x2=6 et Z=14 ENCG AGADIR 2020-2021 12 Application 2 : Résoudre le programme linéaire suivant (méthode graphique) Max Z  16 x1  2 x2 6 x1  x2  0  x  12   2 SC : 8 x1  x2  60 4 x  x  24  1 2   x1  0; x2  0 Solution: (Solutions multiples) La droite de la fonction économique (en rouge) coïncide avec l’une des bornes de la région convexe Solution: (Solutions multiples) Point Coordonnée X1 Coordonnée X2 Valeur de la fonction objective (Z) O 0 0 0 A 2 12 56 I 6 0 96 D 6 12 120 H 7 4 120 B 4,29 25,71 Hors solutions réalisables C 0 12 Hors solutions réalisables E 9 12 Hors solutions réalisables F 0 60 Hors solutions réalisables G 7,5 0 Hors solutions réalisables Deux points extrêmes qui optimisent la fonction économique est (x1=6; x2=12) et (x1=7; x2=4) et Z=120 ENCG AGADIR 2020-2021 15 Application 3 : Résoudre le programme linéaire suivant (méthode graphique) Max Z  x1  2 x2  x1  x2  2  SC :  x2  3  x  0; x  0  1 2 Solution: ( problèmes à solution infinie) Graphiquement, ce problème est caractérisé par le fait qu’on peut déplacer la droite de la fonction objectif indéfiniment de manière à accroître la valeur, en gardant toujours une intersection non vide avec l’ensemble des solutions réalisables. Application 4 : Résoudre le programme linéaire suivant (méthode graphique) Max Z  4 x1  3 x2  x1  x2  2  SC : 3 x1  x2  10  x  0; x  0  1 2 Solution : ( Aucune solution possible) Merci de votre attention ENCG AGADIR 2020-2021 20  Semestre 7 La recherche opérationnelle Résolution d’un pRogRamme linéaiRe Méthode du simplexe (méthode des tableaux) Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1 Introduction L'algorithme du simplexe est un algorithme de résolution des problèmes d'optimisation linéaire. La méthode du simplexe s’applique seulement à un système de contraintes sous forme d’équations. La méthode du Simplexe est une procédure itérative qui permet d'améliorer la résolution de la fonction objectif à chaque étape. Le processus se termine lorsque vous ne pouvez pas continuer à améliorer la valeur, c'est-à-dire, on a atteint la solution optimale (la valeur la plus élevée ou la plus basse possible, selon le cas). Introduction La forme initiale d’un programme linéaire, où une ou toutes les contraintes sont sous forme des inéquations, est appelée forme canonique. Un programme linéaire (PL) mis sous la forme particulière où toutes les contraintes sont des équations et toutes les variables sont non négatives est dit PL sous forme standard. Un programme linéaire sous forme canonique peut toujours se transformer sous forme standard en transformant les inéquations en équations par l’ajout des variables appelées variables d’écart. Variables d’écart Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire, ce programme linéaire doit être converti en un programme équivalent où toutes les contraintes technologiques sont des équations et toutes les variables sont non négatives. 1- Contraintes de type (≤) : Pour chaque contrainte i de ce type, on rajoute une variable d’écart xi, tel que xi ≥ 0 Exemple : Appelée également variable d’excédent 3x1  2 x2  18 se transforme en 3x1  2 x2  x3  18 Avec x3 ≥ 0 Variables d’écart 2- Contraintes de type (≥) : Pour chaque contrainte i de ce type, on retranche une variable d’écart xi, tel que xi ≥ 0 Exemple : 3x1  2 x2  18 se transforme en 3x1  2 x2  x3  18 Avec x3 ≥ 0 Remarques : Les variables d’écart ont une interprétation physique pour chaque contrainte où elles sont introduites. La variable d’écart aura la même unité de mesure que la ressource de la contrainte où elle est introduite. Variables de base et variables hors base Considérons un système d’équations à n variables et m équations où n ≥ m. Une solution de base pour ce système est obtenue de la manière suivante : a) On pose n-m =0. Ces variables sont appelées variables hors base (V.H.B.). b) On résout le système pour les m variables restantes. Ces variables sont appelées les variables de base (V. B.) c) Le vecteur de variables obtenu est appelé solution de base (il contient les variables de base et les variables hors base) Une solution de base est admissible si toutes les variables de la solution de base sont positive. Solutions admissibles Toute solution de base du PL sous forme standard pour laquelle toutes les variables sont non négatives, est appelée solution de base admissible. Cette solution de base admissible correspond à un point extrême. Les étapes de résolution du programme linéaire Cas pratique : problème de maximisation Résoudre le PL suivant par la méthode du simplexe Max Z  15 x1  6 x2  x1  x2  15 2 x  x  20  1 2 SC :   x1  8   x1  0; x2  0 Les étapes de résolution du programme linéaire Étape 1: transformer le PL de la forme canonique à la forme standard : Max Z  15 x1  6 x2 Max Z  15 x1  6 x2  x1  x2  x3  15  x1  x2  15 2 x  x  x  20 2 x  x  20  1 2 4  1  SC :  x1  x5  8 2 SC :   x1  8  x  0; x  0; x  0   x1  0; x2  0  1 2 3   x4  0; x5  0 Nous avons ajouté des variables d’écart : x3; x4 et x5. x3, x4, et x5 sont les variables de base (V.B). x1, et x2 sont les variables hors base (V.H.B). Les étapes de résolution du programme linéaire Formation du tableau initial Il s’agit de la première itération qui consiste à déterminer la solution de base (solution initiale). A partir de la forme standard, nous avons 3 contraintes et 5 variables. En égalant (5-3)=2 variables à zéro, nous obtenons une solution de base. Par conséquent, en égalant les variables principales à zéro : x1=0 et x2=0, la solution réalisable est : x3=15, x4=20 et x5=8. Avec cette solution initial Z=0 Base x1 x2 x3 x4 x5 b x3 1 1 1 0 0 15 x4 2 1 0 1 0 20 x5 1 0 0 0 1 8 Cj-Zj 15 6 0 0 0 0 Les étapes de résolution du programme linéaire Première itération Étape 1: choix de la variable entrante (dans la base) Étape 2 : choix de la variable sortante (de la base) Étape 3 : pivotage et calcul de la nouvelle valeur de Z Étape 4: si tous les Cj-Zj ≤ 0, alors la solution obtenue est optimale et on arrête les calculs, sinon on passe à la 2ème itération et on recommence l’étape 1. Les étapes de résolution du programme linéaire Première itération Étape 1: choix de la variable entrante (dans la base) La variable hors base qui va entrer dans la base correspond au maximum des Cj-Zj (pour des problèmes de max). Alors Max(Cj-Zj)=15,par conséquent, la variable entrante est x2 x1 la variable entrante Base x1 x2 x3 x4 x5 b x3 1 1 1 0 0 15 x4 2 1 0 1 0 20 x5 1 0 0 0 1 8 Cj-Zj 15 6 0 0 0 0 15 est le Max (Cj-Zj) Colonne pivot Les étapes de résolution du programme linéaire Première itération Étape 2: choix de la variable sortante (de la base) Dans un problème de min OU de max, la variable sortante sera le minimum des bi/aij (pour les aij>0) Alors Min(bi/aij)=8,par conséquent, la variable sortante est x5 Base x1 x2 x3 x4 x5 b b/a x3 1 1 1 0 0 15 15/1=15 x4 2 1 0 1 0 20 20/2 =10 x5 1 0 0 0 1 8 8/1=8 Cj-Zj 15 6 0 0 0 0 x5 la variable Min(bi/aij)=8 La ligne pivot sortante Les étapes de résolution du programme linéaire Première itération Étape 3: pivotage et calcul de la nouvelle valeur de Z Le pivot c’est l’intersection entre la colonne pivot et la ligne pivot Le pivotage s’effectue de la manière suivante : On commence par diviser la ligne du pivot par le chiffre du pivot. On applique la procédure d’élimination de Gauss-Jordan autour du pivot : L Lk  i akj aij Pour la dernière colonne du tableau du simplexe: akj bk  bi aij Les étapes de résolution du programme linéaire Étape 3: pivotage et calcul de la nouvelle valeur de Z Base x1 x2 x3 x4 x5 b x3 1 1 1 0 0 15 x4 2 1 0 1 0 20 x5 1 0 0 0 1 8 Cj-Zj 15 6 0 0 0 0 Le pivot aij 15 – (1*8)/1 = 7 0 – (2*1)/1 = -2 Base x1 x2 x3 x4 x5 b Nouvelle x3 0 1 1 0 -1 7 valeur de Z x4 0 1 0 1 -2 4 =120 x1 1 0 0 0 1 8 Z s’est bien améliorée Cj-Zj 0 6 0 0 -15 -120 Or 6≥0 alors on passe à l’itération suivante Les étapes de résolution du programme linéaire Itération suivante : x2 la variable entrante Base x1 x2 x3 x4 x5 b b/a x3 0 1 1 0 -1 7 7/1=7 x4 0 1 0 1 -2 4 4/1 =4 x1 1 0 0 0 1 8 8/0=∞ Cj-Zj 0 6 0 0 -15 -120 La ligne pivot 6 est le Max (Cj-Zj) Colonne pivot Le pivot aij x4 la variable sortante Base x1 x2 x3 x4 x5 b x3 0 0 1 -1 1 3 x2 0 1 0 1 -2 4 x1 1 0 0 0 1 8 Cj-Zj 0 0 0 -6 -3 -144 Les étapes de résolution du programme linéaire Conclusion : Base x1 x2 x3 x4 x5 b x3 0 0 1 -1 1 3 x2 0 1 0 1 -2 4 x1 1 0 0 0 1 8 Cj-Zj 0 0 0 -6 -3 -144 Tous les Cj-Zj sont inférieurs ou égaux à 0. Donc la solution et optimale, cette solution est définie par : Solution optimale x1 =8 x2=4 Z=144 Les étapes de résolution du programme linéaire Exercice 1: problème de maximisation Résoudre le PL suivant par la méthode du simplexe Max Z  7 x1  9 x2  18 x3  17 x4 2 x1  4 x2  5 x3  7 x4  42  x  x  2 x  2 x  17  1 2 3 4 SC :   x1  2 x2  3 x3  3 x4  24   x1  0; x2  0; x3  0; x4  0 Merci de votre attention ENCG AGADIR 2020-2021 19  Semestre 7 La recherche opérationnelle Cas particuliers du simplexe Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1 Plan : Cas 1 : les coefficients de la fonction économique sont égaux Cas 2 : égalité des plus petits rapports positifs Cas 3 : ajout des variables artificielles Cas 4 : méthode du grand M ( cas de la minimisation) Cas 1 : les coefficients de la fonction économique sont égaux Exemple : Max Z  12 x1  12 x2  x1  x2  7  SC : 2 x1  x2  9  x  0; x  0  1 2 Transformation du PL de la forme canonique à la forme standard : Max Z  12 x1  12 x2 Max Z  12 x1  12 x2  x1  x2  7  x1  x2  x3  7   SC : 2 x1  x2  9 SC : 2 x1  x2  x4  9  x  0; x  0  x  0; x  0  1 2  1 2 Nous avons ajouté des variables d’écart : x3; x4 et x5. x3 et x4 sont les variables de base (V.B). x1, et x2 sont les variables hors base (V.H.B). Formation du tableau initial Max Z  12 x1  12 x2  x1  x2  x3  7  SC : 2 x1  x2  x4  9  x  0; x  0  1 2 Base x1 x2 x3 x4 b x3 1 1 1 0 7 x4 2 1 0 1 9 Cj-Zj 12 12 0 0 0 Problème de choix de la variable entrante ! Solution à faire : Base x1 x2 x3 x4 b bi/aij bi/aij x3 1 1 1 0 7 7/1=7 7/1=7 x4 2 1 0 1 9 9/2=4,5 9/1=9 Cj-Zj 12 12 0 0 0 Je compare les rapports (bi/aij) les plus petits (4,5 et 7) et je retiens la variable entrante pour laquelle le rapport est le plus élevé des deux. Par conséquent, la variable entrante est x2 et la variable sortante est x3 Cas 2 : égalité des plus petits rapports positifs Exemple : Max Z  8 x1  5 x2  x1  x2  7  SC : 2 x1  x2  14  x  0; x  0  1 2 Formation du tableau initial Max Z  8 x1  5 x2  x1  x2  x3  7  SC : 2 x1  x2  x4  14  x  0; x  0; x  0; x  0  1 2 3 4 Base x1 x2 x3 x4 bi bi/aij x3 1 1 1 0 7 7/1=7 x4 2 1 0 1 14 14/2=7 Cj-Zj 8 5 0 0 0 On calcule la somme de tous les coefficients aij par ligne de variable de base et on divise le résultat par le pivot de la ligne : Pour x3 : (1+1+1+0)/1=3 Pour x4 : (2+1+0+1)/2=2 On retient le plus grand des deux rapports, le pivot est par conséquent celui qui correspond a ce grand rapport Cas 3 : Ajout des variables artificielles Exemple : forme canonique Max Z  8 x1  5 x2  x1  x2  7 2 x  x  14  1 2 SC :   x1  x2  2   x1  0; x2  0 Cas 3 : Ajout des variables artificielles Exemple : Forme standard Max Z  8 x1  5 x2  x1  x2  x3  7 2 x  x  x  14  1 2 4 SC :   x1  x2  x5  2   xi  0; i  1,2,3,4,5 x1  x2  0 x3  7 x4  14 La variable x5 ≤ 0, il est impossible alors x5  2 de trouver de solution de départ évidente Cas 3 : Ajout des variables artificielles Solution : ajouter une variable artificielle  x1  x2  x3  7 2 x  x  x  14   1 2 4  x1  x2  x5  a1  2 a1 est la variable artificielle  x  0; i  1,2,3,4,5  i  a1  0 x1  x2  x5  0 (V.H.B ) x3  7   x4  14V.B a1  2   Cas 4 : MÉTHODE DU GRAND M ( ou des pénalités ) Cette méthode permet de tenir compte des variables artificielles. On les pénalise en leur affectant un coefficient de valeur très élevée dans la fonction économique (- M pour un problème à maximum, + M pour un problème à minimum). Les pénalités ont pour objet de provoquer l'élimination des variables artificielles au fil des itérations. Normalement, à l'optimum (s'il existe) les variables artificielles sont hors base. Si celles-ci sont à l'optimum dans la base, avec une valeur non nulle, le programme n'a pas de solution. Exemple : Résoudre le PL suivant par la méthode du simplexe Min Z  x1  x2 7 x1  5 x2  40  SC :  x1  4 x2  9  x  0; x  0  1 2 Règles des itérations dans le cas de la minimisation Étape 1: choix de la variable entrante (dans la base) La variable hors base qui va entrer dans la base correspond au Minimum des Cj-Zj Étape 2 : choix de la variable sortante (de la base) Même règle que la maximisation Étape 3 : pivotage et calcul de la nouvelle valeur de Z Mêmes procédures que la maximisation Étape 4: si tous les Cj-Zj ≥ 0, alors la solution obtenue est optimale et on arrête les calculs, sinon on passe à la 2ème itération et on recommence l’étape 1. Forme standard Min Z  x1  x2  0 x3  0 x4  Ma1  Ma2 7 x1  5 x2  x3  a1  40  SC :  x1  4 x2  x4  a2  9  x  0; x  0  1 2 1ère itération Base x1 x2 x3 x4 a1 a2 b b/a Cj 1 1 0 0 M M a1 M 7 5 -1 0 1 0 40 8,00 a2 M 1 4 0 -1 0 1 9 2,25 Zj 8M 9M -M -M M M Cj-Zj 1-8M 1-9M M M 0 0 49M Tous les Cj-Zj ne sont pas ≥ 0, alors on passe à la 2ème itération  2ème itération Base x1 x2 x3 x4 a1 a2 b b/a Cj 1 1 0 0 M M a1 M 5,75 0 -1 1,25 1 -1,25 28,8 5,0 x2 1 0,25 1 0 -0,25 0 0,25 2,25 9,0 Zj 5,75M+0,25 1 -M 1,25M-0,25 M -1,25M+0,25 Cj-Zj -5,75M+0,75 0 M -1,25M+0,25 0 2,25M-0,25 28,8M+2,25 Tous les Cj-Zj ne sont pas ≥ 0, alors on passe à la 2ème itération 3ème itération Base x1 x2 x3 x4 a1 a2 b Cj 1 1 0 0 M M x1 1 1 0 -0,1739 0,2174 0,1739 -0,2174 5 x2 1 0 1 0,0435 -0,3043 -0,043 0,3043 1 Zj 1 1 -0,1304 -0,0870 0,1304 0,0870 Cj-Zj 0 0 0,1304 0,0870 M-0,1304 M-0,0870 6 Tous les Cj-Zj ≥ 0, alors la solution obtenue est optimale et on arrête les calculs, avec : x1 = 5 x2 = 1 Z  x1  x2  5  1  6 Merci de votre attention ENCG AGADIR 2020-2021 19  Semestre 7 La recherche opérationnelle La dualité Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1 Plan :  Principe de base de la dualité  Applications du théorème de dualité  Le dual d'un problème de maximisation  Détermination de la solution du dual à partir de la solution du primal Principe de base : Associer au programme linéaire initial, appelé primal, un deuxième programme linéaire appelé le programme dual tel que : le dual a m variables (autant que de contraintes industrielles dans le primal) il a n contraintes industrielles (autant que de variables dans le primal) le dual est un problème de minimisation pour toute solution du dual et toute solution du primal, l’objectif du dual est supérieur ou égal à celui du primal Principe de base : Primal : n Max Z   c j x j j 1  n  aij x j  bi i  1,2,..., m SC :  j 1  x  0; j  1,2,..., n  j Dual : m Min F   bi yi i 1  m  aij yi  c j j  1,2,..., n SC :  i 1  y  0; i  1,2,..., m  i Théorème Si le primal a une solution optimale x1* , x2* ,..., xn* alors le dual a une solution optimale y1* , y2* ,..., yn* et, pour ces solutions, l’objectif du primal est égal à l’objectif du dual : n m c j 1 j x   bi y * j i 1 * i Applications du théorème de dualité Si le primal a beaucoup de contraintes et moins de variables, le simplexe sera plus efficace sur le problème dual! Le dernier dictionnaire du simplexe nous donnera simultanément une solution optimale pour le primal et pour le dual. Interprétation économique : la solution optimale du dual nous dira s’il est intéressant d’investir plus pour augmenter certaines ressources. Exemple 1 : Le dual d'un problème de maximisation Une usine fabrique des bureaux, des tables et des chaises. La fabrication de chaque type de produit nécessite de la matière première (plaques en bois) et deux types d’activités : menuiserie et finition. La quantité requise de chaque ressource est donnée comme suit : Produit Bureau Table Chaise Quantité de ressource Ressource disponible Bois (plaque) 8 6 1 48 Menuiserie (heure) 2 1,5 0,5 8 Finition (heure) 4 2 1.5 20 Prix de revient (Z) 60 30 20 Détermination du programme primal L’objectif est maximiser les recettes. Par conséquent, Variables de décision : x1 = nombre de bureaux fabriqués x2 = nombre de tables fabriquées x3 = nombre de chaises fabriquées MaxZ  60 x1  30 x2  20 x3 8 x1  6 x2  x3  48 (ressource bois) 2 x  1,5 x  0,5 x  8 (ressource menuiserie)  1 2 3 SC :  (ressource finition)  4 x1  2 x 2  1,5 x3  20   xi  0; i  1,2,3 Programme primal Détermination du programme Dual Supposons qu'un entrepreneur veut acheter toutes les ressources de l’usine (bois, heure menuiserie, heure finition). Il veut certainement que le prix total de ces ressources soit minimal. Produit Bureau Table Chaise Quantité de ressource Ressource disponible Bois (plaque) 8 6 1 48 Menuiserie (heure) 2 1,5 0,5 8 Finition (heure) 4 2 1,5 20 Prix de revient (Z) 60 30 20 Détermination du programme Dual On définit alors : y1 = prix d'une plaque de bois y2 = prix d'une heure de menuiserie y3 = prix d'une heure de finition L'entrepreneur doit payer : D = 48y1 + 8 y2 + 20 y3 Mais doit minimiser D. Également, il doit payer suffisamment pour convaincre l’usine de vendre ses ressources. Par exemple, il doit dépenser au moins 60 pour une combinaison de : 8 plaques de bois + 2 heures de menuiserie + 4 heures de finition car l’usine peut utiliser ces ressources pour fabriquer un bureau et le vendre pour 60. L'entrepreneur doit payer au moins 60, sinon l’usine ne verra aucune raison de lui vendre ses ressources :  8y1 + 2 y2 + 4 y3  60 De même on a : 6y1 + 1,5 y2 + 2 y3  30 y1 + 0,5 y2 + 1,5 y3  20 avec y1, y2, y3  0 (coûts fictifs) Le problème dual est ainsi le suivant : MinD  48 y1  8 y2  20 y3 8 y1  2 y2  4 y3  60 6 y  1,5 y  2 y  30  1 2 3 SC :   y1  0,5 y2  1,5 y3  20   yi  0; i  1,2,3 Remarques : Primal (Dual) Dual (Primal) Fonction à maximiser Fonction à minimiser ième contrainte  ième variable  0 ième contrainte  ième variable  0 ième contrainte = ième variable ≠ 0 jème variable  0 jème contrainte  jème variable  0 jème contrainte  jème variable ≠ 0 jème contrainte = Application Déterminer le programme dual du programme primal suivant : Max Z  2 x1  x2  x1  x2  2 2 x  x  3  1 2 SC :   x1  x 2  1   x1  0; x2  0 Solution Min D  2 y1  3 y2  y3  y1  2 y2  y3  2  SC :  y1  y2  y3  1  y  0; y  0; y  0  1 2 3 Application Déterminer le programme dual de chaque programme primal suivant : Min Z  5 x1  6 x2  7 x3  x4  x1  2 x2  x3  x4  7 6 x  3 x  x  7 x  14  1 2 3 4 SC :    2 x1  17 x 2  4 x3  2 x 4  3   x1  0; x2  0; x3  0; x4  0 Solution Max D  7 y1  14 y2  3 y3  y1  6 y2  2 y3  5 2 y  3 y  17 y  6   1 2 3 SC :  y1  y2  4 y3  7  y  7 y  2 y  1  1 2 3   y1  0; y2  0; y3  0 Détermination de la solution du dual à partir de la solution du primal Programme primal : Solution du programme primal Min D  50 y1  80 y 2 Base y1 y2 y3 y4 y5 bi 3 y1  6 y2 0 1 1/6 -1/4 0 3/2 2 y  4 y  10  1 2 y1 1 0 -1/3 0 0 2 SC :  2 y1  5 y 2  8 y5 0 0 1/6 -5/4 1 7/2   y1  0; y 2  0 cj-Zj 0 0 10/3 20 0 -220 La solution optimale du primal : y1=2, y2=3/2, y3=0, y4=0, y5 = 7/2; Programme dual : x1 = 10/3 Z = 220 Max Z  6 x1  10 x2  8 x3 x2 = 20 Remarque : Les valeurs des 3 x1  2 x2  2 x3  50 x3 = 0 variables d’écart du primal  sont les valeurs des variables SC : 4 x2  xy3  80 x4 = 0  x  0; i  1,2,3 du programme dual et vice  i x5 = 0 versa. Application Trouver le programme dual et sa solution à partir du programme primal suivant : Min Z  340 x1  24006 x2  560 x3  x1  2 x2  x3  1100  x  3 x  2 x  1400  1 2 3 SC :   x1  x2  3 x3  1500   x1 , x2 , x3  0 x1 x2 x3 x4 x5 x6 x6 0 3 0 1 -2 1 200 x3 0 1 1 1 -1 0 300 x1 1 1 0 -2 1 0 800 0 1500 0 120 220 0 -440000 Merci de votre attention ENCG AGADIR 2020-2021 20  Semestre 7 La recherche opérationnelle La théorie des graphes Introduction générale Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Plan Notions élémentaires Le graphe non-orienté Le graphe orienté Le chemin dans un graphe orienté Un sous-graphe Un graphe partiel Modes de représentation d’un graphe Représentation sagittale Représentation par dictionnaire (liste) Représentation matricielle Opérations sur les graphes Union Intersection Complément Inverse Produit ENCG AGADIR 2020-2021 2  Notions élémentaires Un graphe non-orienté G = (X, U) est la donnée de deux ensembles : - Un ensemble X = {x1, x2, · · · , xn} dont les éléments sont appelés sommets ; - Un sous-ensemble U ⊂ X×X noté U = {u1, u2, · · · , um} dont les éléments sont appelés arêtes. Exemple : Sommets : X = {a, b, c, d} Arêtes : U = {u1, u2, u3, u4} ENCG AGADIR 2020-2021 3  Notions élémentaires Une arête est représentée par un ensemble de deux sommets. u1 ={a, b} ; u2= {b, d} … Un sommet qui n’apparaît dans aucune arête est dit isolé : le sommet « e » est isolé. Si {a, b} ∈ U, les sommets a et b sont dits adjacents. Exemple : U = {{a, b}, {b, d}, {d, c}, {a, d}} ENCG AGADIR 2020-2021 4  Notions élémentaires Un graphe orienté est un graphe où les U sont appelés arcs. Pour un arc u = (xi, xj), le sommet xi s’appelle extrémité initiale (ou origine) et xj son extrémité finale (ou destination). Dans l’arc (xi, xj), on dit que le sommet xj est un successeur de xi. On dit aussi que le sommet xi est un prédécesseur de xj. Exemple : Pour u1 :  a est l’origine et b est la destination  b est le successeur de a  a est le prédécesseur de b ENCG AGADIR 2020-2021 5  Notions élémentaires Lorsque xi = xj , l’arc (xi, xi) s’appelle une boucle. Un arc privé de son orientation s’appelle une arête. Deux sommets sont dits adjacents s’ils sont joints par un arc (ou une arête), et deux arcs sont dits adjacents s’ils ont au moins une extrémité commune. Exemple :  L’arc (a, a) est une boucle  u1 et u2, sont adjacents (b est l’extrémité commune)  u2, u3 et u4 sont adjacents (d est l’extrémité commune) ENCG AGADIR 2020-2021 6  Notions élémentaires Le degré d’un sommet xi, noté deg.xi, est le nombre d’arêtes ou d’arcs dans lesquels xi apparaît, (les boucles comptant pour 2). Le degré d’un graphe est le degré du sommet qui a le degré le plus élevé. Exemple : Deg. a =0 ; Deg. b =4; Deg. c =3; Deg. d =2 et Deg. e =3 Deg. G = Deg. b =4 Graphe G ENCG AGADIR 2020-2021 7  Notions élémentaires Chemins Un chemin dans un graphe orienté est une séquence (suite) de sommets et d’arcs telle que 1. la séquence débute par un sommet et se termine par un sommet; 2. les sommets et les arcs alternent; 3. chaque arc est précédé par son sommet origine et est suivi par son sommet cible ; 4. aucun arc n’apparaît plus d’une fois. La longueur d’un chemin est le nombre d’arcs de ce chemin Exemple : (b, (b, c), c, (c, e),e, (e, c), c) est un chemin (b, (b, c), c, (c, e),e, (e, c), c, (c, e),e) n’est pas un chemin longueur de (c,(c, e), e) = 1 Longueur de (b, (b, c), c, (c, e),e, (e, c), c) = 3 ENCG AGADIR 2020-2021 8  Notions élémentaires Chemins Un chemin pourrait aussi être décrit en donnant seulement la séquence d’arcs. Ex: (b, c, e, d) Un chemin simple est un chemin dans lequel aucun sommet n’apparaît plus d’une fois, sauf que le premier et le dernier peuvent être les mêmes. Ex : (b), (b, c, e, d), (c, e, c) sont des chemins simples du graphe ci-dessous. mais pas (b, c, e, c). Un chemin est un cycle s’il contient au moins un arc et que le premier et le dernier sommet du chemin sont identiques. Ex : (c, e, c) est un cycle. Graphe G ENCG AGADIR 2020-2021 9  Notions élémentaires Un sous-graphe est obtenu par suppression d’un certain nombre de sommets (et par conséquent de tous les arcs qui leur sont liés). Un graphe partiel est obtenu par suppression d’un certain nombre d’arcs. Exemple : Un sous graphe de G obtenu par la suppression du sommet b Un graphe partiel de G obtenu par la suppression de l’arc u2 Graphe G ENCG AGADIR 2020-2021 10  Modes de représentation d’un graphe 1- Représentation sagittale Pour un graphe orienté fini, chaque sommet est représenté par un point du plan, chaque arc par une flèche reliant le sommet origine au sommet extrémité. Exemple : Graphe de 4 sommets et 5 arcs ENCG AGADIR 2020-2021 11  Modes de représentation d’un graphe 2- Représentation par dictionnaire (liste) Il s’agit d’un tableau à entrée simple où chaque ligne correspond à un sommet et comporte la liste de ses prédécesseurs (dictionnaire des prédécesseurs) ou de ses successeurs (dictionnaire des successeurs). Exemple : Dictionnaire des Dictionnaire des successeurs prédécesseurs a→[b] a→[d] b→[⊘] b → [ a, d ] c→[⊘] c→[d] d → [ a, b, c ] d→[⊘] ENCG AGADIR 2020-2021 12  Modes de représentation d’un graphe 3- Représentation matricielle Considérons un graphe G = (X, U) contenant n sommets. La matrice d’adjacence (ou matrice booléenne) est une matrice carrée aij  1 si xi , x j U d’ordre n de terme général :     aij  0 sinon  Exemple : A B C D A 1 1 1 0 B 0 0 0 1 C 0 0 0 0 D 0 1 1 0 ENCG AGADIR 2020-2021 13  Opérations sur les graphes Soient les deux graphes orientés suivants : (S : sommets ; A : Arcs) G2 G1 G1 = 〈S, A1〉 G2 = 〈S, A1〉 Leurs matrices sont : M1 = M1 = ENCG AGADIR 2020-2021 14  Opérations sur les graphes Union Deux graphes : G1 U G2 = 〈S, A1〉 U 〈S, A1〉 = 〈S, A1 U A2〉 U = Deux matrices : l’union des matrices est obtenue en faisant la disjonction des entrées correspondantes ENCG AGADIR 2020-2021 15  Opérations sur les graphes Intersection Deux graphes : G1 ⋂ G2 = 〈S, A1〉 ⋂ 〈S, A1〉 = 〈S, A1 ⋂ A2〉 ⋂ = Deux matrices : l’intersection des matrices est obtenue en faisant la conjonction des entrées correspondantes ENCG AGADIR 2020-2021 16  Opérations sur les graphes Complément Le complément d’un graphe : ~G = ~ 〈S, A〉 = 〈S, ~A〉 Le complément d’une matrice est obtenu en faisant la négation des entrées. ENCG AGADIR 2020-2021 17  Opérations sur les graphes Inverse Le complément d’un graphe : G-1 = 〈S, A〉-1 = 〈S, A-1〉 L’inverse d’une matrice est obtenu en transposant la matrice. ENCG AGADIR 2020-2021 18  Opérations sur les graphes Produit Deux graphes : G1 ° G2 = 〈S, A1〉 ° 〈S, A1〉 = 〈S, A1 ° A2〉 Le produit des matrices est obtenu en faisant une opération similaire au produit matriciel en algèbre linéaire ENCG AGADIR 2020-2021 19  Rappel sur les relations sous forme matricielle Les propriétés des relations se transposent aux matrices à partir de leur définition. Totalité : au moins un 1 par ligne Déterminisme (fonction) : au plus un 1 par ligne Surjectivité : au moins un 1 par colonne Injectivité : au plus un 1 par colonne Application : exactement un 1 par ligne Application bijective : exactement un 1 par ligne et par colonne ENCG AGADIR 2020-2021 20  Rappel sur les relations sous forme matricielle Exemples : ENCG AGADIR 2020-2021 21 Merci de votre attention ENCG AGADIR 2020-2021 22  Semestre 7 La recherche opérationnelle La théorie des graphes problèmes d’ordonnancement Méthode MPM Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Plan Introduction Méthode MPM Les conditions de la méthode Principe Construction du graphe MPM Lecture d'un graphe MPM Détermination des dates « au plus tôt » et « au plus tard » Le chemin critique Calcul des marges Exemple d’application exercice ENCG AGADIR 2020-2021 2  Introduction Le problème tout projet est de déterminer dans quel ordre doivent s’enchaîner les diverses tâches de manière à minimiser le temps d’exécution du projet. Les méthodes d'ordonnancement des tâches permettent d'avoir une représentation graphique (immuable ou non) d'une réalisation en représentant chaque opération (ou tâche) par un arc, une liaison, ou un rectangle qui peut être proportionnel ou non à la durée. Ce graphique dans tous les cas permet le positionnement relatif des opérations dans le temps. ENCG AGADIR 2020-2021 3  Introduction L’objectif est d’ordonner dans le temps un ensemble d’opérations contribuant à la réalisation d’un même projet (construction d’un bâtiment, lancement d’un produit,... etc ). Le déroulement de ces diverses tâches doit respecter certaines contraintes de type : - contrainte de succession stricte, - contrainte de date. ENCG AGADIR 2020-2021 4  Introduction Il s’agit donc de minimiser la durée totale de réalisation du projet compte tenu des durées nécessaires à la réalisation de chaque opération et des contraintes qu’elles doivent respecter. Le problème ainsi pos´e peut être schématisé sous forme d’un graphe sans circuit selon deux modes : - la méthode M.P.M. (Méthode des potentiels Metra), appelée également méthode graphe-tâches ; - la méthode PERT (Programm Evaluation Research Task), appelée également méthode graphe-étapes ENCG AGADIR 2020-2021 5  Méthode MPM Définition : La Méthode des Potentiels et antécédents Métra (MPM) est une méthode d’ordonnancement basée sur la théorie des graphes, et visant à optimiser la planification des tâches d'un projet. L’objectif de cet outil est de permettre d'ordonnancer, de hiérarchiser, de classer un très grand nombre de tâches en fonction de contraintes d'antériorité ou de succession qui peuvent évoluer. Dans le graphe, il y a inversion de représentation : le nœud devient « tâche », l’arc devient contrainte d’antériorité. ENCG AGADIR 2020-2021 6  Méthode MPM Les conditions préalables à la construction du graphe MPM La méthode MPM suit une démarche logique qui impose au préalable de satisfaire les étapes suivantes : Établir une liste des tâches à réaliser et déterminer la durée de chaque tâche. Pour chacune des tâches, déterminer les tâches précédentes (relations d'antécédence et de succession). Identifier les tâches dépendantes (qui ne peuvent commencer que si certaines autres tâches sont exécutées partiellement ou terminées). Identifier les tâches pouvant être réalisées simultanément (sous réserve d'une disponibilité des ressources nécessaires). ENCG AGADIR 2020-2021 7  Méthode MPM Principe : Le graphe pour ce mode de représentation est construit comme suit : Chaque tâche xi est représentée par un sommet i. Toute relation d’antériorité immédiate est représentée par un arc. La longueur l(i, j) d’un arc (i, j) est égale à la durée minimale qui doit s’écouler entre le début de la tâche xi et le début de la tâche xj. Lorsque les contraintes sont uniquement de type ”succession stricte”, cette longueur est égale à la durée de la tâche origine xi. ENCG AGADIR 2020-2021 8  Méthode MPM Construction du graphe MPM : Le graphe MPM est ordonné par niveaux (graphe sans circuit). Chaque sommet sera représenté par un rectangle de type : Nom de la tâche Durée de la tâche Date au plutôt Date au plus tard DÉBUT Par convention : 0 Date au plus tard FIN Par convention : Date au plutôt = Date au plus tard ENCG AGADIR 2020-2021 9 Lecture d'un graphe MPM : Le graphe se lit de gauche à droite (du sommet "DÉBUT" à celui de "FIN"). Chaque sommet symbolise une tâche. Les arcs entre les sommets traduisent uniquement les relations d'antériorité des tâches. D'un même sommet peuvent donc partir plusieurs flèches, lorsque la tâche correspondante est immédiatement antérieure à plusieurs tâches indépendantes. ENCG AGADIR 2020-2021 10 DÉTERMINATION DES DATES « AU PLUS TÔT » DANS UN RÉSEAU MPM La détermination des dates au plus tôt des différentes sommets se fait par calculs successifs, à partir du sommet "Début" (dont, par convention, la date au plus tôt est fixée à 0). La durée minimale du projet correspond donc à la date au plus tôt du sommet "Fin". La date au plus tôt d'un réseau MPM correspond à la date à laquelle une tâche peut commencer au plus tôt. Elle s'obtient très simplement en ajoutant à la date au plus tôt de la tâche précédente la durée de la tâche en question : Date au plus tôt tâche T = Date au plus tôt tâche S + Durée tâche S "S" représente l'ensemble des tâches immédiatement antérieures à "T" ENCG AGADIR 2020-2021 11 DÉTERMINATION DES DATES « AU PLUS TÔT » DANS UN RÉSEAU MPM Remarque : Lorsque plusieurs arcs arrivent à un même sommet (c'est-à-dire que plusieurs tâches sont immédiatement antérieures à la tâche considérée), il convient, d'effectuer ce calcul pour toutes les tâches précédant la tâche en question et de retenir comme "date au plus tôt" de cette dernière le maximum des valeurs ainsi trouvée (en effet, cette tâche ne pourra vraiment débuter que lorsque toutes les tâches qui lui sont immédiatement antérieures auront été terminées). La formule précédente devient donc : Date au plus tôt tâche T = Max. (Date plus tôt tâches S + Durée tâches S) ENCG AGADIR 2020-2021 12 DÉTERMINATION DES DATES « AU PLUS TARD» DANS UN RÉSEAU MPM La détermination des dates au plus tard des différentes tâches se fait à rebours du graphe, par calculs successifs, en partant du sommet "Fin" (pour lequel, par convention, on considère que la date au plus tard est égale à sa date au plus tôt). La date au plus tard d'un réseau MPM correspond à la date à laquelle une tâche doit être exécutée au plus tard pour ne pas remettre en cause la durée optimale totale du projet. Elle s'obtient en retirant de la date au plus tard de la tâche qui lui succède sa propre durée : Date au plus tard tâche S = Date au plus tard tâche T - durée tâche S "S" représente l'ensemble des tâches immédiatement antérieures à "T" ENCG AGADIR 2020-2021 13 DÉTERMINATION DES DATES « AU PLUS TARD» DANS UN RÉSEAU MPM Remarque : Lorsque plusieurs arcs partent d'un même sommet (i.e. que plusieurs tâches succèdent à une tâche donnée), il convient de faire ce calcul pour toutes les tâches succédant à la tâche en question et de retenir comme "date au plus tard" de de cette dernière le minimum des valeurs ainsi trouvées : Date au plus tard tâche S = Min. (date au plus tard tâches T - durée tâche S) ENCG AGADIR 2020-2021 14 LE CHEMIN CRITIQUE On appelle chemin critique la succession des tâches pour lesquels aucun retard n'est possible sans remettre en cause la durée optimale du projet (tâches pour lesquelles date au plus tôt = date au plus tard). ENCG AGADIR 2020-2021 15 LES MARGES D'UNE TÂCHE DANS UN RÉSEAU MPM On appelle "marge" d'une tâche le retard qu'il est possible de tolérer dans la réalisation de celle-ci, sans que la durée optimale prévue du projet global en soit affectée. Il est possible de calculer trois types de marges : Marge totale tâche S = Date plus tard tâche S - Date plus tôt tâche S Marge certaine tâche S = Max [ 0 , Min (Date au plus tôt tâche T - Date au plus tard tâche S - Durée tâche S) ] Marge libre tâche S = Date plus tôt tâche T - Date plus tôt tâche S - Durée tâche S ENCG AGADIR 2020-2021 16  Exemple : Les différentes tâches nécessaires à la réalisation d’un projet, leur durée et leurs relations d'antériorité sont résumées dans le tableau suivant : Tâches Durée Antériorité A 2 - B 4 - C 4 A D 5 A, B E 6 C,D 1. Déterminer la durée minimale d’exécution du projet 2. Déterminer le calendrier de début d’exécution (au plus tôt et au plus tard) des différentes tâches 3. Déterminer le chemin critique 4. Calculer les différentes marges ENCG AGADIR 2020-2021 17  Exemple : Le diagramme MPM du projet Le chemin en rouge est le chemin critique du projet ENCG AGADIR 2020-2021 18  Exemple : Calcul des marges : - Marge totale de A = (2 - 0) = 2 -Marge totale de C = (5 - 2) = 3 - Marge libre de A = Min [(2 - 0 - 2) , (4 - 0 - 2)] = Min [0, 2] = 0 - Marge libre de C = (9 - 2 - 4) = 3 - - Marge certaine de A = Max [0, Min ( [2 - 2 - 2], [4 - 2 - 2] ) ] = Max [0, Min (-2, 0)] = 0 - Marge certaine de C = Max [0, (9 - 5 - 4)] = 0 ENCG AGADIR 2020-2021 19  Exercice: Les opérations mises en jeu dans la construction d’un ensemble hydro-électrique sont notées par les lettres a, b, · · · , i. On suppose que toutes les contraintes sont de type contraintes de succession. Les données du problème sont résumées dans le tableau suivant : Opérations pré- Opération Désignation Durée (mois) requises Construction des voies d’accès a 4 - Travaux des terrassemets b 6 a Construction des bâtiments c 4 - administratifs Commande du matériel électrique d 12 Construction de la centrale e 10 b; c; d Construction du barrage f 24 b;c Installation des galeries et conduites g 7 a forcées Montage des machines h 10 e; g Essais de fonctionnement i 3 f; h ENCG AGADIR 2020-2021 20  Exercice: TAF : 1. Déterminer la durée minimale d’exécution du projet 2. Déterminer le calendrier de début d’exécution (au plus tôt et au plus tard) des différentes tâches 3. Déterminer le chemin critique 4. Calculer les différentes marges ENCG AGADIR 2020-2021 21 Merci de votre attention ENCG AGADIR 2020-2021 22  Semestre 7 La recherche opérationnelle La théorie des graphes problèmes d’ordonnancement Méthode PERT Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Plan Introduction Définition Principe Construction du graphe PERT Le chemin critique Exemple d’application exercice ENCG AGADIR 2020-2021 2  Introduction Le PERT (Programm of Evaluation and Review Technic) est, comme la MPM, une technique d'ordonnancement basée sur la théorie des graphes, visant à optimiser la planification des tâches d'un projet. Cette technique a été à l’origine une méthode crée par la marine américaine dans les années 50 sous l'appellation initiale de méthode CPM (Critical Method Path) pour coordonner les tâches des milliers d'entreprises impliquées dans son projet "Polaris" (programme de développement de missiles à ogive nucléaire). Compte tenu de son efficacité elle s'est ensuite rapidement étendue à toute l’industrie américaine puis occidentale. ENCG AGADIR 2020-2021 3 Définition : Le PERT (Programm Evaluation Research Task) peut se définir comme une méthode consistant à ordonnancer sous forme de réseau un ensemble de tâches qui grâce à leur dépendance et à leur chronologie concourent à l’atteinte d’un objectif. Autrement dit, pour traduire la logique d’exécution d’un projet, la méthode PERT consiste à représenter sous forme de réseau des étapes reliées par des tâches en exprimant toutes les relations ou contraintes existant entre ces tâches. ENCG AGADIR 2020-2021 4 Principe : Le graphe pour ce mode de représentation est construit comme suit : Chaque tâche x est représentée par un arc (i, j) dont la longueur est égale à la durée de la tâche. Chaque sommet du graphe est une étape signifiant que : - toutes les tâches qui arrivent sont achevées, - toutes les tâches qui partent peuvent commencer. Remarque : Il est parfois nécessaire d'introduire des "tâches fictives " (de valeur 0) pour traduire correctement sur un graphe les relations d'antériorité de certaines tâches, notamment lorsque celles-ci partagent avec d'autres une partie de leurs antécédents. ENCG AGADIR 2020-2021 5 Principe : Réduire la durée totale d'un projet par une analyse détaillée des tâches ou activités élémentaires et de leur enchainement. On étudie les délais sans prendre en compte les charges. La réalisation d'un projet implique l'exécution de certaines tâches dans un ordre donné, compte tenu, des relations existant entre elles. Ces relations de dépendance sont de deux ordres: 1 - Relations logiques On ne peut commencer une tâche avant que la précédente ne soit terminée. 2 - Relation d'ordre spéculatif L'entrainement du réseau est alors défini par contraintes (souvent la contrainte principale est le délai) Construction du graphe PERT: La construction d'un graphe PERT consiste à procéder par "niveau" : -déterminer les tâches sans antécédent (tâches de niveau 1) et les relier à l'étape de « Début » - identifier ensuite les tâches de niveau 2, c'est-à-dire celles dont les antécédents sont exclusivement du niveau 1 et les positionner sur le graphique en fonction de des derniers, - … continuer ainsi, jusqu'à ce que toutes les tâches aient pu être positionnées entre elles et relier celles n'ayant pas de descendant à l'étape de « Fin » ENCG AGADIR 2020-2021 7 Construction du graphe PERT: ENCG AGADIR 2020-2021 8 Détermination des dates « au plus tôt » dans un réseau PERT Date au plus tôt tâche T = Date au plus tôt tâche S + Durée tâche S Lorsque plusieurs arcs arrivent à un même sommet : Date au plus tôt tâche T = Max. (Date plus tôt tâches S + Durée tâches S) Détermination des dates « au plus tard» dans un réseau PERT Date au plus tard tâche S = Date au plus tard tâche T - durée tâche S Lorsque plusieurs arcs partent d'un même sommet : Date au plus tard tâche S = Min. (date au plus tard tâches T - durée tâche S) "S" représente l'ensemble des tâches immédiatement antérieures à "T" ENCG AGADIR 2020-2021 9 LE CHEMIN CRITIQUE On appelle chemin critique la succession des tâches pour lesquels aucun retard n'est possible sans remettre en cause la durée optimale du projet (tâches pour lesquelles date au plus tôt = date au plus tard). ENCG AGADIR 2020-2021 10 LES MARGES D'UNE TÂCHE DANS UN RÉSEAU MPM On appelle "marge" d'une tâche le retard qu'il est possible de tolérer dans la réalisation de celle-ci, sans que la durée optimale prévue du projet global en soit affectée. Il est possible de calculer trois types de marges : Marge totale tâche S = Date plus tard tâche S - Date plus tôt tâche S Marge certaine tâche S = Max [ 0 , Min (Date au plus tôt tâche T - Date au plus tard tâche S - Durée tâche S) ] Marge libre tâche S = Date plus tôt tâche T - Date plus tôt tâche S - Durée tâche S ENCG AGADIR 2020-2021 11  Exemple : Les différentes tâches nécessaires à la réalisation d’un projet, leur durée et leurs relations d'antériorité sont résumées dans le tableau suivant : Tâche Durée Antécédent(s) A 2 - B 8 - C 5 A D 2 B E 6 B F 5 E TAF: G 3 A,D 1. Construire le graphique. 2. Déterminer les dates au plus Tôt 3. Déterminer les dates au plus tard 4. Mettre en évidence le chemin Critique 5. Calculer la marge libre de chacune des tâches 6. Calculer la marge totale de chacune des tâches ENCG AGADIR 2020-2021 12  Exemple : Montage du réseau en utilisant les liens de dépendance (les antécédents) La tâche en pointillés est qualifiée de fictive. ENCG AGADIR 2020-2021 13  Exemple : Détermination des dates au plus tôt ENCG AGADIR 2020-2021 14  Exemple : Détermination des dates au plus tard ENCG AGADIR 2020-2021 15  Exemple : Chemin critique ENCG AGADIR 2020-2021 16  Exemple : Calcul des marges Tâche Marge libre Marge totale A 0 12 C 12 12 B 0 0 D 0 6 G 6 6 E 0 0 F 0 0 ENCG AGADIR 2020-2021 17  Exercice: Un projet a été décomposé en tâches comme le montre le suivant: Taches Taches Antérieures Durée En Jours A B 5 B - 2 C A; B 3 D B 1 E D 2 F E;D 6 G E 3 H C;F 4 I G;E 1 J I;H;C 1 K H;C 3 L M;C;F 1 M C;F 5 TAF: 1.Déterminez le niveau de chacune tâches (annexe 1) 2.Construire le graphique. 3.Déterminer les dates au plus Tôt 4.Déterminer les dates au plus tard 5.Mettre en évidence le chemin Critique 6.Calculer la marge libre de chacune des tâches 7.Calculer la marge totale de chacune des tâches Annexe 1 Tâches Niveau0 Niveau1 Niveau2 Niveau3 Neveau5 Niveau6 A B B - C A; B D B E D F E;D G E H C;F I G;E J I;H;C K H;C L M;C;F M C;F Merci de votre attention ENCG AGADIR 2020-2021 21  Semestre 7 La recherche opérationnelle La théorie des graphes Problème de transport Pr. A. LAHFIDI Pr. A. AAZZAB ENCG AGADIR 2020-2021 1  Plan Introduction 1- Représentation du problème de transport A- Formulation sous la forme d’un tableau de transport B- Formulation mathématique sous la forme d’un programme linéaire C- Formulation sous la forme de graphe bipartie 2- Résolution du problème de transport I- Recherche de la solution initiale a) La méthode du coin Nord-Ouest b) La méthode du moindre coût II- Recherche de la solution optimale ENCG AGADIR 2020-2021 2  Introduction Le problème du transport est un programme linéaire qui a une structure particulière. Cette classe de PLs englobe les problèmes qui s'énoncent dans une forme approximative à celle-ci : Il y a m origines et n destinations, dans chaque origine on dispose d'une certaine quantité de matières premières (ou produit donné), et dans chaque destination on demande une certaine quantité de ce produit. Le coût de transport est différent pour chaque couple origine- destination. On cherche un plan de transport optimal dans le sens qu'il minimise le coût total de transport. ENCG AGADIR 2020-2021 3  Introduction L'usage des tableaux de simplexe dans le cas des problèmes de transport est bien entendu possible. Toutefois, cette alternative ne présente pas un réel intérêt pratique car les problèmes de transport aboutissent généralement à un grand nombre de variables et de contraintes. Heureusement, une représentation intuitive et permettant un traitement facile des problèmes de transport existe : il s'agit du tableau de transport. ENCG AGADIR 2020-2021 4 1- Représentation du problème de transport Un problème de transport peut être représenté de trois manières : – Sous la forme d’un tableau de transport ; – Sous la forme d’un programme linéaire ; – Sous la forme d’un graphe biparties. ENCG AGADIR 2020-2021 5 A- Formulation sous la forme d’un tableau de transport Exemple: Soit une série de villes (A, B, C, D) alimentées en électricité par des centrales (1, 2, 3). La situation est résumée par la table suivante : Puissance A B C D produite (GWh) 1 6 5 3 1 500 2 10 8 4 2 300 3 7 9 11 12 200 Demande 300 300 300 100 (GWh) Interprétation du tableau : Dans ce problème, on a trois origines et quatre destinations. Les offres des origines sont inscrites sur la dernière colonne, et les quantités disponibles dans les différentes destinations sont inscrites sur la dernière ligne. Les chiffres inscrits en petite taille dans chaque case indiquent les coûts de transport unitaires entre chaque origine et chaque destination. Par exemple, chaque unité transportée de l'origine 2 vers la destination C induit un coût de transport de 4(um). Remarquons que dans ce tableau l'offre totale est égale à la demande totale. On dit que ce problème est équilibré. Si le problème n'est pas équilibré, on est dans le cadre d'un cas particulier des problèmes de transport. ENCG AGADIR 2020-2021 7 B- Formulation mathématique sous la forme d’un programme linéaire Soit la variable xij définit par le nombre de GWh produits à la centrale i et envoyé à la ville j. La fonction économique Z consiste à minimiser le coût du transport : MinZ  6 x11  5 x12  4 x13  1x14  10 x21  8 x22  4 x23  2 x24  7 x31  9 x32  11x33  12 x34 B- Formulation mathématique sous la forme d’un programme linéaire Les contraintes :  x11  x12  x13  x14  500   x21  x22  x23  x24  300 Contraintes de production  x  x  x  x  200  31 32 33 34  x1 1  x2 1  x3 1  300 Contraintes de  x  x  x  300  12 22 32 consommation   x1 3  x2 3  x3 3  300   x1 4  x2 4  x3 3  100 Contraintes de non-négativité xij  0 C- Formulation sous la forme de graphe bipartie 2- Résolution du problème de transport I- Recherche de la solution initiale Une solution de base pour un problème de transport avec m origines et n destinations doit contenir exactement : (m+n-1) variables de base. Dans notre l'exemple on doit donc avoir dans tous les tableaux correspondants 6 variables de base. Il y a plusieurs méthodes qui permettent d'obtenir une solution initiale. Nous présentons les deux méthodes les plus fréquemment utilisées : a)La méthode du coin Nord-Ouest b)La méthode du moindre coût ENCG AGADIR 2020-2021 11 2- Résolution du problème de transport a)Solution initiale selon la méthode du coin Nord-Ouest Les étapes de le méthode : Partir du coin supérieur gauche du tableau. 1.Allouer le plus possible à la cellule courante et ajuster l’offre et la demande ; 2.Se déplacer d’une cellule vers la droite (demande nulle) ou le bas (offre nulle) ; 3.Répéter jusqu’au moment où toute l’offre est allouée et toute la demande est satisfaite. ENCG AGADIR 2020-2021 12 2- Résolution du problème de transport Le coût total correspondant à cette solution est de : Z  (300  6)  (200  5)  (100  8)  (200  4)  (100 11)  (100 12)  6700 ENCG AGADIR 2020-2021 13 2- Résolution du problème de transport a) Solution initiale selon la méthode du coin Nord- Ouest L'avantage principal de la méthode du coin nord-ouest est la facilité de mise en œuvre. L'inconvénient majeur de cette méthode est qu'elle ne tient pas compte de la structure de coût. Généralement, mais pas systématiquement, elle aboutit à un coût total initial assez élevé. ENCG AGADIR 2020-2021 14 2- Résolution du problème de transport a) Solution initiale selon la méthode du moindre coût L’idée consiste à exploiter les cases ayant des coûts de transport faibles et leur attribuer les quantités maximales (dans la mesure du possible). Les étapes de le méthode : Repérer la case du tableau ayant le coût le plus faible ; 1. Affecter à cette case la quantité maximale possible ; une colonne ou une ligne est saturée : 1.1 Si une colonne est saturée, l'éliminer du tableau, mettre à jour la quantité dans la ligne correspondante et reprendre au point 1 avec le nouveau tableau ; 1.2 Si une ligne est saturée, l'éliminer du tableau, mettre à jour la quantité dans la colonne correspondante et reprendre au point 1 avec le nouveau tableau ; Lorsque toutes les lignes et toutes les colonnes sont saturées, le tableau doit contenir exactement (m+n-1) variables de base. ENCG AGADIR 2020-2021 15 2- Résolution du problème de transport Le coût total correspondant à cette solution est de : Z  (100  5)  (300  3)  (100 1)  (100 10)  (200  8)  (200  7)  5500 ENCG AGADIR 2020-2021 16 2- Résolution du problème de transport II- Recherche de la solution optimale Afin de trouver le tableau optimal, on procède comme dans le simplexe classique. La première étape consiste à calculer les coûts marginaux pour les variables hors-base. Il s'agit des δij comme indiqué dans le tableau suivant : Tableau à exploiter : tableau de solution initiale selon la méthode du moindre coût ENCG AGADIR 2020-2021 17 2- Résolution du problème de transport II- Recherche de la solution optimale Ce calcul se fait en trois étapes: 1. Pour chaque variable de base écrire l'équation : cij  ui  v j 2. Résoudre le système obtenu en fixant : ui  0 3. Calculer les valeurs des coûts marginaux à partir du système :  ij  cij  ui  v j Remarque : Il est pratique d'effectuer ce calcul directement sur le tableau de transport. ENCG AGADIR 2020-2021 18 2- Résolution du problème de transport II- Recherche de la solution optimale Ce tableau contient des coûts marginaux strictement négatifs, et donc il ne s'agit pas d'une solution optimale ENCG AGADIR 2020-2021 19 2- Résolution du problème de transport II- Recherche de la solution optimale Si la solution