運(yùn)籌學(xué)課程設(shè)計(jì)運(yùn)籌學(xué)課程設(shè)計(jì)實(shí)踐報(bào)告學(xué)號(hào)：0708210101班級(jí)：管理科學(xué)與工程類(lèi)4班姓名：陳杏兒第一局部小型案例分析建模與求解 制點(diǎn)相連通。圖中的各線段標(biāo)出了允許挖電纜溝的地點(diǎn)和距離〔單位：百米〕。假設(shè)電纜線每米10元，挖電纜溝〔深1米，寬0.6米〕土方每立方米3元，其它材料和施工費(fèi)用每米5元，那么該工程預(yù)算最少需多少元？解：該問(wèn)題等價(jià)于求網(wǎng)絡(luò)最小支撐樹(shù)，利用WinSQB建立模型求解：網(wǎng)絡(luò)最小支撐樹(shù)為上圖加粗線路，所以按照加粗路線挖電纜溝能使工程預(yù)算最小，路線總長(zhǎng)62米，故最小預(yù)算為：62*1*0.6*3+62*〔10+5〕=1041.6〔元〕案例9.零件加工安排問(wèn)題有六臺(tái)機(jī)床，六個(gè)零件；機(jī)床可加工零件；可加工零件；可加工零件；可加工零件；可加工零件；可加工零件；現(xiàn)在要求制定一個(gè)加工方案，使一臺(tái)機(jī)床只加工一個(gè)零件，一個(gè)零件只在一臺(tái)機(jī)床上加工，要求盡可能多地安排零件加工，試把這個(gè)問(wèn)題化為求網(wǎng)絡(luò)最大流問(wèn)題，求出能滿足上述條件的加工方案。解:增設(shè)起始點(diǎn)s，終點(diǎn)t,將加工過(guò)程化成網(wǎng)絡(luò)流程〔設(shè)每段弧上最大流量皆為1〕：那么盡多安排加工的方案等價(jià)于求網(wǎng)絡(luò)取得最大流時(shí)的路徑。利用WinSQB建立模型求解如下〔點(diǎn)1~14分別表示點(diǎn)s，X1~X6，y1~y6，t〕：可以得到兩種結(jié)果〔如上〕，綜上，最正確加工方案為：X1加工y1；X3加工y3；X4加工y2；X5加工y4；X6加工y5或y6共5個(gè)零件。案例10.房屋施工網(wǎng)絡(luò)方案問(wèn)題下面是某公司房屋施工工程作業(yè)明細(xì)表，請(qǐng)繪制網(wǎng)絡(luò)圖，并確定關(guān)鍵路線。工序工序內(nèi)容緊前工序完成時(shí)間工序工序內(nèi)容緊前工序完成時(shí)間a破土挖槽，澆墊層—4l安裝廚房設(shè)備k1b澆混凝土基a2m安裝預(yù)制的衛(wèi)生設(shè)備k2c安裝構(gòu)架及屋面b4n完成細(xì)木工活k3d砌磚c6o完成屋頂并罩面油漆d2e安裝排水管b1p安裝天溝及落水管o1f澆地下室地坪e2q安裝防暴雨水管b1g敷設(shè)主管道e3r地板打磨及上光漆n，s2h敷設(shè)主干電路c2s油漆l，m3i安裝空調(diào)設(shè)備c，f4t完成電器作業(yè)s1j安裝墻板及裝飾板g，h，i10u最后平整p，q2k鋪設(shè)預(yù)制地板j3v鋪便道及綠化u5解：依題意，利用WinSQB建立模型求解：網(wǎng)絡(luò)圖如下：所以關(guān)鍵線路為：ABCHJKMSR第二局部：案例設(shè)計(jì)基于0-1整數(shù)規(guī)劃的公務(wù)員招聘指派問(wèn)題背景：我國(guó)公務(wù)員制度已實(shí)施多年，1993年10月1日公布施行的《國(guó)家公務(wù)員暫行條例》規(guī)定：“國(guó)家行政機(jī)關(guān)錄用擔(dān)任主任科員以下的非領(lǐng)導(dǎo)職務(wù)的國(guó)家公務(wù)員，采用公開(kāi)考試、嚴(yán)格考核的方法，按照德才兼?zhèn)涞臉?biāo)準(zhǔn)擇優(yōu)錄用”。目前,我國(guó)招聘公務(wù)員的程序一般分三步進(jìn)行：公開(kāi)考試〔筆試〕、面試考核、擇優(yōu)錄取。如何對(duì)公務(wù)員選撥中的各方面能力進(jìn)行定量化,使人才的錄用更加理性化越來(lái)越受關(guān)注。同時(shí)，針對(duì)公務(wù)員選舉的最優(yōu)方案建立的數(shù)學(xué)模型和運(yùn)用的方法對(duì)進(jìn)一步改良我國(guó)公務(wù)員招聘的運(yùn)行程序和考核指標(biāo)越發(fā)具有很強(qiáng)的實(shí)用價(jià)值和參考意義。關(guān)鍵詞：公務(wù)員招聘整數(shù)規(guī)劃指派問(wèn)題一、問(wèn)題的提出現(xiàn)有某市直屬單位因工作需要，擬向社會(huì)公開(kāi)招聘8名公務(wù)員，具體的招聘方法和程序如下：〔一〕公開(kāi)考試，根據(jù)考試總分的上下排序按1:2的比例〔共16人〕選擇進(jìn)入第二階段的面試考核?！捕趁嬖嚳己耍好嬖嚳己酥饕己藨?yīng)聘人員的知識(shí)面、對(duì)問(wèn)題的理解能力、應(yīng)變能力、表達(dá)能力等綜合素質(zhì)。按照一定的標(biāo)準(zhǔn)，面試專(zhuān)家組對(duì)每個(gè)應(yīng)聘人員的各個(gè)方面都給出一個(gè)等級(jí)評(píng)分，從高到低分成A/B/C/D四個(gè)等級(jí)，具體結(jié)果見(jiàn)表１所示?！踩秤烧衅割I(lǐng)導(dǎo)小組綜合專(zhuān)家組的意見(jiàn)、筆初試成績(jī)以及各用人部門(mén)需求確定錄用名單,并分配到各用人部門(mén)。該單位擬將錄用的8名公務(wù)員安排到所屬的7個(gè)部門(mén)，并且要求每個(gè)部門(mén)至少安排一名公務(wù)員。這7個(gè)部門(mén)按工作性質(zhì)可分為四類(lèi)：(1)行政管理、(2)技術(shù)管理、(3)行政執(zhí)法、(4)公共事業(yè)。見(jiàn)表2所示。招聘領(lǐng)導(dǎo)小組在確定錄用名單的過(guò)程中，本著公平、公開(kāi)的原那么，同時(shí)考慮錄用人員的合理分配和使用，有利于發(fā)揮個(gè)人的特長(zhǎng)和能力。招聘領(lǐng)導(dǎo)小組將7個(gè)用人單位的根本情況〔包括福利待遇、工作條件、勞動(dòng)強(qiáng)度、晉升時(shí)機(jī)和學(xué)習(xí)深造時(shí)機(jī)等〕和四類(lèi)工作對(duì)聘用公務(wù)員的具體條件的希望到達(dá)的要求都向所有應(yīng)聘人員公布〔見(jiàn)表2〕。每一位參加面試人員都可以申報(bào)兩個(gè)自己的工作類(lèi)別志愿〔見(jiàn)表1〕?，F(xiàn)在在各應(yīng)聘人員面試成績(jī)、專(zhuān)家測(cè)評(píng)和用人單位需求的的情況下,試根據(jù)以下要求探究如何選出適合公務(wù)員需求的人員,指派到適宜的部門(mén)：〔1〕如果不考慮應(yīng)聘人員的意愿，擇優(yōu)按需錄用，試幫助招聘領(lǐng)導(dǎo)小組設(shè)計(jì)一種錄用分配方案；〔2〕在考慮應(yīng)聘人員意愿和用人部門(mén)的希望要求的情況下，請(qǐng)你幫助招聘領(lǐng)導(dǎo)小組設(shè)計(jì)一種分配方案；〔3〕你的方法對(duì)于一般情況，即N個(gè)應(yīng)聘人員M個(gè)用人單位時(shí)，是否可行？表１：招聘公務(wù)員筆試成績(jī)，專(zhuān)家面試評(píng)分及個(gè)人志愿應(yīng)聘人員筆試成績(jī)申報(bào)類(lèi)別志愿專(zhuān)家組對(duì)應(yīng)聘者特長(zhǎng)的等級(jí)評(píng)分知識(shí)面理解能力應(yīng)變能力表達(dá)能力人員1290〔2〕〔3〕AABB人員2288〔3〕〔1〕ABAC人員3288〔1〕〔2〕BADC人員4285〔4〕〔3〕ABBB人員5283〔3〕〔2〕BABC人員6283〔3〕〔4〕BDAB人員7280〔4〕〔1〕ABCB人員8280〔2〕〔4〕BAAC人員9280〔1〕〔3〕BBAB人員10280〔3〕〔1〕DBAC人員11278〔4〕〔1〕DCBA人員12277〔3〕〔4〕ABCA人員13275〔2〕〔1〕BCDA人員14275〔1〕〔3〕DBAB人員15274〔1〕〔4〕ABCB人員16273〔4〕〔1〕BABC表2:用人部門(mén)的根本情況及對(duì)公務(wù)員的期望要求用人部門(mén)工作類(lèi)別各用人部門(mén)的根本情況各部門(mén)對(duì)公務(wù)員特長(zhǎng)的希望到達(dá)的要求福利待遇工作條件勞動(dòng)強(qiáng)度晉升時(shí)機(jī)深造時(shí)機(jī)知識(shí)面理解能力應(yīng)變能力表達(dá)能力部門(mén)1〔1〕優(yōu)優(yōu)中多少BACA部門(mén)2〔2〕中優(yōu)大多少ABBC部門(mén)3〔2〕中優(yōu)中少多部門(mén)4〔3〕優(yōu)差大多多CCAA部門(mén)5〔3〕優(yōu)中中中中部門(mén)6〔4〕中中中中多CBBA部門(mén)7〔4〕優(yōu)中大少多二、具體問(wèn)題分析和建模求解分析：這是一個(gè)人多事少的非標(biāo)準(zhǔn)指派問(wèn)題，適用0—1整數(shù)規(guī)劃求解。使用0—1整數(shù)規(guī)劃求解的條件分析：人員與任務(wù)數(shù)目和指派要求明確：在16個(gè)人中選8人，分配于7個(gè)部門(mén)，每個(gè)部門(mén)至少一個(gè)人，這是本案例的絕對(duì)約束條件；“擇優(yōu)按需”錄用，同時(shí)考慮錄用人員的合理分配和使用，有利于發(fā)揮個(gè)人的特長(zhǎng)和能力。優(yōu)先考慮考慮應(yīng)聘者能力與部門(mén)需求“擇優(yōu)按需”確定初步分配方案，再結(jié)合應(yīng)聘人員意愿進(jìn)行方案優(yōu)化；用人部門(mén)對(duì)公務(wù)員的期望要求和應(yīng)聘人員的意愿不是絕對(duì)約束，但是要盡量滿足〔實(shí)際上這里沒(méi)有一個(gè)應(yīng)聘者可以完全滿足部門(mén)1的能力期許〕。系數(shù)矩陣應(yīng)該表達(dá)“擇優(yōu)按需”原那么，表征每個(gè)應(yīng)聘者能給各個(gè)部門(mén)到來(lái)的效率，在本案例中沒(méi)有直接給出，需要首先求解出系數(shù)矩陣；顯見(jiàn)，“擇優(yōu)”要求受聘者的總體綜合得分盡量地高，“按需”指人員合理分配，各部門(mén)對(duì)公務(wù)員特長(zhǎng)的期望與受聘人員特長(zhǎng)盡量吻合，所以系數(shù)矩陣是充分合理地結(jié)合應(yīng)聘者的筆試成績(jī)，面試成績(jī)及用人部門(mén)要求給每個(gè)應(yīng)聘者打出的綜合評(píng)分。解：數(shù)據(jù)整理面試環(huán)節(jié)采用等級(jí)評(píng)分，不便于分析，給A，B，C，D四個(gè)等級(jí)分別賦值4、3、2、1，同時(shí)，用人部門(mén)的根本情況主要用于應(yīng)聘者參考選擇申報(bào)志愿，在以下求解中可以忽略，重新整理數(shù)據(jù)得新表格：表１：招聘公務(wù)員筆試成績(jī)，專(zhuān)家面試評(píng)分及個(gè)人志愿應(yīng)聘人員i筆試成績(jī)ai申報(bào)類(lèi)別志愿專(zhuān)家組對(duì)應(yīng)聘者特長(zhǎng)的等級(jí)評(píng)分bi知識(shí)面bi1理解能力bi2應(yīng)變能力bi3表達(dá)能力bi4人員1290〔2〕〔3〕4433人員2288〔3〕〔1〕4342人員3288〔1〕〔2〕3412人員4285〔4〕〔3〕4333人員5283〔3〕〔2〕3432人員6283〔3〕〔4〕3143人員7280〔4〕〔1〕4323人員8280〔2〕〔4〕3442人員9280〔1〕〔3〕3343人員10280〔3〕〔1〕1342人員11278〔4〕〔1〕1234人員12277〔3〕〔4〕4324人員13275〔2〕〔1〕3214人員14275〔1〕〔3〕1343人員15274〔1〕〔4〕4323人員16273〔4〕〔1〕3432表2:用人部門(mén)對(duì)公務(wù)員的期望要求用人部門(mén)j工作類(lèi)別各部門(mén)對(duì)公務(wù)員特長(zhǎng)的希望到達(dá)的要求bj知識(shí)面bj1理解能力bj2應(yīng)變能力bj3表達(dá)能力bj4部門(mén)1〔1〕3424部門(mén)2〔2〕4332部門(mén)3〔2〕部門(mén)4〔3〕2244部門(mén)5〔3〕部門(mén)6〔4〕2334部門(mén)7〔4〕2、結(jié)合每個(gè)應(yīng)聘者的筆試，面試成績(jī)及各部門(mén)對(duì)公務(wù)員的能力期望確定系數(shù)矩陣C：由上表可以得到筆試成績(jī)矩陣ai，面試成績(jī)矩陣bi，用人部門(mén)要求矩陣bj，設(shè)Cij為矩陣第i行第j列元素，代表第i個(gè)公務(wù)員對(duì)應(yīng)于第j個(gè)部門(mén)的綜合得分，結(jié)合ai，bi，bj三個(gè)矩陣求解矩陣C，用人部門(mén)對(duì)應(yīng)聘者的特長(zhǎng)要求在筆試成績(jī)局部無(wú)法表達(dá)，的值應(yīng)該包括考慮用人部門(mén)要求影響的面試成績(jī)與筆試成績(jī)兩局部。j部門(mén)k項(xiàng)能力的期望分越高代表這項(xiàng)能力在該部門(mén)越被看重，所以將bj看成bi矩陣的權(quán)重矩陣，取面試成績(jī)矩陣與用人部門(mén)要求矩陣相乘所得矩陣、筆試成績(jī)矩陣分別乘以各自的權(quán)重在相加所得矩陣作為系數(shù)矩陣：即令，有;k=1、2、3、4，、>0為根據(jù)實(shí)際情況設(shè)定的權(quán)數(shù)，這里暫取,可以得到系數(shù)矩陣如下：應(yīng)聘進(jìn)入各部門(mén)的面試得分Cij人員部門(mén)1部門(mén)2部門(mén)3部門(mén)4部門(mén)5部門(mén)6部門(mén)7人員175727269697070人員2人員3人員4人員5人員6人員768656562626363人員869686866666666人員969676768686767人員1059575760605959人員11人員12人員13人員14人員15人員163、用表示決策變量，依題意可建立0-1整數(shù)規(guī)劃模型： 問(wèn)題就轉(zhuǎn)化為求下面的優(yōu)化模型：利用WinSQB求解：增設(shè)虛部門(mén)8，取,得：應(yīng)聘進(jìn)入各部門(mén)的面試得分Cij人員部門(mén)1部門(mén)2部門(mén)3部門(mén)4部門(mén)5部門(mén)6部門(mén)7部門(mén)8人員17572726969707069人員2人員3人員4人員5人員6人員76865656262636362人員86968686666666666人員96967676868676767人員105957576060595957人員11人員12人員13人員14人員15人員16將上表系數(shù)錄入Maximization(AssignmentProblem)模型中得解如下：Solutionfor公務(wù)員招聘分配問(wèn)題:Maximization(AssignmentProblem)From To Assignment/UnitProfit/TotalProfit/ReducedCost1 Assignment1 Assignee7 1 70 70 02 Assignment2 Assignee3 1 69.80 69.80 03 Assignment3 Unused_Supply 1 0 0 04 Assignment4 Assignee6 1 66.50 66.50 05 Assignment5 Unused_Supply 1 0 0 0 6 Assignment6 Assignee5 1 64.30 64.30 07 Assignment7 Unused_Supply 1 0 0 08 Assignment8 Assignee8 1 66 66 09 Assignment9 Assignee4 1 68 68 010 Assignment10 Unused_Supply 1 0 0 011 Assignment11 Unused_Supply 1 0 0 012 Assignment12 Assignee1 1 71.70 71.70 013 Assignment13 Unused_Supply 1 0 0 014 Assignment14 Unused_Supply 1 0 0 015 Assignment15 Unused_Supply 1 0 0 016 Assignment16 Assignee2 1 70.30 70.30 0 Total Objective Function Value= 546.60 8部門(mén)為虛部門(mén)，根據(jù)第8個(gè)應(yīng)聘者的能力特長(zhǎng)，將其安排在部門(mén)1工作，即的最優(yōu)分配方案為：部門(mén)1234567應(yīng)聘者8，121629641考慮應(yīng)聘者意愿和用人部門(mén)的希望要求的情況下進(jìn)行分配。只需在3的模型上增加照顧應(yīng)聘者意愿的約束，優(yōu)化模型即可，選擇或放棄某個(gè)部門(mén)對(duì)于應(yīng)聘者而言是個(gè)相互排斥的問(wèn)題，故可采用0-1整數(shù)規(guī)劃，引入應(yīng)聘者意愿決策變量對(duì)3的模型進(jìn)行優(yōu)化得到新模型：設(shè)

代替組成新系數(shù)矩陣，同上，增設(shè)虛部門(mén)8，得系數(shù)矩陣如下表：應(yīng)聘人員部門(mén)1部門(mén)2部門(mén)3部門(mén)4部門(mén)5部門(mén)6部門(mén)7部門(mén)8人員1072726969000人員200000人員300000人員40000人員50000人員60000人員768000063630人員8068680066660人員969006868000人員1059006060000人員1100000人員120000人員1300000人員1400000人員1500000人員1600000利用利用WinSQB求解：Solutionfor公務(wù)員招聘分配問(wèn)題:Maximization(AssignmentProblem)From To Assignment|UnitProfit|TotalProfit|ReducedCost1 Assignment1 Assignee3 1 72 72 02 Assignment2 Assignee5 1 66.80 66.80 03 Assignment3 Unused_Supply 1 0 0 04 Assignment4 Assignee7 1 66.50 66.50 05 Assignment5 Assignee8 1 0 0 06 Assignment6 Unused_Supply 1 0 0 07 Assignment7 Unused_Supply 1 0 0 08 Assignment8 Assignee2 1 68 68 09 Assignment9 Assignee4 1 68 68 010 Assignment10 Unused_Supply 1 0 0 011 Assignment11 Unused_Supply 1 0 0 012 Assignment12 Assignee6 1 66.70 66.70 013 Assignment13 Unused_Supply 1 0 0 014 Assignment14 Unused_Supply 1 0 0 015 Assignment15 Unused_Supply 1 0 0 016 Assignment16 Assignee1 1 73.30 73.30 0 Tot