Cours [PDF]

Zitiervorschau

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 Participation & Assiduité Examen final

30% 20 % 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 22 2 2n n 2  21 1  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 :

a a . a   x1  b1   11 12 1n  x  b  2 2     X ; C  c1 c2 . cn ; A  . . . . ; B   .  .         am1 am 2 . amn   xn  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 : M1 M2 M3 Gain / unité

A 2 1 0 4

B 1 2 1 5

Stocks 8 7 3

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



Contraintes de non négativité

 x1  0   x2  0

 



 

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 : Formuler le modèle Les coûts unitaires de transport sont : linéaire qui permet de Entrepôts déterminer les quantités à Usines E1 E2 E3 fabriquer pour minimiser U1 6 4 7 les coûts de fabrication et U2 5 3 2 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 : pour E1  x11  x21  1500  pour E2  x12  x22  2000  x  x  1800 pour E3 23  13

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

x3 x1 x2    160 40 160 26

Inéquation 13x18x2  20 x3  83200 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 a < 0; b >0

x2 ≤ ax1 + b 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 a < 0; b >0

x2 ≥ ax1 + b 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) Point

Coordonnée X1

Coordonnée X2

Valeur de la fonction é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 2  1   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 2  1

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 2  1

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  x1  x2  15 2 x  x  20  1 2 SC :   x1  8   x1  0; x2  0

Max Z  15 x1  6 x2  x1  x2  x3  15 2 x  x  x  20 1 2 4   SC :  x1  x5  8  x  0; x  0; x  0 2 3  1   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 x3 x4 x5 Cj-Zj

x1 1 2 1 15

x2 1 1 0 6

x3 1 0 0 0

x4 0 1 0 0

x5 0 0 1 0

b 15 20 8 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 x3 x4 x5 Cj-Zj

x1 1 2 1 15

x2 1 1 0 6

x3 1 0 0 0

15 est le Max (Cj-Zj) Colonne pivot

x4 0 1 0 0

x5 0 0 1 0

b 15 20 8 0

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 x3 x4 x5 Cj-Zj

x1 1 2 1 15

La ligne pivot

x2 1 1 0 6

x3 1 0 0 0 x5 la variable sortante

x4 0 1 0 0

x5 0 0 1 0

b 15 20 8 0

b/a 15/1=15 20/2 =10 8/1=8

Min(bi/aij)=8

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

aij

akj

• Pour la dernière colonne du tableau du simplexe: bk 

akj aij

bi

Les étapes de résolution du programme linéaire Étape 3: pivotage et calcul de la nouvelle valeur de Z Base x3 x4 x5 Cj-Zj

x1 1 2 1 15

x2 1 1 0 6

x3 1 0 0 0

x4 0 1 0 0

x5 0 0 1 0

Le pivot aij

b 15 20 8 0 15 – (1*8)/1 = 7

0 – (2*1)/1 = -2

Base x3 x4 x1 Cj-Zj

x1 0 0 1 0

x2 1 1 0 6

x3 1 0 0 0

x4 0 1 0 0

x5 -1 -2 1 -15

b 7 4 8 -120

Or 6≥0 alors on passe à l’itération suivante

Nouvelle valeur de Z =120 Z s’est bien améliorée

Les étapes de résolution du programme linéaire Itération suivante : x2 la variable entrante

Base x3 x4 x1 Cj-Zj

x1 0 0 1 0

x2 1 1 0 6

La ligne pivot

x3 1 0 0 0

x4 0 1 0 0

x5 -1 -2 1 -15

b 7 4 8 -120

x5 1 -2 1 -3

b 3 4 8 -144

6 est le Max (Cj-Zj)

Colonne pivot

Le pivot aij

x4 la variable sortante

Base x3 x2 x1 Cj-Zj

x1 0 0 1 0

x2 0 1 0 0

x3 1 0 0 0

x4 -1 1 0 -6

b/a 7/1=7 4/1 =4 8/0=∞

Les étapes de résolution du programme linéaire Conclusion : Base x3 x2 x1 Cj-Zj

x1 0 0 1 0

x2 0 1 0 0

x3 1 0 0 0

x4 -1 1 0 -6

x5 1 -2 1 -3

b 3 4 8 -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 2  1

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  SC : 2 x1  x2  9  x  0; x  0 2  1

 x1  x2  x3  7  SC : 2 x1  x2  x4  9  x  0; x  0 2  1

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 2  1

Base x3 x4 Cj-Zj

x1 1 2 12

x2 1 1 12

x3 1 0 0

x4 0 1 0

Problème de choix de la variable entrante !

b 7 9 0

Solution à faire : Base x1 x3 1 x4 2 Cj-Zj 12

x2 1 1 12

x3 1 0 0

x4 0 1 0

b 7 9 0

bi/aij bi/aij 7/1=7 7/1=7 9/2=4,5 9/1=9

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 2  1

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 2 3 4  1 Base x3 x4 Cj-Zj

x1 1 2 8

x2 1 1 5

x3 1 0 0

x4 0 1 0

bi 7 14 0

bi/aij 7/1=7 14/2=7

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 x5  2

La variable x5 ≤ 0, il est impossible alors 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 2  1

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 2  1

1ère itération Base

x1

x2

x3

x4

a1

a2

Cj

1

1

0

0

M

M

a1

M

7

5

-1

0

1

a2

M

1

4

0

-1

9M

-M M

Zj 8M

Cj-Zj 1-8M 1-9M

b

b/a

0

40

8,00

0

1

9

2,25

-M

M

M

M

0

0

Tous les Cj-Zj ne sont pas ≥ 0, alors on passe

à la 2ème itération

49M

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 Cj 1 x1 1 1 x2 1 0 Zj 1 Cj-Zj 0

x2 x3 x4 a1 a2 1 0 0 M M 0 -0,1739 0,2174 0,1739 -0,2174 1 0,0435 -0,3043 -0,043 0,3043 1 -0,1304 -0,0870 0,1304 0,0870 0 0,1304 0,0870 M-0,1304 M-0,0870

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

b 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 SC :  j 1  x  0;  j

Dual :

i  1,2,..., m j  1,2,..., n

m

Min F   bi yi i 1

 m  aij yi  c j SC :  i 1  y  0;  i

j  1,2,..., n i  1,2,..., m

Théorème x1* , x2* ,..., xn* Si le primal a une solution optimale 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

c j 1

m

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 Ressource Bois (plaque) Menuiserie (heure) Finition (heure) Prix de revient (Z)

Bureau

Table

Chaise

8 2 4 60

6 1,5 2 30

1 0,5 1.5 20

Quantité de ressource disponible 48 8 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 x  2 x  1 , 5 x  20 1 2 3    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 Ressource Bois (plaque) Menuiserie (heure) Finition (heure) Prix de revient (Z)

Bureau

Table

Chaise

8 2 4 60

6 1,5 2 30

1 0,5 1,5 20

Quantité de ressource disponible 48 8 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 :  x  x  1 1 2    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 2 3  1

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 x  17 x  4 x  2 x   3 1 2 3 4    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 2 3  1   y1  0; y2  0; y3  0

Détermination de la solution du dual à partir de la solution du primal Programme primal : Min D  50 y1  80 y 2 3 y1  6 2 y  4 y  10  1 2 SC :  2 y1  5 y 2  8   y1  0; y 2  0

Solution du programme primal Base y2 y1 y5 cj-Zj

y1 0 1 0 0

y2 1 0 0 0

y3 1/6 -1/3 1/6 10/3

y4 -1/4 0 -5/4 20

y5 0 0 1 0

bi 3/2 2 7/2 -220

La solution optimale du primal : y1=2, y2=3/2, y3=0, y4=0, y5 = 7/2; Programme dual :

x1 = 10/3

Max Z  6 x1  10 x2  8 x3

x2 = 20

3 x1  2 x2  2 x3  50  SC : 4 x2  xy3  80  x  0; i  1,2,3  i

x3 = 0 x4 = 0 x5 = 0

Z = 220 Remarque : Les valeurs des variables d’écart du primal sont les valeurs des variables du programme dual et vice 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

x6 x3 x1

x1 0 0 1 0

x2 3 1 1 1500

x3 0 1 0 0

x4 x5 1 -2 1 -1 -2 1 120 220

x6 1 0 0 0

200 300 800 -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 successeurs

Dictionnaire des prédécesseurs

a→[b] b→[⊘] c→[⊘] d → [ a, b, c ]

a→[d] b → [ a, d ] c→[d] 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





d’ordre n de terme général :  aij  1 si xi , x j U

  aij  0 sinon

Exemple :

A B C D

A 1 0 0 0

B 1 0 0 1

C 1 0 0 1

D 0 1 0 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 :

U

G1 U G2 = 〈S, A1〉 U 〈S, A1〉 = 〈S, A1 U A2〉

=

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

Produit Deux graphes :

Opérations sur les 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 Par convention :

0

DÉBUT 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 : Durée Tâches Antériorité A B C D E

2 4 4 5 6

A A, B 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ération Construction des voies d’accès Travaux des terrassemets Construction des bâtiments administratifs Commande du matériel électrique Construction de la centrale Construction du barrage Installation des galeries et conduites forcées Montage des machines Essais de fonctionnement

a b

4 6

Opérations prérequises a

c

4

-

d e f

12 10 24

b; c; d b;c

g

7

a

h i

10 3

e; g f; h

Désignation Durée (mois)

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)

TAF:

A B C D E F G

2 8 5 2 6 5 3

A B B E 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 A C B D G E F

Marge libre 0 12 0 0 6 0 0

Marge totale 12 12 0 6 6 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 C D E F G H I J K L M

B A; B B D E;D E C;F G;E I;H;C H;C M;C;F C;F

5 2 3 1 2 6 3 4 1 1 3 1 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

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

Niveau1

Niveau2

Niveau3

Neveau5

Niveau6

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 originedestination. 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 :

1 2 3 Demande (GWh)

A

B

C

D

6 10 7

5 8 9

3 4 11

1 2 12

300

300

300

100

Puissance produite (GWh) 500 300 200

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 : Contraintes de production

Contraintes de consommation

Contraintes de non-négativité

 x11  x12  x13  x14  500   x21  x22  x23  x24  300  x  x  x  x  200 32 33 34  31  x1 1  x2 1  x3 1  300  x  x  x  300  12 22 32   x1 3  x2 3  x3 3  300   x1 4  x2 4  x3 3  100 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 NordOuest 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 est optimale on s'arrête, sinon on refait une autre itération, et ainsi de suite. Dans notre cas on peut prendre la variable x23 comme variable entrante. La valeur de x23 doit être augmentée mais tout en respectant les contraintes d'offre et de demande, ainsi que la non-négativité des autres variables.

ENCG AGADIR 2020-2021

20

2- Résolution du problème de transport II- Recherche de la solution optimale

•Sur le tableau, le cycle ----- indique les variations à effectuer pour sauvegarder une solution de base réalisable. •Un signe ``+'' indique une augmentation de la quantité et un signe ``-'' indique une diminution de la quantité. •En valeur absolue, la variation est la même pour toutes les cases sur le cycle. ENCG AGADIR 2020-2021

21

2- Résolution du problème de transport II- Recherche de la solution optimale Dans notre cas : x23 augmente de 200 unités, x22 diminue de 200 unités, x12 augmente de 200 unités x13 diminue de 200 unités Les résultats obtenus sont :

Z  5200 Ce tableau contient un coût marginal strictement négatif, (-3), donc il ne s'agit pas d'une solution optimale

ENCG AGADIR 2020-2021

22

2- Résolution du problème de transport II- Recherche de la solution optimale pour le tableau précédent, on refait le même travail, afin d'obtenir les résultats suivants :

Z  4800 les coûts marginaux sont strictement positifs, la solution alors est optimale Interprétation de la solution optimale : De la centrale 1 adresser 100 KWh à la ville A, 300 KWh à la ville B et 100 KWh à la ville D. De la centrale 2 adresser 300 KWh à la ville C. De la centrale 3 adresser 200 KWh à la ville A. ENCG AGADIR 2020-2021

23

Merci de votre attention

ENCG AGADIR 2020-2021

24