Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Programmation linéaire : optimisation et dualité

Dans cours

MGT-483: Optimal decision making

This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marketing, transportation and finance to transform data into ...

Description

Cette séance de cours couvre les bases de la programmation linéaire, en mettant l'accent sur l'optimisation et les concepts de dualité. Il explique comment formuler et résoudre des problèmes de programmation linéaire, en introduisant les problèmes primaires et doubles. L'instructeur discute de la méthode simplex et de la théorie de la dualité, illustrant leur application à travers des exemples.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e

Daniel Kuhn

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (26)

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

Contrainte (mathématiques)

En mathématiques, une contrainte est une condition que doit satisfaire la solution d'un problème d'optimisation. On distingue deux types de contraintes : les contraintes d'égalité et les contraintes en inégalité. L'ensemble des solutions satisfaisant toutes les contraintes est appelé l'ensemble admissible. On considère un problème d'optimisation classique : avec et et désigne le vecteur . Dans cet exemple, la première ligne montre la fonction à minimiser (appelée fonction objectif ou fonction-coût) mais aussi l'ensemble où la solution doit être recherché, ici C.

Programmation par contraintes

La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).

Dualité (optimisation)

En théorie de l'optimisation, la dualité ou principe de dualité désigne le principe selon lequel les problèmes d'optimisation peuvent être vus de deux perspectives, le problème primal ou le problème dual, et la solution du problème dual donne une borne inférieure à la solution du problème (de minimisation) primal. Cependant, en général les valeurs optimales des problèmes primal et dual ne sont pas forcément égales : cette différence est appelée saut de dualité. Pour les problèmes en optimisation convexe, ce saut est nul sous contraintes.

Économie mathématique

vignette|Les acteurs économiques (STN et actionnaires) sont classés par importance décroissante, donnée par . Un point de données situé en () correspond à une fraction des principaux acteurs économiques détenant cumulativement la fraction du contrôle, de la valeur ou des revenus d'exploitation du réseau. Les différentes courbes se réfèrent au contrôle du réseau calculé avec trois modèles (LM, TM, RM), voir l'annexe S1, section 3.1, et aux revenus d'exploitation. La ligne horizontale indique une valeur égale à .

Afficher plus

Séances de cours associées (32)

Programmation linéaire : correspondance bipartite pondérée

Couvre la programmation linéaire, la correspondance bipartite pondérée et les problèmes de couverture de sommet en optimisation.

Dualité de programmation linéaire

Couvre la dualité de programmation linéaire et la condition de relâchement complémentaire.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Optimisation avec contraintes : conditions KKT

Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.

Techniques d'optimisation linéaire: approches de résolution de problèmes

Fournit un aperçu des techniques d'optimisation linéaire, en mettant l'accent sur les méthodes de résolution de problèmes et l'importance des contraintes et des fonctions objectives.

Afficher plus

Concepts associés (26)

Optimisation (mathématiques)

Contrainte (mathématiques)

Programmation par contraintes

Dualité (optimisation)

Économie mathématique

Afficher plus