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

Dualité de programmation linéaire

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 le concept de la dualité de programmation linéaire (LP), explorant la relation entre les programmes linéaires primaires et doubles. Il traite du théorème de la dualité faible, de la lenteur complémentaire et du théorème de la dualité forte. L'instructeur explique l'interprétation des multiplicateurs de Lagrange, les solutions optimales et la relation entre les valeurs primaires et duales. Des exemples et des cartes doubles génériques sont utilisés pour illustrer les concepts, en mettant laccent sur le processus doptimisation et les contraintes de faisabilité. La séance de cours se termine par des idées sur les polyèdres et des solutions réalisables de base.

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)

Rom Pinchasi

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.

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (32)

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é.

Verdier duality

In mathematics, Verdier duality is a cohomological duality in algebraic topology that generalizes Poincaré duality for manifolds. Verdier duality was introduced in 1965 by as an analog for locally compact topological spaces of Alexander Grothendieck's theory of Poincaré duality in étale cohomology for schemes in algebraic geometry. It is thus (together with the said étale theory and for example Grothendieck's coherent duality) one instance of Grothendieck's six operations formalism.

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é de Poincaré

En mathématiques, le théorème de de Poincaré est un résultat de base sur la structure des groupes d'homologie et cohomologie des variétés, selon lequel, si M est une variété « fermée » (i.e. compacte et sans bord) orientée de dimension n, le k-ième groupe de cohomologie de M est isomorphe à son (n – k)-ième groupe d'homologie, pour tout entier naturel k ≤ n : La dualité de Poincaré a lieu quel que soit l'anneau de coefficients, dès qu'on a choisi une orientation relativement à cet anneau ; en particulier, puisque toute variété a une unique orientation mod 2, la dualité est vraie mod 2 sans hypothèse d'orientation.

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.

Afficher plus

Séances de cours associées (36)

Dualité de programmation linéaire

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

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.

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.

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.

Optimisation : Problèmes classiques

Couvre les problèmes classiques d'optimisation, les algorithmes de force brute et l'optimisation linéaire entière.

Afficher plus

Concepts associés (32)

Dualité (mathématiques)

Verdier duality

Dualité (optimisation)

Dualité de Poincaré

Feasible region

Afficher plus