CNAM Belfort – RCP101 : Recherche opérationnelle et aide à la décision par Philippe Canalda Recherche opérationnelle et aide à la décision RCP101 Philippe

CNAM Belfort – RCP101 : Recherche opérationnelle et aide à la décision par Philippe Canalda

Recherche opérationnelle et aide à la décision

RCP101Philippe Canalda

[email protected] <[email protected]>

http://psm-serv.univ-fcomte.fr/~pcanalda/cnam

Le 20/03/2008

CNAM Belfort – RCP101 : Recherche opérationnelle et aide à la décision

2

par Philippe Canalda

Références

• Livres de référence (principaux)– Auteurs Titre– Thomas Cormen, INTRODUCTION A L'ALGORITHMIQUE

Charles Leiserson et Ronald Rivest, (chez Dunod)

– Faure, Lemaire, Picouleau Précis de Recherche Opérationnelle, 5ème édition Dunod ;

– Groupe Roseaux Exercices et problèmes résolus de recherche opérationnelle, tome3, Masson ;

– Minoux M. Programmation Mathématique : théorie des algorithmes, 2 tomes ; Dunod.

• Matériel requis : – les livres de Cormen, Leiserson et Rivest

et Faure, Lemaire et Picouleau• Matériel produit :

– vidéo-projection + prises de notes– Un support sur les graphes et optimisations – 2 supports sur la programmation linéaire

Le 20/03/2008


3


Plan 1/4

1. Introduction• Génèse.• Enjeux.• Techniques, méthodes et outils : un aperçu.• Structures ordonnées, applications des treillis et de l’algèbre de

Boole en RO. Exercices• Eléments de complexité (des algorithmes et des problèmes).

Exercices.2. Graphes et ordonnancement en gestion de projet• Rappels des concepts élémentaires de théorie des graphes :

définitions générales, graphes orientés, graphes non orientés, quelques graphes particuliers, représentation des graphes, parcours dans un graphe, exercices.

• …

Le 20/03/2008


4


Plan 2/4

2. Graphes et ordonnancement en gestion de projet• …• Application des graphes à la RO• Aperçu de méthodes de résolution : approche incrémentale,

récursive, notions de programmation dynamique, algorithmes gloutons, problèmes linéaires ou non linéaires avec contraintes, exercices ;

• Problème du chemin de valeur optimale entre 2 sommets, exercices ;

• Ordonnancement de projets : méthode PERT et MPM (chemins critiques, marges), exercices ;

• Traitement des contraintes cumulatives (budget) : flot de valeur maximale, flot de valeur maximale à coût maximal, affectation, arbres optimaux, programmes de transport, …, exercices.

Le 20/03/2008


5


Plan 3/43. Programmation linéaire et applications à l’entreprise• Généralités : origine, domaines d’application, pertinence.• Introduction géométrique puis algébrique à l’algorithme du

simplexe : conditions d’existence de solutions (notation MIN, MAX), applications linéaires matricielles, formes analytiques des programmes linéaires, exercices.

• Problème de la base initiale : méthode à 2 phases de Dantzig, méthodes des pénalités (ou du grand M), exercices.

• Dualité : introduction, illustration, dualité dans le formalisme particulier et dans le cas général, propriétés mathématiques, interprétation économique, exercices.

• Analyse en sensibilité (paramétrages) : critiques de la programmation linéaire, paramétrage de la fonction économique, paramétrage du second membre (analyse post-optimale), exercices.

4. …

Le 20/03/2008


6


Plan 4/4

4. Analyse multicritère et systèmes interactifs d’aide à la décision (SIAD)

• Méthodologies, concepts fondamentaux.• Méthodes ELECTRE, « Goal-programming ».• Présentation des SIAD (intérêts, limites).5. Processus stochastique et programmation dynamique

stochastique6. Eléments de théorie des files d’attente et de sûreté de

fonctionnement• Loi de Poisson, exponentielle.• File d’attente M/M/1 et applications.• Fiabilité des composants, des systèmes (notions).• Paramètres de la sûreté de fonctionnement.

Le 20/03/2008


7


Evaluation

• Examen sur table

• Mini projet– Soit un algo d’optimisation

ex : introduire les fdt ds un algo (de prog dyn/géné) résolvant le N-TSP s’appliquant sur 1 territoire multi-convergent

– Soit un exposé plus collectif sur la gestion des taxis dans le cadre du transport flexible public

– Autre … travail personnel

Le 20/03/2008


8


1.3 Techniques, méthodes et outils : un aperçu.

• <Exercices > : – « Rend la monnaie »,

• Etant donnée, d’une part une liste de pièces (ordonnée ou non)et étant donné un montant de monnaie à rendre

• Calculer les combinaisons de pièces à rendre La meilleure Toutes Une

• Discussion

– « Les huit reines » – « Affectation de ressources »

Le 20/03/2008


9


Interaction – Affectation de Ressources

• Ensemble de groupes d ’étudiants ou liste, avec le nombre– Schéma– Ordonnee : 3, 15, 17, …, 127, …– Ou non ordonnée : 17, 3, 127, 15, …

• Ensemble ou liste de classes avec les capacités– 20, 30, 30, 70, …

• Problème : trouver, si elle existe, une affectation ou on s ’assure que chaque groupe aura une affectation de classe

• Rmq : les problèmes peuvent toujours se complexifier comme :trouver l’affectation qui :

Minimise le taux d’occupation Ou bien qui le maximise

Le 20/03/2008


10


Interaction – Affectation de Ressources (suite)

• Exemple : Ge = 120, 15, 3, 84, 45• Gc= 30, 90, 89, 30, 140

• La méthode basique : – Parcourir Ge de g->d

et pour chaque élément du tableau parcourir Gc de g->d en cherchant à trouver une affectation libre

• Cette méthode aboutit à un échec : 126 à 140, 15 à 30, 3 à 90, 84 à 89, mais nous ne pouvons plus affecter 45

• Rmq: une solution est plus facilement trouvable lorsque l’on ordonne les éléments manipulés. Par exemple le choix croissant, ou décroissant, d’ordonner la liste des groupes. De même pour la liste des classes et de leurs contenances.

Le 20/03/2008


11


« Rend la monnaie »

• Etant donnée, d’une part une liste de pièces (ordonnée ou non) et étant donné un montant de monnaie à rendre

On se donne une Liste ordonnée L={5, 2, 1, 0.5, 0.2, 0.1, 0.05}avec L[0]=5, … L[6]=0.05

Un montant m=12,35 euros de monnaie à rendre

• Calculer les combinaisons de pièces à rendre– La meilleure– Toutes– Une– Discussion

Le 20/03/2008


12


« Rend la monnaie » : vers une solution

L={5, 2, 1, 0.5, 0.2, 0.1, 0.05} avec L[0]=5, … L[6]=0.05m=12.35 euros

• Calculer les combinaisons de pièces à rendre– La meilleure, toutes, une, discussion

Idée : calculer

» i) le nombre de pièces de 5 euros à rendre sur 12.35 => 2, » ii) le reste => 12.35 – 2 * 5 = 2.35, » iii) passer à la pièce suivante

et recommencer les étapes i) et ii) jusqu’à la fin de la liste ou bien jusqu’à ce que le reste soit nul

Le 20/03/2008


13


« Rend la monnaie » : vers une solution

L={5, 2, 1, 0.5, 0.2, 0.1, 0.05} avec L[0]=5, … L[6]=0.05m=12.35 euroscalculer

» i) le nombre de pièces de 5 euros à rendre sur 12.35 => 2,

» ii) le reste => 12.35 – 2 * 5 = 2.35,

» iii) passer à la pièce suivante et recommencer les étapes i) et ii) jusqu’à la fin de la liste ou bien jusqu’à ce que le reste soit nul

• Itérer l’exemple, • Automatiser, concevoir votre programme• analyser la méthode :

– exactitude/preuve, observation de la solution/généralisation, amélioration/complexité

Le 20/03/2008


14


Itérer l’exemple


» i) le nombre de pièces à rendre sur m=12.35,i=0, L[0]=5quotient= 2 = 12.35/5 = m/L[i]

» ii) le reste m= 2.35 = 12.35%5 = m%L[i],

» iii) passer à la pièce suivante et recommencer les étapes i) et ii) jusqu’à la fin de la liste ou bien jusqu’à ce que le reste soit nuli++

Le 20/03/2008


15


Automatiser, concevoir votre programme

•?(Programme itératif, récursif, parallèle, …)

Puis analyser la méthode : – exactitude/preuve, observation de la

solution/généralisation, amélioration/complexité

Le 20/03/2008


16


Exemple de solution


» Tant que (m <> 0) et (i< L.length) faire // invariant de boucle // on a calculé les occurrences optimales des pièces situées // au rang 0..i-1 Ecrire m/L[i] + « pièces de » + L[i] + « euros » m = m%L[i++]fin tant que// conditions de sortie de la boucle:// m == 0 ou i>= L.length

analyser la méthode : exactitude/preuve, observation de la solution/généralisation, amélioration/complexité

Le 20/03/2008


17


analyser la méthode :

• exactitude/preuve, – Déjà fait

• observation de la solution/généralisation, – Calcul de la meilleure solution si elle existe.

Elle marche lorsque/parce que• La liste est ordonnée en ordre décroissant

Contre-exemple évident

• Les éléments situés aux rangs I+1 et au-delà sont générateurs (pour constituer n’importe quel montant, a fortiori < à celui L[i])

L={5, 2, 1.5} m=9.5

Le 20/03/2008


18



• Remarques :– Méthode gloutonne qui calcule l’optimal lorsque le

meilleur choix local (fait à l’indice i) conduit au meilleur choix global qqsoient les indices suivants

– Cf cours prochain sur les graphes et les méthodes d’optimisation gloutonnes

Le 20/03/2008


19



– Calcul d’une solution? De toutes les solutions ?

?

Souvent il s’agit d’appréhender une approche récursive

Le 20/03/2008


20


Exemple de solution bis

Nouvelles étapes :

» représenter la solution» Générer les solutions récursivement» Traiter la condition d’arrêt

L={5, 2, 1, 0.5, 0.2, 0.1, 0.05} avec L[0]=5, … L[6]=0.05m=12.35 euros, S_fifo={}calculer

» Tant que (m <> 0) et (i<= L.length) faire // INVARIANT // on calcule toutes les occurrences des pièces situées // au rang 0..i-1 // on stocke ces occurrences dans une liste FIFO pour j allant de 0 à m/L[i] faire S_fifo.add(j) RelancerCalcul(L, m- j * L[i], i+1, S_fifo) S_fifo.retirerlasteltinséré fin tant que

Le 20/03/2008


21


• Fin 1er cours

Le 20/03/2008


22


Recette méthodologique

• Pour résoudre un problème, il existe plusieurs recettes:– La première consiste à trouver un algorithme résolvant une

version qui simplifie la solution. Ceci peut-être obtenue • en généralisant le problème

Ne pas limiter le nombre d’occurrences des pièces

• En le simplifiant du point de vue combinatoire Ordonner la liste des pièces dans l’ordre décroissant des valeurs des

pièces

– Ensuite, il est toujours plus aisé de rajouter des contraintes comme limiter le nombre d’occurrences des pièces

– Mais il le sera moins de tenir compte d’une liste non ordonnée mais que nous pourrons ordonner pour se ramener au problème que nous aurons su résoudre ou bien entrevoir la solution

Le 20/03/2008


23


Travail personnel :

• Résoudre le problème avec limitation du nombre d’occurrences des pièces

• Avancer le support

Le 20/03/2008


24


Exemple de solution bis Nouvelles étapes :

» représenter la solution» Générer les solutions récursivement» Traiter la condition d’arrêt

L={5, 2, 1, 0.5, 0.2, 0.1, 0.05} avec L[0]=5, … L[6]=0.05m=12.35 euros, S_fifo={}calculer

» If m==0 // solution trouvée ecrire S_fifoelse // m<>0 if i >= L.length // pas de solution else // m<>0 et i <= L.length // on continue // on calcule toutes les occurrences des pièces situées // au rang 0..i-1 et on stocke ces occurrences dans une liste FIFO pour j allant de 0 à m/L[i] faire S_fifo.add(j) RelancerCalcul(L, m- j * L[i], i+1, S_fifo) S_fifo.retirerlasteltinséré fin pour

Le 20/03/2008


25


• Programme– Conduire le programme récursif– Appliquer la méthode à l’exercice des 8 reines– Présenter

• les structures ordonnées• Des applications des treillis et• de l’algèbre de Boole • Exercices

Le 20/03/2008


26


• Fin 2ème cours

• Début 3ème cours– Tableau first in first out

• Fichiers spéciaux : file d’attente• Implantation de cette liste

En tableau En tableau et liste circulaire avec les modulo Les listes pointeur de façon abstraite

– // labouebe : pourquoi les le snap-shot (duplicate) de l’échiquier avant le placement de la reine peut permettre de traiter du LLisme ?

– Voir inscription de Yann Deboeuf

Le 20/03/2008


27



• exactitude/preuve, – Déjà fait grâce à l ’invariant et avec un déroulement de

programme

• observation de la solution/généralisation, – Calcul de toutes les solutions existantes.

Elle marche que• La liste soit ordonnée en ordre décroissant ou non

le lancement se fait avec RelancerCalcul(L, m, i=0, S_fifo={})

Le 20/03/2008


28


déroulage

• Appliquer le programme précédent sur un exemple court mais réaliste…

– Une taille |L|=2,– Une liste ordonnée décroissante, ou non ordonnée– Une liste qui montre l’intérêt de générer

exhaustivement les solutions– une solution à laquelle vous pourrez apporter des

modifications d’optimisations

• L={3, 2}

Le 20/03/2008


29


« Les huit reines »

• Etant donnée, une taille de l’échiquier et un nombre de reines à placer

• Calculer les combinaisons des positionnements des reines– Toutes– Certaines selon heuristiques (positions du cavalier)– Discussion

Le 20/03/2008


30


Chapitre 1

• Structures ordonnées

• Treillis

• Algèbre de Boole

• Applications

• Exercices

Le 20/03/2008


31


Chapitre 1 : Structures ordonnées

• Notions

• Algèbres de Boole

Le 20/03/2008


32


Chapitre 1 : Structures ordonnées

• Relations, relations binaires, propriétés– Une relation désigne n’importe quel sous-ensemble

du produit cartésien de 2 ou de plusieurs variables

• Exemple 1– Prod_cart = A x B avec A = {a,b,c} et

B={e1,e2,e3,e4}alors Prod_cart={(a,e1), (a,e2), (a,e3), (a,e4), (b,e1), (b,e2), (b,e3), (b,e4), (c,e1), (c,e2), (c,e3), (c,e4)}admet le sous-ensemble R={(a,e2), (b,e1), (c,e4)}

Le 20/03/2008


33


Chapitre 1 : Structures ordonnées• relation binaire

– Une relation binaire sur E (abus de langage) est un sous-ensemble de E x E

• Exemple 2– Prod_cart E x E, avec E =

{x, y, z}Représentation matricielle ou sous-forme de tableau

(x,x) (x,z)

(y,y)

(z,x)

(x,x) (x,y) (x,z)

(y,x) (y,y) (y,z)

(z,x) (z,y) (z,z)

(x,x) (x,y)

(y,z)

(z,x) (z,z)

Produitcartésien R2

R1

Le 20/03/2008


34


Ch1, Relations spéciales• Relation diagonale

– Δ = {(x,x), (y,y), (z,z)}

• Relation réflexive– Contient la diagonale

• Relation symétrique– Prtt (x, y) in E x E alors (y,x) in

ExE• R1 est symétrique mais n’est pas

réflexive

• Relation anti-symétrique– Prtt x et y , (y,x) not in R si (x,y)

in R, sauf si x=y• R2 est anti-symétrique mais n’est

pas réflexive

(x,x) (x,z)

(y,y)

(z,x)

(x,x) (x,y)

(y,z)

(z,x) (z,z)

R2

R1

Le 20/03/2008


35


Ch1, Relations spéciales• Relation transitive

– Si (x,y) et (y,z) in R alors (x,z) in R

• Les contraires : irréflexif, asymétrique et intransitif– R est irréflexive si elle contient

aucun élément diagonal– Elle est asymétrique si elle n’est

symétrique pour aucun couple de R

– Elle est intransitive si elle n’est transitive pour aucune paire de couples de R

(x,x) (x,y) (x,z)

(y,z)

(z,z)

R4

R3

X,x X,y X,t

Y,x Y,y Y,t

Z,z

T,x T,y T,t

Le 20/03/2008


36


Ch1, Relations spéciales• Qualifier R3 et R4 ? (x,x) (x,y) (x,z)

(y,z)

(z,z)

R4

R3

X,x X,y X,t

Y,x Y,y Y,t

Z,z

T,x T,y T,t

– R3• Pas réflexive, anti-symétrique et

transitive

– R4• Réflexive, symétrique et transitive

Le 20/03/2008


37


Ch1, Relations spéciales• Qualifier R5 et R6 ? (x,y)

(y,z)

(z,x)

R6

R5– R5• irréflexive, asymétrique et intransitive

– R6• Elle n’est rien …

ou plutôt elle est non réflexive, non symétrique et non transitive

(x,x) (x,y) (x,z)

(y,z)

(z,x)

Le 20/03/2008


38


• Heuristique : pour trouver les graphes circulaires à une composante connexe

• Tester si irréfexif• Intransitf• Et asymétrique

Le 20/03/2008


39


• Programme– Présenter

• La suite des structures ordonnées• Les treillis et des applications• L’algèbre de Boole • Exercices

• Eléments de complexité (des algorithmes et des problèmes). Exercices.

• 2. Graphes et ordonnancement en gestion de projet• Rappels des concepts élémentaires de théorie des graphes :


…

Le 20/03/2008


40


Ch1 : Préordre, équivalence, ordre

• Une relation de préordre est une relation réflexive et transitive• Une relation d’équivalence est une relation réflexive, symétrique

et transitive• Une relation d’ordre (large) est réflexive, antisymétrique et

transitive• Exemple du critérium des champions

– Les champions sont classés selon la relation « avoir obtenu un rang meilleur ou aussi bon que » :

• 1er Camille, • 2ème ex aequo Anatole et Désiré,• 4ème Ernest• 5ème Bernard

– Donner la représentation sous-forme de tableau avec A=Anatole, B=Bernard, …, E=Ernest

Le 20/03/2008


41


• Fin de cours 3

Le 20/03/2008


42


Exemple du critérium des champions


• 1er Camille, • 2ème ex aequo Anatole et

Désiré,• 4ème Ernest• 5ème Bernard


(a,a)

(b,b)

(c,c)

(d,d)

(e,e)

réflexif

Le 20/03/2008


43


Exemple du critérium des champions


• 1er Camille, • 2ème ex aequo Anatole et

Désiré,• 4ème Ernest• 5ème Bernard


(a,a) (a,b) (a,d) (a,e)

(b,b)

(c,a) (c,b) (c,c) (c,d) (c,e)

(d,a) (d,b) (d,d) (d,e)

(e,b) (e,e)

réflexif, non symétrique, et transitif, n’est pas anti-symétrique

Le 20/03/2008


44


Exemple de relation d’équivalence

– Considérons la relation « être parallèle à ou confondu avec », pour les 2 groupes de droites parallèles suivantes : A || C et B || D || E.

• Donner la représentation sous-forme de tableau

– En considérant l’exemple du critérium, déterminer les classes d’équivalence

(a,a) (a,c)

(b,b) (b,d) (b,e)

(c,a) (c,c)

(d,b) (d,d) (d,e)

(e,b) (e,d) (e,e)

réflexif, symétrique, et transitif2 classes {A,C} et {B,D,E}

Le 20/03/2008


45


Vers un ordre strict…

– Il est manifeste que {A,D} forme une classe d’équivalence. Et cela correspond assez à la relation « avoir le même rang que ».

– En faisant le quotient du pré-ordre par cette relation d’équivalence on obtient 4 classes qui s’ordonnent strictement 2 à 2 selon la relation « avoir un meilleur rang que » :

• Les 4 classes {C}, {A, D}, {E} et {B}• Avec {C} > {A, D} > {E} > {B}

– Réordonner le tableau suivant les rangs croissants C, A, D, E et B

– Donner le tableau de la relation stricte sur les classes

– Qualifier cette relation et remarquer qu’elle est irréflexive, asymétrique et transitive

(a,a) (a,b) (a,d) (a,e)

(b,b)

(c,a) (c,b) (c,c) (c,d) (c,e)

(d,a) (d,b) (d,d) (d,e)

(e,b) (e,e)

Le 20/03/2008


46


Un ordre au sens large (i.e. moins strict)

– Rappel : Elle est réflexive, anti-symétrique et transitive

– Soit N* et la relation x | y (x divise exactement y, sans reste / ou encore x modulo y ==0).

• Montrer que la relation est un ordre au sens large

• Soit X un sous-ensemble de N* tel que X={1, 2, 3, 5, 10, 20, 30}Calculer le tableau représentant x | y sur X

Le 20/03/2008


47


Ordres partiels et totaux

– Rappel : Elle est réflexive, anti-symétrique et transitive

– Soit N* et la relation x | y (x divise exactement y, sans reste / ou encore x modulo y ==0).

• Montrer que la relation est un ordre au sens large

• Soit X un sous-ensemble de N* tel que X={1, 2, 3, 5, 10, 20, 30}Calculer le tableau représentant x | y sur X

(1,1) (1,2) (1,3) (1,5) (1,10) (1,20) (1,30)

(2,2) (2,10) (2,20) (2,30)

(3,3) (3,30

(5,5) (5,10) (5,20) (5,30)

(10,10) (10,20) (10,30)

(20,20)

(30,30)

La réflexivité est visible,l’anti-symétrie aussi,la transitivité un peu moins

tous les éléments ne sont pas comparables au dessus de la diagonale

Le 20/03/2008


48


Ordres partiels et totaux

– La relation d’ordre est partielle lorsque tous les éléments ne sont pas comparables 2 à 2

– Sinon elle est totale

Le 20/03/2008


49


Représentation sagittale et diagramme de Hasse

– Dans une représentation sagittale• 2 éléments a et b sont représentés chacun par 1 pt, • ils sont réunis par un arc orienté a – b si a R b

Exemple si a | b il y a autant d’arcs que de couples dans la représentation tableau de la même relation

– Dans le diagramme de Hasse, les arcs qui résultent de la réflexivité et de la transitivité sont supprimés

• Donner ces 2 représentations de la relation « | » sur X• Énumérer des 3 représentations informatiques : tableau, sagittal,

diagramme de Hasse• Donner les algorithmes qui produisent les 2 dernières représentations à

partir de la 1ère représentation (le tableau à 2 dimensions)

Le 20/03/2008


50


• L’exercice de transformation de la matrice sagittale en diagramme de Hasse est TRES intéressant.

• Il exploite l’ordonnancement des éléments de N* manipulés.

Le 20/03/2008


51


– Excellente prise de note :» NotesCoursN°4.pdf

– Support de cours :» cours1..4.pdf

Le 20/03/2008


52


• Programme– Présenter

• Les éléments particuliers d’un ensemble ordonné• Les treillis et des applications• L’algèbre de Boole • Exercices

• Eléments de complexité (des algorithmes et des problèmes). Exercices.

• 2. Graphes et ordonnancement en gestion de projet• Rappels des concepts élémentaires de théorie des graphes :


…

Le 20/03/2008


53


Quelques propriétés

• Pour obtenir une représentation d’un ordre strict à partir d’un ordre large (réflexive, antisymétrique et transitive) il faut …

• … il faut supprimer la diagonale.

Rmq :

1 une relation réflexive, asymétrique et transitive définit un ordre strict.

2 elle peut induire un ordre partiel ou bien un ordre total

• Exemple :– représentez la relation stricte correspondant à ‘||’ qui signifie divise (à la manière euclidienne) et

n’est pas égal.L’ordre obtenu est-il strict ou partiel ? Justifiez.

Le 20/03/2008


54


Quelques propriétés

• A toute relation <= (ou <) correspond une relation converse >= (>, respectivement)

Question : comment l’obtiendriez-vous cette relation converse ?

• Symétrie par rapport à la diagonale

Le 20/03/2008


55


Les éléments particuliers d’un ensemble ordonné (1/3)

• Définition : un ensemble sur lequel est défini une relation d’ordre (partiel ou total) est dit (partiellement ou totalement) ordonné.

• X un ensemble partiellement ordonné par la relation <=, et une partie P de X– Un minorant m de P est un élément m de X qui est <= tout

élément x de P• Similairement, un majorant M de P est un élément M de X qui est >= tout

élément x de P

– Un élément maximal de P est un élément M de P pour lequel il n’existe pas d’élément de P > à M

• Similairement, un élément minimal de P est un élément M de P pour lequel il n’existe pas d’élément de P < à M

Le 20/03/2008


56


Les éléments particuliers d’un ensemble ordonné (2/3)

– Le plus grand élément E (maximum) de P est tel que, pour tout x de P on a E >= x

• Similairement, le plus petit élément e (minimum) de P est tel que, pour tout x de P on a e <= x

– La borne supérieure (b.s.) B (suprémum) de P, noté aussi supP est le plus petit élément de l’ensemble des majorants de P.

• Similairement la borne inférieure (b.i.) b (infimum) de P, noté aussi infP est le plus grand élément de l’ensemble des minorants de P.

– L’élément universel de X est le plus grand élément de X.– L’élément nul de X est le plus petit élément de X.

• Rmq : tous ces éléments n’existent pas forcément, dû au fait notamment que parfois les éléments ne sont pas comparables.

Le 20/03/2008


57


Les éléments particuliers d’un ensemble ordonné : Exemple (3/3)

• Soit X={1, 2, 3, 5, 10, 20, 30}, un ensemble ordonné partiellement par la relation x | y (x divise y).Pour les deux parties suivantes, – P_1={2,3,5,10} et P_2={2,5,10}

• qualifiez les les majorants de P, les minorants de P, les éléments maximaux et les éléments minimaux, le plus grand élément de P, le plus petit élément de P, la b.s., la b.i., l’élément universel et l’élément nul.

Le 20/03/2008


58


– Prise de note <à fournir/venir>:» NotesCoursN°5.pdf


Le 20/03/2008


59


Les éléments particuliers d’un ensemble ordonné (Synthèse)

• Définition : un ensemble sur lequel est défini une relation d’ordre (partiel ou total) est dit (partiellement ou totalement) ordonné.

• X un ensemble partiellement ordonné par la relation <=, et une partie P de X– Un minorant m de P est un élément m de X qui est <= tout élément x de P

• Similairement, un majorant M de P est un élément M de X qui est >= tout élément x de P

– Un élément maximal de P est un élément M de P pour lequel il n’existe pas d’élément de P > à M

• Similairement, un élément minimal de P est un élément M de P pour lequel in n’existe pas d’élément de P < à M

– Le plus grand élément E (maximum) de P est tel que, pour tout x de P on a E >= x• Similairement, le plus petit élément e (minimum) de P est tel que, pour tout x de P on a e <= x

– La borne supérieure (b.s.) B (suprémum) de P, noté aussi supP est le plus petit élément de l’ensemble des majorants de P.

• Similairement la borne inférieure (b.i.) b (infimum) de P, noté aussi infP est le plus grand élément de l’ensemble des minorants de P.

– L’élément universel de X est le plus grand élément de X.– L’élément nul de X est le plus petit élément de X.

Le 20/03/2008


60



résultat 1• Soit X={1, 2, 3, 5, 10, 20, 30}, un ensemble ordonné

partiellement par la relation x | y (x divise y).– P={2,3,5,10}

Les majorants de P, 30 Les minorants de P, 1 les éléments maximaux, {3, 10} et les éléments minimaux, {2, 3, 5} le plus grand élément de P, inexistant le plus petit élément de P, inexistant la b.s. de P de X, 30 la b.i., 1 l’élément universel, inexistant et l’élément nul, 1

Le 20/03/2008


61



résultat 2• Soit X={1, 2, 3, 5, 10, 20, 30}, un ensemble ordonné

partiellement par la relation x | y (x divise y).– P={2,5,10}

Les majorants de P, {10, 20, 30} Les minorants de P, {1} les éléments maximaux, {10} et les éléments minimaux, {2, 5} le plus grand élément de P, {10} le plus petit élément de P, inexistant la b.s. de P, 10 la b.i. de P, 1 Inchangés

» l’élément universel, inexistant » et l’élément nul, 1

Le 20/03/2008


62


Exemples d’usages de ces éléments particuliers 1/2

• La connaissance a priori des données sur lesquelles un calcul combinatoire (ou des optimisations) doi(ven)t s’opérer.

– cas où l’usage du calcul succède nettement dans le temps à la disponibilité des données …

• => optimisations dites statiques ou le résultat peut être stocké sous la forme de tableaux, diagramme sagittal / graphe / automate, diagramme de Hass, etc.Cette partie statique peut parfois correspondre à une génération de données et/ou de code qui, une fois compilées et ajoutées à un noyau d’optimisation dynamique, produira après compilation puis exécution les résultats attendus (voir ci-après).

– … et où parfois l’usage a posteriori (dé)limite le champ d’application du calcul combinatoire sur les données initiales

• => optimisations dites dynamiques qui exploiteront peut-être les traitements statiques antérieurs consécutivement à, et de manière pas nécessairement exclusive,

Compilation, filtrage, parcours d’automate ou de graphe ou …

Le 20/03/2008


63


Exemples d’usages de ces éléments particuliers 2/2 a

• Sur un réseau ou territoire donné, nous disposons des distances séparant les nœuds 2 à 2.Dans un premier temps, et à des fins de simplification, nous comptabiliserons le nombre de segments/arcs séparant différents points/nœuds (d’un graphe)

G=(N={0,1,2,3,4,5,6,7,8},E={(0,5),(0,7),(5,7),(5,3),(3,6),(3,2),(7,3),(7,8),(7,1),(7,4),(4,8), (5,1)})

• Nous souhaitons écrire un programme qui, étant donné un sous-ensemble de ces nœuds et arcs, calcule la liste des noeuds rangés par ordre croissant des distances à un nœud particulier donné.

» Pour le nœud 0 et le sous-ensemble N0={1,3,4,5,7} et les arcs associés E0={={(0,5),(0,7),(5,7),(7,3),(7,1),(7,4), (5,1)}et le résultat attendu est L0={0,5,7,1,3,4}

Le 20/03/2008


64


Exemples d’usages de ces éléments particuliers 2/2 b

• G=(N={0,1,2,3,4,5,6,7,8},E={(0,5),(0,7),(5,7),(5,3),(3,6),(3,2),(7,3),(7,8),(7,1),(7,4),(4,8),(5,1)})

» Pour le nœud 0 et le sous-ensemble N0={0,1,3,4,5,7} et les arcs associés E0={(0,5),(0,7),(5,7),(7,3),(7,1),(7,4), (5,1)}et le résultat attendu est L0={0,5,7,1,3,4}

– Il s’agit de calculer les plus courts chemins depuis 0 vers tous les points (par extension de tout point en tout point),

– de ranger dans L les nœuds en fonction de la distance croissante (mais aussi par ordre alphanumérique en cas d’égalité _ car nous avons un ordre partiel)

– puis lors de l’optimisation dynamique il suffit de parcourir la liste initiale L en exhibant les index des nœuds présents dans N0.

Le 20/03/2008


65


– Prise de note <à fournir/venir>:» NotesCoursN°6.pdf


Le 20/03/2008


66


Exemples d’usages de ces éléments particuliers 2/2 c

• Il s’agit de calculer les plus courts chemins depuis 0 vers tous les points (par extension de

tout point en tout point), de ranger dans L les nœuds en fonction de la distance croissante (mais aussi par

ordre alphanumérique en cas d’égalité _ car nous avons un ordre partiel) puis lors de l’optimisation dynamique il suffit de parcourir la liste initiale L en

exhibant les index des nœuds présents dans N0.• Donner la représentation matricielle,• Caractériser la relation (propriétés)• Donner la représentation sagittale• La représentation du diagramme de Hasse a-t-elle un sens dans le cas présent et

pourquoi• Concevez l’algorithme i) qui calcule les plus courts chemins de tout point en 0• Etendez cet algo en un algo ii) qui retourne la liste ordonnée totalement selon les

distances puis, en cas d’égalité, la liste ordonnée selon l’ordre alphanumérique• Concevez l’algorithme iii) qui calcule la sous-liste L0 correspondant au sous-graphe

G0=(N0,EO)=G\{2,4,6,8}• Concevez l’algo qui étend i) en iv) qui calcule les plus courts chemins de tout point

en tout point• Discussion EXERCICE TRES INTERESSANT A REALISER

Le 20/03/2008


67


Les treillis – définition 1/2

• Lorsque la partie P de X est réduite à 2 éléments (« paire ») {x,y}, il peut exister une b.s. et/ou une b.i.– La b.s. lorsqu’elle existe se note x V y– La b.i. lorsqu’elle existe se note x Λ y

• Définition : on appelle treillis un ensemble partiellement ordonné dans lequel, pour toute paire d’éléments, il existe une b.s. et une b.i.

• Propriété : la définition axiomatique de la page 7 peut être substituée

• Bas de la page 7 preuve de 4’

Le 20/03/2008


68


Suite au bas de la page 7

– Les propriétés et exercices sur les treillis• Preuves par développements et réductions• Preuves par l’absurde

– L’algèbre de Boole– Isomorphisme de l’algèbre de Boole à un corps d’ensemble

Le 20/03/2008


69


Les treillis – définition 2/2

• Soit un ensemble T, dont les éléments sont munis de 2 lois de composition, V (OU) et Λ (ET), vérifiant, Qqsoit x, y et z Є T, les propriétés :

• 1’- x OU y = y OU x (commutativité) 1- x ET y = y ET x• 2’- x OU (y OU z) = (x OU y) OU z (associativité) 2- x ET (y ET z) = (x ET y) ET z• 3’- x OU x = x (idempotence) 3- x ET y = x• 4’- x OU (x ET y) = x (absorption) 4- x ET (x OU y) = x

• Alors T constitue un ensemble ordonné par la relation ≤ telle que :

• 5- [x ≤ y] [x ET y] = x [x OU y] = y

• T est un treillis

Le 20/03/2008


70


Les treillis – exemple• Considérons l’ensemble T des diviseurs de 30 : 1, 2, 3, 5, 6, 10,

15, 30,ordonnés par la relation x | y.

• Si l’on considère le diagramme de Hasse associé (et que vous construirez),et si l’on considère que la b.s. de 2 éléments est leur ppcm et que la b.i. de 2 éléments est leur pgdc,

• Alors T, associé à b.i. et b.s. forment un treillis• L’élément universel est 30, l’élément nul est 1.• De façon générale, N* ordonné par ‘|’ présente une structure de treillis infini dont l’élément nul est

toujours 1 et n’ayant pas d’élément universel• Élaborer les 2 diagrammes de Hasse, celui pour x | y, puis la nouvelle relation

Le 20/03/2008


71


Les treillis – autres définitions 1/2

• Un treillis T avec élément nul n et élément universel U est complémenté si, qqsoit x de T, il existe une association possible d’un élément x noté x-barre telle que:

• 6- x OU x-barre = U et 6’- x ET x-barre = n

• Exercice– vérifier si le treillis de l’exemple précédent est complémenté– Montrer que le système d’axiomes (1-4), (1’-4’) n’est pas minimal,

tout spécialement vous pourrez montrer que l’absorption entraîne l’idem-potence. Ainsi le système d’axiomes (1, 2, 4, 1’, 2’, 4’) est minimal ou générateur.

Le 20/03/2008


72


Les treillis – autres définitions 2/2

• Un treillis est distributif si, aux axiomes 1à 4 et 1’ à 4’ s’ajoutent, qqsoit x, y et z de T:

• 7- x OU (y ET z) = (x OU y) ET (x OU z)

• Exercice– Ces axiomes entraînent :

• 7’- x ET (y OU z) = (x ET y) OU (x ET z)

– Inversement 7’ entraîne 7– Dans un treillis distributif la complémentation est unique

(démonstration par l’absurde)

• Un treillis à la fois distributif et complémenté est appelé treillis de Boole. Il est isomorphe à une algèbre de Boole qui est :

– Un ensemble partiellement ordonné, doté d’un élément nul et d’un autre universel, dont les éléments vérifient 1à 4, 1’ à 4’, 6, 6’, 7La relation d’ordre est définie par une des 4 relations suivantes :

• 5*- [x ≤ y] [x ET y] = x [x OU y] = y x ET y-barre = 0 x OU y-barre =1, avec n=0 et U=1

Le 20/03/2008


73


Une algèbre de Boole

• Une algèbre de Boole à un générateur, différent de 0 et de 1, comporte 4 éléments. (diagramme de Hasse)

• A 2 éléments, il comporte 16 éléments.(cf. page 9)

• Théorème de Stone : Toute algèbre de Boole est isomorphe à un corps d’ensemble.

• Exemple : à partir de l’algèbre de Boole à 2 générateurs a et b tels que a != b et a ET b ! = 0,on fait plus clairement apparaître …

Le 20/03/2008


74


Corps d’ensemble

• Exemple : à partir de l’algèbre de Boole à 2 générateurs a et b tels que a != b et a ET b ! = 0,on fait plus clairement apparaître …

Dans une forme parallélépipédique (diagramme d’Euler-Venn) représentant l’univers 1 :A, B, A ∩ B, A ∩ B-barre, A-barre ∩ B, A-barre ∩ B-barrequi sont des « régions » correspondant aux atomes respectifsa, b, a ET b, a OU b-barre, a-barre ET b, a-barre ET b-barre

• On appelle corps d’ensembles une famille de parties d’un ensemble, munie des opérations ensemblistes classiques (réunion, intersection, complémentation).

Le 20/03/2008


75


Corps d’ensemble

• Représentation ensembliste des algèbres de Boole– Logique aristotélicienne (bas de la page 13)– Principe de contradiction (page 14)– Formules de Morgan (pages 15-…)

Le 20/03/2008


76


La suite déjà traitée en pointillée

• Représentation ensembliste des algèbres de Boole– Logique aristotélicienne (bas de la page 13)– Principe de contradiction (page 14)– Formules de Morgan (pages 15-…)

• L’algèbre de Boole binaire (pages 22- …)• Notions de complexité (pages 48-…)• Éléments de la théorie des graphes : définition, concepts

essentiels, parcours des graphes (pages 60-…)• Application des graphes à la recherche opérationnelle

– Notions de programmations dynamiques (pages 95-…)– …

Documents

CNAM Belfort – RCP101 : Recherche opérationnelle et aide à la décision par Philippe Canalda Recherche opérationnelle et aide à la décision RCP101 Philippe