[科普中國]-效率矩陣

效率矩陣(efficiency matrix)亦稱價值矩陣，指派問題中的重要參數(shù)，是由指派問題的數(shù)學(xué)模型中元素cij(i=1,2,…,m;j=1,2,…,n)構(gòu)成的矩陣。

基本介紹將指派問題數(shù)學(xué)模型中的效率系數(shù)排成一個n×n型矩陣，稱為效率矩陣(或價值系數(shù)矩陣)，即1

相關(guān)定理定理1 設(shè)指派問題的效率矩陣為。若將該矩陣的某一行(或某一列)的各個元素都減去同一常數(shù)t(t可正可負)，得到新的效率矩陣，則以C'為效率矩陣的新指派問題與原指派問題的最優(yōu)解相同，但其最優(yōu)值比原最優(yōu)值減少t。

證明 設(shè)原指派問題的數(shù)學(xué)模型為

使得

式(1)表示完成全部n項工作所消耗的總資源數(shù)最少；式(2)表示第i個人只能完成且必須完成一項工作；式(3)表示第j項工作只派一個人去且必須派一個人去完成；式(4)要求決策變量只取0或1兩個整數(shù)值。

現(xiàn)在矩陣C的第k行各元素都減去同一常數(shù)t，記新指派問題的目標(biāo)函數(shù)為Z'，則有

上式最后兩步，利用了式(2)，因此有

又新的指派問題與原指派問題的約束方程相同，因此其最優(yōu)解必相同，而最優(yōu)值差一常數(shù)t。

推論1 若將指派問題的效率矩陣每一行和每一列分別減去各行和各列的最小元素，則得到的新指派問題與原指派問題有相同的最優(yōu)解。

證明 結(jié)論是顯然的，只要反復(fù)運用定理1便可得證。

當(dāng)將效率矩陣的每一行都減去各行的最小元素，將所得的矩陣的每一列再減去當(dāng)前列中最小元素，則最后得到的新效率矩陣C'中必然會出現(xiàn)一些零元素。設(shè)，從第i行來看，它表示第i個人去干第j項工作效率(相對)最好。而從第j列來看，它表示第j項工作以第i個人來干效率(相對)最高。

定義 在效率矩陣C中，處在不同行不同列的一組零元素，稱為獨立零元素組，此時其中每個零元素稱為獨立零元素1。

定理2 效率矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最小直線數(shù)。

本詞條內(nèi)容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所