目錄
一、0-1型整數(shù)規(guī)劃問(wèn)題
1.1 案例
1.2 指派問(wèn)題的標(biāo)準(zhǔn)形式
2.2 非標(biāo)準(zhǔn)形式的指派問(wèn)題
二、指派問(wèn)題的匈牙利解法?
2.1 匈牙利解法的一般步驟
2.2 匈牙利解法的實(shí)例
2.3 代碼實(shí)現(xiàn)
一、0-1型整數(shù)規(guī)劃問(wèn)題
1.1 案例
投資問(wèn)題：
有600萬(wàn)元投資5個(gè)項(xiàng)目，收益如表，求利潤(rùn)最大的方案?
設(shè)置決策變量：
模型：
指派問(wèn)題：
甲乙丙丁四個(gè)人，ABCD四項(xiàng)工作，要求每人只能做一項(xiàng)工作，每項(xiàng)工作只由一人完成，問(wèn)如何指派總時(shí)間最短?
設(shè)置決策變量：
模型：
約束條件：
1.2 指派問(wèn)題的標(biāo)準(zhǔn)形式
標(biāo)準(zhǔn)的指派問(wèn)題：
有n個(gè)人和n項(xiàng)工作，已知第i個(gè)人做第j項(xiàng)工作的代價(jià)為cj(i,j=1,…..,n),要求每項(xiàng)工作只能交與其中一人完成，每個(gè)人只能完成其中一項(xiàng)工作，問(wèn)如何分配可使總代價(jià)最少?
指派問(wèn)題標(biāo)準(zhǔn)求解形式：
（1） 指派問(wèn)題的系數(shù)矩陣
（2）決策變量的設(shè)置
（3）指派問(wèn)題的解矩陣
?指派問(wèn)題的可行解中，每行每列有且僅有一個(gè)1。
（4）標(biāo)準(zhǔn)模型
2.2 非標(biāo)準(zhǔn)形式的指派問(wèn)題
（1）最大化指派問(wèn)題
例如：求利潤(rùn)，只需找出最大元素，令最大元素減去所有元素，構(gòu)建一個(gè)新的系數(shù)矩陣即可。
中最大元素為m，令 。
（2）人數(shù)和工作數(shù)不等
人少工作多：添加虛擬的 “人”，代價(jià)都為0。
人多工作少：添加虛擬的工作，代價(jià)都為0。
（3）一個(gè)人可做多件工作
該人可化為幾個(gè)相同的 “人”。
（4）某工作一定不能由某人做
該人做該工作的相應(yīng)代價(jià)取足夠大M。例如，將某人做某工作代價(jià)設(shè)為負(fù)值。
二、指派問(wèn)題的匈牙利解法?
匈牙利法是一種求解指派問(wèn)題的簡(jiǎn)便解法，它利用了矩陣中0元素的定理。若從系數(shù)矩陣的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣。以新矩陣為系數(shù)矩陣求得的最優(yōu)解和用原矩陣求得的最優(yōu)解相同。
2.1 匈牙利解法的一般步驟
第一步：變換指派問(wèn)題的系數(shù)(也稱效率)矩陣()為()，使在()的各行各列中都出現(xiàn)0元素，即
- (1) 從矩陣()的每行元素都減去該行的最小元素。
- (2) 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。
第二步：進(jìn)行試指派，以尋求最優(yōu)解。
在()中找盡可能多的獨(dú)立0元素（即行和列中只有這一個(gè)0元素），若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣()中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：
- (1) 從只有一個(gè)0元素的行開(kāi)始，給這個(gè)0元素加圈，記作，然后劃去所在列的其它0元素，記作
。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 - (2) 給只有一個(gè)0元素的列中的0元素加圈，記作，然后劃去所在行的0元素，記作。
- (3) 反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。
- (4) 若仍有沒(méi)有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈。然后劃掉同行同列的其它0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。
- (5) 若元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。
第三步：作最少的直線覆蓋所有0元素。
- (1) 對(duì)沒(méi)有的行打√號(hào);
- (2) 對(duì)已打√號(hào)的行中所有含元素的列打√號(hào)。
- (3) 再對(duì)打有√號(hào)的列中含元素的行打√號(hào)。
- (4) 重復(fù)(2)，(3)直到得不出新的打√號(hào)的行、列為止。
- (5) 對(duì)沒(méi)有打√號(hào)的行畫(huà)橫線，有打√號(hào)的列畫(huà)縱線，這就得到覆蓋所有0元素的最少直線數(shù) 。 應(yīng)等于m，轉(zhuǎn)第四步。若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)。
第四步：變換矩陣()以增加0元素。
在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素。打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步，直到找出最優(yōu)解。
2.2 匈牙利解法的實(shí)例
?甲乙丙丁四人要完成四項(xiàng)工作A、B、C、D，每人只能完成一項(xiàng)工作，要求完成總時(shí)間最短。
匈牙利解法：
第一步：減去最小值。
第二步：加圈和劃掉，比較圈數(shù)是否等于矩陣的階數(shù)。
等于，則輸出最優(yōu)值， 否則，轉(zhuǎn)到第三步重整矩陣。
2.3 代碼實(shí)現(xiàn)
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5; 8 4 2 3 5;9 10 6 9 10];%系數(shù)矩陣
c=c(:); %把矩陣c轉(zhuǎn)化為向量
a=zeros(10,25);
for i=1:5 % 實(shí)現(xiàn)循環(huán)運(yùn)算
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end % 此循環(huán)把指派問(wèn)題轉(zhuǎn)換為線性規(guī)劃問(wèn)題
b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
X=reshape(x,5,5)
opt=y
輸出：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-667656.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-667656.html
到了這里，關(guān)于數(shù)學(xué)建模（四）整數(shù)規(guī)劃—匈牙利算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
