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. L’optimisation linéaire (OL) est la discipline qui étudie ces problèmes. Elle est également désignée par le nom de programmation linéaire, terme introduit par George Dantzig vers 1947, mais cette appellation tend à être abandonnée à cause de la confusion possible avec la notion de programmation informatique. Par exemple, le problème à deux variables suivant qui consiste à minimiser la fonction linéaire sous la contrainte d'inégalité affine x + 2x ≥ 2 et les contraintes de positivité des x est un problème d'optimisation linéaire. Sa solution est (x , x) = (0,1). Dès que le nombre de variables et de contraintes augmente, le problème ne peut plus se résoudre par tâtonnement. Plus généralement, un problème d'OL s'écrira donc en notation matricielle de la manière suivante où est l'inconnue, le vecteur des variables réelles x,...,x à optimiser, et les données sont des vecteurs et et une matrice . L'inégalité vectorielle Ax ≤ b doit être entendue composante par composante : pour tout indice i, on doit avoir (Ax – b) ≤ 0. Lensemble admissible est donc bien un polyèdre convexe, puisqu'il s'agit de l'intersection des demi-espaces , pour i = 1,...,m, en nombre fini. Un problème de maximisation se ramène à la formulation précédente en minimisant l'opposé de la fonction-coût sur le même polyèdre convexe. Parmi les problèmes d'optimisation avec contraintes d'inégalité, les problèmes linéaires sont simples à résoudre numériquement. On connaît en effet des algorithmes polynomiaux efficaces, requérant donc un nombre d'itérations qui est majoré par un polynôme, fonction des dimensions du problème.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (32)
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 p
CS-450: Algorithms II
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
MGT-483: Optimal decision making
This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marke
Afficher plus
Publications associées (32)
Concepts associés (14)
Optimisation (mathématiques)
L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.
Enveloppe convexe
L'enveloppe convexe d'un objet ou d'un regroupement d'objets géométriques est l'ensemble convexe le plus petit parmi ceux qui le contiennent. Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. L'idée serait la même dans l'espace avec un ballon qui se dégonflerait jusqu'à être en contact avec tous les points qui sont à la surface de l'enveloppe convexe.
Problème du voyageur de commerce
vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.
Afficher plus

Graph Chatbot

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.