Séance de cours

Programmation Linéaire Mixte: Formules et Applications

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

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, marketing, transportation and finance to transform data into ...

Description

Cette séance de cours couvre la motivation derrière la programmation linéaire mixte (MILP) en soulignant la nécessité de modéliser des problèmes pratiques avec des variables discrètes. Il explique le concept de variables binaires dans les LP, la formulation de LP mixtes, et leurs applications dans les problèmes de prise de décision tels que le problème du sac à dos 0-1 et le problème daffectation. La séance de cours explore également les relations entre les événements, les contraintes disjonctives et les contraintes de forçage dans les MILP. Il se termine par une discussion sur la force des relaxations LP, la formulation idéale pour un problème entier, et l'importance de formuler efficacement MILPs.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e

Daniel Kuhn

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (32)

Stokes' theorem

Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on . Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical theorem of Stokes can be stated in one sentence: The line integral of a vector field over a loop is equal to the flux of its curl through the enclosed surface.

Théorème de Green

En mathématiques, le théorème de Green, ou théorème de Green-Riemann, donne la relation entre une intégrale curviligne le long d'une courbe simple fermée orientée C par morceaux et l'intégrale double sur la région du plan délimitée par cette courbe. Ce théorème, nommé d'après George Green et Bernhard Riemann, est un cas particulier du théorème de Stokes. thumb|upright=0.9|Domaine délimité par une courbe régulière par morceaux. Vu comme cas particulier du théorème de Stokes, le théorème s'écrit sous la forme suivante, en notant ∂D la courbe C et ω la forme différentielle.

Graphe étoile

thumb|upright=3|Les graphes en étoile S3, S4, S5 et S6. En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k. On peut aussi le voir comme un arbre avec un nœud et k feuilles, du moins lorsque k > 1. Enfin, on peut le définir comme un graphe connexe dont tous les sommets sauf un sont de degré 1. Certains auteurs définissent toutefois Sk comme l'arbre à k sommets de diamètre maximal 2. Attention, avec cette définition, une étoile n'a que k − 1 feuilles.

Arbre (théorie des graphes)

En théorie des graphes, un arbre est un graphe acyclique et connexe. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique, qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley. Un ensemble d'arbres est appelé une forêt.

Problème d'affectation

En informatique, plus précisément en recherche opérationnelle et d'optimisation combinatoire, le problème d'affectation consiste à attribuer au mieux des tâches à des agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit être réalisée par un unique agent. Les affectations (c'est-à-dire les couples agent-tâche) ont toutes un coût défini. Le but est de minimiser le coût total des affectations afin de réaliser toutes les tâches.

Afficher plus

Séances de cours associées (64)

Groupes fondamentaux

Explore les groupes fondamentaux, les classes d'homotopie et les revêtements dans les variétés connectées.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

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.

Les flux réseau rencontrent Simplex

Explore les flux réseau, la méthode simplex, la programmation linéaire, les solutions arborescentes et les solutions doubles dans les problèmes d'optimisation.

Afficher plus

Concepts associés (32)

Stokes' theorem

Théorème de Green

Graphe étoile

Arbre (théorie des graphes)

Problème d'affectation

Afficher plus