Calcul de plus courts chemins dans un environnement 2D et 3D
Plan du cours
Séance 1 : Programmation linéaire réelle
Programmation liénaire réelle dans P (admis). Programme canonique. Programme équationnel. Tableau. Solution basique. Variables dans la base et hors base. Algorithme du simplexe. Terminaison avec règle de Bland. Prétraitement pour obtenir un tableau avec solution basique.
Programmation linéaire réelle Programmation linéaire réelle(version longue)
Séance 2 : Dualité en programmation linéaire (séance à diviser en deux la prochaine année)
Motivation pour certificat. Programme dual. Illustration avec le problème du calcul d'un plus court chemin. Théorème de dualité faible et forte. Coefficients magiques. Théorème des écarts complémentaires. Interprétration physique de la dualité. Matrices totalement unimodulaires. Théorème de König. Théorème min-max de Von Neumann dans les jeux à sommes nulles.
Dualité en programmation linéaire Dualité en programmation linéaire(version longue)
Séance 3 : Algorithmes d'approximation
Algorithmes PTAS, FPTAS. Classes de complexité PTA, FPTA, APX. Couverture de sommets. Couverture de sommets pondérés et relaxation linéaire. Innapproximalité du problème de voyageur de commerce (TSP). TSP avec inégalité triangulaire. Algorithme de Christofides.
Algorithmes d'approximation Algorithmes d'approximation(version longue)