Ce cours a pour but de présenter des algorithmes fondamentaux d'optimisation.

Une première partie décrit l'optimisation linéaire, en particulier l'algorithme du simplexe, son fonctionnement, son interprétation géométrique. Cet algorithme est traité de manière détaillée puisque nous présentons à la fois les phases I et II, et nous traitons la dualité afin d'obtenir des algorithmes de réoptimisation rapides. Nous présentons aussi quelques applications de la programmation linéaire et de la dualité. Certaines de ces applications sont d'ordre théorique comme le célèbre théorème de l'alternative ou le lemme de Farkas, d'autres sont plus pratiques comme l'utilisation de la programmation linéaire pour résoudre des problèmes de théorie des jeux avec des stratégies mixtes.

Dans une deuxième partie, nous abandonnons le cadre confortable de la programmation linéaire pour nous focaliser sur des programmes dans lesquels la fonction objectif (ou bien les contraintes) sont non linéaires. Dans ce cadre, nous étudions plus spécifiquement la programmation convexe et, en particulier, la programmation quadratique et ses liens avec la programmation linéaire.

Programmation linéaire

• Généralités sur la programmation linéaire.
• Forme générale, standard, canonique d'un programme linéaire (PL).
• Aspect géométrique : polyèdres ; points extrêmes.
• Bases ; solutions de base réalisables.
• Fondements de l'algorithme du simplexe.
• Phases I et II de l'algorithme du simplexe ; dégénérescence et convergence.
• Méthode révisée du simplexe.

Dualité en programmation linéaire

• Dual d'un programme linéaire (PL).
• Théorème d'existence et de dualité.
• Algorithme dual du simplexe.
• Lemme de Minkowski-Farkas.

Applications pratiques de la PL

• Problèmes de transport et d'affectation.
• Jeux à deux joueurs à somme nulle.
• Théorème MINIMAX ; Jeux symétriques ; Résolution d'un jeu par la PL.

Rappels d'optimisation sans contraintes

• Optimisation uni-dimensionnelle.
• Méthodes de gradient.
• Méthodes de gradient conjugué.

Programmation non linéaire

• Généralités : programmation convexe ; lagrangien ; programmation différentiable.
• Théorème du col en programmation convexe.
• Conditions de Kuhn et Tucker en programmation convexe et/ou différentiable.
• Méthode du gradient projeté de Rosen.
• Programmes quadratiques (PQ).

• V. Chvatal (1983) « Linear Programming », W.H. Freeman & Company.
• R. J. Vanderbei (1998) « Linear Programming: Foundations and Extensions », Kluwer Academic Publishers.
• M. Minoux (1983) « Programmation mathématique, Théorie et Algorithmes », Dunod.
• D. De Werra, T.M. Liebling, J.-F. Hêche (2003) « Recherche Opérationnelle pour Ingénieurs I », Presses polytechniques et universitaires romandes.

Cours 1 :	( transparents)	( 1/page)	( 4/page)
Cours 2 :	( transparents)	( 1/page)	( 4/page)
Cours 3 :	( transparents)	( 1/page)	( 4/page)
Cours 4 :	( transparents)	( 1/page)	( 4/page)
Cours 5 :	( transparents)	( 1/page)	( 4/page)
Cours 6 :	( transparents)	( 1/page)	( 4/page)
Cours 7 :	( transparents)	( 1/page)	( 4/page)
Cours 8 :	( transparents)	( 1/page)	( 4/page)
Cours 9 :	( transparents)	( 1/page)	( 4/page)
Cours 10 :	( transparents)	( 1/page)	( 4/page)
Cours 11 :	( transparents)	( 1/page)	( 4/page)
Cours 12 :	( transparents)	( 1/page)	( 4/page)
Cours 13 :	( transparents)	( 1/page)	( 4/page)
Cours 14 :	( transparents)	( 1/page)	( 4/page)

Le poly de cours dans son intégralité  

• le poly de résolution de systèmes linéaires de Jean-Yves Jaffray
• le poly de programmation linéaire de Jean-Yves Jaffray
• le poly d'optimisation non linéaire de Jean-Yves Jaffray