Assignment problem (original) (raw)
مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة.
Property | Value |
---|---|
dbo:abstract | مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة. (ar) Das (lineare) Zuordnungsproblem ist ein diskretes Optimierungsproblem aus der Graphentheorie. Es ist ein spezielles klassisches Transportproblem und findet Anwendung in der Operations Research. Es kann mittels linearer Programmierung oder mithilfe der Ungarischen Methode gelöst werden. (de) The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized. Alternatively, describing the problem using graph theory: The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment. If the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called linear assignment. Commonly, when speaking of the assignment problem without any additional qualification, then the linear balanced assignment problem is meant. (en) El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad. Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en un grafo bipartito ponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor 1. (es) 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. Plus formellement, l'objectif est de déterminer un couplage d'une taille égale au nombre de tâches, de poids minimum dans un graphe biparti valué. Si il y a autant d'agents que de tâches, il s'agit de déterminer un couplage parfait de poids minimum dans un graphe biparti valué. Le problème d'affectation peut être résolu en temps polynomial par l'algorithme hongrois, il appartient par conséquent à la classe de complexité P. (fr) I problemi di assegnazione (o problemi di assegnamento) sono quei problemi di ricerca operativa in cui bisogna assegnare diverse attività in maniera ottimale. Il problema di assegnazione è considerato un problema facile, anche se è un problema combinatorio e generalmente tali problemi sono NP-hard, cioèdifficili da risolvere. Tuttavia questo è uno dei particolari problemi che godono della proprietà di integralità e difatti altro non è che un particolare problema del flusso di costo minimo. Questo è un problema di fondamentale importanza in poiché spesso si ritrova nella struttura di problemi più complessi: ovvero spesso i problemi applicativi sono un problema di assegnamento con dei vincoli aggiuntivi. In questo modo - tramite le cosiddettetecniche di rilassamento - si possono utilizzare gli algoritmi studiati per questo problema per risolvere il problema originario. (it) Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе. В наиболее общей форме задача формулируется следующим образом: Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами. Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях. (ru) 任务分配问题是在加权二分图中寻找最大(或最小)加权匹配的问题。 (zh) Задача про призначення є однією з базових задач комбінаторної оптимізації в галузі оптимізації або дослідження операцій в математиці. Вона полягає в знаходженні парування мінімальної (або максимальної) ваги між елементами двох скінчених множин. Вона може бути подана як знаходження парування у зваженому дводольному графі. З іншого боку Задача про призначення належить до задач лінійного програмування. Вона є спеціальним випадком транспортної задачі, яка своєю чергою може бути представлена як . (uk) |
dbo:wikiPageExternalLink | https://archive.org/details/combinatorialmat0000brua |
dbo:wikiPageID | 140592 (xsd:integer) |
dbo:wikiPageLength | 15938 (xsd:nonNegativeInteger) |
dbo:wikiPageRevisionID | 1120341860 (xsd:integer) |
dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Approximation_algorithm dbc:Combinatorial_optimization dbc:Matching_(graph_theory) dbr:Matching_(graph_theory) dbr:Matrix_(mathematics) dbr:Generalized_assignment_problem dbr:Multidimensional_assignment_problem_(MAP) dbr:Combinatorial_optimization dbr:House_allocation_problem dbr:Maximum_weight_matching dbr:Weighted_graph dbr:Linear_bottleneck_assignment_problem dbr:Adjacency_matrix dbc:Polynomial-time_problems dbr:Isolation_lemma dbr:Quadratic_assignment_problem dbr:Auction_algorithm dbr:Hungarian_algorithm dbr:Stable_roommates_problem dbc:Linear_programming dbr:Bijection dbr:Bipartite_graph dbr:Weight_function dbr:Fibonacci_heap dbr:Polynomial_time dbr:National_Resident_Matching_Program dbr:Real_number dbr:Loss_function dbr:Stable_marriage_problem dbr:Simplex_algorithm dbr:Unimodular_matrix dbr:Weapon_target_assignment_problem dbr:Factorial dbr:Secretary_problem dbr:Linear_program dbr:Strongly_polynomial dbr:Minimum_cost_flow_problem dbr:Rank-maximal_matching dbr:Transportation_problem dbr:Monge-Kantorovich_transportation_problem |
dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Cite_book dbt:Frac dbt:Math dbt:Reflist dbt:Rp dbt:Short_description dbt:Tmath |
dct:subject | dbc:Combinatorial_optimization dbc:Matching_(graph_theory) dbc:Polynomial-time_problems dbc:Linear_programming |
gold:hypernym | dbr:Problems |
rdf:type | owl:Thing yago:WikicatComputationalProblemsInGraphTheory yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Disease yago:State100024720 yago:WikicatPolynomial-timeProblems |
rdfs:comment | مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة. (ar) Das (lineare) Zuordnungsproblem ist ein diskretes Optimierungsproblem aus der Graphentheorie. Es ist ein spezielles klassisches Transportproblem und findet Anwendung in der Operations Research. Es kann mittels linearer Programmierung oder mithilfe der Ungarischen Methode gelöst werden. (de) 任务分配问题是在加权二分图中寻找最大(或最小)加权匹配的问题。 (zh) Задача про призначення є однією з базових задач комбінаторної оптимізації в галузі оптимізації або дослідження операцій в математиці. Вона полягає в знаходженні парування мінімальної (або максимальної) ваги між елементами двох скінчених множин. Вона може бути подана як знаходження парування у зваженому дводольному графі. З іншого боку Задача про призначення належить до задач лінійного програмування. Вона є спеціальним випадком транспортної задачі, яка своєю чергою може бути представлена як . (uk) The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized. Alternatively, describing the problem using graph theory: (en) El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad. (es) 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. (fr) I problemi di assegnazione (o problemi di assegnamento) sono quei problemi di ricerca operativa in cui bisogna assegnare diverse attività in maniera ottimale. Il problema di assegnazione è considerato un problema facile, anche se è un problema combinatorio e generalmente tali problemi sono NP-hard, cioèdifficili da risolvere. Tuttavia questo è uno dei particolari problemi che godono della proprietà di integralità e difatti altro non è che un particolare problema del flusso di costo minimo. (it) Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе. В наиболее общей форме задача формулируется следующим образом: Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами. (ru) |
rdfs:label | مسألة الإسناد (ar) Zuordnungsproblem (de) Assignment problem (en) Problema de asignación (es) Problème d'affectation (fr) Problema di assegnazione (it) Задача о назначениях (ru) Задача про призначення (uk) 任务分配问题 (zh) |
owl:sameAs | freebase:Assignment problem yago-res:Assignment problem wikidata:Assignment problem dbpedia-ar:Assignment problem dbpedia-de:Assignment problem dbpedia-es:Assignment problem dbpedia-fr:Assignment problem dbpedia-it:Assignment problem dbpedia-ru:Assignment problem dbpedia-uk:Assignment problem dbpedia-zh:Assignment problem https://global.dbpedia.org/id/4okjf |
prov:wasDerivedFrom | wikipedia-en:Assignment_problem?oldid=1120341860&ns=0 |
foaf:isPrimaryTopicOf | wikipedia-en:Assignment_problem |
is dbo:wikiPageDisambiguates of | dbr:Assignment |
is dbo:wikiPageRedirects of | dbr:Linear_assignment_problem dbr:Credit_assignment_problem dbr:Unbalanced_assignment_problem |
is dbo:wikiPageWikiLink of | dbr:Behavioral_operations_management dbr:Round-robin_item_allocation dbr:List_of_academic_fields dbr:List_of_algorithms dbr:Nurse_scheduling_problem dbr:Anna_Bogomolnaia dbr:Index_of_combinatorics_articles dbr:List_of_knapsack_problems dbr:Matching_(graph_theory) dbr:Maximum_cardinality_matching dbr:Mechanism_design dbr:Generalized_assignment_problem dbr:Network_theory dbr:Transshipment_problem dbr:Combinatorial_optimization dbr:Hopcroft–Karp_algorithm dbr:House_allocation_problem dbr:Maximum_weight_matching dbr:Linear_programming dbr:Network_simplex_algorithm dbr:Minimum-cost_flow_problem dbr:Flow_network dbr:Dimitri_Bertsekas dbr:Quadratic_assignment_problem dbr:Harold_W._Kuhn dbr:Auction_algorithm dbr:Hungarian_algorithm dbr:Jenő_Egerváry dbr:Transportation_theory_(mathematics) dbr:Articulated_body_pose_estimation dbr:Autonomous_mobility_on_demand dbr:Network_science dbr:Assignment dbr:OR-Tools dbr:Operations_research dbr:Marriage_problem dbr:Stable_marriage_problem dbr:Weapon_target_assignment_problem dbr:Externality dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Multidimensional_assignment_problem dbr:Secretary_problem dbr:Rental_harmony dbr:Outline_of_academic_disciplines dbr:Linear_assignment_problem dbr:Credit_assignment_problem dbr:Unbalanced_assignment_problem |
is foaf:primaryTopic of | wikipedia-en:Assignment_problem |