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

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