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

Le problème du transbordement : l’unimodularité totale

Description

Cette séance de cours couvre le problème de transbordement sous forme standard, la matrice d'incidence, les solutions optimales utilisant la règle de Cramer, et le concept d'unimodularité totale dans les matrices. Il comprend également des exemples et l'intégralité des solutions de base dans les polyèdres.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Source officielle

Concepts associés (16)

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.

Matrice d'incidence

En mathématiques, et plus particulièrement en théorie des graphes, la matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens arrivent sur quels sommets. La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe et p est le nombre de liens (arêtes ou arcs). Cette matrice est définie de deux façons différentes selon que le graphe est orienté ou non orienté.

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

Afficher plus

Séances de cours associées (30)

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, Dégénérescence MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Couvre les contraintes linéaires et la dégénérescence dans les polyèdres, en se concentrant sur les solutions de base et les cas dégénérés.

Optimisation : Problèmes classiques

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

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, la matrice d'incidence et l'unimodularité totale.

Afficher plus

Concepts associés (16)