運籌學應用實例分析

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