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 et le théorème d'unimodularité totale. Il explique comment la matrice d'incidence d'un réseau est totalement unimodulaire, conduisant à des solutions optimales entières pour le problème de transbordement lorsque le vecteur d'approvisionnement est entier.

Dans MOOC

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

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (19)

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.

Matrice unimodulaire

En algèbre linéaire, une matrice unimodulaire sur l'anneau des entiers relatifs est une matrice carrée à coefficients entiers dont le déterminant vaut +1 ou –1. Plus généralement, une matrice unimodulaire sur un anneau commutatif A est une matrice inversible à coefficients dans A, dont l'inverse est aussi à coefficients dans A. Le groupe général linéaire GL(A) des matrices unimodulaires de taille n sur l'anneau A est donc constitué des matrices dont le déterminant est inversible dans A.

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

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.

Structure d'incidence

vignette| Exemples de structures d'incidence: Exemple 1: Points et droites du plan euclidien Exemple 2: Points et cercles Exemple 3: Structure définie par une matrice d'incidence. En mathématiques, une structure d'incidence est toute composition de deux types d'objets dans le plan euclidien : des points ou l'équivalent de points et des droites ou l'équivalent de droites et d'une seule relation possible entre ces types, les autres propriétés étant ignorées et la structure pouvant ainsi se représenter par une matrice.

Afficher plus

Séances de cours associées (50)

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.

Le problème du transbordement : formulaire standard MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Couvre le problème d'optimisation linéaire du modèle de transbordement.

Méthodes exactes : Branche et Liée MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore l'algorithme Branch et Bound dans une optimisation discrète, en trouvant efficacement des solutions optimales en calculant des limites inférieures sur des sous-ensembles.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

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

Explore la résolution de problèmes d'optimisation discrets en assouplissant les contraintes d'intégralité.

Afficher plus

Concepts associés (19)

Optimisation linéaire en nombres entiers

Matrice unimodulaire

Matrice d'incidence

Optimisation linéaire

Structure d'incidence

Afficher plus