運(yùn)籌學(xué)指派問題實(shí)驗(yàn)報(bào)告

1、運(yùn)籌學(xué)實(shí)踐報(bào)告指派問題1激勵(lì)的時(shí)候才會(huì)努力工作。為了保證這些科學(xué)家都能夠到他們感興趣的項(xiàng)目中去，你為這個(gè)項(xiàng)目建立了一個(gè)投標(biāo)系統(tǒng)。這 5 位科學(xué)家每個(gè)人都有 1000 點(diǎn)的投標(biāo)點(diǎn)。他們向每一個(gè)項(xiàng)目投標(biāo)，并且把較多的投標(biāo)點(diǎn)投向自己最感興趣的項(xiàng)目之中。下表顯示了這 5 位科學(xué)家進(jìn)行投標(biāo)的情況。項(xiàng)目 克瓦爾博士 朱諾博士 特塞博士 米凱博士 羅林斯博士Up 項(xiàng)目 100 0 100 267 100Stable 項(xiàng)目 400 200 100 15

2、3 33Choice 項(xiàng)目 200 800 100 99 33Hope 項(xiàng)目 200 0 100 451 34Release 項(xiàng)目 100 0 600 30 800第二部分 第二部分 指派問題的標(biāo)準(zhǔn)形式與建模 指派問題的標(biāo)準(zhǔn)形式與建模指派問題 指派問題（Assignment problem）的定義：在滿足特定指派要求條件下，使指派方案總體效果最佳。在生活中經(jīng)常遇到這樣的問題，某單位需完成 n 項(xiàng)任務(wù)，恰好有 n 個(gè)人可承擔(dān)這些任務(wù)。由于

3、每人的專長不同，各人完成任務(wù)不同，效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高。這類問題稱為指派問題。指派問題的標(biāo)準(zhǔn)形式是：有 n 個(gè)人和 n 件事，已知第 i 個(gè)人做第 j 件事的費(fèi)用為 (i,j=1,2,…，n)，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完 ij c成這 n 件事的總費(fèi)用最小。設(shè) n2 個(gè) 0-1 變量? 1 0 ? ij x數(shù)學(xué)模型為若指派第 i 個(gè)人做第 j 件事若不指派第 i