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

Théorèmes de dualité

Dans cours

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Description

Cette séance de cours couvre les théorèmes faibles et forts de la dualité dans la programmation linéaire, expliquant la relation entre les solutions primaires et les solutions duales optimales. Il traite également du relâchement complémentaire et des conséquences d'une dualité forte, soulignant l'importance de solutions réalisables et optimales. La séance de cours se termine par les implications de la dualité faible, de la dualité forte et de la condition de relâchement complémentaire pour toutes les solutions optimales, soulignant l'importance des dégénérescences dans les problèmes primaires et dual.

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·s (2)

Friedrich Eisenbrand

Friedrich Eisenbrand's main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems in practice. Before joining EPFL in March 2008, Friedrich Eisenbrand was a full professor of mathematics at the University of Paderborn. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004 and the Otto Hahn medal of the Max Planck Society in 2001.

Rom Pinchasi

Source officielle

Concepts associés (14)

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.

Feasible region

In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.

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.

Dualité (mathématiques)

thumb|Dual d'un cube : un octaèdre. En mathématiques, le mot dualité a de nombreuses utilisations. Une dualité est définie à l'intérieur d'une famille d'objets mathématiques, c'est-à-dire qu'à tout objet de on associe un autre objet de . On dit que est le dual de et que est le primal de . Si (par = on peut sous-entendre des relations d'isomorphies complexes), on dit que est autodual. Dans de nombreux cas de dualité, le dual du dual est le primal. Ainsi, par exemple, le concept de complémentaire d'un ensemble pourrait être vu comme le premier des concepts de dualité.

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.

Afficher plus

Séances de cours associées (46)

Dualité de programmation linéaire

Explore la dualité de programmation linéaire, couvrant les contraintes, les variables, les solutions et la relation entre les LP primal et dual.

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é : la dualité dans l’optimisation linéaire MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Couvre le concept d'optimisation linéaire et la relation de dualité entre les problèmes primaires et duaux.

Dualité, relaxation des contraintes MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Explore la dualité et la relaxation des contraintes dans les problèmes d'optimisation avec des exemples pratiques.

La dualité dans la programmation linéaire Connectez-vous à Mediaspace pour regarder cette vidéo

Explore le concept de dualité dans la programmation linéaire, en discutant de la relation entre les problèmes primaires et duaux.

Afficher plus

Concepts associés (14)

Optimisation linéaire

Feasible region

Dualité (optimisation)

Dualité (mathématiques)

Optimisation linéaire en nombres entiers

Afficher plus