Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Graphes et Recherche Op´ erationnelle ESIAL 2` eme ann´ ee Notes de cours de J.

Graphes et Recherche Op´ erationnelle ESIAL 2` eme ann´ ee Notes de cours de J.-F. Scheid 2010-2011 2 Table des mati` eres 1 Introduction g´ en´ erale 5 1.1 Quelques exemples et domaines d’applications de la R.O. . . . . . . . . . . . . . . . . . . 5 1.2 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Contenu du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 El´ ements de bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Programmation lin´ eaire 11 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 Mod´ elisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.2 R´ esolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Formes g´ en´ erales d’un programme lin´ eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Forme canonique mixte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Forme canonique pure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.3 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.4 Variable d’´ ecarts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Solutions de base r´ ealisables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Propri´ et´ es g´ eom´ etriques des solutions de base r´ ealisables . . . . . . . . . . . . . . . . . . . 16 2.5 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.1 L’algorithme du simplexe proprement dit : la phase 2 . . . . . . . . . . . . . . . . 17 2.5.2 M´ ethode des dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.3 M´ ethode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.4 Finitude du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5.5 Initialisation et variables artiﬁcielles : la phase 1 . . . . . . . . . . . . . . . . . . . 27 2.6 Analyse post-optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6.1 Analyse post-optimale de l’objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6.2 Analyse post-optimale du second membre des contraintes . . . . . . . . . . . . . . 29 2.7 Dualit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7.1 Introduction et d´ eﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7.2 Propri´ et´ es - Th´ eor` emes de dualit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7.3 Conditions d’optimalit´ e primal-dual (COPD) . . . . . . . . . . . . . . . . . . . . . 33 3 4 TABLE DES MATI` ERES Chapitre 1 Introduction g´ en´ erale Une d´ eﬁnition possible de la R.O pourrait ˆ etre la suivante : il s’agit d’un ensemble de m´ ethodes d’analyse scientiﬁque (maths et info.) des ph´ enom` enes d’organisation qui traite de la maximisation d’un proﬁt, d’une performance, d’un rendement ou bien de la minimisation d’un coˆ ut, d’une d´ epense. La R.O. est avant tout un outil d’aide ` a la d´ ecision. Le sch´ ema g´ en´ eral suivi par ces m´ ethodes est : Probl` eme concret (de type R.O) →mod´ elisation → r´ esolution par une m´ ethode de R.O →interpr´ etation des r´ esultats →prise de d´ ecision. 1.1 Quelques exemples et domaines d’applications de la R.O. 1. Un premier exemple : Les ponts de K¨ onigsberg (Euler 1735). Deux ˆ ıles de la ville sont reli´ ees entre elles par 1 pont. D’autre part 6 autres ponts relient les ˆ ıles ` a la ville. La question pos´ ee est la suivante : ` a partir d’un point de d´ epart quelconque, existe-t-il un chemin passant une et une seule fois par chaque pont et qui revient au point de d´ epart ? Fig. 1.1 – La ville de K¨ onigsberg et ses 7 ponts. La r´ eponse (apport´ ee par Euler) est NON. La preuve utilise un graphe : les arˆ etes du graphe repr´ esentent les ponts et les sommets correspondent aux diﬀ´ erents endroits de la ville : les rives gauche et droite et les deux ˆ ıles (cf. Figure 1.2). Supposons qu’un tel chemin existe. Un tel chemin est appel´ e chemin eul´ erien. Alors n´ ecessairement en chacun des noeuds du graphe il y a toujours un nombre pair d’arˆ etes reli´ ees au noeud : s’il y a une arˆ ete qui arrive au noeud, il y en a n´ ecessairement une autre (diﬀ´ erente) qui le quitte. Or, on constate que le graphe poss` ede des noeuds (tous en fait !) reli´ es ` a un nombre impair d’arˆ etes. Par cons´ equent, il n’existe pas de chemin eul´ erien. 5 6 CHAPITRE 1. INTRODUCTION G´ EN´ ERALE A C B D Fig. 1.2 – Graphe associ´ e au probl` eme des ponts de K¨ onigsberg 2. Graphe et PageRank Classement des pages Web utilis´ e par les moteurs de recherches. Le web est mod´ elis´ e ` a l’aide d’un graphe orient´ e dont les sommets j repr´ esentent les pages du Web et les arcs j →i les hyperliens. Fig. 1.3 – Exemple de pages uploads/Management/ et-grphe-imp.pdf