Programmation mathématique

Code UE : US331C

  • Cours
  • 4 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Compétences visées

Capacité à modéliser un problème d'optimisation discrète ou mixte par la programmation mathématique. Connaissance des principales méthodes permettant de le résoudre.

Contenu

Dans une première partie, on montrera comment aborder par la programmation mathématique les problèmes d'optimisation combinatoire que l'on rencontre dans de nombreux domaines d'applications. On présentera différentes méthodes de résolution en insistant sur la phase de modélisation. On introduira dans une deuxième partie les méthodes dites polyédriques qui fournissent un cadre général et efficace pour la résolution de ces problèmes. Cette méthodologie a été à l'origine de progrès importants en optimisation combinatoire. La troisième partie du cours est une initiation à la programmation semi-définie qui est un cas particulier de la programmation convexe. La SDP permet d'obtenir des bornes de très bonne qualité pour de nombreux problèmes d'optimisation combinatoires difficiles et est également à la base d'heuristiques efficaces pour ces problèmes. Contenu détaillé : Modélisation, choix d'une formulation, exemples concrets. Programmation linéaire et non linéaire en nombres entiers, prétraitements. Dualité et décomposition lagrangienne. Réductions, linéarisations, relaxations convexes. Notions essentielles relatives à la description des polyèdres. Inégalités valides en programmation linéaire en nombres entiers. Coupes de Chvatal-Gomory. Le problème de séparation. Application au problème du voyageur de commerce. Quelques rappels sur les matrices positives, formes primale et duale d'un programme semi-défini. Modélisation et étude de plusieurs problèmes d'optimisation combinatoire.

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Lieu(x)
Lieu(x)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr

Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

Enseignement non programmé s'il s'agit d'un diplôme, d'un certificat ou d'une UE ou enseignement qui ne fait jamais l'objet d'une programmation s'il s'agit d'une UA ou d'une US (le code formation commence alors par UA ou US).