指派問(wèn)題ppt課件(已修改)
2025-05-12 18:05 本頁(yè)面
【正文】 信息處理中的組合優(yōu)化 第四章 指派問(wèn)題 指派 問(wèn)題 （ Assignment Problem , AP）是一種特殊的線性規(guī)劃問(wèn)題，也屬于 01 整數(shù)規(guī)劃問(wèn)題 . 在圖論中稱為最佳匹配問(wèn)題 （ Optimal Matching） . 問(wèn)題描述： 有 n 項(xiàng)任務(wù)需要去完成，恰好有 n 個(gè)人可以去完成這 n 項(xiàng)任務(wù)，而每個(gè)人完成各項(xiàng)任務(wù)的效率是不同的，如果要求每人完成其中一項(xiàng)，且每項(xiàng)任務(wù)只交給其中一人去完成，應(yīng)如何分配，使總的效率最高 .第四章 指派問(wèn)題167。1 最大基數(shù)匹配問(wèn)題167。2 指派問(wèn)題167。3 指派問(wèn)題的應(yīng)用167。4 瓶頸分配問(wèn)題第四章 指派問(wèn)題167。1 最大基數(shù)匹配問(wèn)題人員工作分配問(wèn)題： 某公司有工作人員 x1, x2, …, xn,他們?nèi)プ? n 項(xiàng)工作 y1, y2,…, yn ，每人會(huì)做其中的一項(xiàng)或幾項(xiàng)，要求每人至多做一項(xiàng)，每項(xiàng)工作至多由一人來(lái)做，問(wèn)能否每人都分配到一項(xiàng) 會(huì)做 的工作？x3x1x2 y2y1y3如果不那么最多幾人有會(huì)做的工作可做？且如何安排？可用圖和矩陣給出它的數(shù)學(xué)模型及求解方法 .167。1 最大基數(shù)匹配問(wèn)題Definition 設(shè)圖 G = ( V， E )Graph Vertex Edge 如果 ， 且對(duì) ， 與 無(wú) 公共頂點(diǎn)，則稱邊子集 M 是 G 的一個(gè) 匹配 ； M 中的每條邊的兩個(gè)頂點(diǎn)稱為關(guān)于 M 是 飽和 的， 否則稱為 非飽和 的； G 中 每個(gè)頂點(diǎn)都 關(guān)于 M 是 飽和 的，則稱 M 是 G 的 一個(gè) 完備 匹配 ； 如果 M 是 一匹配，而不存在其他匹配 M1，使得 如果 M 是 一匹配，而對(duì) 不是 G的匹配，則稱 M 是 G 的一個(gè) 極大匹配 . Note: 最大匹配與極大匹配的邊數(shù)是不同的x3x1x2 y2y1y3，則稱 M 是 G 的 最大（基數(shù)）匹配 ；第四章 指派問(wèn)題 如果 G 的頂點(diǎn) V 可分 成兩個(gè)滿足如下條件的 子集 X ， Y ：② 對(duì) ，則與 ej 關(guān)聯(lián)的兩個(gè)頂點(diǎn)分屬 X Y，稱 G = ( X, Y, E )為 二部圖 或 偶圖 .x3x1x2 y2y1y3x4x5y4y5①人員工作分配問(wèn)題就是在二部圖中尋找最大匹配 .167。1 最大基數(shù)匹配問(wèn)題x3x1x2 y2y1y3x4x5y4y5 該問(wèn)題也可用矩陣表示如果 xi 會(huì)做 yj否則11111111110 0 0000000000000 在矩陣中尋找什么？ 尋找最多的不同行不同列的 1 元素 .(二部圖 G 的 鄰接矩陣 ) 稱為獨(dú)立元（素）第四章 指派問(wèn)題如何尋找 ？ 禮讓原則 從每行、每列中， 1 最少的行或列先取，一樣多時(shí)隨意 . 遺憾的是這是錯(cuò)的 167。1 最大基數(shù)匹配問(wèn)題 1965年匈牙利著名數(shù)學(xué)家 Edmonds 為之設(shè)計(jì)了命名為 “匈牙利算法 ”的有效算法，計(jì)算復(fù)雜性為 O( n ).就二部圖的鄰接矩陣，先給出幾個(gè)概念： 在第 i 行第 j 列上的 ① （ 1 被加圈）表示 xi ( 或 yj ) 已被分配，或該行（或列）已被分配 ； 此時(shí)，由于所在行和列的 1 元素不能再取，用 1 表示。不同行不同列的 ① ，稱為 A 的一個(gè)分配，用 M 表示。第四章 指派問(wèn)題設(shè) M 為已知分配， xi 未被分配，而該行沒(méi)有 1，則 xi 不能被分配；若有 1，選擇一個(gè) 1(aij),如果第 j 列沒(méi)有加圈 1，則對(duì)該1 加圈，得到一新的分配 M′,有 ， 如果有加圈 1（ ai1j），則對(duì) aij,ai1j打 √,√√√且劃去第 j 列， 再看第
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1