基于0-1整數(shù)規(guī)劃的就業(yè)選擇模型.doc

2012高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?參賽隊(duì)員 (打印并簽名) ：1. 孔甜程 2. 王成 3. 劉子恒 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2012 年 8月 15 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2012高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：全國評(píng)閱編號(hào)（由全國組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：基于0-1整數(shù)規(guī)劃的就業(yè)選擇模型摘要：當(dāng)今社會(huì)，大學(xué)生就業(yè)問題已引起了廣大的關(guān)注，針對(duì)這一現(xiàn)象，假設(shè)有25個(gè)用人單位和25位應(yīng)聘者，每個(gè)人及每個(gè)單位的基本條件和要求條件各不相同，某高等院校學(xué)生就業(yè)指導(dǎo)中心就如何根據(jù)用人單位和大學(xué)生的基本條件和要求條件進(jìn)行牽線搭橋，使用人單位和大學(xué)生簽訂就業(yè)協(xié)議。本文利用0-1型整數(shù)規(guī)劃建立了大學(xué)生就業(yè)問題的數(shù)學(xué)模型，并結(jié)合實(shí)際提出了通用可行的算法。首先將用人單位的五個(gè)要求條件和應(yīng)聘者的五個(gè)要求條件等級(jí)A、B、C、D、E分別做量化處理為5、4、3、2、1，得到用人單位和應(yīng)聘者的基本條件量化矩陣和要求條件量化矩陣，得出滿意度分量。然后確定最優(yōu)方案模型，被選人員對(duì)用人單位的滿意度最大時(shí)的人員選取即為所求，從而建立了應(yīng)聘人員最優(yōu)選取的0-1整數(shù)規(guī)劃模型關(guān)鍵詞：0-1整數(shù)規(guī)劃 條件量化 滿意度1 問題重述目前，隨著我國高等教育的持續(xù)發(fā)展，大學(xué)生畢業(yè)人數(shù)逐年增多，大學(xué)生就業(yè)難問題已經(jīng)引起了社會(huì)各方的廣泛關(guān)注。一方面，大量大學(xué)生畢業(yè)后不能很快找到工作，實(shí)現(xiàn)就業(yè)；一方面，用人單位也苦于不能招收到適合的人才。這種現(xiàn)象的持續(xù)，嚴(yán)重影響到我國高等教育和國民經(jīng)濟(jì)的持續(xù)發(fā)展。本題要求根據(jù)所給原始數(shù)據(jù)，解答以下五個(gè)問題：?jiǎn)栴}一:在盡量滿足雙方各自要求的條件下，給出一種最佳的配對(duì)方案，并使得配對(duì)成功率盡可能高；問題二：給出一種25個(gè)用人單位和25位應(yīng)聘者可同時(shí)配對(duì)的最佳方案，使得全部配對(duì)成功的可能性最大；問題三:如果25個(gè)用人單位和25位應(yīng)聘者都相互了解對(duì)方的條件和要求，讓每個(gè)用人單位和每位應(yīng)聘者都可以做出一次選擇，只有當(dāng)雙方都選中對(duì)方時(shí)才能夠配對(duì)成功，每方只有一次選擇機(jī)會(huì)。請(qǐng)問25個(gè)用人單位和25位應(yīng)聘者應(yīng)該如何選擇，使得自己配對(duì)的可能性最大？按你的選擇方案最多能配對(duì)成功多少對(duì)？問題四：由于用人單位工作要求的限制，如用人單位5和用人單位13只招聘男生，用人單位9和用人單位20只招聘女生會(huì)對(duì)你上面的結(jié)論產(chǎn)生怎樣的影響？問題五：你的方法對(duì)一般的情況，即N個(gè)應(yīng)聘人員M個(gè)用人單位時(shí)，是否可行？2 模型假設(shè)(1)每位應(yīng)聘者只能被一個(gè)用人單位錄取，一個(gè)單位只能錄取一個(gè)一個(gè)人；（2）題目所給出的條件的評(píng)價(jià)是客觀真實(shí)的；（3）用人單位和應(yīng)聘者的相關(guān)數(shù)據(jù)是透明的，即雙方都知道；（4）應(yīng)聘者的基本要求在綜合評(píng)價(jià)中的地位是等價(jià)的；（5）用人單位的五項(xiàng)基本要求對(duì)應(yīng)聘者的影響地位是同等的；（6）雙方在選擇的時(shí)候是理智的。3 符號(hào)說明用人單位的基本條件量化矩陣用人單位的要求條件量化矩陣應(yīng)聘人員的基本條件量化矩陣應(yīng)聘人員的要求條件量化矩陣1,2,3,4,5分別表示五個(gè)基本條件表示用人單位的序號(hào)表示應(yīng)聘單位的序號(hào)用人單位對(duì)應(yīng)聘人員在第方面的滿意度分量用人單位對(duì)應(yīng)聘人員的綜合滿意度應(yīng)聘人員對(duì)用人單位在第方面的滿意度分量應(yīng)聘人員對(duì)用人單位的綜合滿意度應(yīng)聘人員與用人單位之間的綜合滿意度應(yīng)聘人員與用人單位之間的相互滿意度應(yīng)聘人員應(yīng)聘成功的概率4 問題分析 該問題是現(xiàn)實(shí)生活中的實(shí)際問題，主要就是確定合理配對(duì)方案，使得在盡量滿足個(gè)人要求條件下，使配對(duì)成功率盡可能的高。對(duì)于問題（1），在充分考慮用人單位和應(yīng)聘者的要求條件的前提下，綜合雙方的滿意度，尤其將雙方的基本條件和要求條件有機(jī)結(jié)合而綜合確定一個(gè)優(yōu)化指標(biāo)，建立起優(yōu)化模型（或算法）,給出最優(yōu)的配對(duì)問題。對(duì)于問題（2），要是25個(gè)用人單位和25位應(yīng)聘者同時(shí)配對(duì)，使得全部同時(shí)成功的可能性（概率）最大。對(duì)于問題(3),因?yàn)槊總€(gè)人只有選擇一次，能不能配對(duì)成功取決于雙方是不是同時(shí)選中對(duì)方，即要看雙方彼此的滿意度如何。實(shí)際上，假如一個(gè)用人單位對(duì)一個(gè)應(yīng)聘者的滿意度最高，但是對(duì)的滿意度不一定最高，即若選擇，但不一定選擇。因此與不一定配對(duì)成功，反之亦然?，F(xiàn)在的問題是誰選誰，使得配對(duì)成功的可能性最大呢？對(duì)于問題(4),要基于前面三個(gè)方案來看，可對(duì)應(yīng)每個(gè)方案中這四個(gè)用人單位最優(yōu)配對(duì)中其配對(duì)對(duì)象的性別討論前面的最優(yōu)方案是否受到影響。若和這幾個(gè)用人單位的工作要求限制符合，則對(duì)整個(gè)方案而言，不會(huì)造成影響；若不符合，則需先考慮用人單位的工作要求。尋求他們的最優(yōu)方案，將余下的用人單位和應(yīng)聘者如上如上三問那樣建立模型，并求解。對(duì)于問題（5），只有把上述模型推廣到N個(gè)應(yīng)聘者M(jìn)個(gè)用人單位時(shí)情況。在建模時(shí)，其模型與前述問題的模型一致，只需將的取值推廣到M，的值推廣到N即可。5 模型建立與求解5.1 問題一的模型建立與求解針對(duì)問題一要使配對(duì)成功率盡可能的高，也就是給出一種方案，使得25個(gè)用人單位和25位應(yīng)聘者的配對(duì)成功指數(shù)之和最高。5.1.1 模型準(zhǔn)備5.1.1.1 條件量化處理 對(duì)于每位應(yīng)聘者對(duì)用人單位的工資待遇、工作條件、勞動(dòng)強(qiáng)度、晉升機(jī)會(huì)、深造機(jī)會(huì)的五個(gè)要求條件和每個(gè)用人單位對(duì)應(yīng)聘者的基本知識(shí)面、專業(yè)知識(shí)面、動(dòng)手能力、計(jì)算機(jī)能力、表達(dá)能力的五個(gè)要求條件等級(jí)A、B、C、D、E分別作量化處理為5、4、3、2、1.于是根據(jù)上表可以得到用人單位和應(yīng)聘者的基本條件量化矩陣和要求條件量化矩陣以及滿意度分量分別記為：則， 最后，用人單位對(duì)應(yīng)聘者的綜合滿意度為應(yīng)聘者對(duì)用人單位的綜合滿意度為則用人單位與應(yīng)聘者之間的綜合滿意度為5.1.2 模型建立在充分考慮應(yīng)聘人員的意愿和用人單位期望要求的情況下，尋求更好的錄用分配方案。應(yīng)聘人員的意愿包括對(duì)用人單位的工資待遇、勞動(dòng)強(qiáng)度等五個(gè)要求條件，即可用應(yīng)聘人員對(duì)用人單位的綜合滿意度來表示，用人單位對(duì)應(yīng)聘者的期望要求也用綜合滿意度來表示。一個(gè)好的錄用方案就是使二者的滿意度都盡可能的高，故就是要求兩者之間的綜合滿意度之和最大，可以建立如下優(yōu)化模型：目標(biāo)函數(shù)：約束條件: 5.1.3 模型求解根據(jù)上述建立的模型中，可以看出這是一個(gè)0-1整數(shù)規(guī)劃問題，在求解過程中，我們用lingo軟件尋求其最優(yōu)配對(duì)方案，并得出其最優(yōu)解為。方案如下:配對(duì)成功率最高方案用人單位P1P2P3P4P5P6P7P8P10應(yīng)聘人員Q8Q17Q20Q12Q11Q23Q18Q19Q15滿意度1.60.211.61.611.61.20.2用人單位P11P12P13P14P15P16P17P18P19應(yīng)聘人員Q21Q3Q7Q2Q13Q22Q28Q4Q10滿意度10.811.60.80.20.60.80.8用人單位P20P21P22P24P25應(yīng)聘人員Q6Q16Q5Q18Q9滿意度1.21.60.81.80.6表一 5.2 問題二的模型建立與求解針對(duì)問題二求解得出的匹配方案應(yīng)使25個(gè)用人單位與25位應(yīng)聘者全部配對(duì)成功，且配對(duì)的成功率之和最大。5.2.1 模型建立要使25個(gè)用人單位與25位應(yīng)聘者同時(shí)配對(duì)且配對(duì)成功率盡可能高，記25個(gè)用人單位與25位應(yīng)聘者成功配對(duì)概率為則目標(biāo)函數(shù)為： 由于，正比于，所以目標(biāo)函數(shù)等價(jià)于令，則，約束條件:：5.2.2 模型求解在求解過程中，應(yīng)聘人員與用人單位的綜合滿意度有為0的情況，但是在求解全部配對(duì)成功的概率最大的情況時(shí)，利用對(duì)數(shù)函數(shù)求解過程中，0不能求出來，得出負(fù)無窮大的情況，為了方便計(jì)算，我們把負(fù)無窮換為-10000。至于求解過程，與問題一的方法一致。我們利用lingo軟件計(jì)算出其最優(yōu)配對(duì)方案，并得出其最優(yōu)解z=-3.9。（注意：其最優(yōu)解并不是所求概率，只是其變化趨勢(shì)與概率等價(jià)，當(dāng)Z最大時(shí)，其概率就最大。）方案如下：全部配對(duì)成功的概率最大方案用人單位P1P2P3P4P5P6P7P8P9應(yīng)聘人員Q19Q14Q10Q23Q5Q21Q1Q9Q12滿意度10.30.810.810.810.6用人單位P10P11P12P13P14P15P16P17P18應(yīng)聘人員Q11Q24Q7Q18Q25Q3Q6Q16Q4滿意度0.81110.810.60.80.8用人單位P19P20P21P22P23P24P25應(yīng)聘人員Q22Q2Q13Q20Q8Q17Q15滿意度0.811.210.410.8表二5.3 模型改進(jìn) 首先要注意兩個(gè)事實(shí)：其一，如果基本條件比的要求條件差很多的話，則對(duì)的第項(xiàng)條件的滿意度就越小，反之亦然。也就是說，如果一方的實(shí)際條件比對(duì)方期望的條件差距越大，則對(duì)方對(duì)另一方失望就越大，即滿意度就越小。其二，如果的基本條件比的要求條件高，則對(duì)的第項(xiàng)條件的滿意度就會(huì)增加，但不會(huì)增加很多。即當(dāng)一方的實(shí)際條件高于對(duì)方期望的條件是，則對(duì)方對(duì)另一方的滿意度增加不會(huì)太大。也就是說，人們對(duì)不滿意程度的敏感遠(yuǎn)遠(yuǎn)大于對(duì)滿意程度的敏感，即用人部門對(duì)應(yīng)聘者的滿意程度降低一級(jí)可能導(dǎo)致用人單位的極大不滿，但滿意度增加一級(jí)只能引起滿意程度的少量。為此現(xiàn)在在模型一的基礎(chǔ)上把滿意度稍加修改。如果（）基本條件（）達(dá)不到（）的要求()，即（）時(shí)，給它賦值（）它是一個(gè)負(fù)值，體現(xiàn)了當(dāng)一方實(shí)際條件低于期望的條件是，則對(duì)方對(duì)他失望（相當(dāng)于要求條件）就會(huì)增加差距越大，失望度就越大，相應(yīng)的滿意度就越小。顯然改進(jìn)后成功的解決了上述所提的問題，所以更加合理。滿意度矩陣中的各個(gè)分量分別表示如下：至于模型的求解與優(yōu)化與模型一類似，我們通過原始數(shù)據(jù)得出滿意度，然后編程求的結(jié)果：方案如下:配對(duì)成功率最高方案用人單位P1P2P3P4P5P6P7P8P9應(yīng)聘人員Q14Q6Q22Q13Q5Q23Q9Q4Q12滿意度1.60.80.80.80.8111.60.6用人單位P10P11P12P13P14P15P16P17P18應(yīng)聘人員Q2Q21Q24Q18Q25Q20Q16Q7Q19滿意度0.410.810.810.40.80.4用人單位P19P20P21P22P23P24P25應(yīng)聘人員Q3Q10Q8Q15Q11Q1Q17滿意度10.61.80.80.40.80.6表三5.4 模型比較在模型一中，我們忽略了用人單位對(duì)應(yīng)聘者綜合滿意度的負(fù)值及應(yīng)聘者對(duì)用人單位綜合滿意度的負(fù)值，也就是說在模型一中，我們認(rèn)為滿意度及不滿意度（滿意度為負(fù)值時(shí)）對(duì)配對(duì)成功率的影響是一樣的，但在實(shí)際情況中，人們對(duì)不滿意度的敏感度比滿意度的敏感度高的多，于是在模型改進(jìn)中，我們對(duì)雙方的滿意度定義加以修正。根據(jù)得出的結(jié)論可知，模型改進(jìn)后的得到的配對(duì)方式更優(yōu)。5.5 問題三的模型建立與求解針對(duì)問題三，由于每個(gè)人只能選擇一次，能否配對(duì)成功主要取決于雙方能否同時(shí)選中對(duì)方，則需從雙方彼此的滿意度來看。要使配對(duì)率最高，則要使雙方的相互滿意度達(dá)到最大。5.5.1 模型建立用人單位與應(yīng)聘者的相互滿意度定義為當(dāng)與滿足可能配對(duì)的條件時(shí)：當(dāng)與不滿足可能配對(duì)的條件時(shí)：配對(duì)成功率達(dá)到最大取決于雙方的相互滿意度之和達(dá)到最大值。于是根據(jù)0-1整數(shù)規(guī)劃模型，得出目標(biāo)函數(shù)為,其約束條件與問題一相同，即為5.5.2 模型求解 根據(jù)上述模型，編程可以得到最優(yōu)解為Z=11.57，其配對(duì)方案如下:配對(duì)方案用人單位P1P2P3P4P5P6P7P8P11應(yīng)聘人員Q22Q23Q19Q12Q18Q13Q15Q24Q14滿意度0.490.20.40.80.60.40.570.70.7用人單位P12P13P14P15P17P18P19P20P21應(yīng)聘人員Q7Q8Q21Q5Q16Q2Q10Q11Q3滿意度0.490.570.70.40.40.40.40.70.7用人單位P22P24P25應(yīng)聘人員Q6Q20Q4滿意度0.70.70.6表四5.5.3 模型改進(jìn)由于只能選擇一次，要使成功率盡可能的大，則不能單純的只考慮自己對(duì)對(duì)方的滿意度。因?yàn)樵趯?shí)際中，一個(gè)用人單位對(duì)一位應(yīng)聘者的滿意度高，但不代表這位應(yīng)聘者對(duì)該用人單位的滿意度高，即選擇了，但不一定選擇，于是兩人不一定配對(duì)成功。因此，要使每一個(gè)個(gè)體配對(duì)成功的可能性最大，要保證雙方的滿意度差值不能太大。 所以我們定義了雙方滿意度差值的絕對(duì)值為差異指數(shù)，那么雙方滿意度差異指數(shù)為：=要使其配對(duì)成功率最高，則要使雙方滿意度差異指數(shù)最小，故根據(jù)上述分析，利用0-1整數(shù)規(guī)劃模型，得出目標(biāo)函數(shù)：，約束條件如下;5.5.4 模型求解根據(jù)模型，我們得出最優(yōu)解Z=2.00，其最佳配對(duì)方式如下：配對(duì)方案用人單位P1P5P6P7P8P12P14P22應(yīng)聘人員Q7Q21Q23Q8Q20Q4Q3Q24滿意度0.20.20.20.60.20.20.20.2表五5.5.5 模型比較在問題三中，模型一我們定義了相互滿意度，相互滿意度等于用人單位對(duì)應(yīng)聘者的滿意度與應(yīng)聘者對(duì)用人單位的滿意度的幾何算術(shù)平均數(shù)，在實(shí)際情況中，如果一方的滿意度過高，另一方的滿意度偏低，兩者相差太大，但是由于前者的滿意度過高，使得相互滿意度還是有點(diǎn)高，那樣得出的結(jié)論可能會(huì)與實(shí)際情況有偏差。于是我們?cè)谀Ｐ透倪M(jìn)中，又定義了滿意度差異指數(shù)，要使配對(duì)成功率盡可能高，則要求滿意度差異指數(shù)之和最小，這樣得出的配對(duì)方案更具可取性，并且得出的結(jié)論更符合實(shí)際情況。5.6 問題四的模型建立與求解針對(duì)問題四，我們只需將工作要求也作為過濾條件，在已知的方案中對(duì)配對(duì)進(jìn)行篩選，使得在滿足工作條件的情況下，配對(duì)盡可能成功。由于用人單位的工作要求的限制，用人單位招收有男女限制。這樣對(duì)于用人單位5,13,9,20,的要求條件就多了一項(xiàng)，其他的不變。首先我們根據(jù)用人單位的用人限制，再對(duì)照前面已求的方案對(duì)照，如果已有的配對(duì)方案與用人單位的要求不沖突，那么我們就不用在進(jìn)行優(yōu)化，通過比較，發(fā)現(xiàn)已有方案不符合用人單位的要求，則我們用條件過濾的方法首先對(duì)特殊用人單位進(jìn)行篩選。5.6.1 模型建立對(duì)于工作單位的性別要求，針對(duì)問題一，我們?cè)谶M(jìn)行條件篩選時(shí)，只需在模型一的基礎(chǔ)上強(qiáng)化約束條件。目標(biāo)函數(shù)：其約束條件:5.6.2 模型求解根據(jù)lingo軟件求的Z=23.6，其配對(duì)方式如下：配對(duì)成功率最高方案用人單位P1P2P3P4P5P6P7P8P10應(yīng)聘人員Q6Q17Q13Q15Q21Q11Q8Q7Q22滿意度1.60.20.80.811.61.81.60.2用人單位P11P12P13P14P15P17P18P19P20應(yīng)聘人員Q5Q24Q20Q4Q23Q19Q18Q12Q14滿意度0.80.80.81.610.40.81.61.2用人單位P21P22P24P25應(yīng)聘人員Q16Q10Q2Q3滿意度1.60.81.61表六對(duì)于問題二和問題三的求解方法也問題一類似，只需在約束條件方面加強(qiáng)。問題二的配對(duì)方式：Z=，全部配對(duì)成功的概率最大方案用人單位P1P2P3P4P5P6P7P8P9應(yīng)聘人員Q22Q6Q13Q3Q20Q24Q25Q9Q14滿意度10.80.81110.810.4用人單位P11P12P13P14P15P16P17P18P19應(yīng)聘人員Q19Q2Q16Q15Q23Q12Q7Q4Q10滿意度0.8111.210.80.80.80.8用人單位P20P21P22P23P24P25應(yīng)聘人員Q18Q1Q21Q8Q17Q5滿意度10.810.410.8表七根據(jù)上表，可得由于用人單位的條件限制，不可能全部配對(duì)成功，用人單位10未找到合適的應(yīng)聘人員，應(yīng)聘人員11未找到合適的工作。問題三的配對(duì)方式：配對(duì)方案用人單位P1P8P11P16P17P20P21P25應(yīng)聘人員Q7Q8Q21Q3Q6Q16Q24Q23滿意度0.20.60.20.20.20.20.20.2表八5.7 問題五的求解對(duì)于N個(gè)應(yīng)聘人員和M個(gè)用人單位的情況，如上的方法都實(shí)用，只是兩個(gè)優(yōu)化模型的規(guī)模會(huì)變大，給求解帶來一定的困難。實(shí)際中，用人單位個(gè)數(shù)M不會(huì)太大，當(dāng)應(yīng)聘人員的個(gè)數(shù)N達(dá)到一定的程度時(shí)，可以分步處理。對(duì)于問題一而言，取所有應(yīng)聘人員綜合滿意度與用人單位的綜合滿意度的均值，即可得，對(duì)于滿足應(yīng)聘人員應(yīng)該淘汰掉