Séance de cours

La dualité dans la programmation linéaire

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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 dualité en programmation linéaire, explorant la relation entre les problèmes primaires et duaux. Il traite du théorème de la dualité, du relâchement complémentaire et de la dualité forte. La séance de cours se penche également sur l'interprétation des solutions optimales et l'importance des régions réalisables dans les deux problèmes primaires et doubles.

Enseignant·e·s (2)

Friedrich Eisenbrand

Enseignement et PhD Doctorant·es actuel·les Ruben Manuel Skorupinski, Neta Singer, Lukas Vogl, Jiaye Wei A dirigé les thèses EPFL de Thomas Rothvoss, Nicolai Hähnle, Martin Niemeier, Adrian Aloysius Bock, Carsten Moldenhauer, Alfonso Bolívar Cevallos Manzano, Manuel Francesco Aprile, Igor Malinovic, Christoph Hunkenschröder, Moritz Andreas Venzin, Jana Tabea Cslovjecsek A co-dirigé les thèses EPFL de Puck van Gerwen Cours Algèbre linéaire avancée II - diagonalisation MATH-115(a) L'objectif

Rom Pinchasi

Enseignement et PhD Cours The Maths of Puzzles MATH-704

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (32)

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.

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

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.

Optimisation convexe

vignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.

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.

Afficher plus

Séances de cours associées (64)

Dualité de programmation linéaire

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

Dualité de programmation linéaire

Explore la dualité de programmation linéaire, couvrant la dualité faible, la dualité forte, l'interprétation des multiplicateurs de Lagrange et les contraintes d'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.

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.

Afficher plus

Concepts associés (32)

Optimisation linéaire

Dualité (mathématiques)

Dualité (optimisation)

Optimisation convexe

Dualité de Poincaré

Afficher plus