Séance de cours

Le problème du transbordement, Le problème de l'affectation

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 explique le problème d'affectation, où les ressources doivent être affectées aux tâches, et comment il peut être modélisé comme un problème de transbordement à l'aide d'un réseau artificiel. À travers un exemple de vente de chefs-d’œuvre aux enfants, l’instructeur montre comment représenter le problème en tant que réseau, définir des nœuds et des arcs et calculer les coûts pour maximiser les revenus. La séance de cours explore ensuite le problème d'optimisation, les contraintes et les contraintes de capacité associées au problème de transbordement, en soulignant la nature intégrale de la solution optimale.

Dans MOOC

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

Introduction au concept mathématique des réseaux et à deux importants problèmes d'optimisation sur les réseaux : le problème du transbordement et le problème du chemin le plus court. Brève introduction à la puissance de modélisation de l'optimisation discrète, avec référence à des problèmes classiques. Introduction à l'algorithme branch and bound et au concept de coupes.

Source officielle

Concepts associés (17)

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.

Weapon target assignment problem

The weapon target assignment problem (WTA) is a class of combinatorial optimization problems present in the fields of optimization and operations research. It consists of finding an optimal assignment of a set of weapons of various types to a set of targets in order to maximize the total expected damage done to the opponent. The basic problem is as follows: There are a number of weapons and a number of targets. The weapons are of type . There are available weapons of type . Similarly, there are targets, each with a value of .

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.

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Quadratic assignment problem

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koopmans and Beckmann. The problem models the following real-life problem: There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g.

Afficher plus

Séances de cours associées (44)

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.

Stratégies d'optimisation de l'énergie

Couvre les options de brainstorming pour les changements de fonctionnement intelligents, la récupération de chaleur, et les performances du panneau PV.

Optimisation avec contraintes : conditions KKT

Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.

Formulation, Transformations de problèmes MOOC: Optimisation : principes et algorithmes - Optimisation non linéaire sans contrainte MOOC: Optimisation : principes et algorithmes - Optimisation linéaire

Explore la transformation des problèmes d'optimisation pour répondre aux exigences de l'algorithme et les rendre équivalents.

Programmation semi-définie

Couvre la programmation et l'optimisation semi-définies sur des cônes semi-définis positifs.

Afficher plus

Concepts associés (17)

Problème d'affectation

Weapon target assignment problem

Optimisation (mathématiques)

Optimisation combinatoire

Quadratic assignment problem

Afficher plus