Algorithme d'Euclide

des mati` eres Introduction 5 I 9 Th´ eorie, formulation et algorithmes de r´ esolution 1 Mod´ elisation pour la programmation math´ ematique 11 2 Programmation lin´ eaire 2.1 Un exemple : formulation, repr´esentation et r´esolution . . 2.1.1 Le probl`eme de la nourriture pour chiens . . . . . 2.1.2 Cas de figure des solutions possibles . . . . . . . . 2.1.3 Recherche d’optimum . . . . . . . . . . . . . . . . 2.1.4 Un algorithme ´el´ementaire du simplexe . . . . . . 2.1.5 R´esum´e . . . . .

Optimisation linéaire Algorithme du simplexe Recherche opérationnelle Génie Civil Rappel Si un problème de programmation linéaire en forme standard possède une solution optimale, alors il existe une solution de base admissible qui soit optimale. Méthode du simplexe : passer d’une solution de base admissible à l’autre, en réduisant le coût. Algorithme du simplexe Michel Bierlaire 3 Problème avec – – – A matrice m lignes n colonnes lignes de A linéairement indépendantes On note

ALGORITHME DU SIMPLEXE Considérons le problème de programmation linéaire suivant : Max Z = 2x1 + x2 x1 + x2 6 3x1 + 4x2 9 x1 0 , x2 0 La mise sous forme standard (introduction des variables d'inactivité x3 et x4) donne : Max Z = 2x1 + x2 x1 + x2 + x3 = 6 3x1 + 4x2 + x4 = 9 x1 0 , x2 0, x3 0, x4 0 On passe de cette forme standard au tableau suivant : |x1 |x2 |x3 |x4 |R |

. . . . . . . . . . 3 Lagrangien et point selle 3.1 Point selle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Théorie de Kuhn et Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II Algorithmes 4 Méthodes de descente. Problèmes sans contraintes 4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . 4.2 Méthode de relaxation . . . . . . . . . . . . . . . 4.3 Méthode du gradient . . . . . . . . . . . . . . . . 4.3.1 Méthode à pas variable

  problme  d’ordonnancement  et  méthode  de  Pert,   et  flots  dans  les  réseaux  et  algorithme  de  Ford   Fulkerson,  problème  du  plus  courts  chemins.     •  Programma0on  linéaire  :  modélisa0on  des   problèmes,  de  la  resolu0on  graphique  au   algorithme  du  simplexe.  Problème  de  la  dualité  et   méthode  dual-­‐simplexe.     •  Modèle  de

lin´aire ` valeurs enti`res. e e a e Il est peut-ˆtre surprenant de constater que la presque totalit´ des probl`mes d’optimie e e sations ´nonc´s dans ce cours (hormis ceux relevant de la programmation dynamique) e e peuvent ˆtre r´solus ` l’aide d’un algorithme de programmation lin´aire. Cependant, e e a e des solutions sp´cifiques, par exemple au probl`me du flot maximal ou du flot de e e coˆt total minimal dans un r´seau, sont propos´es. Elles sont souvent d´velopp´es u e e e e a ` partir d’un programme

Complexité & optimalité Chap-3: Algorithmes de tri: analyse et estimation de la complexité Chap-4: Récursivité     Différents types de récursivité Dérécursivation d’algorithmes Récursivité terminale et non terminale Paradigme « diviser pour régner »   Chap-5: Graphes et arbres Chap-6: Arbres binaires de recherche Objectifs du cours          Elaborer des algorithmes performants et efficaces Comprendre la notion de complexité d’un algorithme Maîtriser la récursivité

Cours 4 : les tableaux, recheche et tri 1 Cours ´ La structure de donnees tableau et quelques algorithmes • La structure de donn´e tableaux e • Evaluation de polynˆmes, recherche de minimum o • Les algorithmes de tri • Les algorithmes de recherche s´quentiel et dichotomique e Cours 4 : les tableaux, recheche et tri 2 Tableaux: d´claration/initilisation e Tableau= collection de donn´es homog`nes, accessibles par un indice entier. e e D´claration d’un type tableau e type = tableau

ˆtre exprim´s comme e e e e 2. L’algorithme du simplexe des programmes lin´aires. e 3. Simplexe : comment ´viter les pi`ges e e • Les programmes lin´aires peuvent ˆtre r´solus efficacement e e e 4. Dualit´ e par certains algorithmes. 5. Programmation lin´aire en nombres entiers e • Ce sont d’excellents exemples de questions pratiques dont la r´solution n´cessite une combinaison de m´thodes e e e algorithmiques, de math´matiques ´l´mentaires et de bon e ee sens

. . . . . 2.2.4 Variable d’´carts . . . . . . . . . . . . . . . . . . . . . . . e 2.3 Solutions de base r´alisables . . . . . . . . . . . . . . . . . . . . . e 2.4 Propri´t´s g´om´triques des solutions de base r´alisables . . . . . ee e e e 2.5 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 L’algorithme du simplexe proprement dit : la phase 2 . . 2.5.2 M´thode des dictionnaires . . . . . . . . . . . . . . . . . . e 2.5.3 M´thode des tableaux . . . . . . . . . . . . .