運(yùn)籌學(xué)應(yīng)用實(shí)例分析

運(yùn)籌學(xué)課程設(shè)計(jì)實(shí)踐報(bào)告管理科學(xué)與工程類第一部分小型案例分析建模與求解.............................錯(cuò)誤!未定義書簽。案例1.雜糧銷售問題.....................................錯(cuò)誤!未定義書簽。案例2.生產(chǎn)計(jì)劃問題.....................................錯(cuò)誤!未定義書簽。案例3.報(bào)刊征訂、推廣費(fèi)用的節(jié)省問題....................錯(cuò)誤!未定義書簽。案例4.供電部門職工交通安排問題.........................錯(cuò)誤!未定義書簽。案例5.籃球隊(duì)員選拔問題.................................錯(cuò)誤!未定義書簽。案例6.工程項(xiàng)目選擇問題................................錯(cuò)誤!未定義書簽。案例8.電纜工程投資資金優(yōu)化問題.........................錯(cuò)誤!未定義書簽。案例9.零件加工安排問題.................................錯(cuò)誤!未定義書簽。案例10.房屋施工網(wǎng)絡(luò)計(jì)劃問題............................錯(cuò)誤!未定義書簽。第二部分：案例設(shè)計(jì)..........................................錯(cuò)誤!未定義書簽。一、問題的提出...........................................錯(cuò)誤!未定義書簽。二、具體問題分析和建模求解...............................錯(cuò)誤!未定義書簽。第一部分小型案例分析建模與求解案例1.雜糧銷售問題一月份，進(jìn)貨價(jià)元，出貨價(jià)元；二月份，進(jìn)貨價(jià)元，出貨價(jià)元；三月份，進(jìn)貨價(jià)元，出貨價(jià)元；如買進(jìn)的雜糧當(dāng)月到貨，需到下月才能賣出，且規(guī)定“貨到付款公司希望本季度末庫(kù)存為2000擔(dān)，問應(yīng)采取什么樣的買進(jìn)與賣出的策略使三個(gè)月總的獲利最大，每個(gè)月考慮先賣后買利用WinSQB求解(x1,x2,x3,x4,x5,x6分別表示x10,x11,x21,x21,x30,x31)：案例2.生產(chǎn)計(jì)劃問題某廠生產(chǎn)四種產(chǎn)品。每種產(chǎn)品要經(jīng)過A，B兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成A工序，以A1，A2表示；有三種規(guī)格的設(shè)備能完成B工序，以B1，B2，B3表示。產(chǎn)品D可在A，B任何一種規(guī)格的設(shè)備上加工。產(chǎn)品E可在任何規(guī)格的A設(shè)產(chǎn)品G可在任何一種規(guī)格的A設(shè)備上加工，但完成B工序時(shí)只能在B1，B2設(shè)備上加工。已知生產(chǎn)單件產(chǎn)品的設(shè)備工時(shí)，原材料費(fèi)，及產(chǎn)品單價(jià)，各種設(shè)備有效臺(tái)時(shí)如下表，要求安排最優(yōu)的生產(chǎn)計(jì)劃，使該廠利潤(rùn)最大產(chǎn)品產(chǎn)品設(shè)備有效臺(tái)時(shí)21240003原料費(fèi)（元/件）298564ABBB設(shè)設(shè)A1設(shè)Xia(b)j為i產(chǎn)品在a(b)j設(shè)備上的加工數(shù)量,i=1,2,3,4;j=1,2,3，得變量列表設(shè)產(chǎn)品設(shè)備有效臺(tái)時(shí)Ta(b)AX1a1X2a1X3a1X4a160111AX1a2X2a2X3a2X4a2100002X2b11X3b22X3b33原料費(fèi)Ci（元/件單價(jià)Pi（元/件）X1b1X1b2X1b3X3b1X3b2X3b3X4b1X4b2X4b340004000BBB其中，令X3a1，X3b1，X3b2，X3b3，X4b3=0目標(biāo)函數(shù):ΣΣ=*（X1a1+X1a2）+*（X2a1+X2a2）+*X3a2+*（X4a1+X4a2）ΣXΣXΣX利用WinSQB求解（X1~X4，X5~X8,X9~X12,X13~X17,X18~X20分別表示各行變量綜上，最優(yōu)生產(chǎn)計(jì)劃如下：設(shè)設(shè)設(shè)A1A2B1B2B3產(chǎn)品3400422423400目標(biāo)函數(shù)Maxz=3495，即最大利潤(rùn)為3495案例3.報(bào)刊征訂、推廣費(fèi)用的節(jié)省問題該問題可以看成是求費(fèi)用最小的產(chǎn)銷平衡運(yùn)輸問題，中文書刊出口部720深圳分公司4147500利用WinSQB求解中文書刊出口部125002500深圳分公司7500上海分公司25005000案例4.供電部門職工交通安排問題我們把通勤費(fèi)作為優(yōu)化的目標(biāo)。ai(i=1，2，......18)表示住地的職工人數(shù)，用表示每個(gè)職工從住地到各工作地點(diǎn)的月通勤費(fèi)（單位：元），有關(guān)數(shù)據(jù)列表如下表，試建立此問題的數(shù)學(xué)模型并求解。工作地點(diǎn)工作地點(diǎn)1309200975000005800000054000006000006ai39296711815642441C住地根據(jù)題意，以員工住地為產(chǎn)地，工作地點(diǎn)為銷地，將問題轉(zhuǎn)化為求月總通勤費(fèi)最小利用WinSQB建立模型求解：：（CC1住地23456781335192581961567778119114481155664422442241199565某?；@球隊(duì)準(zhǔn)備從十名預(yù)備隊(duì)員中選擇五名作為正式隊(duì)員，隊(duì)員的各種情況如下隊(duì)員號(hào)碼隊(duì)員號(hào)碼技術(shù)分位置1241123000932600435005250068722008后衛(wèi)92400后衛(wèi)3200后衛(wèi)（1）至少補(bǔ)充一名中鋒。（5）技術(shù)分平均要求不低于分。由于經(jīng)費(fèi)有限，希望月薪總數(shù)越少越好。試建立此問題的數(shù)學(xué)模型。Xi={1ΣiΣ利用WinSQB建立模型求解：綜上，應(yīng)該選拔第2，6，7，8，10號(hào)隊(duì)員為正式隊(duì)員，共需支付月薪12100（元）案例6.工程項(xiàng)目選擇問題某承包企業(yè)在同一時(shí)期內(nèi)有八項(xiàng)工程可供選擇投標(biāo)。其中有五項(xiàng)住宅工程，三項(xiàng)工業(yè)車間。由于這些工程要求同時(shí)施工，而企業(yè)又沒有能力同時(shí)承擔(dān)，企業(yè)應(yīng)根據(jù)自身的能力，分析這兩類工程的盈利水平，作出正確的投標(biāo)方案。有關(guān)數(shù)據(jù)見下表：表1可供選擇投標(biāo)工程的有關(guān)數(shù)據(jù)統(tǒng)計(jì)工程類型預(yù)期利潤(rùn)/元抹灰量/m2混凝土量/m3砌筑量/m3住宅每項(xiàng)50011工業(yè)車間每項(xiàng)480企業(yè)尚有能力試建立此問題的數(shù)學(xué)模型。目標(biāo)是獲利最高，故得目標(biāo)函數(shù)為根據(jù)企業(yè)工程量能力限制與項(xiàng)目本身特性，有約束：利用WinSQB建立模型求解：綜上，承包商對(duì)2項(xiàng)住宅工程，3項(xiàng)車間工程進(jìn)行投標(biāo)，可獲利最大，目標(biāo)函數(shù)Max各類人員承擔(dān)的工作量、工資及所占比例如下表：變量x1x2x3x4x5x6x7x8x9y1y2y3y4y5承擔(dān)的教學(xué)工作量本科生0研究生本科生0066300所占教師的百分工資 3，0003，000美元3，0008，0002，00030，0004，0002，00030，000———— ————— —7521——————— 2——2—1至少有75%的人具有博士學(xué)位。P2要求各類人員增加工資的總額不得超過176，000美元，其中x1、x2和x9增加的工資數(shù)為其原工資基數(shù)的6%，而其他人員為8%。P3要求能完成學(xué)校的各項(xiàng)教學(xué)工作。即學(xué)校計(jì)劃招收本科生1，820名，研究生100名。要求為本科生每周開課不低于910學(xué)時(shí)。要求為研究生每周開課不低于100學(xué)P4iy，要求各類教學(xué)人員有適當(dāng)比例，如上表。iP要求教師與行政管理職工之比不超過4：1。5P要求教師與助研x1之比不超過5：1。6P7設(shè)所有人員總的年工資基數(shù)為1，850，000美元，要求其盡可能小。試建立其目標(biāo)規(guī)劃的數(shù)學(xué)模型。依題意，建立目標(biāo)規(guī)劃模型：)ΣidΣ+ΣΣΣ8dΣΣΣΣΣdddΣdddΣΣΣΣddΣΣΣΣΣ案例8.電纜工程投資資金優(yōu)化問題有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與15個(gè)控制點(diǎn)相連通。圖中的各線段標(biāo)出了允許挖電纜溝的地點(diǎn)和距離（單位：百米）。若電纜線每米10元，挖電纜溝（深1米，寬米）土方每立方米3元，其它材料和施工費(fèi)用每米5元，則該工程預(yù)算最少需多少元776885289536749465453355889966644227案例9.零件加工安排問題件只在一臺(tái)機(jī)床上加工，要求盡可能多地安排零件加工，試把這個(gè)問題化為求網(wǎng)絡(luò)最大流問題，求出能滿足上述條件的加工方案。XXXXXXy1y2y3y4y5y6t解:增設(shè)起始點(diǎn)s，終點(diǎn)t,將加工過程化成網(wǎng)絡(luò)流程（設(shè)每段弧上最大流量皆為1則盡多安排加工的方案等價(jià)于求網(wǎng)絡(luò)取得最大流時(shí)的路徑?；蚶肳inSQB建立模型求解如下（點(diǎn)1~14分別表示點(diǎn)s，X1~X6，y1~y6，t），案例10.房屋施工網(wǎng)絡(luò)計(jì)劃問題下面是某公司房屋施工工程作業(yè)明細(xì)表，請(qǐng)繪制網(wǎng)絡(luò)圖，并確定關(guān)鍵路線。完成緊前完成緊前工序工序內(nèi)容4l安裝廚房設(shè)備k2m安裝預(yù)制的衛(wèi)生設(shè)備ka破土挖槽，澆墊層—b澆混凝土基a完成12工序工序內(nèi)容c安裝構(gòu)架及屋面b4n完成細(xì)木工活k3d砌磚c6o完成屋頂并罩面油漆d2e安裝排水管b1p安裝天溝及落水管o1f澆地下室地坪e2q安裝防暴雨水管b1g敷設(shè)主管道e3r地板打磨及上光漆n，s2k鋪設(shè)預(yù)制地板j3v鋪便道及綠化u5第二部分：案例設(shè)計(jì)基于0-1整數(shù)規(guī)劃的公務(wù)員招聘指派試、嚴(yán)格考核的辦法，按照德才兼?zhèn)涞臉?biāo)準(zhǔn)擇優(yōu)錄用”。目前,我國(guó)招聘公務(wù)員的程序一般分三步進(jìn)行：公開考試（筆試）、面試考核、擇優(yōu)錄取。如何對(duì)公務(wù)員選撥中的各方面能力進(jìn)行定量化,使人才的錄用更加理性化越來越受關(guān)注。同時(shí)，針對(duì)公務(wù)員選舉的最優(yōu)方案建立的數(shù)學(xué)模型和運(yùn)用的方法對(duì)進(jìn)一步改進(jìn)我國(guó)公務(wù)員招聘的運(yùn)行程序和考核指標(biāo)越發(fā)具有很強(qiáng)的實(shí)用價(jià)值和參考意義。關(guān)鍵詞：公務(wù)員招聘整數(shù)規(guī)劃指派問題一、問題的提出現(xiàn)有某市直屬單位因工作需要，擬向社會(huì)公開招聘8名公務(wù)員，具體的招聘辦法（一）公開考試，根據(jù)考試總分的高低排序按1:2的比例（共16人）選擇進(jìn)入第二階（二）面試考核：面試考核主要考核應(yīng)聘人員的知識(shí)面、對(duì)問題的理解能力、應(yīng)變能力、表達(dá)能力等綜合素質(zhì)。按照一定的標(biāo)準(zhǔn)，面試專家組對(duì)每個(gè)應(yīng)聘人員的各個(gè)方面都給出一個(gè)等級(jí)評(píng)分，從高到低分成A/B/C/D四個(gè)等級(jí)，具體結(jié)果見表1所示。（三）由招聘領(lǐng)導(dǎo)小組綜合專家組的意見、筆初試成績(jī)以及各用人部門需求確定錄用名單,并分配到各用人部門。該單位擬將錄用的8名公務(wù)員安排到所屬的7個(gè)部門，并且要求每個(gè)部門至少安排招聘領(lǐng)導(dǎo)小組在確定錄用名單的過程中，本著公平、公開的原則，同時(shí)考慮錄用人員的合理分配和使用，有利于發(fā)揮個(gè)人的特長(zhǎng)和能力。招聘領(lǐng)導(dǎo)小組將7個(gè)用人單位的基本情況（包括福利待遇、工作條件、勞動(dòng)強(qiáng)度、晉升機(jī)會(huì)和學(xué)習(xí)深造機(jī)會(huì)等）和每一位參加面試人員都可以申報(bào)兩個(gè)自己的工作類別志愿（見表1）?，F(xiàn)在在已知各應(yīng)聘人員面試成績(jī)、專家測(cè)評(píng)和用人單位需求的的情況下,試根據(jù)以下要求探究如何選出適合公務(wù)員需求的人員,指派到合適的部門：（1）如果不考慮應(yīng)聘人員的意愿，擇優(yōu)按需錄用，試幫助招聘領(lǐng)導(dǎo)小組設(shè)計(jì)一種（2）在考慮應(yīng)聘人員意愿和用人部門的希望要求的情況下，請(qǐng)你幫助招聘領(lǐng)導(dǎo)?。?）你的方法對(duì)于一般情況，即N個(gè)應(yīng)聘人員M個(gè)用人單位時(shí)，是否可行表1：招聘公務(wù)員筆試成績(jī)，專家面試評(píng)分及個(gè)人志愿應(yīng)聘人員人員2人員3人員4人員5人員6人員7人員8人員9人員人員人員人員人員人員人員筆試成績(jī)專家組對(duì)應(yīng)聘者特長(zhǎng)的等級(jí)評(píng)分知識(shí)理解能應(yīng)變能表達(dá)能AABABBABBDDABDABABABADBABBCBCBBABADBBACAAABCDACBCCBCBBCBCAAABBC表2:用人部門的基本情況及對(duì)公務(wù)員的期望要求各部門對(duì)公務(wù)員特長(zhǎng)的希望達(dá)各部門對(duì)公務(wù)員特長(zhǎng)的希望達(dá)到的要求工作類別知識(shí)面BACC理解能力ABCB應(yīng)變能力CBAB表達(dá)能力ACAA少少多多中多多多多少多中中少中大中大中中大優(yōu)優(yōu)優(yōu)差中中中優(yōu)中中優(yōu)優(yōu)中優(yōu)部門部門部門部門部門部門部門各用人部門的基本情用人部門二、具體問題分析和建模求解這是一個(gè)人多事少的非標(biāo)準(zhǔn)指派問題，適用0—1整數(shù)規(guī)劃求解。人員與任務(wù)數(shù)目和指派要求明確：在16個(gè)人中選8人，分配于7個(gè)部門，每個(gè)部門至少一個(gè)人，這是本案例的絕“擇優(yōu)按需”錄用，同時(shí)考慮錄用人員的合理分配和使用，有利于發(fā)揮個(gè)人的特長(zhǎng)和能力。優(yōu)先考慮考慮應(yīng)聘者能力與部門需求“擇優(yōu)按需”確定初步分配方案，再結(jié)合應(yīng)聘人員意愿進(jìn)行方案優(yōu)化；用人部門對(duì)公務(wù)員的期望要求和應(yīng)聘人員的意愿不是絕對(duì)約束，但是要盡量滿系數(shù)矩陣應(yīng)該體現(xiàn)“擇優(yōu)按需”原則，表征每個(gè)應(yīng)聘者能給各個(gè)部門到來的效率，的總體綜合得分盡量地高，“按需”指人員合理分配，各部門對(duì)公務(wù)員特長(zhǎng)的期望與受聘人員特長(zhǎng)盡量吻合，所以系數(shù)矩陣是充分合理地結(jié)合應(yīng)聘者的筆試成績(jī)，面試成績(jī)及用人部門要求給每個(gè)應(yīng)聘者打出的綜合評(píng)分。面試環(huán)節(jié)采用等級(jí)評(píng)分，不便于分析，給A，B，C，D四個(gè)等級(jí)分別賦值4、3、2、1，同時(shí)，用人部門的基本情況主要用于應(yīng)聘者參考選擇申報(bào)志愿，在以下求解中可以忽略，重新整理數(shù)據(jù)得新表格：表1：招聘公務(wù)員筆試成績(jī)，專家面試評(píng)分及個(gè)人志愿面bi14434理解能4343應(yīng)變能3413表達(dá)能3223專家組對(duì)應(yīng)聘者特長(zhǎng)的等級(jí)評(píng)分bi應(yīng)聘人員i人員2人員3人員4人員5343人員6314人員7432人員8344人員9334134123432321134432343表2:用人部門對(duì)公務(wù)員的期望要求各部門對(duì)公務(wù)員特長(zhǎng)的希望達(dá)各部門對(duì)公務(wù)員特長(zhǎng)的希望達(dá)到的要求bj知識(shí)理解應(yīng)變表達(dá)工作類別用人部門j部門部門部門部門部門部門部門2、結(jié)合每個(gè)應(yīng)聘者的筆試，面試成績(jī)及各部門對(duì)公務(wù)員的能力期望確定系數(shù)矩陣C：bi，bj三個(gè)矩陣求解矩陣C，用人部門對(duì)應(yīng)聘者的特長(zhǎng)要求在筆試成績(jī)部分無法體現(xiàn)，力的期望分越高代表這項(xiàng)能力在該部門越被看重，所以將bj看成bi矩陣的權(quán)重矩陣，取面試成績(jī)矩陣與用人部門要求矩陣相乘所得矩陣、筆試成績(jī)矩陣分別乘以各自的權(quán)重在相加所得矩陣作為系數(shù)矩陣：T，為根據(jù)實(shí)際情況設(shè)定的權(quán)數(shù)，這應(yīng)聘進(jìn)入各部門的面試得分Cij部部部部部部部部人員123456789表示決策變量，依題意可建立0-1整數(shù)規(guī)劃模型：xΣ7Cx|1<Σ應(yīng)聘應(yīng)聘進(jìn)入各部門的面試得分Cij人員123456789將上表系數(shù)錄入Maximization(AssignmentProblem)模型中得解如下：Solutionfor公務(wù)員招聘分配問題:Maximization(AssignmentProblem)FromToAssignment/UnitProfit/TotalProfit/ReducedCost2Assignment2Assignee3103Assignment3Unused_Supply10004Assignment4Assignee6105Assignment5Unused_Supply10006Assignment6Assignee5107Assignment7Unused_Supply10008Assignment8Assignee81666609Assignment9Assignee4168680Assignment12Assignee110Assignment13Unused_Supply100Assignment14Unused_Supply100Assignment15Unused_Supply100Assignment16Assignee210TotalObjectiveFunctionValue=8部門為虛部門，根據(jù)第8個(gè)應(yīng)聘者的能力特長(zhǎng)，將其安排在部門1工作，即的最部門應(yīng)聘者18，12232495664714、考慮應(yīng)聘者意愿和用人部門的希望要求的情況下進(jìn)行分配。只需在3的模型上增加照顧應(yīng)聘者意愿的約束，優(yōu)化模型即可，選擇或放棄某個(gè)部門對(duì)于應(yīng)聘者而言是個(gè)相互排斥的問題，故可采用0-1整數(shù)規(guī)劃，引入應(yīng)聘者意愿決策變量y對(duì)3設(shè)y16|||1<Σ||Cy代替C組成新系數(shù)矩陣，同上，增設(shè)虛部門8，得系數(shù)矩陣如下表：123456789應(yīng)聘Cy應(yīng)聘部00000部000000部000000部000部000部000000部000000部000000000000000000000000000000000000000利用利用WinSQB求解：Solutionfor公務(wù)員招聘分配問題:Maximization(AssignmentProblem)FromToAssignment|UnitProfit|TotalProfit|ReducedCost2Assignment2Assignee5103Assignment3Unused_Supply10004Assignment4Assignee7106Assignment6Unused_Supply10007Assignment7Unused_Supply10008Assignment8Assignee216868