Séance de cours

Contraintes linéaires, Dégénérescence

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.

Description

Cette séance de cours couvre les contraintes linéaires et la dégénérescence dans les polyèdres, en se concentrant sur des exemples de polyèdres dans R2 et leurs formes équivalentes dans R5. L'instructeur explique le concept de solutions de base et définit les solutions de base dégénérées comme celles où plus de contraintes sont actives que de variables ou plus de variables sont nulles que la différence entre les variables et les contraintes.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation linéaire

Ce que vous apprendrez Formulation : vous apprendrez à partir d'exemples simples comment formuler, transformer et caractériser un problème d'optimisation. Contraintes : vous apprendrez à représenter les contraintes d'un problème d'optimisation linéaire, à la fois d'un point de vue géométrique et algébrique. Dualité : vous apprendrez à dériver un problème complémentaire appelé "dual". Conditions d'optimalité : vous apprendrez les conditions suffisantes et nécessaires pour une solution optimale. Méthode du si

Source officielle

Concepts associés (10)

Polyèdre

Un polyèdre est une forme géométrique à trois dimensions (un solide géométrique) ayant des faces planes polygonales qui se rencontrent selon des segments de droite qu'on appelle arêtes. Le mot polyèdre, signifiant à plusieurs faces, provient des racines grecques πολύς (polys), « beaucoup » et ἕδρα (hedra), « base », « siège » ou « face ». Un polyèdre est un solide dont toutes les faces sont des polygones. Les côtés de ces polygones sont appelés arêtes. Les extrémités des arêtes sont des points appelés sommets.

Dual d'un polyèdre

En géométrie, il existe plusieurs façons (géométrique, combinatoire) de mettre les polyèdres en dualité : on peut se passer de support géométrique et définir une notion de dualité en termes purement combinatoires, qui s'étend d'ailleurs aux polyèdres et polytopes abstraits. Dans chaque cas, à tout polyèdre est associé un polyèdre appelé dual du premier, tel que : le dual du polyèdre dual est le polyèdre initial, les faces de l'un sont en correspondance avec les sommets de l'autre, en respectant les propriétés d'adjacence.

Goldberg polyhedron

In mathematics, and more specifically in polyhedral combinatorics, a Goldberg polyhedron is a convex polyhedron made from hexagons and pentagons. They were first described in 1937 by Michael Goldberg (1902–1990). They are defined by three properties: each face is either a pentagon or hexagon, exactly three faces meet at each vertex, and they have rotational icosahedral symmetry. They are not necessarily mirror-symmetric; e.g. GP(5,3) and GP(3,5) are enantiomorphs of each other.

Polyèdre flexible

En géométrie, un polyèdre flexible, ou flexaèdre, est un polyèdre que l'on peut déformer continûment sans changer la forme de ses faces. Le théorème de rigidité de Cauchy montre qu'un tel polyèdre ne peut être convexe. Les premiers exemples de polyèdres flexibles, les , furent découverts par Raoul Bricard en 1897. Ce sont des surfaces auto-intersectantes (on parle parfois de polyèdres croisés, ou étoilés).

Schönhardt polyhedron

In geometry, the Schönhardt polyhedron is the simplest non-convex polyhedron that cannot be triangulated into tetrahedra without adding new vertices. It is named after German mathematician Erich Schönhardt, who described it in 1928. The same polyhedra have also been studied in connection with Cauchy's rigidity theorem as an example where polyhedra with two different shapes have faces of the same shapes. One way of constructing the Schönhardt polyhedron starts with a triangular prism, with two parallel equilateral triangles as its faces.

Afficher plus

Séances de cours associées (17)

Contraintes linéaires : Solutions de base MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Explore les solutions de base dans les contraintes linéaires et l'équivalence avec les sommets.

Contraintes linéaires et sommets MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Explore l'importance des sommets dans l'optimisation et décrit une méthode pour les identifier en utilisant l'algèbre linéaire.

Le problème du transbordement : l’unimodularité totale MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Couvre le problème de transbordement, les solutions optimales et l'unimodularité totale dans les matrices.

Optimisation : Problèmes classiques

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

Bases de la programmation linéaire

Couvre les bases de la programmation linéaire, définissant les coins, les points extrêmes et les solutions réalisables dans les polyèdres.

Afficher plus

Concepts associés (10)

Schönhardt polyhedron

Afficher plus