任务分配问题
详述编辑
分为以下几类:
- 线性任务分配问题: 是二元组 的集合,其中 和 分别是集合 和 中的元素。 是某一函数,并满足特定约束条件,例如: 的每一个元素必须在 中出现一次,或者 的每一个元素必须在 中出现一次,或者以上二者都必须满足。线性任务分配问题的目标就是最大化或者最小化 之和。
该问题是线性的,因为代价函数 只取决于特定的二元组 ,而与其它的二元组没有任何关系。
- 二次任务分配问题:给定 家工厂和 个库房。每个库房被分配给一家工厂。很显然有 种不同的分配组合。每家工厂和它的库房间的代价函数被定义为二者间的距离和物流量的乘积。如何分配以使所有的代价总和最小?
这些问题都是组合优化的研究对象。
举例编辑
有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少?
婚配问题:有一些男人和一些女人,各位男人如果和某位女人结婚则其婚姻稳定程度具有不同的稳定数值。如何匹配可以使得所有配对的稳定值总和最大?也称婚姻匹配问题。
算法编辑
匈牙利算法是众多用于解决线性任务分配问题的算法之一,它可以在多项式时间内解决问题。分配问题是运输问题的特例,运输问题是最少成本流量问题的特例,而它们都是线性规划的特例。因此,单纯形法可以作为解决这些问题的通法。然而,针对每种特殊情形设计的专门算法可以提高解决问题的效率。如果问题的成本函数包含二次不等式,则称之为二次分配问题。
任务分配問題一般可以在多項式時間內轉化成最大流量問題(Maximum Flow Problem)。
参看编辑
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命