MATHEMATIQUES #1 - marcajp.pagesperso-orange.frmarcajp.pagesperso-orange.fr/france/chap14par01/pdfIntec205Maths/... · • Convention usuelle (Maths) • Notre convention (Tableur)

(c) JP Marca pour CNAM INTEC

UV205 UV205 MATHEMATIQUES #1


• Mettre en oeuvre les outils mathématiques sur lesquels s'appuient les méthodes quantitatives de gestion

• Utiliser les outils mathématiques pour résoudre des problèmes d'optimisation et d'organisation

ObjectifsObjectifs


PlanPlan

• Présentation de la formation.

• Matrices et programmation linéaire

• Théorie des graphes

• Probabilités et statistiques

• Analyse des données


MatriceMatrice et et programmationprogrammation linlinééaireaire

• Notion de présentation matricielle

• Programmation linéaire : résolution graphique, méthode du simplexe


ThThééorieorie des des graphesgraphes

• Langage élémentaire des graphes

• Application à des problèmes d'ordonnancement et de transport

• Méthode des potentiels et méthode PERT


ProbabilitProbabilitééss et et statistiquesstatistiques

• Définition, axiomes, théorèmes généraux

• Variables aléatoires, fonction de répartition et espérance mathématique

• Loi usuelles, loi binomiale, loi exponentielle, loi normale, variance et écart type.

• Initiation à la statistique inductive


• Lecture des résultats d'une analyse de données

AnalyseAnalyse des des donndonnééeses


UV205 UV205 MathMathéématiquesmatiques

Matrices

(c) JP Marca pour CNAM INTECUne sUne séérie de questionsrie de questions

• Qu’est ce qu’une matrice ?• Quel est l’intérêt des matrices ?• Quelles opérations sont possibles sur

les matrices• Qu’est ce que l’inversion d’une

matrice ? Quel intérêt ?• Quels fonctions nous offrent les

tableurs pour traiter les problèmes de matrices ? Quel intérêt pratique ?


• Matrice ?• Matrice carrée ?• Matrice transposée ?• Matrice symétrique ?• Matrice diagonale ?• Matrice unité?• Vecteur ?• Système d’équations et matrice ?• Matrice des coefficients

techniques ?

QuizzQuizz


• Matrices égales ?• Somme de matrices ?• Produits de matrices ?

• Produit matrice * nombre ?• Produit vecteur * vecteur ?• Produit matrice * vecteur ?• Produit matrice * matrice ?

• Inversion matrice ?• Résolution matricielle système

d’équation ?

QuizzQuizz


• Déterminant ?• Méthode inversion matrice ?

• Déterminants ?• Combinaisons linéaires ?

QuizzQuizz


• Un tableau rectangulaire de nombres sur lesquels on définit certaines opérations

QuQu’’est ce quest ce qu’’une matrice ?une matrice ?


• Physique• Statistiques• Economie

· Econométrie· Production· Consommation

IntIntéérêt du calcul matricielrêt du calcul matriciel


QuQu’’est ce quest ce qu’’une matrice ?une matrice ?

Eco Compta Droit InfoDUPONT 12 9 16 15GARCIA 14 11 15 14HUSSEIN 13 12 15 12MARTIN 9 12 14 16NDIAYE 11 13 14 15RASKOLNIKOFF 15 14 13 11SMITH 16 14 12 9STEINER 12 15 12 13TCHAKOUNTE 14 15 11 14THIEU 15 16 9 12

Modele excelElément ij de la matrice

En-tête de colonne j

En-tête de ligne i


• Convention usuelle (Maths)

• Notre convention (Tableur)

Convention de reprConvention de repréésentationsentation

a11 a12 a13a21 a22 a23

a11 a12 a13a21 a22 a23


Convention de reprConvention de repréésentationsentation

Eco Compta Droit InfoDUPONT a11 a12 a13 a14GARCIA a21 a22 a23 a24HUSSEIN a31 a32 a33 a34MARTIN a41 a42 a43 a44NDIAYE a51 a52 a53 a54RASKOLNIKOFF a61 a62 a63 a64SMITH a71 a72 a73 a74STEINER a81 a82 a83 a84TCHAKOUNTE a91 a92 a93 a94THIEU a101 a102 a103 a104


• Nombre identique de lignes et de colonnes

Matrice carrMatrice carrééee

Eco Compta Droit InfoDUPONT a11 a12 a13 a14GARCIA a21 a22 a23 a24HUSSEIN a31 a32 a33 a34MARTIN a41 a42 a43 a44


• Les lignes deviennent colonnes et les colonnes deviennent lignes.

• Fonction Collage spécial Transpose

Matrice transposMatrice transposééee


Matrice symMatrice syméétriquetrique

Paris Lyon MarseilleParis 0 460 800Lyon 460 0 340Marseille 800 340 0


Matrice diagonale. Matrice IdentitMatrice diagonale. Matrice Identitéé..

3 0 00 7 00 0 6

1 0 00 1 00 0 1


Matrice Matrice uniligneuniligne ou ou unicolonneunicolonne : vecteur: vecteur

7 12 6 9 11 7

712

69

117


• Soit le système à deux équations et à trois inconnues3x + 2y – z = 05x + z = 0

• On peut représenter les coefficients des inconnues de ce système sous forme d’une matrice

Exemples de matricesExemples de matrices

3 2 -15 0 1


• Soit une entreprise qui fabrique des voitures télécommandées

• Les modèles Action Kart (A) et Super Speed (B) ont besoin de 4 composants a, b, c, d.

• A nécessite 4a, 2b, 5c et 3d• B nécessite 5a, 3b, 3c et 4d• Ces besoins sont synthétisés dans une

matrice dite des coefficients techniques

Exemples de matricesExemples de matrices

4 2 5 35 3 3 4


OpOpéérations sur les matrices : rations sur les matrices : EgalitEgalitéé

• Deux matrices sont égales lorsqu’elles sont de même dimension et que les éléments de même indice sont égaux


OpOpéérations : Sommerations : Somme

1er semEco Compta Droit Info

DUPONT 12 9 16 15GARCIA 14 11 15 14HUSSEIN 13 12 15 12MARTIN 9 12 14 16NDIAYE 11 13 14 15RASKOLNIKOFF 15 14 13 11SMITH 16 14 12 9STEINER 12 15 12 13TCHAKOUNTE 14 15 11 14THIEU 15 16 9 12

2eme semestreEco Compta Droit Info

DUPONT 11 17 16 6GARCIA 7 13 15 9HUSSEIN 12 12 14 11MARTIN 9 9 14 6NDIAYE 14 15 15 8RASKOLNIKOFF 6 14 13 9SMITH 9 12 12 8STEINER 11 12 14 11TCHAKOUNTE 10 9 15 10THIEU 15 8 13 12

Eco Compta Droit InfoDUPONT 23 26 32 21GARCIA 21 24 30 23HUSSEIN 25 24 29 23MARTIN 18 21 28 22NDIAYE 25 28 29 23RASKOL 21 28 26 20SMITH 25 26 24 17STEINER 23 27 26 24TCHAKO 24 24 26 24THIEU 30 24 22 24


OpOpéérations : Produit drations : Produit d’’une matrice par un nombreune matrice par un nombre

Eco Compta Droit Info Eco Compta DroitDUPONT 11 17 16 6 DUPONT 22 34 32GARCIA 7 13 15 9 GARCIA 14 26 30HUSSEIN 12 12 14 11 HUSSEIN 24 24 28MARTIN 9 9 14 6 Coeff MARTIN 18 18 28NDIAYE 14 15 15 8 2 NDIAYE 28 30 30RASKOLNIKOFF 6 14 13 9 RASKOLNIKOFF 12 28 26SMITH 9 12 12 8 SMITH 18 24 24STEINER 11 12 14 11 STEINER 22 24 28TCHAKOUNTE 10 9 15 10 TCHAKOUNTE 20 18 30THIEU 15 8 13 12 THIEU 30 16 26


OpOpéérations : Produit de vecteurs (scalaire)rations : Produit de vecteurs (scalaire)

Eco Compta Droit Info CoeffRASKOLNIKOFF 6 14 13 9 Eco 3

Compta 4Droit 3Info 2somme 12

Resultat pondéré

Eco Compta Droit Info ResultatRASKOLNIKOFF 18 56 39 18 131

10,92


OpOpéérations : Produit drations : Produit d’’une matrice par un vecteurune matrice par un vecteur

2 4 53 7 -1 * =2*2+4*-1+5*3

= =3*2+7*-1+-1*3

152 -4

-13

PostmultiplicationPostmultiplicationLe nombre de colonnes de la matrice A est Le nombre de colonnes de la matrice A est éégal au gal au nombre dnombre d’é’éllééments du vecteur colonne Bments du vecteur colonne B



PrPréémultiplicationmultiplicationLe nombre de lignes de la matrice B est Le nombre de lignes de la matrice B est éégalgalau nombre dau nombre d’é’éllééments du vecteur ligne Aments du vecteur ligne A

2 4* 3 7 =2*2+-1*3+3*5 =2*4+-1*7+3*-

2 -1 3 5 -1

16 -2

16 -2


• Le produit est de deux matrices est uematrice

• On ne peut multiplier 2 matrices que si le nombre de colonnes de la 1e matrice est égal au nombre de lignes de la seconde

• Le produit n’est pas une opération commutative

Produit de matricesProduit de matrices


• De manière pratique, on peut poser le produit de matrice de la manière suivante

Produits de matricesProduits de matrices

Colonne KX X X X XX X X X XX X X X XX X X X X

X X X Xligne i X X X X Cik

X X X X


• De manière pratique, on peut poser le produit de matrice de la manière suivante


Colonne KX X X X XX X X X XX X X X XX X X X X

X X X Xligne i X X X X Cik

X X X X

A B

A*B


• Application au produit de vecteurs


Eco Comp Droit Info CoeffM. R 6 14 13 9 Eco 3

Comp 4Droit 3Info 2

3432

6 14 13 9131

6 14 13 93432

18 42 39 2724 56 52 3618 42 39 2712 28 26 18


UtilitUtilitéé

Pour quelles applications ces formulesPour quelles applications ces formulesSontSont--elles utiles ?elles utiles ?



Produit matrice par un vecteur Post multiplication

Acier Aluminium Caoutchouc Fer PlastiqSuperCar 11 6 2 9 5HyperBagnole 12 6 3 8 4BelAuto 9 5 2 10 9TireGeniale 7 4 2 11 11

Prix matiereAcier 200Aluminium 300Caoutchouc 350Fer 150Plastiq 120

Prix matiereSuperCar 6650 6650HyperBagnole 6930 6930BelAuto 6580TireGeniale 6270


OpOpéérations : Produit de deux matricesrations : Produit de deux matrices

3 1 4 PRODUIT MATRICIEL2 0 5

1 0 00 -1 01 1 1

7 3 47 5 5


OpOpéérations : Inversion drations : Inversion d’’une matrice carrune matrice carrééee

• Soit A une matrice carrée• On note A-1 l’inverse de la matrice

A telle que :• A-1 * A = I matrice identité• Plusieurs méthodes permettent

d’obtenir l’inverse d’une matrice (déterminant, pivot)

• Fonction Inversemat d’Excel• Pour pouvoir inverser une

matrice, il faut que son déterminant ne soit pas nul


• La théorie des déterminants est complexe puisqu’elle fait appel aux concepts peu aisés de fonction alternée et de forme multilinéaire.

• Il faut donc avoir une approche pragmatique -du type recette- des problèmes de déterminants

• Le calcul d’un déterminant du second ordre est bien connu

• D =

• D = ab’ - ba’

DDééterminantterminant

a a'b b'


• Cette formule suit une logique de permutation extensible au 3ème ordre

DDééterminantterminant

a a'

b b'

lignes 1 2 2 1 a = 11 b = 21

colonnes 1 2 1 2 b' = 22 a' = 12 Notez constance colonnes

D = ab' - ba'

a a' a"

b b' b"

c c' c"

lignes 123 132 312 213 231 321

colonnes 123 123 123 123 123 123

ab'c"- ac'b"+ ca'b"- ba'c"+ bc'a"- cb'a"


• Plusieurs méthodes possibles

• Les plus pratiquées :

· Méthode des déterminants

· Méthode des combinaisons linéaires

• Méthodes fastidieuses qui imposent le recours à l’ordinateur pour les rangs > 3

Inverse matriceInverse matrice


• Trois étapes (2ème ordre)

1. Calcul du déterminant (cf § précédent : ab’-ba’) )

2. Obtention matrice adjointe : permuter les éléments a et b’, changer le signe des termes a’ b.

3. Multiplication de la matrice adjointe par l’inverse du déterminant.

MMééthode des dthode des dééterminantsterminants


• Principe : multiplier (prémultiplication) la matrice de départ par une matrice pour obtenir des zéros dans une colonne : C2 = C1 M

MMééthode des combinaisons linthode des combinaisons linééairesaires

1 0 5 2 . .x 1 * 4 3 = 0 .

Calcul de c215 24 3

1 0x 1

5x+4=0 x=-4/5

1 0 5 2 5 2-0,8 1 * 4 3 = 0 1,4


• Multiplication du résultat par une autre matrice C2 pour obtenir une nouvelle colonne avec 0


1 x 5 2 . 00 1 * 0 1,4 = . .

Calcul de c125 20 1,4

1 x 2+1,4x=00 1 x= -1,4

1 -1,4 5 2 5 00 1 * 0 1,4 = 0 1,4


• Pour obtenir la matrice unitaire, il suffit de prémultiplier C2.C1.M par une matrice diagonale D avec les valeurs adéquates

• Nous avons donc D.C2.C1.M=I

• Or M-1.M = I => M-1 = D.C2.C1


0,2 0 5 0 1 00 0,71 * 0 1,4 = 0 1


• M-1 = D.C2.C1


0,2 0 1 -1,4 1 00 0,71 * 0 1 * -0,8 1

0,2 -0,30 0,71

0,43 -0,29-0,57 0,71


RRéésolution matricielle dsolution matricielle d’’un systun systèème dme d’é’équations quations linlinééairesaires

• a1x+b1y+c1z=d1• a2x+b2y+c2z=d2• a3x+b3y+c3z=d3

• AX = D• A-1 A X = A-1 D• X = A-1 D


• Soient quelques matrices

• Quelles sont celles que l’on peut additionner 2 à 2 ?

• Quelles sont celles que l’on peut multiplier 2 à2 ?

• Quelles sont celles que l’on peut inverser ?

Exercice No 1Exercice No 1

A4 10 3

B-2-4

C1 2 34 5 6

D1 -15 -20 4

E4 26 3

F1 0 -12 3 24 -1 1


Exercices : produit (10)Exercices : produit (10)

A4 1 A*E 22 110 3 18 9

B E*A-2 16 10-4 24 15

C A*C1 2 3 8 13 184 5 6 12 15 18

D D*C1 -1 -3 -3 -35 -2 -3 0 30 4 16 20 24

E4 2 A*F FAUX6 3 #VALEUR! #VALEUR! #VALEUR!

#VALEUR! #VALEUR! #VALEUR!F #VALEUR! #VALEUR! #VALEUR!1 0 -1 C*F2 3 2 17 3 64 -1 1 38 9 12

#N/A #N/A #N/A


Exercices : inversion (11)Exercices : inversion (11)

A4 1 matrices inversibles parmi les matrices carrées ?0 3

B Déterminant de A-2 12 0,25 -0,083333333 0,25-4 12 Inversible 0 0,333333333 0

C1 2 34 5 6

D1 -15 -20 4

E Déterminant de E4 2 0 Pas inversible ### #NOMBRE!6 3 ### #NOMBRE!

F Déterminant de F1 0 -1 19 Inversible 0,26 0,052631579 0,162 3 2 0,32 0,263157895 -0,24 -1 1 -0,7 0,052631579 0,16


• Soient deux matrices• Vérifier que l’une est l’inverse de

l ’autre• Résoudre un système d’équations

Exercice No 2 Exercice No 2


Exercices : inversion (20)Exercices : inversion (20)

A2 5 -2 Inverse de A 0,1 -0,1 0,31 2 1 0,066666667 0,27 -0,1333333333 -1 1 -0,23333333 0,57 -0,033333333

B 0,1 -0,1 0,33 -3 9 0,066666667 0,27 -0,1333333332 8 -4 * 1/30 -0,23333333 0,57 -0,033333333

-7 17 -1


Exercices : rExercices : réésolution systsolution systèème me ééquation (21)quation (21)

Systeme d'equation2x+5y-2z=-2x+2y+z=03x-y+Z=4

2 5 -2 x -21 2 1 * y = 03 -1 1 z 4

Mx -2y = inverse M * 0z 4

x 0,1 -0,1 0,3 -2y = 0,066667 0,266667 -0,13333333 * 0z -0,233333 0,566667 -0,03333333 4

x 1y = -0,666667z 0,333333


• La production d’une unité de 2 types d’aliments A et B nécessitent :

· 2 unités de viande et 1 unité de légumes pour A

· 1 unité de viande et 3 unités de légumes pour B

• Nous savons :· Stock journalier de viande de 150 unités

· Stock journalier de légumes de 400 unités

• Formaliser le pgm de fabrication permettant d’épuiser complètement les stocks quotidiens

Exercice No 3 Exercice No 3


Exercices : Analyse production (30)Exercices : Analyse production (30)

Equation de production

2 1 * x = A 2 1 * x = 1501 3 y B 1 3 y 400

x = Inv M * 150y 400

x = 0,60 -0,20 * 150y -0,20 0,40 400

x = 10y 130


Exercices : marges (31)Exercices : marges (31)


2 1 * x = A 2 1 * x = 1501 3 y B 1 3 y 400

x = Inv M * 150y 400

x = 0,6 -0 * 150y -0,2 0,4 400

x = 10y 130

Marge0,60 60,40 52


• Une usine fabrique 3 articles X, Y et Z• Chaque article exige le passage dans 3

ateliers A1, A2, A3· X (A1=2, A2=5, A3=3)· Y (A1=1, A2=3, A3=2)· Z (A1= 1, A2=2, A3=2)

• Au cours d’un cycle, la charge horaire a été :

• A1 = 48, A2=118, A3=81• Déterminer les quantités de produits

fabriquées• Les coûts unitaires : X=25, Y = 22, Z = 23• Coût total de fabrication ?

Exercice No 4Exercice No 4


Exercices : Production (40)Exercices : Production (40)


x y z * 2 5 31 3 2 = 48 118 811 2 2

48 118 81 * 2 -4 10 1 -1

-1 1 1

15 7 11


Exercices : CoExercices : Coûût total (41t total (41))


x y z * 2 5 31 3 2 = 48 118 811 2 2

48 118 81 * 2 -4 10 1 -1

-1 1 1

Calcul des coûts 15 7 11 252223

Coût total 782782

(c) JP Marca pour CNAM INTECRRééponses ponses àà nos questionsnos questions

• Intérêt des matrices : dans de nombreux domaines

• Qu’est ce qu’une matrice : un tableau• Opérations sur les matrices : somme,

produit par un scalaire, produit de vecteurs, produit de matrice par un vecteur, produit de matrices

• Inversion de matrices : intéressant pour la résolution d’équations matricielles

• Matrices et tableurs : la saisie des fonctions matricielles, les fonctions produitmat, inversemat et determatd’Excel


UV205 UV205 -- MathMathéématiquesmatiques

PROGRAMMATION LINEAIREALGORITHME DU SIMPLEXE

DUALITE

(c) JP Marca pour CNAM INTECUne sUne séérie de questionsrie de questions

• Qu’est ce que la programmation linéaire ?

• Quel intérêt dans le domaine de la gestion ?

• Comment résoudre les problèmes de programmation linéaire ?


• Programmation linéaire ?• Formalisation des

programmes de PL ?• Résolution graphique ?• Solveur sur tableur ?• Règle du simplexe ?• Dualité ?

QuizzQuizz


QU’EST CE QUE LA PROGRAMMATION

LINEAIRE ?


• Héritage de la « Recherche opérationnelle « , science qui a connu beaucoup de succès après le seconde guerre mondiale.

• Objectif : optimisation de l’emploi des ressources.

• Méthode : recherche de l’optimum d’une fonction de plusieurs variables liées entre elles par des contraintes sous forme d’égalités et d’inégalités.

• Contraintes linéaire (C=ax+b) => Programmation linéaire

• Regain d’intérêt en fonction de l’augmentation de la puissance des processeurs (supply chain).

Programmation linProgrammation linééaireaire


• Premier type : maximisation du profit dégagé par une unité de production (business unit) en fonction des contraintes de limitation des facteurs de production

• Second type : la demande étant fixée, quel est la manière optimale de combiner les ressources de la BU pour la satisfaire (minimisation du coût de production)

Typologie des problTypologie des problèèmesmes


• Production de n biens• Quantités à produire : X1, X2, …, Xn >= 0• m facteurs de productions• Quantités des facteurs de production (Qté limitée, d’où

contrainte): b1, b2, …, bm• aij : quantité du facteur de production i nécessaire pour

produire une unité du bien j• cj : bénéfice unitaire apporté par Xj• a11X1 + a12X2 + … + a1nXn <= b1• a21X1 + a22X2 + … + a2nXn <= b2• ……• am1X1 + am2X2 + … + amnXn <= bm

n

• Maximisation profit : Recherche X1, X2, .. Pour max(ΣcjXjj=1

Premier type : maximisation du profitPremier type : maximisation du profit


• Production de 3 (n) voitures : R5, R12, R20 • Quantités à produire (variables): X1, X2, X3 >= 0• 4 (m) facteurs de productions : acier, alu, plastique,

caoutchouc• Quantités des facteurs de production (Qté limitée, d’où

contrainte): 107 500, 80 500, 154 000, 69 500• aij : quantité du facteur de production i nécessaire pour

produire une unité du bien j• 50*X1 + 75*X2 + 100*X3 <= 107 500 (Acier)• 50*X1 + 45*X2 + 40*X3 <= 80 500 (Alu)• 100*X1 + 80*X2 + 70*X3 <= 154 000 (Plastique)• 40*X1 + 45*X2 + 35*X3 <= 69 500 (Caoutchouc)• c1 = 35, c2= 45, c3 = 65 : bénéfice unitaire apporté par X1,

X2 et X3• Maximisation profit : Recherche X1, X2, X3 pour max(35*X1

+ 45*X2 + 65*X3)

ExempleExemple


• Production de m biens• Qtés à produire (connues) : b1, b2, …, bn >= 0• N facteurs de productions• Quantités des facteurs de production : X1, X2, …, Xn• aij : quantité de bien i produite à partir de la limite Xj de

production j• cj : coût unitaire du facteur de production j• a11X1 + a12X2 + … + a1nXn >= b1• a21X1 + a22X2 + … + a2nXn >= b2• ……• am1X1 + am2X2 + … + amnXn >= bm

n

• Minimisation coût : Recherche X1, X2 pour min(ΣcjXjj=1

Second type : minimisation des coSecond type : minimisation des coûûtsts


• Elevage d’animaux exigeant une certaine Qté journalière d’aliments de base au nombre de 3 (m) : lipides, protides, glucides

• Qtés à fournir connues : 246 000, 247 500 et 247 500 >= 0• 4 (n) aliments Alim, Betay, CowFood et Degust• Les variables : X1 = Qté de Alim, X2 = Qté de Betay, X3 = Qté

de CowFood et X4 = Qté de Degust• Quantités des facteurs de production Alim(50 lipides, 75

protides,100 glucides), Betay (50, 45, 40), CowFood (100, 80, 70) et Degust (40, 45, 35)

• Aij : quantité du facteur de production i nécessaire pour produire une unité du bien j

• 50*X1 + 50*X2 + 100*X3 + 40*X4 >= 246 000 (lipides)• 75*X1 + 45*X2 + 80*X3 + 45*X4 >= 247 500 (protides)• 100*X1 + 40*X2 + 70*X3 + 35*X4 >= 247 500 (glucides)• c1 = 35, c2= 45, c3 = 65, c4 = 52 : coût unitaire de X1, X2, X3

et X4• Satisfaction des objectifs au coût minimum : Recherche X1, X2,

X3 et X4 pour min(35*X1 + 45*X2 + 65*X3 + 52*X4)

ExemplesExemples


• Tout pb de PL peut se ramener à l’une des 2 formes remarquables : la forme canonique et la forme standard

• Dans le cas de la recherche de maximisation :• Forme canonique

n n

Σ aij Xj <= bi i=1,2, …, m avec Max Z= Σ cjXj et Xj>=0

j=1 j=1

• Forme standardn n

Σ aij Xj = bi i=1,2, …, m avec Max Z= Σ cjXj et Xj>=0

j=1 j=1

Formalisation des Formalisation des problprobléémesmes de PLde PL


ETUDE DU CASDENIS PAPIN


• La société Denis Papin fabrique des autocuiseurs A et des cafetières automatiques B

• Les opérations d’usinage : estampage, reprise, assemblage• Chaque atelier a une capacité limitée de production

EtudeEtude du cas Denis Papindu cas Denis Papin

22 500Assemblage A

15 000Assemblage B

16 66733 333Reprise

35 00025 000Estampage

Cafetières BAutocuiseurs A


• La marge sur un autocuiseur est de 15 €• La marge sur une cafetière est de 12,5 €• Soit X1 (A) et X2 (B) les productions• Les pourcentages d’utilisation des capacités des ateliers :


0,00444Assemblage A

0,00667Assemblage B

0,0060,003Reprise

0,002860,004Estampage

Cafetières BAutocuiseurs A


• Quelles quantités d’autocuiseurs et de cafetières doit on produire pour que le profit soit maximal ?

• Profit = 15*X1 + 12,5*X2



• Formalisation mathématique du problème posé

Estampage 0,004 X1 + 0,00286 X2 <= 100Reprise 0,003 X1 + 0,006 X2 <= 100Assemblage A 0,00444 X1 <= 100Assemblage B 0,00667 X2 <= 100



• Résolution graphique

Dans le repère (X2, X1) les droitesx2 = (100-0,004X1)/0,00286 Estampagex2 = (100-0,003X1)/0,006 RepriseX1 = 100/0,00444 Ass AX2 = 100/0,00667 Ass BX2 = (P - 15 X1)/12,5 Equation du profit




• Résolution graphique

• Les quatre premières droites définissent un espace (polygone) des solutions possibles

• La droite du profit est une droite de pente constante de paramètre P

• On la fait glisser dans le polyèdre en recherchant la valeur de P maxi



-20 000

-10 000

0

10 000

20 000

30 000

40 0001 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35

x2 Estx2 RepriseX2 Ass Ax2 Ass BProfit


• Max P = 386 111 €• Pour x1 = 20 363 et x2 = 6 485• Ces valeurs correspondent approximativement au

point d’intersection des courbes Estampage et Reprise

• Ces deux ateliers sont donc utilisés au maximum de leurs capacités

• Les ateliers d’assemblage sont utilisés à 90% (A) et 43% (B).

• La solution se trouve toujours sur un des sommets du polygone



• Dans la pratique :• Utilisation du solveur du tableur



Rappel sur Rappel sur solveursolveur




• Avec l’ouverture des marchés de l’est européen, Denis Papin & Co se propose de fabriquer des samovars.

• La modélisation de la gestion de production se complique et passe à trois dimensions (ou plus si plus de produits, ce qui est le cas général dans la pratique).

• Dans l’espace, le polygone devient polyèdre.• Nécessité d’une autre méthode.• La méthode utilisée est la méthode du simplexe.• La démonstration en a été faite par un

mathématicien américain : Georges Dantzig.



• Nouvelle répartition des contraintes atelier


12 000Assemblage B

10 000

30 000

Cafetières B

20 000Assemblage A

8 000Assemblage C

10 00030 000Reprise

12 00020 000Estampage

Samovar CAutocuiseurs A


• La marge sur un autocuiseur est de 15 €• La marge sur une cafetière est de 12 €• La marge sur un samovar est de 14 €• La nouvelle fonction de profit

P = 15 X1 + 12 X2 + 14 X3

• Soit X1 (A), X2 (B) et X3 (C) les productions• Les pourcentages d’utilisation des capacités des ateliers :


Autocuiseurs A Cafetières B Samovars CEstampage 0,00500 0,00333 0,00833Reprise 0,00333 0,01000 0,01000Assemblage 0,00500Assemblage 0,00833Assemblage 0,01250


• Formalisation des contraintes ∆

∆1 0,00500 X1 +0,00333 X2 +0,00833 X3 <=100∆2 0,00333 X1 +0,01000 X2 +0,01000 X3 <=100∆3 0,00500 X1 <= 100∆4 0,00833 X2 <= 100∆5 0,01250 X3 <= 100

• X1, X2 et X3 >= 0

• Recherche Max(15 X1 + 12 X2 + 14 X3)



• On remarque en premier lieu que certaines contraintes∆1 => ∆3 est toujours vérifiée∆2 => ∆4 est toujours vérifiée

• En tenant compte des contraints les plus astreignantes, le système se réduit à :

∆1 0,00500 X1 +0,00333 X2 +0,00833 X3 <=100∆2 0,00333 X1 +0,01000 X2 +0,01000 X3 <=100∆5 0,01250 X3 <= 100



•Ramenons les inéquations à des équations en introduisant les valeurs d’écart X4, X5 et X6•Le nouveau système d’équation

0,00500 X1 +0,00333 X2 +0,00833 X3 + X4 = 1000,00333 X1 +0,01000 X2 +0,01000 X3 + X5 = 100

0,01250 X3 + X6= 10015 X1 + 12 X2 + 14 X3 = P

•Une solution évidente (X1 = X2 = X3 = 0, X4 = 100, X5 = 100, X6 = 100, P = 0) est sans intérêt.



• La solution graphique nous a montré que la solution se trouvait sur un des sommets du polyèdre.

• Un quelconque des sommets constitue une solution dans laquelle trois des six variables X1 à X6 sont nulles.

• La solution X1 = X2 = X3 = 0 donne le sommet O (Point origine) du polyèdre.

• L’idée est de passer d’un sommet du polyèdre à un autre, en augmentant la valeur de P si possible.

• On choisit la variable qui a dans P le plus grand coefficient positif, soit X1.

• Par substitution, ligne par ligne, on s’arrange pour que demeure un seul coefficient non nul dans la colonne des x1 et que le coefficient des x1 disparaisse dans P.



• On multiplie la 1ere ligne par 200 pour avoir le coefficient 1 sur X1

• 0,00500 X1 +0,00333 X2 +0,00833 X3 + X4 = 100 devientX1 + 0,666 X2 + 1,666 X3 + 200 X4 = 20000

• On élimine le terme en X1 en combinant avec les autres équations

• Une nouvelle solution apparaît, plus avantageuse que O :X2 = X3 = X4 = 0X1 = 20 000X5 = 33X6 = 100P = 300 000

• Pour ce point, l’équation de P :2 X2 - 11 X3 - 3000 X4 = P - 300 000



• Le calcul se poursuit en s’intéressant au sommet suivant, cette fois en éliminant X2 du système d’équation

• La solution donne :X3=X4=X5 = 0X1 = 17143X2 = 4286P = 310 714

• C’est le point recherché car dans l’équation de P, tous les coefficients sont négatifs

-12,14 X3 - 2828 X4 - 257 X3 = F - 310 714• On peut vérifier le résultat par le biais du solveur• Nécessité d’une démarche formalisée, plus

systématique, celle-la même mise en œuvre dans le tableur => Algorithme du simplexe



EtudeEtude du cas Denis Papin : la solution tableurdu cas Denis Papin : la solution tableur


• Bilan de l’étude :• La fabrication de samovars conduirait à une

dégradation du résultat• Il faut donc se recentrer sur les deux produits de

base



ALGORITHME DU SIMPLEXE


• Processus de calcul manuel• Soit une situation économique, analogue à celle de

notre société Denis Papin, décrite par le système d’équation suivant :

X1 + 5X2 <= 1005X1 + 5X2 <= 180X1 <= 30

avec la fonction économique à maximiser

P = 400 X1 + 800 X2

• N’oublions pas X1 et X2 sont >=0

RRèègle pratique du simplexegle pratique du simplexe


• En introduisant les variables d’écart, le problème s ’énonce :

1X1 + 5X2 + X3 = 1005X1 + 5X2 + X4 = 1801X1 + + X5 = 30

X1, X2, X3, X4, X5 >= 0

Avec Max(P = 400 X1 + 800 X2)



• Ce système peut se représenter sous forme matricielle :

X1X2

1 5 1 0 0 X3 1005 5 0 1 0 X4 = 1801 0 0 0 1 X5 30

• Les 3 dernières colonnes forment une matrice unitéqui constitue la base d’un espace vectoriel à n dimensions (n=nombre de contraintes)

• L’algorithme va progresser de sommet en sommet en ayant soin de ne pas diminuer la valeur de la fonction économique, dans une représentation matricielle i,j ou j représente les vecteurs colonnes de l’espace vectoriel et i le rang des variables



• Tout vecteur de l’espace vectoriel peut être représenté en fonction d’un certain nombre de vecteurs unitaires appelés base, qui sont ceux des axes X3, X4 et X5

• Les variables X3, X4 et X5 sont les variables de base• Les variables X1 et X2 sont les variables hors base




valeursListe indices Coefficients du système d'équations variables base

de baseXB P1 P2 P3 P4 P5 XB

P3 1 5 1 0 0 100

P4 5 5 0 1 0 180

P5 1 0 0 0 1 30

∆j 400 800 0 0 0 P-0

Coefficient de chaque variable dans la fonction économique


• On procède par itération• On sélectionne dans la ligne des ∆j la plus grande

valeur positive (1er critère de Dantzig)• C’est 800 qui correspond à X2• C’est cette variable qui va entrer en base• On calcule pour chaque ligne i le quotient du terme

de XB par le coefficient de la ligne i qui se trouve dans la colonne 2






P3 1 5 1 0 0 100 20

P4 5 5 0 1 0 180 36

P5 1 0 0 0 1 30 #DIV/0!

∆j 400 800 0 0 0 P-0



• On détermine la valeur sortante par application du second critère de Dantzig

• C’est la variable correspondant à l’indice de ligne du plus petit rapport positif (20), soit X1

• On repère alors le pivot, qui est à l ’intersection de la ligne de la variable sortante (X3) et de la colonne de la variable entrante (X2)

• Le pivot est égal à 5• On rend le pivot égal à 1 en divisant les éléments de

la ligne du pivot par le pivot lui-même






P3 1 5 1 0 0 100 20

P4 5 5 0 1 0 180 36

P5 1 0 0 0 1 30 #DIV/0!

∆j 400 800 0 0 0 P-0




• Ancienne ligne du pivot

• Nouvelle ligne du pivot

• On va ensuite combiner chaque ligne du tableau avec la nouvelle ligne du pivot pour éliminer X2 (X) dans ces lignes

P3 1 5 1 0 0 100 20

P3 0,2 1,0 0,2 0,0 0,0 20,0





P3 1,0 5,0 1,0 0,0 0,0 100,0P3 0,2 1,0 0,2 0,0 0,0 20,0

P4 5,0 5,0 0,0 1,0 0,0 180,01,0 5,0 1,0 0,0 0,0 100,04,0 0,0 -1,0 1,0 0,0 80,0

P5 1,0 0,0 0,0 0,0 1,0 30,0

∆j 400,0 800,0 0,0 0,0 0,0160,0 800,0 160,0 0,0 0,0 16000,0240,0 0,0 -160,0 0,0 0,0 -16000,0






Y 0,2 1,0 0,2 0,0 0,0 20,0

P4 4,0 0,0 -1,0 1,0 0,0 80,0

P5 1,0 0,0 0,0 0,0 1,0 30,0

∆j 240,0 0,0 -160,0 0,0 0,0 -16000,0


Le nouveau tableau :



• Itération du processus pour remplacer en tant que base la variable d’écart X3 par la deuxième variable recherchée X1 (Y)





Y 0,2 1,0 0,2 0,0 0,0 20,0

P4 4,0 0,0 -1,0 1,0 0,0 80,0

P5 1,0 0,0 0,0 0,0 1,0 30,0

∆j 240,0 0,0 -160,0 0,0 0,0 -16000,0






Y 0,20 1,00 0,20 0,00 0,00 20,000,20 0,00 -0,05 0,05 0,00 4,000,00 1,00 0,25 -0,05 0,00 16,00

X 4,00 0,00 -1,00 1,00 0,00 80,001,00 0,00 -0,25 0,25 0,00 20,00

P5 1,00 0,00 0,00 0,00 1,00 30,000,00 0,00 0,25 -0,25 1,00 10,00

∆j 240,00 0,00 -160,00 0,00 0,00 -16000,00240,00 0,00 -60,00 60,00 0,00 4800,00

0,00 0,00 -100,00 -60,00 0,00 -20800,00Coefficient de chaque variable dans la fonction économique



• La solution :• X1 (X) = 16• X2 (Y) = 20• Profit max P = 20 800

•


RRèègle pratique du simplexe / gle pratique du simplexe / VVéérifrif tableurtableur



• Action de support aux PMEs pour créer des emplois· 1000 PE· 500 ME

• Coût d’un dossier (subvention et traitement)· 50 000 pour une PE· 100 000 pour une ME· Budget 62 500 000

• Temps de traitement d’un dossier· 5j pour PE· 5j pour ME· 5000 j dispo

• Emplois créés· 1 par PE· 3 par ME· Optimiser le nombre d’emplois créé



• Modele Excel


DualitDualitéé

• Etant donné un problème de programmation linéaire PL1 mis sous forme canonique

· Ax <= b (A matrice (m,n))· x >= 0 (x vecteur colonne (n,1))· Max Z = Cx (c vecteur ligne (1,n)

• On associe à PL1 un autre problème de programmation linéaire PL2 tel que

· yA >= c (y vecteur ligne (1,m))· y >= 0 · Min Z’ = yb

• PL2 est le dual de PL1


DualitDualitéé

• Pour passer du primal au dual• Les termes du second membre du primal deviennent

les coefficients de la fonction économique du dual et réciproquement.

• Si le primal est un problème de maximisation, le dual est un problème de minimisation.

• Les inégalités <= deviennent inégalités >=• La matrice A se change sur le dual en sa transposée


DualitDualitéé

Soit le programme linéaire primalX1 + 2X2 <= 483X1 + 4X2 <= 120X1, X2 >= 0Recherche Max Z = 5X1 + 6X2

Le programme dual s’exprimeY1 + 3Y2 >=52Y2 + 4Y2 >= 6Y1; y2>0=0Recherche Min Z’=48Y1 + 120 Y2


ExerciceExercice

• Optimex fabrique des produits cosmétiques à partir de 2 produits : lanoline et glycérine

• Fourniture de lots mixtes• Tout cycle de fabrication nécessite 120 g de lanoline

et 90 g de glycérine• Trois fournisseurs possibles

• Pb en équation / Primal ou dual ? / Poser ?

2260X3

46132X2

26120X1

Contenu en glycérine

Contenu en lanolinePrix du lotFournisseur


ExerciceExercice

• Contrainte lanoline : 6X1 + 6X2 + 2X3 >= 120• Contrainte glycérine : 2X1 + 4X2 + 2X3 >= 90• Recherche Min de 120 X1 + 132 X + 60 X3

• Le problème étant la recherche d’un maximum, il faut passer par le dual


ExerciceExercice

• Contrainte lanoline : 6X1 + 6X2 + 2X3 >= 120• Contrainte glycérine : 2X1 + 4X2 + 2X3 >= 90• Recherche Min de 120 X1 + 132 X + 60 X3

• Le problème étant la recherche d’un maximum, il faut passer par le dual

• Le programme dual• 6Y1 + 2Y2 <= 120• 6Y1 + 4Y2 <= 132• 2Y1 + 2Y2 <= 60• Recherche Max de 120Y1 + 90Y2

(c) JP Marca pour CNAM INTECRRééponses ponses àà nos questionsnos questions

• Méthode de programmation linéaire pour résoudre les problèmes d’optimisation de gain maxi (le plus grand profit) ou de contrainte mini (le coût le plus faible)

• Processus itératif du simplexe• Emploi solveur dans la pratique (qui

fonctionne selon le même principe)


Espaces vectoriels, matrices et applications linéaires


• Les sessions 1 et 2.1 ont été consacrées aux matrices

• Les sessions 2. 2 et 3 ont été consacrées àla programmation linéaire, qui fait état d’applications linéaires (les contraintes) entre variables.

• Pour celle-ci, dans le cadre de la présentation de l’algorithme du simplexe, nous avons fait référence à la notion d’espace vectoriel.

• Il y a une relation très forte entre espace vectoriel, matrices et applications linéaires.

Espaces vectoriels, matrices et applis linEspaces vectoriels, matrices et applis linééairesaires


• La définition mathématique de l’espace vectoriel est assez complexe.

• En première approximation on peut le représenter comme l’ensemble des vecteurs V1, V2, … , Vn que l’on peut définir à partir du point origine dans un référentiel à n dimensions.

• Les vecteurs que l’on peut définir sont des vecteurs abstraits qui n’ont en commun avec les vecteurs géométriques que les lois de composition, mais nous pouvons nous représenter ceux-ci plus facilement, du moins dans un espace à 2 ou 3 dimensions.

Espaces vectoriels et matricesEspaces vectoriels et matrices


• p vecteurs V1, V2, … Vn d’un espace vectoriel Ep sont déterminés par leurs coordonnées V1(X11, X12, X13, … X1p), V2(X21, X22, X23, ... X2p), …, Vn (Xn1, Xn2, Xn3, ... Xnp) dans une base définie par des vecteurs i (i1, i2, …, ip)

• Il est commode de représenter cet ensemble de la façon suivante :

• V1 V2 …. Vn

• i1 X11 X12 …. X1n

• i2 X21 X22 …. X2n

• ………………………………….

• ip Xp1 Xp2 …. Xpn



• p vecteurs V1, V2, … Vn d’un espace vectoriel Ep sont déterminés par leurs coordonnées V1(X11, X12, X13, … X1p), V2(X21, X22, X23, ... X2p), …, Vn (Xn1, Xn2, Xn3, ... Xnp) dans une base définie par des vecteurs i (i1, i2, …, ip)

• Il est commode de représenter cet ensemble de la façon suivante :

• V1 V2 …. Vn

• i1 X11 X12 …. X1n

• i2 X21 X22 …. X2n

• ………………………………….

• ip Xp1 Xp2 …. Xpn


Nous reconnaissonsici une matrice

Les vecteurs i constituent la base(au sens d‘une base pour système de coordonnées)


• Un problème classique est celui du changement de base (E1 -> E2)

• L’espace E2 était rapporté à une première base B(i1, i2, …, ip), dite ancienne, dans laquelle un vecteur Vn a pour coordonnées (X1n X2n …. Xpn).

• E2 est rapporté à une nouvelle base B’(j1, j2, …, jp), dans laquelle le vecteur Vn a pour coordonnées (X’1n X’2n …. Xpn).



• Pour simplifier, considérons un espace vectoriel à 2 dimensions

• Soit V défini avec la base B(i,j)

• V = X i + Y j

• V défini avec la base B’(i’,j’)

• V = X’ i’ + Y’ j’

• Nous avons donc

• V = X i + Y j = X’ i’ + Y’ j’



• On résoud l’équation en exprimant les vecteurs i’ et j’ dans l’ancienne base

• i’ = ai + bj

• j’ = a’i + b’j

• On appelle matrice de passage de la base B à la base B’ la matrice dont les vecteurs-colonnes sont les vecteurs de la nouvelle base exprimée dans l’ancienne

X a a’ X’

Y b b’ Y’


=


• Soit E et F deux espaces vectoriels

• Soit une base U(u1, u2, …) dans E

• Soit une base V(v1, v2, ..) dans F

• Soit X un vecteur de E

• X = u1 x1 + u2 X2 + … + un xn

• L’application linéaire f lui fait correspondre un vecteur f(X) de F

• f(X) = f(u1)x1 + f(u2)x2 + … f(un)xn

• Le problème est de même nature que le précédent avec une matrice de transformation constituée cette fois des coordonnées des vecteurs de la base de E dans la base V de F

ReprRepréésentation dsentation d’’une application linune application linééaire aire par une matricepar une matrice


yj = aj1x1 + aj2x2 + …. + ajnxn

j=1, 2, … p

Application notée Y = A X

ReprRepréésentation dsentation d’’une application linune application linééaire aire par une matricepar une matrice

x1x2x3………xn

a11 a12 : a1n y1a21 a22 : a2n y2a31 a32 : a3n y3……… ……… : ……… ………ap1 ap2 : apn yp


THEORIE DES GRAPHES


Qu’est ce que la théorie des graphes ?Comment permet-elle de traiter les problèmes d’ordonnancement et de planning ?

Une sUne séérie de questionsrie de questions


• Langage des graphes· Sommet· Arc· Arète· Graphe orienté

• Représentation d’un graphe· MPM· PERT

QuizzQuizz


• Dates de début au plus tôt• Dates de début au plus tard• Marge totale• Marge libre• Chemin critique• Réseau de transport

· Algorithme Ford Fulkerson

QuizzQuizz


• Définition d’un graphe :

• Un ensemble X de n sommets

• Une application A entre les éléments de l’ensemble X

• Le graphe est le couple (X,A) qui définit la relation liant les points.

• Définition d’un graphe orienté

• La relation entre deux sommets peut être orientée ou non.

• Si oui, cette relation est un arc.

• Si non, cette relation est une arête.

• Un graphe dont toutes les relations sont orientées est un graphe orienté.

Langage Langage éélléémentaire des graphesmentaire des graphes


• Représentation sagittale

ReprRepréésentation dsentation d’’un grapheun graphe

A

BC

D

EF • Les arcs sont

explicitement définis


• Représentation matricielle associée un graphe sagittal


F

E

D

C

B

A

000000

101000

000000

001000

001100

010010

FEDCBA • Un 1 sur le couple L(B)(C )= signifie explicitement l’arc BC

• En ligne : du sommet E partent les arcs ED et EF

• En colonne ; Au sommet D arrivent les arcs BD, CD,ED.


• Représentation sous forme de dictionnaire (1)


ABCDEF

Sommets

/ABB,C,EAE

Immédiatement précédents

• Le dictionnaire ne fournit que le sommets adjacents

• C’est le graphe considéré

ABCDEF

Sommets

B, EC,DD/F,/

Immédiatement suivants




ABCDEF

Sommets

/ABB,C,EAE

Immédiatement précédents

• Le dictionnaire ne fournit que le sommets adjacents

• C’est le graphe considéré

ABCDEF

Sommets

B, EC,DD/F,D/

Immédiatement suivants




ABCDEF

Sommets

/AA,BA,B,C,EAA,E

Précédents

ABCDEF

Sommets

B, C, D, E, FC,DD/F,D/

Suivants

• On définit des règles d’antériorité (ou de postériorité) générales.

• Ce mode de représentation ne définit pas explicitement le graphe.

• Plusieurs graphes répondent à un même dictionnaire.• Parmi ces graphes, un graphe optimal


• Le dernier mode est classique dans les problèmes d’ordonnancement

• L’ordonnancement a pour but d’organiser dans le temps un ensemble de tâches, soumises àdes contraintes, qui concourent à la réalisation d ’un objectif.

• Dans ce contexte, il vise à déterminer:

• le meilleur temps de réalisation de l’objectif.

•Les taches qui ne peuvent souffrir de retard sans remettre en cause la durée totale du projet

• Qu’est ce qu’un projet ?



• Les méthodes d’ordonnancement sont fondées sur la théorie des graphes.

• La méthode PERT (Program Evaluation ResearchTask) développée aux USA dans les années 50 pour la gestion du projet Polaris

• La méthode MPM (Méthode des potentiels Metra) développée pour l’implantation d’une centrale nucléaire.





ABCDEF

Tâche

/AA,BA,B,C,EAA,E

Pour lancer cette tâche, il faut que soient réalisées les tâches

• Recherche des niveaux• Suppression des redondances


• Recherche des niveaux à partir du dictionnaire

• Niveau 0 : Sommets sans précédent = A

• Niveau 1 : On élimine dans le dictionnaire les sommets de niveau 0 (A)

Recherche des niveauxRecherche des niveaux

ABCDEF

Sommets

/AA,BA,B,C,EAA,E

Précédents

BCDEF

Sommets

/BB,C,E/E

Précédents


• Niveau 1 : Sommets B et E dont tous les précédents ont été éliminés

• Niveau 2 : On élimine dans le dictionnaire les sommets de niveau 1 (B et E)


CDF

Sommets

/C/

Précédents

BCDEF

Sommets

/BB,C,E/E

Précédents


• Niveau 2 : Sommets C et F dont tous les précédents ont été éliminés

• Niveau 3 : Reste D


DSommets

CPrécédents



A

BC

D

EF

Niveau 0 Niveau 1 Niveau 2 Niveau 3


• Cette recherche peut s’opérer à partir d ’une matrice, un peut différente de celle déjà vue car le graphe n’est pas explicitement défini


F

E

D

C

B

A

000000

101000

000000

001000

001100

111110

FEDCBA

• A est un antécédent pour B, C, D, E et F

• B est un antécédent pour C et D

• C est un antécédent pour D

• E est un antécédent pour D et F

• D et F ne sont des antécédents pour rien


• Sont de niveau 0 les sommets dont le total est égal à 0


Σ

F

E

D

C

B

A

214210

000000

101000

000000

001000

001100

111110

FEDCBA

• A est de niveau 0


• Pour déterminer le niveau 1, les lignes et les colonnes de niveau 0 (A) sont barrées et le total des colonnes est recalculé.


Σ

F

E

D

C

B

10310

00000

10100

00000

00100

00110

FEDCB

• B et E sont de niveau 1


• Pour déterminer le niveau 2, les lignes et les colonnes de niveau 1 (B et E) sont barrées et le total des colonnes est recalculé.


Σ

F

D

C

010

000

000

010

FDC

• C et F sont de niveau 2

• D est de niveau 3


• La suppression des redondances ne s’opère que dans le cas de dictionnaires de type 2

•Graphe non complètement définis

•Tous sommets fournis (et non seulement les sommets adjacents)

• La démarche consiste à rechercher les antécédents des tâches antérieures

Suppression des redondancesSuppression des redondances



ABCDEF

Sommets

/AA,BA,B,C,EAA,E

Précédents

/AA,A,B,A

A

Antécédents

/ABC,EAE

Antérieur immédiat:

A et B sont éliminés car présents dans

les 2 tableaux



A

BC

D

EF

Niveau 0 Niveau 1 Niveau 2 Niveau 3

La liaison BD a étéconsidérée comme

redondante


MMééthode des potentielsthode des potentiels

t T

X

t T

Y

Nom de la tâche

Début au plus tôt

Début au plus tard

Durée de la tâche

La tâche Y suit la tâche X et ne peut

commencer avant l’achèvement de X



• La construction de votre maison se décompose en 9 tâches reliées entre elles par des contraintes d’antériorité

AucuneAA

B,CDDD

E,GE

Tâches précédentesadjacentes

A. PlanB. Achat matériauxC. FondationsD. MursE. ElectricitéF. DiversG. ToitureH. PeintureI. Finition (Alarme, chauffage, ..)

Tâche

226523622

Durée



0 0

A

0 0

C

0 0

B

0 0

D

0 0

E

0 0

G

0 0

F

0 0

H

0 0

I

0 0

FIN

Nécessitébloc fin

• Tracé du graphe



0 0

A

0 0

C

0 0

B

0 0

D

0 0

E

0 0

G

0 0

F

0 0

H

0 0

I

0 0

FIN

Nécessitébloc fin

• Valorisation des liens (durée des tâches)

2

2

2

6

5

5

5

2

2

3

6 2

2


• Détermination des dates de début au plus tôt

• On part du début (Gauche)

• La date de début au plus tôt est la date àlaquelle une tâche peut commencer

• Une tâche ne peut commencer tant que les tâches antérieures ne sont pas toutes terminées

• Quand il y a convergence vers une tâche, on retient le chemin le plus long




0 0

A

2 0

C

2 0

B

8 0

D

13 0

E

13 0

G

13 0

F

19 0

H

15 0

I

21 0

FIN

Le projet ne peut être terminé au mieux que dans 21 semaines

• Détermination des dates de début au plus tôt

2

2

2

6

5

5

5

2

2

3

6 2

2


• Détermination des dates de début au plus tard

• On part de la fin (Droite)

• La date de début au plus tard est la date limite à laquelle une tâche doit commencer sous peine de retarder le projet

• Une tâche ne doit pas remettre en cause la durée totale du projet

• Quand il y a convergence vers une tâche, on retient le chemin le plus court




0 0

A

2 2

C

2 6

B

8 8

D

13 17

E

13 13

G

13 18

F

19 19

H

15 19

I

21 21

FIN

• Détermination des dates de début au plus tard

2

2

2

6

5

5

5

2

2

3

6 2

2


• Détermination du chemin critique

• Le chemin critique est le chemin le plus long entre le début et la fin du projet

• Il est constitué par l’ensemble des tâches critiques c’est à dire dont la réalisation ne souffre aucun retard

• Une tâche est critique quand sa date de début au plus tôt est égale à sa date de début au plus tard

• La longueur du chemin critique est donc égale àla somme des durées des tâches critiques




0 0

A

2 2

C

2 6

B

8 8

D

13 17

E

13 13

G

13 18

F

19 19

H

15 19

I

21 21

FIN

• Détermination du chemin critique

2

2

2

6

5

5

5

2

2

3

6 2

2

Vérification : 2+6+5+6+2 = 21



• Calcul et interprétation des marges

La marge libre est le retard maximum que peut prendre la réalisation d’une tâche sans remettre en cause les dates au plus tôt des tâches suivantes, et donc sans retarder la durée totale du projet

Marge libre de X = ty - dx - tx

La marge totale est le retard maximum que peut prendre la réalisation d’une tâche sans retarder la durée totale du projet

Marge totale de X = Tx - tx

Marge libreMarge totale

tx Tx

X

tx Tx

X

ty Ty

Ydx



• Calcul et interprétation des marges

13 – 5 – 8 = 00D

21 – 2 – 19 = 00H

19 – 6 – 6 – 13 = 00G

21 – 3 – 13 = 518 – 13 = 5F

15 – 2 - 13 = 0; 19 – 2 – 13 = 4 17 - 13 = 4E

8 – 6 - 2 = 00C

8 – 2 - 2 = 46 – 2 =4B

2 – 2 –0 = 0; 2 – 2 - 0 = 00A

19 – 15 = 4

Marge totale

21 – 2 – 15 = 4I

Marge libreTâches


• Les marges d ’une tâche critique sont nulles

• La marge libre d’une tâche est toujours inférieure ou égale à sa marge totale

• Interprétation de E :

•La marge totale de 4 implique qu’un retard de 4 semaines sur cette tâche ne met pas en cause la date de fin prévue du projet.

•Mais, une marge libre de 0 implique qu’un retard est impossible si on ne veut pas remettre en cause la date de début au plus tôt des tâches suivantes



• Les tâches critiques ont des marges nulles puisqu’aucun retard n’est possible pour ces tâches

• Tout retard dans l‘accomplissement d’une tâche critique retarde d’autant le projet

• La réduction de la durée d’une tâche critique ne réduit la durée totale du projet que si il y a un seul chemin critique

• La durée d’une tâche non critique peut varier dans le limite de sa marge libre



ExerciceExercice

AucuneAAC

B,D

ECFF

G,H,I

Tâches précédentes

A. Sélection progicielB. Formation Equipe projetC. Choix des standards techniques D. Mise en place maquetteE. Définition des règles de gestion et choix paramètresF. Intégration et vérification d’aptitudeG. Déploiement infrastructure techniqueH. Formation utilisateursI. Déploiement systèmes et logicielsJ. Vérification Service Régulier

Tâche

24235

25843

Durée

• Déploiement progiciel comptable


ExerciceExercice

AucuneAucuneAucune

A,BB,CB

D,FE, F


A. B. C. D. E. F. G. H.

Tâche

54643654

Durée

• Exercice 5 Série 6 Application 13

• Graphe MPM ?• Ordonnancement au plus tôt ? • Ordonnancement au plus tard ?• Chemin critique ?• Durée minimale projet ?• Impact de contraintes

supplémentaires• A, F et H nécessitent l’usage

d’une ressource critique O disponible en un seul exemplaire.

• E et F sont exécutées par le même prestataire et ne peuvent être réalisées simultanément


CorrigCorrigéé

1 La tache F est contrainte par H qui est contrainte par A

2 La tache H est contrainte par F qui est contrainte par A

11 La tache E est contrainte par F

12 La tache F est contrainte par E

21 La tache E est contrainte par F

22 La tache F est contrainte par E


CorrigCorrigéé

AucuneAucuneAucune

A,BB,C,FB, HD,F

E,F,A


A. B. C. D. E. F. G. H.

Tâche

54643654

Durée

• Cas 11• La tache F est contrainte par H qui est contrainte par A• La tache E est contrainte par F

Cas à rejeter puisque H est contraint par F


CorrigCorrigéé

AucuneAucuneAucune

A,BB,C

B, H, ED,F

E,F,A


A. B. C. D. E. F. G. H.

Tâche

54643654

Durée

• Cas 12• La tache F est contrainte par H qui est contrainte par A• La tache F est contrainte par E

Cas à rejeter puisque H est contraint par F


CorrigCorrigéé

AucuneAucuneAucune

A,BB,C,FB,AD,FE,F


A. B. C. D. E. F. G. H.

Tâche

54643654

Durée

• Cas 21• La tache H est contrainte par F qui est contrainte par A• La tache E est contrainte par F

Solution à 18 jF est réalisé avant ELa ressource O passe

de A (5j) à F (6j) puis à H (4j)


CorrigCorrigéé

AucuneAucuneAucune

A,BB,C

B,E,AD,FE,F


A. B. C. D. E. F. G. H.

Tâche

54643654

Durée

• Cas 22• La tache H est contrainte par F qui est contrainte par A• La tache F est contrainte par E

Solution à 20 jE et réalisé avant F

La ressource O passe de A (5j) à F (6j)

puis à H (4j)


ExerciceExercice

AucuneAucune

A,BA,BA,BAAFF

I,G,H,EDKD

J,C,M,L


A. B. C. D. E. F. G.H.I.J.K.L.M.N.

Tâche

63536455225462

Durée

• Exercice 6 Série 6 Application 13

• Graphe MPM ?• Ordonnancement au plus tôt ? • Ordonnancement au plus tard ?• Chemin critique ?• Marges libres et totales sur E et

F ?• Il est possible de réduire la

durée de K à 3 j mais cette réduction implique une dépense de 50 000 Euros alors que chaque jour gagné réduit le coût du projet de 30 000 Euros. L’objectif de réduction est-il sensé ?


ExerciceExercice

0 0

A

0 0

B

6 0

C

6 0

D

6 0

E

5 0

G

6 0

F

10 0

I

10 0

H

15 0

J

9 0

K

14 0

L

9 0

M

18 0

N20 0

FIN

6

4

5

5

25

3

6

3

3

2

5

4

6

2


ExerciceExercice

0 0

A

0 3

B

6 13

C

6 6

D

6 10

E

5 10

G

6 7

F

10 14

I

10 11

H

15 16

J

9 9

K

14 14

L

9 12

M

18 18

N20 20

FIN

6

4

5

5

25

3

6

3

3

2

5

4

6

2


ExerciceExercice

0 0

A

0 3

B

6 13

C

6 6

D

6 10

E

5 10

G

6 7

F

10 14

I

10 11

H

15 16

J

9 9

K

14 14

L

9 12

M

18 18

N20 20

FIN

6

4

5

5

25

3

6

3

3

2

5

4

6

2


ExerciceExercice

10 – 6 – 4 = 07 – 6 = 1F

15 – 6 – 6 = 310 – 6 = 4E

Marge totale Marge libreTâches


ExerciceExercice

• Démonstration project


MMééthode Pertthode Pert

Méthode PertMéthode des potentiels

tx Tx

X

ty Ty

Ydx

Contrainte de succession

valorisée avec la durée de la

tâche

Tâche

dx

Tâche avec durée

Jalon

Xtx Tx

Xtx Tx

Date de début au plus tôt de

X

Date de début au plus tard de

X

Date de début au plus tôt des

tâches qui partent de X

Date de fin au plus tard des tâches qui

aboutissent àX



• Tracé du graphe

1

A(2)

2

2’

B(2)

C(6)

β(0)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

ε(0)



• Points délicats

1

A(2)

2

2’

B(2)

C(6)

β(0)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

Introduction tâche fictive et sommet fictifD est contraint par B et C, tâches parallèles qui succèdent à une même tâche (A) et précèdent une même tâche (D).Il faut pouvoir identifier sans ambiguïté les sommets, d’où le sommet fictif S2’ et la tâche fictive β(0)

ε(0)



• Points délicats

1

A(2)

2

2’

B(2)

C(6)

β(0)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

Introduction tâche fictiveI n’est précédé que de EH est précédé de E et GLa tâche permet de ne pas représenter I comme dépendant de G

ε(0)


ε(0)


• Calcul des dates de début au plus tôt des tâches qui partent de S

1

A(2)

2

2’

B(2)

C(6)

β(6)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

2

4

8 13 19

15

210


ε(0)


• Calcul des dates de fin au plus tard des tâches qui aboutissent à S

1

A(2)

2

2’

B(2)

C(6)

β(6)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

2

4

8 13 19

15

210

8

2

8 13

19

19

0


ε(0)


• Chemin critique

1

A(2)

2

2’

B(2)

C(6)

β(0)

3D(5) 5

DébutFin

4

F(3)

G(6)

H(2)

E(2)I(2)

2

4

8 13 19

15

210

8

2

8 13

19

19

021


RRééseaux de transportseaux de transport

• Un réseau de transport est un graphe dont :

• Un sommet fictif E sans précédent figure le point de départ

• Un sommet fictif S sans suivant figure la fin

• Les autres sommets sont les nœuds du réseau

• Les arcs qui figurent les liaisons entre les sommets possèdent une capacité maximale de transport

• L’algorithme de Ford et Fulkerson permet de maximiser les flux qui circulent sur le réseau, compte tenu des capacités de transport.



Les stocks d’une entreprise sont conservés dans trois dépôts

ABC

Dépôt1004040

Quantité



Les besoins des trois clients

XYZ

Client12010040

Quantité



Les capacités du transporteur

4000

X304020

YABC

Transport200

30

Z



E

A

B

C

X

Y

Z

S

• Schématisons le réseau de transport



E

A

B

C

X

Y

Z

S

100

40

40

• Schématisons le réseau de transport : mes capacités de stockage



E

A

B

C

X

Y

Z

S

100

40

4040

100

120

• Schématisons le réseau de transport : ce qui doit être livré au client



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Schématisons le réseau de transport : ce que peut faire le transporteur


• Le flot (ou flux = flow) est la quantité réelle qui transite sur le réseau

• Il ne peut excéder la capacité des arcs

• Il est soumis à l’hypothèse de conservation ; la somme des flots qui arrivent à un nœud est égale la somme des flots qui en partent.




E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Première étape (1.1.) : Choix d’un flot de départ (défini et réparti au jugé)

• Ce qui part de E : 70 + 40 + 30 = 140

70

40

30

40

30

0

30

30

0

70

40

40

• Ce qui arrive à S : 70 + 40 + 30 = 140



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Première étape (1.2.) : Identification des arcs saturés

70

40

30

40

30

0

30

30

0

70

40

40



• Un chemin de E à S est saturé si au moins un des arcs est saturé

• Le flot est complet si tous les chemins de E à S sont saturés

• Qu’avons nous ?

Etude des chemins qui vont de E à S

Saturé (CZ)ECZS

Non saturéECYS

Saturé (EB et BY)EBYS

Non saturéEAZS

Saturé (AY)EAYS

Saturé (AX)EAXS



• Le flot n’est pas complet

• Pour le rendre complet, il faut saturer les chemins EAZS et ECYS

• Pour saturer ces chemins, il faut prendre le minimum des capacités résiduelles des arcs

Etude des chemins qui vont de E à S

Capacité EC = 40 – 30 = 10Capacité CY = 20 - = 20Capacité YS = 100 – 70 = 30 => 10

ECYS

Capacité EA = 100 – 70 = 30Capacité AZ = 20 – 0 = 20Capacité ZS = 40 – 30 = 10 => 10

EAZS



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Deuxième étape (2.1.) : Exploitation des capacités résiduelles

70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

• Le flot est complet (Tous les chemins ont un arc saturé) mais est-il maximal ?


•• Il est encore possible dIl est encore possible d’’augmenter le flot complet saugmenter le flot complet s’’il il existe une chaexiste une chaîîne (suite ordonnne (suite ordonnéée de sommets) non e de sommets) non satursaturéée de E e de E àà S.S.

•• La recherche des chaLa recherche des chaîînes non saturnes non saturéées ses s’’opopèère selon re selon ll’’algorithme suivant :algorithme suivant :

•• Marquer E tout suivant de E atteint par un arc non Marquer E tout suivant de E atteint par un arc non satursaturéé

•• Soit xi un sommet marquSoit xi un sommet marquéé du graphe. Il faut du graphe. Il faut éétudier tudier les suivants et les prles suivants et les prééccéédents de ce sommet et dents de ce sommet et marquer xi prmarquer xi prèès de :s de :

••Tout suivant non non encore marquTout suivant non non encore marquéé de xi atteint de xi atteint par un arc par un arc non saturnon saturéé

••Tout prTout prééccéédent non encore marqudent non encore marquéé de xi atteint de xi atteint par un arc par un arc dont le flot est non nuldont le flot est non nul




E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Troisième étape (3.1.) : Détermination du flot maximal par la recherche des chaînes non saturées

70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet A, suivant de E, atteint par un arc non saturé, est marqué de E

E



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet A, étant marqué, il faut étudier ses suivants et son précédent

E



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Les arcs AX et AY étant saturés, X et Y ne sont pas marqués

E



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

L’arc AZ n’étant pas saturé, marquer Z avec A

E

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le flot de l’arc EA étant non nul, inscrire A près du sommet E

E

A

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet Z étant marqué, il faut étudier son suivant et ses précédents

E

A

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

L’arc ZS étant saturé, ne rien inscrire près du sommet S

E

A

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le flot de l’arc CZ étant non nul, inscrire Z près de C

E

AZ

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet E étant marqué, il faut étudier ses suivants.

E

AZ

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Les arcs EB et EC étant saturés, rien n’est inscrit sur les suivants

E

AZ

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet C étant marqué, il faut étudier ses suivants et son précédent

E

AZ

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

L’arc CY n’étant pas saturé, inscrire C près du sommet Y

E

AZ

C

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Pour l’arc CZ, le sommet Z est déjà marqué et de toute maniere, CZ est saturé

E

AZ

C

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Pour l’arc EC, le sommet E est déjà marqué de A

E

AZ

C

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet Y étant marqué, il faut étudier son suivant et ses précédents

E

AZ

C

A



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

L’arc YS n’étant pas saturé, inscrire Y près du sommet S

E

AZ

C

A

Y



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le flot de l’arc BY étant non nul, inscrire Y près du sommet B

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Les sommets qui encadrent B étant déjàmarqués, le process est arrété

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Le sommet S est marqué. Il y a une chaîne non saturée et le flot complet n’est pas maximal

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

La chaîne non saturée est identifiée depuis S en allant à chaque fois au sommet de

marquage S <- Y <- C -> Z <- A <- E

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

La chaîne est donc E ->A->Z<-C->Y->S

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Troisième étape (3.2.) : Amélioration du flot

70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

L’amélioration du flot se fait en deux étapes

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Calcul de la capacitérésiduelle C1des arcs ->

E

AZ

C

A

YY

10Minimum

100 – 80 = 20Y -> S

20 – 10 = 10C -> Y

20 – 10 = 10A -> Z

100 – 80 = 20E -> A

CAPACITE RESIDUELLEARCS



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Calcul du flot minimum C2 des arcs <-

E

AZ

C

A

YY

30Minimum

30Z <- C

FLOT MINIMUMARCS



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10

40

30 + 10

40

30

10

30

30 + 10

0 + 10

70+10

40

40

Calcul minimum des minimums

E

AZ

C

A

YY

10Minimum

30C2

10C1



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40


70 + 10 + 10

40

30 + 10

40

30

10 + 10

30 - 10

30 + 10

10 + 10

70+10 + 10

40

40

On peut donc augmenter le flot de 10

=> Flot à 170

E

AZ

C

A

YY



E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

• Ce flot est-il maximal ?

• Pour le savoir, il faut réitérer le process pour déterminer s’il existe une chaîne non saturée

90

40

40

40

30

20

20

40

20

90

40

40




Le sommet A, suivant de E, atteint par un arc non saturé, est marqué de E

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40




Le sommet A étant marqué, il faut étudier ses suivants et son précédent

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40




Tous les arcs partant de A sont saturés. On ne marque rien

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40




Le flot de l’arc EA étant non nul, inscrire A près du sommet E

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40

A



• Seuls les sommets A et E peuvent être marqués.

• Il n’y a plus de chaîne non saturée de E à S

• Le flot de 170 est maximal

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40

A


•• La vLa véérification du fait que 170 constitue bien lrification du fait que 170 constitue bien l’’optimum se optimum se fait grâce fait grâce àà la coupe des derniers sommets marqula coupe des derniers sommets marquéés.s.

•• Soit F un sousSoit F un sous--ensemble de sommets du graphe ensemble de sommets du graphe contenant le sommet E mais pas le sommet Scontenant le sommet E mais pas le sommet S

•• La coupe associLa coupe associéée e àà F est lF est l’’ensemble des arcs reliant xi ensemble des arcs reliant xi ààxjxj, tels que xi , tels que xi ∈∈ F et F et xjxj ∉∉F (lF (l’’ensemble des arcs dont ensemble des arcs dont ll’’origine est marquorigine est marquéée et le et l’’extrextréémitmitéé ne lne l’’est pas)est pas)

•• La capacitLa capacitéé de la coupe est la somme des capacitde la coupe est la somme des capacitéés des s des arcs de la coupearcs de la coupe




• Coupe des derniers sommets marquésSoit l’ensemble F = {E,A} des derniers

sommets marquésF = (AX), (AY), (AZ), (EB), (EC)

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40

A



• Coupe des derniers sommets marquésLes arcs de la coupe sont en vertIls sont saturés. Il est donc impossible de faire pénétrer un flot supérieur dans l’ensemble des sommets non marqués

E

E

A

B

C

X

Y

Z

S40

100

40

40 20

30

40

100

120

20

30

40

90

40

40

40

30

20

20

40

20

90

40

40

A


•• ThThééororèème de me de FordFord--FulkersonFulkerson

•• Le flot maximal du graphe est Le flot maximal du graphe est éégal gal àà la capacitla capacitéé minimale minimale de la coupe des derniers sommets marqude la coupe des derniers sommets marquééss

•• La capacitLa capacitéé de la coupe est de la coupe est éégale gale àà

•• 40 + 40 + 20 + 30 + 40 = 17040 + 40 + 20 + 30 + 40 = 170

•• Ce qui correspond au flot maximal dCe qui correspond au flot maximal dééterminterminéé



•• Exercice 4 Application 4Exercice 4 Application 4


Documents

MATHEMATIQUES #1 - marcajp.pagesperso-orange.frmarcajp.pagesperso-orange.fr/france/chap14par01/pdfIntec205Maths/... · • Convention usuelle (Maths) • Notre convention (Tableur)