运筹学应用实例分析

运筹学课程设计实践报告管理科学与工程类第一部分小型案例分析建模与求解.............................错误!未定义书签。案例1.杂粮销售问题.....................................错误!未定义书签。案例2.生产计划问题.....................................错误!未定义书签。案例3.报刊征订、推广费用的节省问题....................错误!未定义书签。案例4.供电部门职工交通安排问题.........................错误!未定义书签。案例5.篮球队员选拔问题.................................错误!未定义书签。案例6.工程项目选择问题................................错误!未定义书签。案例8.电缆工程投资资金优化问题.........................错误!未定义书签。案例9.零件加工安排问题.................................错误!未定义书签。案例10.房屋施工网络计划问题............................错误!未定义书签。第二部分：案例设计..........................................错误!未定义书签。一、问题的提出...........................................错误!未定义书签。二、具体问题分析和建模求解...............................错误!未定义书签。第一部分小型案例分析建模与求解案例1.杂粮销售问题一月份，进货价元，出货价元；二月份，进货价元，出货价元；三月份，进货价元，出货价元；如买进的杂粮当月到货，需到下月才能卖出，且规定“货到付款公司希望本季度末库存为2000担，问应采取什么样的买进与卖出的策略使三个月总的获利最大，每个月考虑先卖后买利用WinSQB求解(x1,x2,x3,x4,x5,x6分别表示x10,x11,x21,x21,x30,x31)：案例2.生产计划问题某厂生产四种产品。每种产品要经过A，B两道工序加工。设该厂有两种规格的设备能完成A工序，以A1，A2表示；有三种规格的设备能完成B工序，以B1，B2，B3表示。产品D可在A，B任何一种规格的设备上加工。产品E可在任何规格的A设产品G可在任何一种规格的A设备上加工，但完成B工序时只能在B1，B2设备上加工。已知生产单件产品的设备工时，原材料费，及产品单价，各种设备有效台时如下表，要求安排最优的生产计划，使该厂利润最大产品产品设备有效台时21240003原料费（元/件）298564ABBB设设A1设Xia(b)j为i产品在a(b)j设备上的加工数量,i=1,2,3,4;j=1,2,3，得变量列表设产品设备有效台时Ta(b)AX1a1X2a1X3a1X4a160111AX1a2X2a2X3a2X4a2100002X2b11X3b22X3b33原料费Ci（元/件单价Pi（元/件）X1b1X1b2X1b3X3b1X3b2X3b3X4b1X4b2X4b340004000BBB其中，令X3a1，X3b1，X3b2，X3b3，X4b3=0目标函数:ΣΣ=*（X1a1+X1a2）+*（X2a1+X2a2）+*X3a2+*（X4a1+X4a2）ΣXΣXΣX利用WinSQB求解（X1~X4，X5~X8,X9~X12,X13~X17,X18~X20分别表示各行变量综上，最优生产计划如下：设设设A1A2B1B2B3产品3400422423400目标函数Maxz=3495，即最大利润为3495案例3.报刊征订、推广费用的节省问题该问题可以看成是求费用最小的产销平衡运输问题，中文书刊出口部720深圳分公司4147500利用WinSQB求解中文书刊出口部125002500深圳分公司7500上海分公司25005000案例4.供电部门职工交通安排问题我们把通勤费作为优化的目标。ai(i=1，2，......18)表示住地的职工人数，用表示每个职工从住地到各工作地点的月通勤费（单位：元），有关数据列表如下表，试建立此问题的数学模型并求解。工作地点工作地点1309200975000005800000054000006000006ai39296711815642441C住地根据题意，以员工住地为产地，工作地点为销地，将问题转化为求月总通勤费最小利用WinSQB建立模型求解：：（CC1住地23456781335192581961567778119114481155664422442241199565某校篮球队准备从十名预备队员中选择五名作为正式队员，队员的各种情况如下队员号码队员号码技术分位置1241123000932600435005250068722008后卫92400后卫3200后卫（1）至少补充一名中锋。（5）技术分平均要求不低于分。由于经费有限，希望月薪总数越少越好。试建立此问题的数学模型。Xi={1ΣiΣ利用WinSQB建立模型求解：综上，应该选拔第2，6，7，8，10号队员为正式队员，共需支付月薪12100（元）案例6.工程项目选择问题某承包企业在同一时期内有八项工程可供选择投标。其中有五项住宅工程，三项工业车间。由于这些工程要求同时施工，而企业又没有能力同时承担，企业应根据自身的能力，分析这两类工程的盈利水平，作出正确的投标方案。有关数据见下表：表1可供选择投标工程的有关数据统计工程类型预期利润/元抹灰量/m2混凝土量/m3砌筑量/m3住宅每项50011工业车间每项480企业尚有能力试建立此问题的数学模型。目标是获利最高，故得目标函数为根据企业工程量能力限制与项目本身特性，有约束：利用WinSQB建立模型求解：综上，承包商对2项住宅工程，3项车间工程进行投标，可获利最大，目标函数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增加的工资数为其原工资基数的6%，而其他人员为8%。P3要求能完成学校的各项教学工作。即学校计划招收本科生1，820名，研究生100名。要求为本科生每周开课不低于910学时。要求为研究生每周开课不低于100学P4iy，要求各类教学人员有适当比例，如上表。iP要求教师与行政管理职工之比不超过4：1。5P要求教师与助研x1之比不超过5：1。6P7设所有人员总的年工资基数为1，850，000美元，要求其尽可能小。试建立其目标规划的数学模型。依题意，建立目标规划模型：)ΣidΣ+ΣΣΣ8dΣΣΣΣΣdddΣdddΣΣΣΣddΣΣΣΣΣ案例8.电缆工程投资资金优化问题有一项工程，要埋设电缆将中央控制室与15个控制点相连通。图中的各线段标出了允许挖电缆沟的地点和距离（单位：百米）。若电缆线每米10元，挖电缆沟（深1米，宽米）土方每立方米3元，其它材料和施工费用每米5元，则该工程预算最少需多少元776885289536749465453355889966644227案例9.零件加工安排问题件只在一台机床上加工，要求尽可能多地安排零件加工，试把这个问题化为求网络最大流问题，求出能满足上述条件的加工方案。XXXXXXy1y2y3y4y5y6t解:增设起始点s，终点t,将加工过程化成网络流程（设每段弧上最大流量皆为1则尽多安排加工的方案等价于求网络取得最大流时的路径。或利用WinSQB建立模型求解如下（点1~14分别表示点s，X1~X6，y1~y6，t），案例10.房屋施工网络计划问题下面是某公司房屋施工工程作业明细表，请绘制网络图，并确定关键路线。完成紧前完成紧前工序工序内容4l安装厨房设备k2m安装预制的卫生设备ka破土挖槽，浇垫层—b浇混凝土基a完成12工序工序内容c安装构架及屋面b4n完成细木工活k3d砌砖c6o完成屋顶并罩面油漆d2e安装排水管b1p安装天沟及落水管o1f浇地下室地坪e2q安装防暴雨水管b1g敷设主管道e3r地板打磨及上光漆n，s2k铺设预制地板j3v铺便道及绿化u5第二部分：案例设计基于0-1整数规划的公务员招聘指派试、严格考核的办法，按照德才兼备的标准择优录用”。目前,我国招聘公务员的程序一般分三步进行：公开考试（笔试）、面试考核、择优录取。如何对公务员选拨中的各方面能力进行定量化,使人才的录用更加理性化越来越受关注。同时，针对公务员选举的最优方案建立的数学模型和运用的方法对进一步改进我国公务员招聘的运行程序和考核指标越发具有很强的实用价值和参考意义。关键词：公务员招聘整数规划指派问题一、问题的提出现有某市直属单位因工作需要，拟向社会公开招聘8名公务员，具体的招聘办法（一）公开考试，根据考试总分的高低排序按1:2的比例（共16人）选择进入第二阶（二）面试考核：面试考核主要考核应聘人员的知识面、对问题的理解能力、应变能力、表达能力等综合素质。按照一定的标准，面试专家组对每个应聘人员的各个方面都给出一个等级评分，从高到低分成A/B/C/D四个等级，具体结果见表1所示。（三）由招聘领导小组综合专家组的意见、笔初试成绩以及各用人部门需求确定录用名单,并分配到各用人部门。该单位拟将录用的8名公务员安排到所属的7个部门，并且要求每个部门至少安排招聘领导小组在确定录用名单的过程中，本着公平、公开的原则，同时考虑录用人员的合理分配和使用，有利于发挥个人的特长和能力。招聘领导小组将7个用人单位的基本情况（包括福利待遇、工作条件、劳动强度、晋升机会和学习深造机会等）和每一位参加面试人员都可以申报两个自己的工作类别志愿（见表1）。现在在已知各应聘人员面试成绩、专家测评和用人单位需求的的情况下,试根据以下要求探究如何选出适合公务员需求的人员,指派到合适的部门：（1）如果不考虑应聘人员的意愿，择优按需录用，试帮助招聘领导小组设计一种（2）在考虑应聘人员意愿和用人部门的希望要求的情况下，请你帮助招聘领导小（3）你的方法对于一般情况，即N个应聘人员M个用人单位时，是否可行表1：招聘公务员笔试成绩，专家面试评分及个人志愿应聘人员人员2人员3人员4人员5人员6人员7人员8人员9人员人员人员人员人员人员人员笔试成绩专家组对应聘者特长的等级评分知识理解能应变能表达能AABABBABBDDABDABABABADBABBCBCBBABADBBACAAABCDACBCCBCBBCBCAAABBC表2:用人部门的基本情况及对公务员的期望要求各部门对公务员特长的希望达各部门对公务员特长的希望达到的要求工作类别知识面BACC理解能力ABCB应变能力CBAB表达能力ACAA少少多多中多多多多少多中中少中大中大中中大优优优差中中中优中中优优中优部门部门部门部门部门部门部门各用人部门的基本情用人部门二、具体问题分析和建模求解这是一个人多事少的非标准指派问题，适用0—1整数规划求解。人员与任务数目和指派要求明确：在16个人中选8人，分配于7个部门，每个部门至少一个人，这是本案例的绝“择优按需”录用，同时考虑录用人员的合理分配和使用，有利于发挥个人的特长和能力。优先考虑考虑应聘者能力与部门需求“择优按需”确定初步分配方案，再结合应聘人员意愿进行方案优化；用人部门对公务员的期望要求和应聘人员的意愿不是绝对约束，但是要尽量满系数矩阵应该体现“择优按需”原则，表征每个应聘者能给各个部门到来的效率，的总体综合得分尽量地高，“按需”指人员合理分配，各部门对公务员特长的期望与受聘人员特长尽量吻合，所以系数矩阵是充分合理地结合应聘者的笔试成绩，面试成绩及用人部门要求给每个应聘者打出的综合评分。面试环节采用等级评分，不便于分析，给A，B，C，D四个等级分别赋值4、3、2、1，同时，用人部门的基本情况主要用于应聘者参考选择申报志愿，在以下求解中可以忽略，重新整理数据得新表格：表1：招聘公务员笔试成绩，专家面试评分及个人志愿面bi14434理解能4343应变能3413表达能3223专家组对应聘者特长的等级评分bi应聘人员i人员2人员3人员4人员5343人员6314人员7432人员8344人员9334134123432321134432343表2:用人部门对公务员的期望要求各部门对公务员特长的希望达各部门对公务员特长的希望达到的要求bj知识理解应变表达工作类别用人部门j部门部门部门部门部门部门部门2、结合每个应聘者的笔试，面试成绩及各部门对公务员的能力期望确定系数矩阵C：bi，bj三个矩阵求解矩阵C，用人部门对应聘者的特长要求在笔试成绩部分无法体现，力的期望分越高代表这项能力在该部门越被看重，所以将bj看成bi矩阵的权重矩阵，取面试成绩矩阵与用人部门要求矩阵相乘所得矩阵、笔试成绩矩阵分别乘以各自的权重在相加所得矩阵作为系数矩阵：T，为根据实际情况设定的权数，这应聘进入各部门的面试得分Cij部部部部部部部部人员123456789表示决策变量，依题意可建立0-1整数规划模型：xΣ7Cx|1<Σ应聘应聘进入各部门的面试得分Cij人员123456789将上表系数录入Maximization(AssignmentProblem)模型中得解如下：Solutionfor公务员招聘分配问题:Maximization(AssignmentProblem)FromToAssignment/UnitProfit/TotalProfit/ReducedCost2Assignment2Assignee3103Assignment3Unused_Supply10004Assignment4Assignee6105Assignment5Unused_Supply10006Assignment6Assignee5107Assignment7Unused_Supply10008Assignment8Assignee81666609Assignment9Assignee4168680Assignment12Assignee110Assignment13Unused_Supply100Assignment14Unused_Supply100Assignment15Unused_Supply100Assignment16Assignee210TotalObjectiveFunctionValue=8部门为虚部门，根据第8个应聘者的能力特长，将其安排在部门1工作，即的最部门应聘者18，12232495664714、考虑应聘者意愿和用人部门的希望要求的情况下进行分配。只需在3的模型上增加照顾应聘者意愿的约束，优化模型即可，选择或放弃某个部门对于应聘者而言是个相互排斥的问题，故可采用0-1整数规划，引入应聘者意愿决策变量y对3设y16|||1<Σ||Cy代替C组成新系数矩阵，同上，增设虚部门8，得系数矩阵如下表：123456789应聘Cy应聘部00000部000000部000000部000部000部000000部000000部000000000000000000000000000000000000000利用利用WinSQB求解：Solutionfor公务员招聘分配问题:Maximization(AssignmentProblem)FromToAssignment|UnitProfit|TotalProfit|ReducedCost2Assignment2Assignee5103Assignment3Unused_Supply10004Assignment4Assignee7106Assignment6Unused_Supply10007Assignment7Unused_Supply10008Assignment8Assignee216868