運籌學指派問題試驗報告

運籌學實踐報告

指派問題第一部分問題背景泰澤公司（Tazer）是一家制藥公司。它進入醫(yī)藥市場已經(jīng)有12年的歷史了，并且推出了6種新藥。這6種新藥中5種是市場上已經(jīng)存在藥物的同類產(chǎn)品，所以銷售的情況并不是很樂觀。然而，主治高血壓的第6種藥物卻獲得了巨大的成功。由于泰澤公司擁有生產(chǎn)治療高血壓藥物的專利權(quán)，所以公司并沒有遇到什么競爭對手。僅僅從第6種藥物中所獲得的利潤就可以使泰澤公司正常運營下去。在過去的12年中，泰澤公司不斷地進行適量的研究和發(fā)展工作，但是卻并沒有發(fā)現(xiàn)有哪一種藥物能夠獲得像高血壓藥物一樣的成功。一個原因是公司沒有大量投資進行創(chuàng)新研究開發(fā)的動力。公司依賴高血壓藥物，覺得沒有必要花費大量的資源尋找新藥物的突破。但是現(xiàn)在泰澤公司不得不面對競爭的壓力了。高血壓藥物的專利保護期還有5年1。泰澤公司知道只要專利期限一到，大量藥品制造公司就會像禿鷹一樣涌進市場。歷史數(shù)據(jù)表明普通藥物會降低品牌藥物75%的銷售量。今年泰澤公司投入大量的資金進行研究和開發(fā)工作以求能夠取得突破，給公司帶來像高血壓藥物一樣的巨大成功。泰澤公司相信如果現(xiàn)在就開始進行大量的研究和開發(fā)工作，在高血壓藥物專利到期之后能夠發(fā)明一種成功藥物的概率是很高的。作為泰澤公司研究和開發(fā)的負責人，你將負責選擇項目并為每一個項目指派項目負責人。在研究了市場的需要，分析了當前藥物的不足并且拜會了大量在有良好前景的醫(yī)藥領(lǐng)域進行研究的科學家之后，你決定你的部門進行五個項目，如下所示：Up項目：開發(fā)一種更加有效的抗憂郁劑，這種新藥并不會帶來使用者情緒的急劇變化。5126兒項目：開發(fā)一種治療躁狂抑郁病的新藥。Choice項目：為女性開發(fā)一種副作用更小的節(jié)育方法。Hope項目：開發(fā)一種預防HIV的疫苗。Release項目：開發(fā)一種更有效的降壓藥。對于這5個項目之中的任何一個來說，由于在進行研究之前你并不知道使用的配方以及哪種配方是有效的，所以你只能明確研究所要解決的疾病。你還有5位資深的科學家來領(lǐng)導進行這5個項目。有一點你十分清楚，那就是科學家都是一些喜怒無常的人，而且他們只有在受到項目所帶來的挑戰(zhàn)和激勵的時候才會努力工作。為了保證這些科學家都能夠到他們感興趣的項目中去，你為這個項目建立了一個投標系統(tǒng)。這5位科學家每個人都有1000點的投標點。1一般來說，專利權(quán)保護發(fā)明的期限為17年。在1995年，GATT立法拓展專利權(quán)的保護期限到20年。在本案例之中，泰澤公司的高血壓藥物的注冊時間是在1995年之前，所以專利權(quán)只能夠保護這種藥物17年。他們向每一個項目投標，并且把較多的投標點投向自己最感興趣的項目之中。下表顯示了這5位科學家進行投標的情況。項目克瓦爾博士朱諾博士特塞博士米凱博士羅林斯博士Up項目1000100267100Stable項目40020010015333Choice項目2008001009933Hope項目200010045134Release項目100060030800第二部分指派問題的標準形式與建模指派問題(Assignmentproblem)的定義：在滿足特定指派要求條件下，使指派方案總體效果最佳。在生活中經(jīng)常遇到這樣的問題，某單位需完成n項任務(wù)，恰好有n個人可承擔這些任務(wù)。由于每人的專長不同，各人完成任務(wù)不同，效率也不同。于是產(chǎn)生應(yīng)指派哪個人去完成哪項任務(wù)，使完成門項任務(wù)的總效率最高。這類問題稱為指派問題。指派問題的標準形式是：有n個人和n件事，已知第i個人做第j件事的費用為cj(i,j=1,2，…，用，要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費用最小。設(shè)n2個0-1變量X={1 若指派第i個人做第j件事ij0若不指派第i個人做第j件事 (i,J=1,2，...，n)數(shù)學模型為i=12>=1>=1 ijx=0or1 i,j=1,2,…，nij第三部分不同類型的指派問題我們將指派問題分為幾個不同的類型，解決不同指派問題的基本理念是將其轉(zhuǎn)化為標準型，之后再求解。（一）最大化指派問題生活中有許多問題是需要我們求目標函數(shù)的最大值的，例如本題中我們需要求解使科學家的滿意度最大化。這時，我們就需要了解與掌握最大化指派問題的解法。最大化指派問題的解法同標準型指派問題類似，只是將目標函數(shù)取最小值改為目標函數(shù)取最大值。其余的建模與求解過程均與標準型相同。（以下幾種類型的問題，我們默認均以最大化問題為前提。）（二）人數(shù)與項目數(shù)不等的指派問題這里默認一人只能領(lǐng)導一個項目。將問題轉(zhuǎn)化為標準指派問題是求解問題的主體思路。人數(shù)與項目數(shù)不等的指派問題分為兩種情況，一種是人數(shù)小于項目數(shù)的指派問題，另一種是人數(shù)大于項目數(shù)的指派問題。我們將原問題默認為最大化指派問題，即求目標為目標函數(shù)的最大值。首先，關(guān)于人數(shù)小于項目數(shù)的指派問題的解法，我們需要添加虛擬的人，虛擬人的個數(shù)與人數(shù)和項目數(shù)之間的差額確定，并將虛擬人對應(yīng)的系數(shù)矩陣中的系數(shù)設(shè)置為0。添加虛擬人后，就將原問題轉(zhuǎn)化為人數(shù)與項目數(shù)相等的標準型指派問題，接著按標準型指派問題的建模和求解步驟求解。得到結(jié)果后，虛擬人對應(yīng)的項目就是我們應(yīng)該放棄的項目。另外，關(guān)于人數(shù)大于項目數(shù)的指派問題的解法，我們需要添加虛擬的項目，虛擬項目的個數(shù)與人數(shù)和項目數(shù)之間的差額確定，并將虛擬項目對應(yīng)的系數(shù)矩陣中的系數(shù)與其對應(yīng)的項目的系數(shù)相同。（例如，A項目可以由兩個人領(lǐng)導，那么我們將A項目變?yōu)锳1項目，并添加A2虛擬項目，使得A1與A2對應(yīng)的系數(shù)相等。）添加虛擬項目后，就將原問題轉(zhuǎn)化為人數(shù)與項目數(shù)相等的標準型指派問題，接著按標準型指派問題的建模和求解步驟求解。得到結(jié)果后，分別領(lǐng)導相同系數(shù)項目的人即為共同領(lǐng)導同一項目的人。（即求得分別領(lǐng)導A1與A2項目的人為共同領(lǐng)導A項目的人。）（三）一人可以領(lǐng)導多個項目的指派問題一人領(lǐng)導多個項目的指派問題其實與人數(shù)大于項目數(shù)的指派問題的解法類似，只是將虛擬項目改為虛擬人。關(guān)于一人領(lǐng)導多個項目的指派問題的解法，我們需要添加虛擬的人，虛擬人的個數(shù)與人數(shù)和項目數(shù)之間的差額確定，并將虛擬人對應(yīng)的系數(shù)矩陣中的系數(shù)與其對應(yīng)的人的系數(shù)相同。（例如，甲可以同時領(lǐng)導兩個項目，那么我們將甲變?yōu)榧?，并添加甲2虛擬人，使得甲1與甲2對應(yīng)的系數(shù)相等。）添加虛擬人后，就將原問題轉(zhuǎn)化為人數(shù)與項目數(shù)相等的標準型指派問題，接著按標準型指派問題的建模和求解步驟求解。得到結(jié)果后，相同系數(shù)的人領(lǐng)導的項目則是這個人同時領(lǐng)導的項目。（即求得甲1和甲2領(lǐng)導的項目即為甲所領(lǐng)導的兩個項目。）（四）某人不能領(lǐng)導某項目的指派問題某人不能領(lǐng)導某項目，我們可以直接將對應(yīng)于人和項目的交叉項的系數(shù)設(shè)置為一個負的無窮大的數(shù)，因為這里我們是要求目標函數(shù)的最大值。在后面的實際問題求解中，我們將系數(shù)設(shè)置為-10000。其余建模與求解過程與標準型指派問題相同。第四部分實際問題分析（一）問題一（最大化指派問題） ：根據(jù)所給出的投標情況，你需要為每一個項目指派一位資深的科學家并且使得這位科學家的滿意度最高。那么應(yīng)當項目的束1項目的束1=11=11=11=11=1目標函數(shù)2551怎樣進行指派？1.目標：選擇一種方案使得5位博士的總滿意度最大化。2.Excel求解過程：如下圖系破兆陣克瓦爾博士朱諾博士特塞博士永凱博士羅林斯博士Up項目1000100267100Stab3項目40020010015333Choig號項目2008001009933Hop。項目200010045134Re1eds白項目100060030800百變量克瓦依博土朱諾博士特塞博士素凱博士羅林斯博心Up項目00100Stab1e項目10000Choi”項目01000Hope項目00010Released目00001投標綺束11111————11111.解釋：投標約束表示一個博士只能領(lǐng)導一個約束。項目約束表示一個項目只能由一個博士領(lǐng)導。

.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，5位博士的總投標點數(shù)即總滿意度為2551。（二）問題二（人數(shù)小于項目數(shù)的指派問題）:羅林斯博士接到了哈（二）問題二（人數(shù)小于項目數(shù)的指派問題）:羅林斯博士接到了哈佛醫(yī)學院的邀請去完成一個教學任務(wù)，而你卻非常想把她留下來。但是哈佛的聲望會使她離開公司。如果這種情況真的發(fā)生的話，公司就只有放棄那個最缺乏熱情的項目。公司應(yīng)當放棄哪一個項目？.解題思路：將問題轉(zhuǎn)化為標準指派問題是求解問題的主體思路。因為本題目中存在5個項目和4位博士，所以添加一個虛擬博士，使得博士數(shù)目與項目數(shù)目相等。將虛擬博士的滿意度系數(shù)均設(shè)置為0，求解出結(jié)果后虛擬博士所領(lǐng)導的項目則是泰澤公司需要拋棄的項目。.目標:博士總滿意度最高。.Excel求解過程：如下圖系教殍陣克瓦爾博士朱諾博上特塞博士來凱博士虛版博士Up項目10001002670Stabled同4002001001530Choice項目200800100990Hgpe項目20001004510Rei后君鄉(xiāng)右項目1000600300夔量克瓦爾博士朱諾將主特塞博士卡凱博士虛擬博士u□項目00001Stable^目10000Choigc項目01000Hope項目00010Ke1后ase項目00100投標約束11111—————11111

項目約束目標函數(shù)項目約束目標函數(shù)2251.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，4位博士的總投標點數(shù)即總滿意度為2251。虛擬博士所領(lǐng)導的Up項目則是需要拋棄的項目。（三）問題三（一人可以領(lǐng)導多個項目的指派問題） ：當然你并不愿意放棄任何一個項目，因為如果放棄一個項目而只剩下4個項目的話，會大大降低找到突破性新藥的概率。你決定讓朱諾博士或者米凱博士同時領(lǐng)導兩個項目。大只有4個科學家的情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大？.目標：博士的總滿意度最大化.Excel求解過程：如下圖項目克瓦爾博士朱諾博士特塞博士朱凱博士Up項目1000100267StabIe項目400200100153Choice項目20080010099Hope項目2000100451Re1ea導e項百100060030變量克瓦爾博士朱諾博士特塞博士來凱博士U9項目0001Stab1e項目1000Choice項目0100Hope項目0001Re1e日se項0010束仍然是對應(yīng)一列數(shù)字加和為1。另外，約束要求朱諾博士與米凱博士的自變量總和為3且兩人的對應(yīng)列數(shù)字和均小于等于2。4.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，其中米凱博士領(lǐng)導Up項目與Hope項目兩個項目。（四）問題四（一人可以領(lǐng)導多個項目的指派問題） ：如果朱諾博士被告知她和米凱博士都有機會來同時領(lǐng)導兩個項目，她決定要改變好的投標。朱諾博士對每一個項目的投標的情況如下所示：Up項目：20Stable項目：450Choice項目：451Hope項目：39Release項目：40在只有4個科學家的情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大？.目標：博士的總滿意度最大化.Excel求解過程：如下圖

項目克瓦爾博士朱諾博士特塞博士來凱博士Up項目10020100267StabIe項目400450100153Choice項目20045110099Hope項目20039100451Re1ease項目1004060030變量克瓦爾博士朱諾博士特塞博士來凱博士Up項目0001Stab1c項目1000Choice項目0100Hope項目0001Re1e8號后項目0010投標約束10103===10103項目約束1—11二11=11二1項目約束1—11二11=11二11二1目標函數(shù)2169.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，其中米凱博士領(lǐng)導Up項目與Hope項目兩個項目，博士的總滿意度為2169。（五）問題五：你是否支持從d得出的指派？為什么？答：不支持。我們可以從已給出的數(shù)據(jù)問題得知，朱諾博士在尚未得知他本人有機會領(lǐng)導兩個項目時對Stable項目的投標點數(shù)為200，對Choice項目的投標點數(shù)為800。而在得知他有機會領(lǐng)導兩個項目后，他為了領(lǐng)導兩個項目，將Choice項目的投標點數(shù)降低到451，將Stable的點數(shù)升高到450。然而最后我們的指派結(jié)果朱諾博士只領(lǐng)導了一個項目，為孫。k6項目，并且Stable項目由科瓦爾博士領(lǐng)導，他對Stable項目投標點數(shù)為400，小于朱諾博士隨Stable的投標點數(shù)。故這種指派結(jié)果很有可能引起朱諾博士的不滿。這樣的指派結(jié)果并沒有考慮博士的個人情緒。（對于問題的改進，我們會在后續(xù)優(yōu)化中予以介紹）（六）問題六（某人不能領(lǐng)導某項目的指派問題）：現(xiàn)在我們還是來分析擁有5位科學家的情況。但是，你決定有幾個科學家不能領(lǐng)導幾個特定的項目。具體來說米凱博士在免疫系統(tǒng)的研究方面沒有什么經(jīng)驗，所以他不能領(lǐng)導Hope項目。而且他的家族有著躁狂抑郁病的病史，所以你覺得他作為一個項目的領(lǐng)導者參與到Stable項目的研究中是不太合適的。于是米凱博士也不能領(lǐng)導5七2目6項目?？送郀柌┦坑捎谠诿庖呦到y(tǒng)的研究方面沒有什么經(jīng)驗，也不能領(lǐng)導Hope項目。還有克瓦爾博士由于在心血管系統(tǒng)的研究方面沒有什么經(jīng)驗，不能領(lǐng)導區(qū)6匕256項目。羅林斯博士由于家族有低血壓的病史，所以你覺得她作為一個項目的領(lǐng)導者參加到Up項目中是不太合適的，所以羅林斯博士不能領(lǐng)導Up項目。因為米凱博士和克瓦爾博士都有兩個項目不能進行領(lǐng)導，所以他們每人的投標點就只剩下600點。羅林斯博士由于有一個項目不能進行領(lǐng)導，所以她的投標點剩下800點。下表顯示了米凱博士、克瓦爾博士和羅林斯博士投標情況：項目米凱博士克瓦爾博士羅林斯博士Up項目30086不能領(lǐng)導Stable項目不能領(lǐng)導34350Choice項目12517150Hope項目不能領(lǐng)導不能領(lǐng)導100Release項目175不能領(lǐng)導600在這種情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大?.解題思路：本題同樣利用0-1整數(shù)規(guī)劃求解，但與之前不同的是本題中存在博士不能領(lǐng)導項目的情況，因為我們的目標為總滿意度最大化，故我們在系數(shù)10

矩陣中將不能領(lǐng)導轉(zhuǎn)化為一個負無窮大，本題求解過程中我們將其設(shè)置為-10000。.目標：博士的總滿意度最大化.Excel求解過程：如下圖項目約束1項目約束1—11=11二11—11=1目標函數(shù)2143系數(shù)矩陣克瓦爾博士朱褚博士特塞博士米凱博士羅秫新博士Up項目860100300-10000StabledL343200100-1000050Chois項目17180010012550Hop。項目-100000100-10000100Re1ease項目-100000600175600自變量克瓦爾博4朱諾博上特塞博士米凱博士羅林斯博士Up項目00010StabIe項010000Choice項目01000Hop9項目00100Rc1esse項百00001投標約束11111====—11111.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，4位博士的總投標點數(shù)即總滿意度為2143。（七）問題七（項目數(shù)小于人數(shù)的指派問題）：你覺得Release項目和Hope項目太復雜了，各讓一位科學家分別進行領(lǐng)導是不太合適的。因此，這兩個項目都要指派兩位科學家進行領(lǐng)導?，F(xiàn)在你需要雇用更多的科學家來領(lǐng)導所有

的項目：阿利加博士和桑托斯博士。由于宗教的原因，這兩個新加入的科學家都不能領(lǐng)導訃0憶6項目。下表顯示了所有的項目、科學家以及他們的投標情況。項目克瓦爾博士朱諾博士特塞博士米凱博士羅^斯博士阿加利博士桑托斯博士Up項目860100300不能領(lǐng)導250111Stable項目343200100不能領(lǐng)導502501Choice項目17180010012550不能領(lǐng)導不能領(lǐng)導Hope項目不能領(lǐng)導0100不能領(lǐng)導100250333Release項目不能領(lǐng)導0600175600250555.解題思路：與問題六類似，“不能領(lǐng)導”在系數(shù)矩陣中體現(xiàn)為對應(yīng)的系數(shù)為-10000。因為本題中項目數(shù)小于博士人數(shù)，所以我們自行加入兩個虛擬項目，把本題轉(zhuǎn)化為標準指派問題。由于Release項目和Hope項目都要由2位博士來領(lǐng)導，故將Hope項目變?yōu)镠ope項目1與Hope項目2，Release項目變?yōu)镽elease項目1與Release項目2。這樣就將題目轉(zhuǎn)化成了7個項目對應(yīng)7位博士的標準型指派問題。結(jié)果中求出的領(lǐng)導Release項目1與Release項目2的博士則是領(lǐng)導Release項目的兩位博士，求出的領(lǐng)導Hope項目1和Hope項目2的兩位博士則是領(lǐng)導Hope項目的博士。.目標：博士的總滿意度最大化.Excel求解過程：如下圖系數(shù)矩陣克瓦爾博士朱諾博上特塞塔+來凱博士羅林斯博士阿加刎博士栗托斯博士Up項目860100300-10000250111S匕bW項目343200100-10000502501Choice^同17180010012550-10000-10000Hope項目1-100000100-10000100250333Hbp白項82-100000100「10000100250333Re1 S1-100000600175600250555Re1ease罰S2-100000600175600￡5055512

0肥量克兄爾博士朱諾博士轉(zhuǎn)塞博士米凱博W羅林斯博士阿加利博士桑托斯博士如項目0001000Stabled目1000000ChoiceV目0100000Hope項目10000010Hore項目20000001Ra 耳10000100RaIe自白匕騎自20010000投標的束1111111=二=三三三三1111111項目約束1—11-11=11—11—11=11二1目標函數(shù)3226|4.結(jié)論:如上圖所示，自變量矩陣中“1”代表對應(yīng)的博士領(lǐng)導對應(yīng)的項目，4位博士的總投標點數(shù)即總滿意度為3226。其中，Hope項目由阿加利博士與桑托斯博士領(lǐng)導，Release項目由特塞博士與羅林斯博士領(lǐng)導。第五部分后期優(yōu)化改進（一）解法缺陷在對問題的初步研究求解之后我們發(fā)現(xiàn)了原有解法的兩點缺陷：第一，原目標函數(shù)設(shè)置是要求所求總滿意度最大化，這種目標設(shè)置只是站在了決策者的角度考慮問題，沒有充分考慮博士的感受，有可能會影響其做項目的積極性，從而對項目推進產(chǎn)生阻礙，進而影響公司利益；第二，題目中原先只給出了一個指標，即個人滿意度，這僅僅考慮了博士個人的興趣，但并未考慮到其能力是否與興趣匹配，致使可能產(chǎn)生這樣一種情況：某個博士很傾向于領(lǐng)導某個項目，但實際上他并沒有足夠的能力來完成這個項目。針對上述兩個弊端，我們從以下三個方面進行一些改進：（1）將總滿意度最大化目標改為最小滿意度最大化。（2）在原題單一指標（興趣度指數(shù)）基礎(chǔ)上再引進另一個指標（項目適應(yīng)度指數(shù)），做到既考慮博士個人興趣，又考慮他對這個項目的適應(yīng)性。（3）變更角度，利用博弈論相關(guān)知識進行新一輪的思考。（二）優(yōu)化改進.最小滿意度最大化在博弈論中，有極大化極小策略：一種選擇所有最小收益中的最大值的策略。依據(jù)這樣的思路，類似地，我們可以得到最小滿意度最大化：一種選擇所有最小滿意度中的最大值的策略。以警匪問題為例來說明這種思想：有n名警察和n名小偷，每個警察對應(yīng)追一個小偷，由于n名警察和n名小偷個人能力及素質(zhì)不同，因此分配不同的警察去最追捕不同的小偷，每個人追到小偷所花費的時間是不同的。在原有解法中，我們希望最終的分配方案可以使得這n名警察所花費的總時間最短，但是應(yīng)用最小滿意度最大化思想，我們希望最終方案使得花費時間最長的那個警察所花費的時間是在所有方案中的最長時間中最短的。最小滿意度最大化是一種保守策略，它不追求最大利益，而是避免比較大的風險和虧損。我們選擇最小滿意度最大化策略，也是出于保守考慮，使得泰澤制藥公司在新項目研究開發(fā)時避免過大的風險?，F(xiàn)在我們將最小滿意度最大化方法應(yīng)用在本題中，即給定一種方案，使得每個博士所領(lǐng)導的項目對應(yīng)的最小滿意度是所有可選方案中的最小滿意度之中最大的。下面我們以這種方法重新依次解一遍原題的第1、2、3、4、6、7問：一）問題一（最大化指派問題）：根據(jù)所給出的投標情況，你需要為每一個項目指派一位資深的科學家并且使得這位科學家的滿意度最高。那么應(yīng)當怎樣進行指派?系數(shù)矩除克瓦爾博士朱諾博士特塞博士米凱博士寫林斯博士工礴目1000100267100StaMe頊目4002001001E333Choice項目2008001009933Hope項目200010045134Rflea&e項目100060030800

自克里克瓦爾博士朱諾博士特塞博士米凱博士羅林斯博士匚兩目00001項目10000Choice項目01000Hope項目00010Bfkas總項目00100]皈目約束]皈目約束1—11二1111二111原目標函數(shù)（總就意摩）2351新目標函數(shù)100新總道意度2351最小茜意度400800600451100 |提標約束11111—=—11111注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘；⑥對比：同一道題應(yīng)用原解法得出總滿意度為3226，新解法也為2351，由此我們可以看到兩種求解方法并不一定會得到不同的解。（二）問題二（人數(shù)小于項目數(shù)的指派問題） ：羅林斯博士接到了哈佛醫(yī)學院的邀請去完成一個教學任務(wù)，而你卻非常想把她留下來。但是哈佛的聲望會使她離開公司。如果這種情況真的發(fā)生的話，公司就只有放棄那個最缺乏熱情的項目。公司應(yīng)當放棄哪一個項目？15

嗯目豹束1=嗯目豹束1=11二1111二111原目標由救（原總耨意度）2251新目標函數(shù)400新總箭意度2251頂目克瓦爾博士朱諾逋士特塞他士米凱博士虛報傅士中頁目1QQ010。2670StaMm項目4002001001530Choice項目200800100990Hope項目20001004510Rflease項目1000600300變里克瓦爾博士朱諾博士特塞博士米凱博士虛損博士中頁目00001StaMe項目10000Choice項目01000Hope項目00010Bflease項目00100最小薪意度400800600451投標約束11111二二二=—11111注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘;16

⑥對比：同一道題應(yīng)用原解法得出總滿意度為2251,新解法也為2251,由此我們可以看到兩種求解方法并不一定會得到不同的解。（三）問題三（一人可以領(lǐng)導多個項目的指派問題） ：當然你并不愿意放棄任何一個項目，因為如果放棄一個項目而只剩下4個項目的話，會大大降低找到突破性新藥的概率。你決定讓朱諾博士或者米凱博士同時領(lǐng)導兩個項目。大只有4個科學家的情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大？項目的電L項目的電L=1L=1L=1L=11=1噫目標畫數(shù)2518輔目標畫故267輔息浦丸度2516項目克瓦爾博士朱諾博士特準博士米凱博士最小滿意司2671C00L00267Shb】。項三400200100153400Choice項目200800L0099800Hcjpe項目2000L0045L451RUg：sb：項目100060030600 |變量克乩爾博士朱諾博士特塞博士米凱博士W頁目0001Stabk項目1000Choic電項目0100Hope項目0001Kek加電項目0010投標笛班木3U朱諾11123—<=—<=—12123注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘；⑥對比：同一道題應(yīng)用原解法得出總滿意度為2518,新解法也為2518,由此我們可以看到兩種求解方法并不一定會得到不同的解。（四）問題四（一人可以領(lǐng)導多個項目的指派問題） ：如果朱諾博士被告知她和米凱博士都有機會來同時領(lǐng)導兩個項目，她決定要改變好的投標。朱諾博士對每一個項目的投標的情況如下所示：Up項目：20Stable項目：450Choice項目：451Hope項目：39Release項目：40在只有4個科學家的情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大？求解：嗔目克瓦爾博士朱諾博士特塞博士朱凱博士最小滿意度267中頁目10020100267400區(qū)恰項目40。450100153451口1毗￡項目20045110C99451Hopei頁目2003910C451600Rfkase項目1004060030變里克瓦爾插土朱諾炳土特塞博士米凱博士中頁目0001mtaHe項目1000Choice項目0100Hope項目0001sse?曰001018

原目標函軟2169新目標隨數(shù)267新總新意度2169注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘；⑥對比：同一道題應(yīng)用原解法得出總滿意度為2169，新解法也為2169，由此我們可以看到兩種求解方法并不一定會得到不同的解。（六）問題六（某人不能領(lǐng)導某項目的指派問題）（六）問題六（某人不能領(lǐng)導某項目的指派問題）：現(xiàn)在我們還是來分析擁有5位科學家的情況。但是，你決定有幾個科學家不能領(lǐng)導幾個特定的項目。具體來說米凱博士在免疫系統(tǒng)的研究方面沒有什么經(jīng)驗，所以他不能領(lǐng)導Hope項目。而且他的家族有著躁狂抑郁病的病史，所以你覺得他作為一個項目的領(lǐng)導者參與到Stable項目的研究中是不太合適的。于是米凱博士也不能領(lǐng)導Stable19

項目。克瓦爾博士由于在免疫系統(tǒng)的研究方面沒有什么經(jīng)驗，也不能領(lǐng)導Hope項目。還有克瓦爾博士由于在心血管系統(tǒng)的研究方面沒有什么經(jīng)驗，不能領(lǐng)導區(qū)6匕256項目。羅林斯博士由于家族有低血壓的病史，所以你覺得她作為一個項目的領(lǐng)導者參加到Up項目中是不太合適的，所以羅林斯博士不能領(lǐng)導Up項目。因為米凱博士和克瓦爾博士都有兩個項目不能進行領(lǐng)導，所以他們每人的投標點就只剩下600點。羅林斯博士由于有一個項目不能進行領(lǐng)導，所以她的投標點剩下800點。下表顯示了米凱博士、克瓦爾博士和羅林斯博士投標情況：項目米凱博士克瓦爾博士羅林斯博士Up項目30086不能領(lǐng)導Stable項目不能領(lǐng)導34350Choice項目12517150Hope項目不能領(lǐng)導不能領(lǐng)導100Release項目175不能領(lǐng)導600在這種情況下，讓哪一個科學家領(lǐng)導哪一個項目才能使得對項目的熱情最大?求解：自費里克瓦爾博士朱諾博土恃塞博士米凱博士羅林斯博士Up0目00010Btat熊項目10000Chaise項目01000Hope項目00100Ekk幽電項目00001系勃矩陣克瓦爾博士朱諾博士特塞博士木凱博士羅福斯博士Up?目860100300-10000Statde目343200100-1000050Choi轉(zhuǎn)項目17180010012550Ripe項目-100000100-10000100Rlease項目-100000600175600最小滿意度 孔3 S02 100 300 600原目標畫數(shù)2143新目標函數(shù)100新總薪意度2143投標約束11111二=———11111注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘；⑥對比：同一道題應(yīng)用原解法得出總滿意度為2143，新解法也為2143，由此我們可以看到兩種求解方法并不一定會得到不同的解。（七）問題七（項目數(shù)小于人數(shù)的指派問題） ：你覺得Release項目和Hope項目太復雜了，各讓一位科學家分別進行領(lǐng)導是不太合適的。因此，這兩個項目都要指派兩位科學家進行領(lǐng)導?，F(xiàn)在你需要雇用更多的科學家來領(lǐng)導所有的項目：阿利加博士和桑托斯博士。由于宗教的原因，這兩個新加入的科學家都不能領(lǐng)導孫。憶6項目。下表顯示了所有的項目、科學家以及他們的投標情況。2L

項目克瓦爾博士朱諾博士特塞博士米凱博士羅^斯博士阿加利博士桑托斯博士的項目860100300不能領(lǐng)導250111Stable項目343200100不能領(lǐng)導502501Choice項目17180010012550不能領(lǐng)導不能領(lǐng)導Hope項目不能領(lǐng)導0100不能領(lǐng)導100250333Release項目不能領(lǐng)導0600175600250555注：滿意度-10000代表不能領(lǐng)導的項目求解：首先將原題系數(shù)矩陣轉(zhuǎn)化如下:系數(shù)矩陣克瓦爾博士朱諾博士特塞博士米凱博士羅林斯博士阿加利博士暴托斯博士。項目860100300-10000250111由訊心項目343200100-10000502501Choice項目17180010012550-10000-10000Hope項目1-100000100-1D000100250333叼e項目2-100000100-10000100250333Rule脂e項目］-100000600175600250555Rekase項目：-10000060017560025055522

自費里克瓦爾博士朱諾博士特塞博士米凱博士羅林斯博士阿加利博士豪托斯博士匚誦目0001000StaMe項目1000000Chok史項目0100000Hope項目10000010Hope項目20000001Rfileas2項目10000100Rfkas總項目20010000最小滿意度343800600300600250333投標約束1111111=======1111111原目標困教3226新目標函勒250新總耨意度3226項目約束1二11二11—11—11二11二11二1注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新解法新增個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列④目標函數(shù)：目標函數(shù)為Min｛個人滿意度行｝，在求解時使得目標函數(shù)取得最大值；⑤總滿意度：總滿意度為自變量矩陣與滿意度系數(shù)矩陣對應(yīng)相乘；⑥對比：同一道題應(yīng)用原解法得出總滿意度為3226，新解法為2101，由此23我們可以看到選取保守策略會在犧牲一定程度的總滿意度，顯然這種最小滿意度最大化方法不能得到最大的總滿意度。.雙目標策略雙目標策略的應(yīng)用是為了改進原有的第二個缺陷，使得判斷標準從原先的單一指標即興趣度指數(shù)轉(zhuǎn)為雙指標：興趣度和項目適應(yīng)度。其中，興趣度作為主觀指標，項目適應(yīng)度作為客觀指標。項目適應(yīng)度的數(shù)據(jù)來源于博士個人能力和以往項目經(jīng)驗兩個方面，綜合起來產(chǎn)生博士對項目的適應(yīng)度。關(guān)于具體數(shù)據(jù)來源：主觀指標數(shù)據(jù)由題目中給出，是以每一位博士為主體，每一個人分配1000個投標點，其中每有一個博士不能領(lǐng)導的項目，該博士的投標點減少200；客觀指標數(shù)據(jù)由我們自行給出，以每一個項目為主體，給每一個項目分配700個投標點，其中每有一個博士不能領(lǐng)導這個項目，該項目的投標點減少100。如此我們可以得出如下兩張系數(shù)矩陣（以第六題為例）：髓虐系教克瓦翎由土朱諾懂土犍饞土米凱恥弗斯骷地利像土桑托斯惱土四目8601003000250111StibUO3432001000502501Che展現(xiàn)自1718001001255000H吁聞日I001000100250333Hop*第目士0010001M250333KMhse項目100$0017560?！?0555目工0060017560Q250555照適應(yīng)度翹克瓦爾毗朱諾毗特塞毗耦骷羅橢恥阿*硼土就雕土生城目15050100150010050341MBi目2501001000508020Ch加過目4023。501255500珀州取自107075075130150Hnpefl!那07075075130150艮出13』目105705216587113Release^3205785216587113注：表格中陰影部分代表博士不能領(lǐng)導的項目我們將表格中的原數(shù)據(jù)歸一化后，設(shè)r..為主觀指標，表示第i個博士對第j項工作的興趣點，u..為客觀指標，表示第j項工作由第i個博士完成的合適性，r￡[0,1]，u..￡[0,1】。建模過程如下:TI&t. =1,j=刃一=1?i=1,2,…，*」*1=0OrI?/*J=l,2「*z舞.可以看到約束條件和自變量設(shè)置都與前面一致，唯一不同的在于目標函數(shù)的設(shè)置。我們給出兩種目標函數(shù)的設(shè)置方法將這兩個指標綜合考慮：①將兩個指標直接相乘：maxf=min{%x釬=1}min{r.:/=1}②為兩個指標分配不同權(quán)重并相加：這里我們假設(shè)比例為4:6maxf=0,4xniin工廿=1}+0,6xmin{0-%=1}至此建模過程結(jié)束，下面是excel的求解過程：歸-it項目適睡系數(shù)克瓦爾恒士朱溜赳特塞他士朱凱傅土罌蕭醒士陽加利傳土桑托斯懂土Ip艇目0.214290.071430.142860.2142900.142860.07143Stable嚼目0.357140.142660.1428600.071430.1142P0.02957OunceQi目0.057140.328570.071430.178570.0785700H0"現(xiàn)3100.100000.1071400.107140.185710.21429Hope?目200.100000.1071400.107140.185710.21429K巨加口總項目100.007140.111430.074250.235710.124250.16143EeIbwS自士00.007140.111430.074290.235710.1242?0.16143歸-化髓度翻克瓦爾毗朱部士特塞毗W±羅蠲毗阿加利博士鼾斯毗加目0.03600.10.300.250.111StiMcf目0.3430.20.100.050.250.001Cbrinfl（目0.1710.B0.10.1250.0500比”項目1000.100.10.250.333HopeK目2000.100.10.250.333Rehm支溟目1000.60.1750.60.250.555Released目工000.60.1750.60.250.55525

自變更克瓦爾假士朱諾便士特塞博士柳幅土羅獻博土阿加利毗基托斯博士Up項目0001000理目1000000Chm同目0100000H叩己理目10000001H照足配0000010KeJuse4910000100Rdwas或日土0010000個人最小新意瞪G25項目最小適應(yīng)性個人最小新意瞪G25項目最小適應(yīng)性0.1114目標函數(shù)10.0279目標函救20.1946投標的束1111111—=—————1111111歸-俯人狗熊0.3430.80.60.30.60.250.333注：①自變量設(shè)置與前期設(shè)法一致；②約束條件與前期一致：兩個約束分別為投標約束和項目約束；③新增：歸一化個人滿意度行：這行的數(shù)據(jù)來源是對應(yīng)的自變量列乘以對應(yīng)的滿意度系數(shù)列之后歸一歸一化項目適應(yīng)性列：這列的數(shù)據(jù)來源是對應(yīng)的自變量行乘以對應(yīng)的適應(yīng)度系數(shù)行之后歸一④個人最小滿意度：Min｛歸一化個人滿意度行｝項目最小適應(yīng)性：Min｛歸一化項目最小適應(yīng)性列｝⑤目標函數(shù)：目標函數(shù)一：個人最小滿意度*項目最小適應(yīng)性目標函數(shù)二：0.4*項目最小適應(yīng)性+0.6*個人最小滿意度最終結(jié)果如下表所示：Up項目米凱博士Stable項目克瓦爾博士Choice項目朱諾博士Hope項目阿加利博士，桑托斯博士以勵瞿項目特塞博士,羅林斯博士.從博弈論的角度思考指派問題傳統(tǒng)指派方法體現(xiàn)的集體理性。而從博弈論的角度，體現(xiàn)的是個體理性。在實際中，被指派人往往是理性的，即每個人都想承擔自己效率最大的任，為組織創(chuàng)造最大的效用，并獲得最多的收入。在這種情況下，常常出現(xiàn)n個人中存在2人或多人爭搶同一任務(wù)的情況。對于這種情況，傳統(tǒng)指派問題均以整體效率最大化為目標化解沖突。然而，從博弈論的角度看，這種沖突化解方法不符合個體理性。事實上，指派問題是一個被指派人追求效率最大化的完全信息靜態(tài)博弈過程。因此，本文從博弈論的角度研究指派問題，即在被指派人是理性的且理性是被指派人的共同知識的情況下，求解每個參與人的最優(yōu)選擇。從另一個角度來理解，假設(shè)指派問題是一個被指派人選擇任務(wù)的博弈，所有被指派人事先達成一項協(xié)議，規(guī)定每個人的選擇。那么，在沒有外在約束力的情況下，當事人是否會自覺遵守這個協(xié)議?如果當事人會自覺遵守這個協(xié)議，那么這個協(xié)議構(gòu)成一個納什均衡：給定別人遵守協(xié)議的情況下，沒有人有積極性偏離協(xié)議中規(guī)定的自己的選擇。為了尋找這種協(xié)議，提出一個求解指派問題納什均衡的簡化方法，并證明了不存在沖突的指派問題的最優(yōu)解一定為純納什均衡解，存在沖突的指派問題的納什均衡解小于等于指派問題的最優(yōu)解，且有限指派問題有且僅有純納什均衡解。問題一（2人4項任務(wù)的指派問題）：如圖所示，一個2人4項任務(wù)的指派問題。與本題對應(yīng)的博弈問題是，在每個參與人追求最大效率的工作的假設(shè)下，構(gòu)成納什均衡的指派方案是什么？為了求解這個方案，需要將指派問題轉(zhuǎn)化為博弈問題的形式，見表2。其中，甲、乙的目標為追求各自效率最大的任務(wù)。27

人員任務(wù)人員EJG甲 2 13 15 4乙 1。 4 14 5注;效率矩陣為人員完成任務(wù)的效率表格中的數(shù)字代表著支付，其中支付的含義為每個人創(chuàng)造的效用。將上表打來得到以下表格。表格中數(shù)字仍然代表著支付，其中左側(cè)的數(shù)字為甲的支付，右側(cè)的數(shù)字為乙的支付。由于同一個任務(wù)不能由同一人領(lǐng)導，故主對角線上的數(shù)字均為表格中數(shù)字仍然代表著支付，其中左側(cè)的數(shù)字為甲的支付，右側(cè)的數(shù)字為乙的支付。由于同一個任務(wù)不能由同一人領(lǐng)導，故主對角線上的數(shù)字均為(-8,-8)。利用劃線法求納什均衡解：(其中，劃線法的基本步驟：依據(jù)策略之間的相對優(yōu)劣關(guān)系，分別尋找行和列的最優(yōu)解：固定其中一個量，在另一個量收益大的下面劃線；然后固定另一個量，對另外一個量收益大的劃線。兩者都有線的就是純策略納什均衡。)使用劃線法求解納什均衡，存在兩個純納什均衡解：(1)甲承擔任務(wù)G,乙承擔任務(wù)￡,目標值25。(2)甲承擔任務(wù)J,乙承擔任務(wù)6,目標值27。G REG RE7,一k2,4 2.L4 2,5以上的兩個解都是充分考慮了個體理性得到的解，同時我們也可以在其中選擇目標值最大的第二個方案，這樣選擇出的方案就是既考慮了集體理性，又考慮28以上的兩個解都是充分考慮了個體理性得到的解，同時我們也可以在其中選擇目標值最大的第二個方案，這樣選擇出的方案就是既考慮了集體理性，又考慮28了個體理性后得到的解，也就是我們想要得到的最優(yōu)方案。利用同樣的方法，我們可以將二人的問題拓展到更多人的情況。問題二（3人4項任務(wù)的指派問題）：人員-任務(wù)G甲1041415乙9141613丙7110注：效率矩陣為人員完成任務(wù)的效率表格中的數(shù)字代表著支付，其中支付的含義為每個人創(chuàng)造的效用。將上表打來得到以下表格。29

表43人4項任務(wù)的博弈問題乙￡JGrkrr1選E-?T-00r-001-o&￥-a,-?-co?gp.BJ~81.?付.—8-4/6,7E甲C-0,—0專-81工14,7E81-R副「RR-?.-?(—OD15J4.715/61"i"丙￡JG