面試問(wèn)題論文docVIP

1、承諾書我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白， 在競(jìng)賽開始后參賽隊(duì)員不能以任何方式 （包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wè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)填寫） ：E我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：所屬學(xué)院 （請(qǐng)?zhí)顚懲?/p>

2、整的全名） ：自動(dòng)化學(xué)院參賽隊(duì)員(打印并簽名 ) ：1.祁冰露2.劉健濱3.李玉杰日期：2009 年 8月21日評(píng)閱編號(hào)(教師評(píng)閱時(shí)填寫) ：學(xué)生面試中的教師分組問(wèn)題探討摘要本文研究了在保證面試工作公平性的情況下，使用計(jì)算機(jī)搜索、逐步修正等方法，解決了在 N 一定的條件下，所需教師數(shù)量的最小值 M，并建立 0-1 整數(shù)規(guī)劃模型和多目標(biāo)優(yōu)化模型， 應(yīng)用貪婪法求解模型給出具體的分組情況，最后對(duì)模型進(jìn)行了評(píng)價(jià)并提出改進(jìn)方法。問(wèn)題一：要解決在給定條件下，求出應(yīng)聘教師最小值問(wèn)題。只要求出教師 M 與面試學(xué)生 N 的關(guān)系表達(dá)式即可。文中針對(duì)題目要求及目標(biāo)建立了單目標(biāo)規(guī)劃模型。為了確定M和 N 的關(guān)系， 我

3、們將教師任意四人分成一組，共有 C 4 M 種不同組合，各組排列按照第一個(gè)老師 >第二個(gè)老師 >第三個(gè)老師 > 第四個(gè)老師的優(yōu)先順序進(jìn)行升序或降序排列，再利用計(jì)算機(jī)從這組排列中進(jìn)行搜索比較，如果兩組中相同的老師數(shù)超過(guò)我們規(guī)定的最大值，則將后面的一組刪除，如此循環(huán)下去，直到搜索結(jié)束。另外，不斷改變M（最小取4）的值，即可求出對(duì)應(yīng)的最大面試學(xué)生數(shù)N。但是，教師編碼排序規(guī)則的不同，會(huì)直接影響輸出值N，所以，文中設(shè)計(jì)四種教師編碼排序規(guī)則，分別編程求解出四組不同的數(shù)據(jù)，根據(jù)四組數(shù)據(jù)對(duì)不滿足條件的點(diǎn)進(jìn)行修正，得到最優(yōu)數(shù)據(jù)組。最后，分別對(duì)最優(yōu)數(shù)據(jù)組進(jìn)行高斯函數(shù)和多項(xiàng)式擬和，選擇一種誤差較小

4、的擬和方案。 最后得到滿足“沒有兩個(gè)教師相同”和“沒有三個(gè)教師相同”要求下 M與 N 的關(guān)系表達(dá)式分別為：N 23.63 e N 23.69 e( M38.47 )2 20.5(M 417.8)2 232.65.701e10.95e( M4.897)2 4.186( M 155)2 125.7M15. 552()8.876 e11.28( M 45.49)25.91 e46. 38。問(wèn)題二：要求在滿足一定條件下，建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ停o出具體分配方案，并對(duì)方案進(jìn)行合理性分析。文中建立了教師與學(xué)生組合分配的多目標(biāo)規(guī)劃模型。求解模型時(shí)，通過(guò)設(shè)置約束（面試組）的優(yōu)先級(jí)別，確定優(yōu)化目標(biāo)

5、，并利用貪婪算法對(duì)模型求解，最后給出M與 N的“面試組”方案（詳見附表1）。問(wèn)題三：要做的是在新加條件（面試?yán)蠋熚睦砀靼耄幻课粚W(xué)生接受兩位文科和兩位理科教師的面試）下，解決問(wèn)題一和問(wèn)題二。本問(wèn)在問(wèn)題一模型的基礎(chǔ)上，對(duì)約束條件稍加修改，得到新的0-1整數(shù)規(guī)劃模型。解決問(wèn)題二，也是在問(wèn)題二的結(jié)論上進(jìn)行修改。將問(wèn)題進(jìn)一步簡(jiǎn)化，即從已分配好的“面試組”中挑選出滿足新條件的組合（兩奇兩偶），對(duì)余下組合，重新分配，這樣就大大減少了計(jì)算量。最后，本文在面試公平性的條件下給出題目以外的合理建議，并對(duì)模型進(jìn)行了客觀評(píng)價(jià)。 關(guān)鍵字 計(jì)算機(jī)搜索；數(shù)值擬合；0-1 整數(shù)規(guī)劃；貪婪法.1一. 問(wèn)題的重述自國(guó)家教育局實(shí)施

6、高校自主招生以來(lái)，各地高校陸續(xù)采用自主招生的模式進(jìn)行錄取新生。自主招生還處于探索階段，很多方面還不夠完善，正在進(jìn)一步發(fā)展?？忌ㄟ^(guò)考試等綜合素質(zhì)的考核后，還要經(jīng)過(guò)教師面試，決定是否錄取，這樣就會(huì)出現(xiàn)考生與面試?yán)蠋熤g分配的均勻性和面試公平性問(wèn)題。某高校采用通過(guò)專家面試的方式進(jìn)行自主招生, 經(jīng)過(guò)初選合格進(jìn)入面試的考生有N 人，擬聘請(qǐng)老師M 人進(jìn)行面試。每位學(xué)生要分別接收“面試組”每位老師的單獨(dú)面試，每個(gè)面試組由4 名老師組成，各位老師獨(dú)立對(duì)考生進(jìn)行提問(wèn)并根據(jù)學(xué)生回答問(wèn)題的情況給予評(píng)分。為了保證面試工作的公平性，組織者提出如下要求：Y1：每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡；Y2：面試不同考生的“面試

7、組”成員不能完全相同；Y3:兩個(gè)考生的“面試組”中有兩位或三位老師相同的情形盡量的少；Y4：任意兩位老師面試的兩個(gè)學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少。本文要解決下面四個(gè)問(wèn)題：?jiǎn)栴}一：設(shè)考生數(shù) N 已知，要求在滿足條件二的情況下，說(shuō)明聘請(qǐng)老師數(shù) M至少分別應(yīng)為多大，才能做到任兩位學(xué)生的“面試組”都沒有兩位以及三位面試?yán)蠋熛嗤那樾?。?wèn)題二：根據(jù)條件一至條件四的要求建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ停?并就 N=379 ，M=24 的情形給出每位老師面試學(xué)生名單的具體分配方案，并分析該方案滿足條件一至條件四的情況問(wèn)題三：假設(shè)面試?yán)蠋熤欣砜婆c文科的老師各占一般，并且要求每位學(xué)生接收兩位文科與兩位理

8、科老師的面試，在此假設(shè)下分別回答問(wèn)題一與問(wèn)題二。問(wèn)題四： 討論考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)系。為了保證面試的公平性，除了組織者提出的要求外，還有哪些因素需要考慮進(jìn)來(lái)，并給出新的分配方案或建議。二 . 模型的假設(shè)1. 假設(shè)每位學(xué)生分別單獨(dú)接受四位老師的面試；2. 假設(shè)面試時(shí)老師之間是獨(dú)立進(jìn)行互不影響；3. 假設(shè)每位考生只有一次面試的機(jī)會(huì)；4.假設(shè)假設(shè)考生的人數(shù)為N，老師的人數(shù)為M， NCM4 ；5. 假設(shè)所有老師和學(xué)生都嚴(yán)格遵守分配方案；6. 假設(shè)假設(shè)每個(gè)老師對(duì)待每個(gè)學(xué)生都是公正的。三 . 符號(hào)說(shuō)明符號(hào)含義備注M表示參加面試的老師人數(shù)N表示參加面試的學(xué)生人數(shù)2xijWjqi ,

9、 j , kpi , j , kQijPjkTijH ijF總F1F2w1w2e1e2AB為 0-1 變量，當(dāng) xij =1 時(shí)表示 第 j 個(gè)老師面試第 i 個(gè)學(xué)生時(shí)，表示被 第 j 個(gè)老師面試的學(xué)生的個(gè)數(shù)為 0-1 變量， 當(dāng) q1 時(shí)，表示第 i 個(gè)和第 j 個(gè)學(xué)i , j ,k生都被第 k 個(gè)老師面試為 0-1 變量，當(dāng) pi , j , k1 時(shí)，表示 老師 j 、 k 面試都學(xué)生 i學(xué)生 i 和 j 的面試組中含有相同老師的個(gè)數(shù)老師 j 、 k 面試相同學(xué)生的個(gè)數(shù)為 0-1變量，當(dāng) Tij1時(shí)，表示 學(xué)生 i 和 j 的面試組中含有相同老師的個(gè)數(shù)分別為2為 0-1變量，當(dāng) H ij

10、1時(shí)，表示學(xué)生 i 和 j 的面試組中含有相同老師的個(gè)數(shù)分別為 3 考生面試的總成績(jī)考生面試的理科成績(jī)考生面試的文科成績(jī)考生理科成績(jī)占的權(quán)重考生文科成績(jī)占的權(quán)重非線性擬和結(jié)果平均誤差非線性擬和結(jié)果平均誤差全部為奇數(shù)的編碼組合全部為偶數(shù)的編碼組合模型一問(wèn)題二問(wèn)題二問(wèn)題二問(wèn)題四問(wèn)題四問(wèn)題四問(wèn)題四問(wèn)題四問(wèn)題一問(wèn)題一問(wèn)題三問(wèn)題三四 . 問(wèn)題分析4.1 問(wèn)題題干的分析面試在自主招生中扮演著越來(lái)越重要的角色，考生面試的成績(jī)不容忽視。因此如何確定面試專家的分配方案，使錄取工作真正公平合理的進(jìn)行，是各大高校積極考慮的問(wèn)題。本文要解決的是在公平、均衡的情況下對(duì)面試?yán)蠋熯M(jìn)行合理分配。這是一個(gè)優(yōu)化問(wèn)題，所以我們考慮

11、到用目標(biāo)規(guī)劃模型來(lái)解決問(wèn)題一和問(wèn)題二，問(wèn)題三可以根據(jù)問(wèn)題一二稍加修改即可以解決。規(guī)劃模型中的目標(biāo)函數(shù)和約束條件，我們可以根據(jù)將題目中的約束條件、變量和求解目標(biāo)轉(zhuǎn)化為數(shù)學(xué)表達(dá)式，這樣就構(gòu)成了目標(biāo)規(guī)劃模型。最后要做的是求解模型，可以考慮用遺傳算法、極大極小法、理想點(diǎn)法等進(jìn)行模型求解。4.2 問(wèn)題一的分析問(wèn)題一要求的是在學(xué)生數(shù)N 已知，且滿足面試不同考生的“面試組”3成員不能完全相同的情況下，計(jì)算聘請(qǐng)老師數(shù) M 至少分別應(yīng)為多大，才能做到任兩位學(xué)生的“面試組”都沒有兩位以及三位面試?yán)蠋熛嗤那樾巍?wèn)題一相對(duì)較簡(jiǎn)單，是一個(gè)單目標(biāo)規(guī)劃問(wèn)題。只要把題目要求的決策變量和約束條件轉(zhuǎn)化成數(shù)學(xué)表達(dá)式，就可以得到目

12、標(biāo)規(guī)劃模型的約束條件和目標(biāo)函數(shù)。由于教師數(shù)M 、學(xué)生數(shù) N 均未知，因此無(wú)法求出最少教師數(shù)目或最多學(xué)生數(shù)目。因此考慮應(yīng)用枚舉法（取部分?jǐn)?shù)據(jù)），列出 M 值求出對(duì)應(yīng)的最優(yōu)學(xué)生數(shù)N，此步應(yīng)用計(jì)算機(jī)編程實(shí)現(xiàn)。最后對(duì)所得數(shù)據(jù)進(jìn)行函數(shù)擬合，即可得到面試學(xué)生數(shù)N 與所需最少教師M 的函數(shù)表達(dá)式。4.3 問(wèn)題二的分析問(wèn)題二與問(wèn)題一類似，只是多出了條件Y1和 Y4 ，是一個(gè)多目標(biāo)最優(yōu)化問(wèn)題。條件Y1 （每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡）作為模型二的約束條件；條件Y4（任意兩位老師面試的兩個(gè)學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少）讓求的是盡量最優(yōu)問(wèn)題，因此可以作為目標(biāo)函數(shù)。我們可以在模型一的基礎(chǔ)上，增加一個(gè)約束條件

13、，增加一個(gè)目標(biāo)，這樣就建立一個(gè)新的多目標(biāo)優(yōu)化模型。我們把“面試組”分為四類，分別為：沒有一個(gè)教師相同的情形；有一個(gè)教師相同；有兩個(gè)教師相同；有三個(gè)教師相同，且優(yōu)先級(jí)逐次降低。求解模型時(shí)，我們采用貪婪法思想編程，按照四種“面試組”的優(yōu)先級(jí)順序，分別從 C 4 M 中教師組合中，搜索出面試學(xué)生數(shù)目的“面試組”。至此，對(duì) M=24 ， N=379 進(jìn)行合理公平的分配基本完成。4.4 問(wèn)題三的分析問(wèn)題三和問(wèn)題二相比，增加了新的約束條件“文理科教師各占一半”和“每 位學(xué)生 分別 接受兩位 文科兩 位理 科教師的 面試”。我們假設(shè)1 、3M 1的編碼代表文科教師， 2、 4、 6M 的編碼代表理科教師（M

14、為偶數(shù)的前提下） 。新的條件下解決問(wèn)題一：只是在模型中加入“文理科教師各占一半”和“每位學(xué)生分別接受兩位文科兩位理科教師的面試”的約束條件，其余做法和模型一完全相同。新條件下解決問(wèn)題二：將問(wèn)題轉(zhuǎn)化成數(shù)學(xué)語(yǔ)言，就是我們所求出的所有 378 的教師組合中，必須含有兩個(gè)奇數(shù)和兩個(gè)偶數(shù)。本問(wèn)可以直接在模型二結(jié)果的基礎(chǔ)上求解。第一步，挑選出不符合“兩奇、兩偶”的組合；第二步， 將不符合條件的組合相互之間重新安排分配組合，這樣就組成378組“最多有兩個(gè)教師相同”的分配方案；第三步，第379 位同學(xué)的“面試組”可以從24 位教師中任選4 位，這樣就會(huì)出現(xiàn)5 為同學(xué)的“面試組”有“三個(gè)教師相同”的情形。最后對(duì)

15、新的分配方案進(jìn)行條件Y1Y4 的合理性分析。4.5 問(wèn)題四的分析借鑒問(wèn)題 13 的求解過(guò)程及結(jié)果，針對(duì)面試面試均勻性與公平性的關(guān)系，給出幾點(diǎn)可行建議，以避免出現(xiàn)面試過(guò)程不公平現(xiàn)象的產(chǎn)生。五 . 模型的建立和求解45.1 問(wèn)題 1 模型的建立及其求解本問(wèn)題解決的是滿足一定約束條件要求，計(jì)算在給出一定的學(xué)生人數(shù)下，所需要教師的最少人數(shù)。我們把這個(gè)實(shí)際問(wèn)題抽象為目標(biāo)規(guī)劃模型的數(shù)學(xué)問(wèn)題來(lái)求解。根據(jù)實(shí)際情況分析，一般面試學(xué)生的個(gè)數(shù)要遠(yuǎn)大于教師的個(gè)數(shù)。因?yàn)榻處熑藬?shù)較少，容易進(jìn)行分組（即按照約束條件將教師每四人分成一組），滿足約束條件的情況下， 所能組合的最大組數(shù)目即可面試學(xué)生的最大人數(shù)。因此，我們改變優(yōu)化

16、變量，當(dāng)教師數(shù)目M 一定的情況下最多可面試的學(xué)生個(gè)數(shù)，即求 max N 。5.1.2 沒有兩位老師相同的情形5.1.2.1 模型 1.1的建立（1）設(shè) xi j代表第 j 個(gè)老師面試第 i 學(xué)生， xi j 0 表示第 j 個(gè)老師不面試第 i 個(gè)學(xué)生， xi j1表示第 j 個(gè)老師面試第 i 個(gè)學(xué)生，用數(shù)學(xué)語(yǔ)言表達(dá)即：第j 個(gè)老師面試第 i 個(gè)學(xué)生1,（ xi j 為 0 1 變量）。xij0,第j 個(gè)老師不面試第 i 個(gè)學(xué)生（2）每個(gè)學(xué)生只能接受四名老師面試，轉(zhuǎn)化成數(shù)學(xué)表達(dá)式為：Mxik 4(i 1, 2 ,N,。)k 1（3）任意兩位學(xué)生的“面試組”不能有兩個(gè)老師相同的情形，轉(zhuǎn)化為M，其中

17、 k 表示第 k 個(gè)老如下數(shù)學(xué)表達(dá)式：xik x jk 1(ij; i, j 1,2, ,N )k1師， xi k 、 x j k 是 0 1 變量。通過(guò)以上 3 步的模型準(zhǔn)備，針對(duì)“沒有兩個(gè)老師相同的情形”可建立如下單目標(biāo)規(guī)劃模型 1.1：max N(1)Mxik x jk 1 (i j; i, j 1,2, , N )(2)k 1Mst.xik4(i 1,2, , N )(3)k 1xik, x j k0或1（是 0-1變量）(4)5.1.2.2 模型 1.1 的求解由于 M 是未知數(shù)，所以沒有辦法使用優(yōu)化算法求出具體的N 值，這里我們采用數(shù)值模擬的方法，通過(guò)列舉一定的 M 值，求出相應(yīng)的

18、最優(yōu)的N 值，然后通過(guò)曲線擬合的方法求出M 和 N 的近似表達(dá)式，從而求出考生數(shù)為N時(shí)，至少需要聘請(qǐng)的老師數(shù)M 。列舉 M 值，求相應(yīng)的最優(yōu)的N 值，針對(duì)此模型我們?cè)O(shè)計(jì)了尋優(yōu)算法，此步可以通過(guò) Matlab 編程實(shí)現(xiàn)，程序的算法由以下步驟實(shí)現(xiàn)：Step1：首先對(duì) M 位教師每四人一組進(jìn)行組合，求出所有組合項(xiàng)為CM4 ，把所有項(xiàng)按遞增方式排列成序列S0 ；5Stsp2：從 S0 第一項(xiàng)開始，逐次掃描后面所有項(xiàng)，如果后面項(xiàng)同第一項(xiàng)有兩個(gè)或超過(guò)數(shù)字相同的就將其刪除，這樣形成了一個(gè)新的序列S1 ；Step3：從 S1 的第二項(xiàng)開始，逐次掃描后面所有項(xiàng)，如果后面項(xiàng)同第二項(xiàng)有兩個(gè)或超過(guò)兩個(gè)數(shù)字相同的就將其

19、刪除， 這樣形成了一個(gè)新的序列 S2 ，然后從 S2 的第三項(xiàng)開始，逐次掃描后面所有項(xiàng)，如果后面項(xiàng)同第三項(xiàng)有超過(guò)兩個(gè)數(shù)字相同的就將其刪除，這樣形成了一個(gè)新的序列S3 ，依次類推，直到搜索完成。注：考慮到問(wèn)題二有讓求解24 位教師的面試分配情況，在此，我們只列舉出 4 24 位教師，所能面試的最大學(xué)生數(shù)。將24 位教師分別編號(hào)為1、 2、324；學(xué)生分別編號(hào)為1、2、 3N。通過(guò) Matlab 軟件編程實(shí)現(xiàn)（見附錄程序1），所得數(shù)據(jù)如表1：表 1 不能有兩個(gè)教師相同的情況教師（M） 4567891011121314學(xué)生（ N） 1112233691311教師（M） 151617181920212

20、22324學(xué)生（ N） 13151720212426303335從表 1 得到的數(shù)據(jù)看，當(dāng)教師從13 位增加到 14 時(shí)，所能面試的學(xué)生的最大人數(shù)不增加，反而變小了（本文將這種數(shù)稱為“特殊數(shù)”）。這說(shuō)明算法陷入局部最優(yōu)， 即不能按照表1 數(shù)據(jù)進(jìn)行教師數(shù)M 與學(xué)生數(shù) N 的數(shù)值擬和，局部最優(yōu)擬和出的結(jié)果會(huì)產(chǎn)生很大的殘差，致使擬和結(jié)果誤差較大。因此我們將表 1 數(shù)據(jù)進(jìn)行修正， 即將 14 個(gè)教師所能面試的最大學(xué)生數(shù)改為13 個(gè)教師所能面試的學(xué)生數(shù)13。M 值對(duì)應(yīng)的最大我們知道，當(dāng)教師編號(hào)按照不同規(guī)則排序，列舉出的N 會(huì)不同。所以，本文為得到最優(yōu)結(jié)果或使計(jì)算結(jié)果逼近最優(yōu)值，利用 Matlab編程分別

21、求出教師編號(hào)按照不同規(guī)則排序情況下，一定數(shù)量教師M 對(duì)應(yīng)能面試的最多學(xué)生數(shù)N 值。然后對(duì)每組數(shù)據(jù)都按照上述方法進(jìn)行修正，最后可以得到一組最優(yōu)值，即每一個(gè)M 值，對(duì)應(yīng)能得到真實(shí)的最大N 值。四種教師編碼排序規(guī)則如下：C1：第一個(gè)老師編號(hào)遞增, 第二個(gè)老師編號(hào)遞增, 第三個(gè)老師編號(hào)遞增 ,第四個(gè)老師編號(hào)遞增；C2：第一個(gè)老師編號(hào)遞增 , 第二個(gè)老師編號(hào)遞增 , 第三個(gè)老師編號(hào)遞增 , 第四個(gè)老師編號(hào)遞減；C3：第一個(gè)老師編號(hào)遞增 , 第二個(gè)老師編號(hào)遞增 , 第三個(gè)老師編號(hào)遞減 , 第四個(gè)老師編號(hào)遞減；C4：第一個(gè)老師編號(hào)遞增 , 第二個(gè)老師編號(hào)遞減 , 第三個(gè)老師編號(hào)遞減 , 第四個(gè)老師編號(hào)遞減；

22、通過(guò) Matlab軟件編程（見附錄程序1），得到四組數(shù)據(jù)分別如下：按 C1 規(guī)則：教師（ M） 4567891011121314學(xué)生（ N） 1112233691311教師（ M） 15161718192021222324學(xué)生（ N） 13151720212426303335按 C2 規(guī)則：6教師（ M）4567891011121314學(xué)生（ N）1112233691312教師（ M）15161718192021222324學(xué)生（ N） 12161720222329303538按 C3 規(guī)則：教師（ M）4567891011121314學(xué)生（ N）1112233691313教師（ M）1516

23、1718192021222324學(xué)生（ N） 14161820232527303136按 C4 規(guī)則：教師（ M） 4567891011121314學(xué)生（ N）1112233691313教師（ M） 15161718192021222324學(xué)生（ N） 13141415152023252525將以上四個(gè)表格中的“特殊點(diǎn)”M 對(duì)應(yīng)的 N 值，全部修正為第M-1 個(gè)數(shù)對(duì)應(yīng)的 N 值，最后得到一組修正后的最優(yōu)結(jié)果見下表：教師（ M） 4567891011121314學(xué)生（ N） 1112233691313教師（ M） 15161718192021222324學(xué)生（ N） 1416182023 25

24、29 30 35 38分析上表得到對(duì)應(yīng)的學(xué)生數(shù)與所需老師的最少數(shù)量的數(shù)據(jù)如下表2:表 2 “沒有兩個(gè)老師相同”已知N 對(duì)應(yīng)的最小 M表M479111213141516N1236913131416M1718192021222324N1820232529303538表 2 中顯示， 24 位教師可以面試的最多學(xué)生數(shù)為38 人；而未修正前的表 1 顯示 24 位教師能面試學(xué)生的最大人數(shù)為35 人。由此可見，修正后的數(shù)據(jù)更逼近最優(yōu)解或者即為最優(yōu)解。針對(duì)表 2數(shù)據(jù)，為了用 Matlab 編程，進(jìn)行曲線擬合，為了擬合結(jié)果更加準(zhǔn)確，我們采用兩種方式擬合。1) 高斯函數(shù)擬和用 Matlab 編程，采用高斯函數(shù)

25、逼近，擬合所得圖形如下圖1 所示：7圖 1 “沒有兩個(gè)老師相同”情形下擬合圖通過(guò)運(yùn)行結(jié)果得到的參數(shù)，列出教師數(shù)M 和面試最大面試學(xué)生數(shù)N 的函數(shù)表達(dá)式：M 38.47)2M 4. 897)2M 15. 55)2(（ 1）N 23.63 e20.55.701 e4 .1868.876 e11.282) 多項(xiàng)式擬和直接用 polyfit函數(shù)對(duì)數(shù)據(jù)進(jìn)行5 次擬合時(shí) , 所得圖形如下圖2：圖 2 “沒有兩個(gè)老師相同”情形下擬合圖得到的函數(shù)表達(dá)式為：f ( x)0.00048x0.01807x 20.30479x 32.74139x 42.25378x5（ 2）5.1.2.3結(jié)果和誤差分析根據(jù)公式（ 1

26、）求出 M擬合值，并與原始值做比較，結(jié)果見下表3：表 3非線性擬和誤差分析表原始數(shù)4791112131516擬合數(shù)4.916.638.4011.5811.5113.6214.4415.97誤差0.910.370.60.580.490.620.560.03原始數(shù)1718192021222324擬合數(shù) 17.19 18.09 19.11 19.74誤差0.190.090.110.268求出表 3中誤差值的平均誤差e10.2508。根據(jù)公式（ 2）求出 M擬合值，并與原始值做比較，結(jié)果見下表4：表 4 線性擬和誤差分析表原始數(shù)4791112131516擬合數(shù)4.716.658.1811.0512.5

27、3114.0814.5115.47誤差0.710.350.820.050.531.080.490.53原始數(shù)1718192021222324擬合數(shù)16.5417.6819.3220.2621.5221.7122.5824.20誤差0.460.320.320.260.520.290.420.20求出表 4中誤差值的平均誤差e20.3063。由此得出，第一種線型擬合的得出的結(jié)果誤差要小，擬合的值更接近真實(shí)值，所以采用第一種方案。即 M一定時(shí)，可面試的最大學(xué)生人數(shù) N 與 M 的關(guān)系表達(dá)式為：( M 38.47)2( M 4.897)2( M 15.55) 2N 23.63 e20.55.701 e

28、4 .1868.876 e11.28（ 3）沒有三位老師相同的情形任兩位學(xué)生的“面試組”都沒有三位面試?yán)蠋熛嗤那樾危O(shè)計(jì)模型步驟和算法基本與模型.1.1（見）相同。只有上文中第三小點(diǎn)：任意兩位學(xué)生的“面試組”不能有三位老師相同的情形，更改為如下數(shù)學(xué)M表達(dá)式：xik x jk2，其中 k 表示第 k 個(gè)老師，xi k 、( i j; i, j 1, 2, , N )k 1x j k 是 0 1 變量。同理可建立單目標(biāo)規(guī)劃模型1.2：maxNMxik xjk2(ij; i , j1,2, N )k 1Mst.xik4(i 1,2, N )k1x, xj k0或1（是 0-1變量）ik設(shè)計(jì)尋優(yōu)算法

29、，利用Matlab 編程（程序及運(yùn)行結(jié)果見附錄程序2），運(yùn)行結(jié)果所得數(shù)據(jù)如表5：表 5不能有三個(gè)教師相同的情況教師（ M） 4567891011121314學(xué)生（ N） 113714141826395577教師（ M） 15161718192021222324學(xué)生（ N） 105140140148164189221263315378同理，針對(duì)“不能有三個(gè)教師相同的情形”，我們也不能直接使用表 2 中一次得出的數(shù)據(jù)擬合。因?yàn)椋脭?shù)據(jù)沒有對(duì)不合理的數(shù)進(jìn)行修正，也使結(jié)果陷入局部最優(yōu)，最終導(dǎo)致擬和結(jié)果與實(shí)際相差太大的后果。根據(jù)“沒有兩個(gè)教師相同的情形” 中的四個(gè)教師編碼規(guī)則， 使用 Matlab編程

30、計(jì)算出如下四組結(jié)果：按 C1 規(guī)則：9教師（M） 4567891011121314學(xué)生（N） 113714141826395577教師（M） 15161718192021222324學(xué)生（ N） 105140140148164189221263315378按 C2 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714152130395571教師（M） 15161718192021222324學(xué)生（N） 95140140163195229272324376424按 C3 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714141830395577教師（

31、M） 15161718192021222324學(xué)生（ N） 105140140148177189244295328378按 C4 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714142029405472教師（M） 15161718192021222324學(xué)生（N） 96140138163190220 257296331384將以上四個(gè)表格中的“特殊點(diǎn)”M對(duì)應(yīng)的 N 值，全部修正為第M-1 個(gè)數(shù)對(duì)應(yīng)的 N 值，最后得到一組修正后的最優(yōu)結(jié)果見下表：教師（ M） 4567891011121314學(xué)生（ N） 113714152130405577教師（ M） 15161718

32、192021222324學(xué)生（ N） 105140140163195229272324376424分析上表得到對(duì)應(yīng)的學(xué)生數(shù)與所需老師的最少數(shù)量的數(shù)據(jù)如下表6:表 6“沒有三個(gè)老師相同”已知N 對(duì)應(yīng)的最小 M表M467891011121314N13714152130405577M15161718192021222324N105140140163195229272324376424對(duì)比表6 和表 5：表 3 顯示， 24 位教師可以面試的最多學(xué)生數(shù)為424人；而未修正前的表2 顯示 24 位教師能面試學(xué)生的最大人數(shù)為378 人。教師人數(shù)越大時(shí)，所能面試的學(xué)生最大學(xué)生人數(shù)相差越大。因此，修正后的數(shù)據(jù)

33、擬和出的數(shù)值表達(dá)式更能真實(shí)的反映教師數(shù)M 和可面試的最大學(xué)生數(shù)N 的關(guān)系。已經(jīng)證明，采用高斯函數(shù)擬合，比采用多項(xiàng)式擬合得出的結(jié)果更準(zhǔn)確，因此，對(duì)“沒有三個(gè)教師相同的情形”，我們直接采用高斯函數(shù)進(jìn)行擬合。通過(guò)對(duì)表4 中的數(shù)據(jù)進(jìn)行數(shù)據(jù)擬和，擬合所得圖形如下圖3 所示：10圖 3 “沒有三個(gè)老師相同”情形下的擬合圖由圖 3 也可以看到，曲線擬合效果比較好，基本上所有的點(diǎn)都在曲線的附近浮動(dòng)。對(duì)應(yīng)的M 與 N 的表達(dá)式為：(M 417.82(M 1552M 45.49)2)5.91 e(（ 4）N 23.69 e232.610.95 e125.746.385.2 問(wèn)題二模型的建立及求解本問(wèn)題是要求根據(jù)

34、Y1Y4 的要求，建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ?。相?dāng)于在問(wèn)題一的基礎(chǔ)上增加了約束和目標(biāo)，因此問(wèn)題二要解決的是一個(gè)多目標(biāo)規(guī)劃問(wèn)題。首先對(duì)題目給出的四個(gè)要求進(jìn)行量化分析，轉(zhuǎn)化為多目標(biāo)規(guī)劃的四個(gè)約束條件；再將問(wèn)題2 的目標(biāo)轉(zhuǎn)化為數(shù)學(xué)表達(dá)式，得到目標(biāo)函數(shù)，最后進(jìn)行規(guī)劃分配得到到一個(gè)多目標(biāo)規(guī)劃求最優(yōu)的模型2。貪婪法思想簡(jiǎn)介貪心方法是一種改進(jìn)了的分級(jí)處理方法。它首先根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。然后按這種量度標(biāo)準(zhǔn)對(duì)這n 個(gè)輸入排序，并按序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)

35、處理方法稱為貪心方法。由上述定義知，選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法設(shè)計(jì)求解的核心問(wèn)題。本問(wèn)中也建立的優(yōu)先級(jí)標(biāo)準(zhǔn)，詳細(xì)見5.2.4 程序算法編寫步驟。5.2.2 將題目要求量化處理1、對(duì)于 Y1 的要求：要使每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡第j 個(gè)老師面試第 i 個(gè)學(xué)生1,，其中 i = （ 1 ， 2， ， N ） , j =設(shè) xij0,第j 個(gè)老師不面試第 i 個(gè)學(xué)生（1，2， ，M）則第j 個(gè)老師面試學(xué)生的個(gè)數(shù)為：11NWjxij(i1,2, N; j1,2, M )i 1要使老師面試的學(xué)生數(shù)量應(yīng)盡量均衡，由于有N 個(gè)學(xué)生和M 個(gè)老師，則平均每個(gè)老師面試學(xué)生的個(gè)數(shù)為W4N

36、 ，代入 N 379,M 24， 求得MW63.1667 ，我們可以假設(shè)WiWj12、對(duì)于 Y2 的要求：面試不同考生的“面試組”成員不能完全相同通過(guò)分析可以求出任意兩位學(xué)生被同一個(gè)老師面試為：qi, j ,kxikx jk(i j且 i, j1,2, N ; k1,2, ,M) ，式中， xik, x jk 均為 0 1 變量，所以：，第 i 和第 j 個(gè)學(xué)生都被第 k個(gè)老師面試qi , j ,k1，第 i 和第 j 個(gè)學(xué)生不都被第 k個(gè)老師面試0由此得到任意兩個(gè)學(xué)生i 和 j 的面試組中含有相同老師的個(gè)數(shù)為Qij ，MQijqi , j ,k(ij且 i , j1,2,N ; k1,2,

37、M )k1由于面試不同考生的“面試組”成員不能完全相同，則：Qij43、對(duì)于Y3 的要求 : 兩個(gè)考生的“面試組”中有兩位或三位老師相同的情形盡量的少通過(guò)分析得到：Tij1， Qij2j 且i, j1,2,N0，其它， i1， Qij3j且i , j1,2,NH ij， i0，其它式中 Tij 和 H ij 分別表示任意兩個(gè)學(xué)生i 和 j 的面試組中含有相同老師的個(gè)數(shù)分別為2和 3的情況。要使這兩種情況數(shù)目盡量少，應(yīng)當(dāng)對(duì)含有相同老師的不同組合進(jìn)行加權(quán)處理，由題目公平性的理解，當(dāng)面試組中含有相同老師的數(shù)目越小是，更顯公平性，所以，就是先考慮使兩個(gè)老師相同的數(shù)目少，在考慮三個(gè)老師相同的數(shù)目少。用數(shù)

38、學(xué)語(yǔ)言表示為求：N1NN1NminZ1TijH ij()i 1 ji 1i1 ji 14、對(duì)于 Y4 的要求 : 任意兩位老師面試的兩個(gè)學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少設(shè) p xij xik 表示任意兩個(gè)老師 j 、 k 面試學(xué)生 i 的情況，由于 xij 和 xik 為 01 變量，則：1，j,k 兩個(gè)老師都面試學(xué)生 ipi, j , k0，j,k 兩個(gè)老師不都面試學(xué)生 i 所以，任意兩個(gè)老師 j 、 k 都面試學(xué)生相同的個(gè)數(shù)為：12nPjkpi , j ,ki1根據(jù)題目意思，所以有：M 1Mmin Z2Pjkk 1j k 1模型 2 的建立根據(jù)模型準(zhǔn)備， 以任意兩個(gè)學(xué)生的面試組中有兩個(gè)老

39、師或三個(gè)老師相同的情況盡量少、任意兩個(gè)老師面試學(xué)生的集合出現(xiàn)相同學(xué)生盡量少為目標(biāo)，在滿足約束條件下，可以建立整數(shù)規(guī)劃模型如下：N1NN1NminZ1TijH iji1 ji1i 1 ji1M1MminZ2Pjkk 1 jk1WiWj1Mxij4j 1st.Qij4NW jxiji 1xij 為01變量模型解釋：1) 目標(biāo) 1：表示兩個(gè)考生的“面試組”中有兩位或三位老師相同的情形盡量的少；2) 目標(biāo) 2：表示任意兩位老師面試的兩個(gè)學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少；3) 約束 1：表示每位老師面試的學(xué)生數(shù)量應(yīng)盡量的均衡；4) 約束 2：每位學(xué)生只能接受四位教師的面試；5) 約束 3：表示面試不同

40、考生的“面試組”成員不能完全相同；6) 約束 4：代表第 j 個(gè)教師面試學(xué)生的總數(shù)；7) 約束 5：代表第 j 個(gè)教師面試第 i 個(gè)學(xué)生的 0-1 變量。求解當(dāng) N=379 ， M=24 的分配方案1、設(shè)計(jì)算法針對(duì)本問(wèn)，我們?cè)O(shè)計(jì)了如下尋優(yōu)標(biāo)準(zhǔn)：把“面試組”分為四類，分別為：沒有一個(gè)教師相同的情形；有一個(gè)教師相同；有兩個(gè)教師相同；有三個(gè)教師相同，且優(yōu)先級(jí)逐次降低。求解模型時(shí)，我們采用貪婪法思想編程，按照四種“面試組”的優(yōu)先級(jí)順序，分別從 C 4 M 中教師組合中，搜索出面試學(xué)生數(shù)目的“面試組”。至此，對(duì)M=24 ， N=379 進(jìn)行合理公平的分配基本完成。程序算法步驟如下：Step1：首先對(duì) M 位教師每四人一組進(jìn)行組合，求出所有組合項(xiàng)為CM4 ，把所