1、运筹学应用实例分析运筹学应用实例分析(总25页)第一部分 小型案例分析建模与求解案例1. 杂粮销售问题一贸易公司专门经营某种杂粮的批发业务，公司现有库容5011担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000元。估计第一季度杂粮价格如下所示：一月份，进货价元，出货价元；二月份，进货价元，出货价元；三月份，进货价元，出货价元；如买进的杂粮当月到货，需到下月才能卖出，且规定“货到付款”。公司希望本季度末库存为2000担，问应采取什么样的买进与卖出的策略使三个月总的获利最大，每个月考虑先卖后买解：设第i月出货担，进货担，i=1，2，3；可建立数学模型如下：目标函数：约束条件：利用W
2、inSQB求解(x1,x2,x3,x4,x5,x6分别表示x10,x11,x21,x21,x30,x31)：所以最优策略为：1月份卖出1000担，进货5011担；2月份卖出5011担，不进货；3月份不出货，进货2000担。此时，资金余额为=（元），存货为2000担。案例2. 生产计划问题某厂生产四种产品。每种产品要经过A，B两道工序加工。设该厂有两种规格的设备能完成A工序，以 A1 ， A2表示；有三种规格的设备能完成B工序，以B1 ， B2， B3 表示。产品D可在A，B任何一种规格的设备上加工。产品E可在任何规格的A设备上加工，但完成B工序时只能在B1设备上加工。产品F可在A2及B2 ，
3、B3上加工。产品G可在任何一种规格的A设备上加工，但完成B工序时只能在B1 ， B2设备上加工。已知生产单件产品的设备工时，原材料费，及产品单价，各种设备有效台时如下表，要求安排最优的生产计划，使该厂利润最大 设备 设 产品设备有效台时 1 2 3 4 A1 A2 B1 B2 B3 5 7 6 4 7 10 9 8 12 11 10 6 8 10 8 601110000 4000 7000 4000原料费（元/件）单价 （元/件） 解：设Xia(b)j为i产品在a(b)j设备上的加工数量,i=1,2,3,4;j=1,2,3，得变量列表如下： 设备 设 产品设备有效台时Ta(b)j 1 2 3
4、4 A1 A2 B1 B2 B3 X1a1 X1a2 X1b1 X1b2 X1b3 X2a1 X2a2 X2b1X3b2 X3b3 X3a1 X3a2 X3b1 X3b2 X3b3 X4a1 X4a2 X4b1 X4b2 X4b3 601110000 4000 7000 4000原料费Ci（元/件）单价Pi（元/件） 其中，令X3a1，X3b1，X3b2，X3b3，X4b3=0可建立数学模型如下：目标函数: =*（X1a1+X1a2）+*（X2a1+X2a2）+* X3a2+*（ X4a1+X4a2）约束条件：利用WinSQB求解（X1X4，X5X8,X9X12,X13X17,X18X20分别
5、表示各行变量）：综上，最优生产计划如下： 设备 设 产品 1 2 3 4 A1 A2 B1 B2 B3 77 423 500 400 400 873 2 875目标函数 =3495，即最大利润为3495案例3. 报刊征订、推广费用的节省问题解：该问题可以看成是求费用最小的产销平衡运输问题，日 本香港特别行政区韩 国产量中文书刊出口部72015000深圳分公司4147500上海分公司687500销量15000100005000利用WinSQB求解得最优分配方案为：即最优任务分配如下：日 本香港特别行政区韩 国中文书刊出口部125002500深圳分公司7500上海分公司25005000采用此方案费
6、用最小，为 227500（元）。案例4. 供电部门职工交通安排问题我们把通勤费作为优化的目标。ai (i=1，2，.18)表示住地的职工人数，用bj (j=1，2，.8)表示工作地点的定员，cij (i=1，2，.18; j=1，2，.8)表示每个职工从住地到各工作地点的月通勤费（单位：元），有关数据列表如下表，试建立此问题的数学模型并求解。解：根据题意，以员工住地为产地，工作地点为销地，将问题转化为求月总通勤费最小的运输方案利用WinSQB建立模型求解：得分配结果如下：即为最优执勤分配方案如下，最小总月通勤费用为： （元）案例5. 篮球队员选拔问题某校篮球队准备从十名预备队员中选择五名作为正
7、式队员，队员的各种情况如下表：队员号码身高（厘米）月薪（元）技术分位置11852411中锋218630009中锋31922600中锋41903500中锋51822500前锋618418008前锋71882200前锋81861900后卫91902400后卫101923200后卫队员的挑选要满足下面条件：（1）至少补充一名中锋。（2）至多补充2名后卫。（3）1号和3号队员最多只能入选1个。（4）平均身高要达到187厘米。（5）技术分平均要求不低于分。由于经费有限，希望月薪总数越少越好。试建立此问题的数学模型。解：依题意，建立0-1整数规划： 目标函数为： 约束为： 利用WinSQB建立模型求解：综
8、上，应该选拔第 2，6，7，8，10号队员为正式队员，共需支付月薪12 100（元）案例6. 工程项目选择问题某承包企业在同一时期内有八项工程可供选择投标。其中有五项住宅工程，三项工业车间。由于这些工程要求同时施工，而企业又没有能力同时承担，企业应根据自身的能力，分析这两类工程的盈利水平，作出正确的投标方案。有关数据见下表：表1 可供选择投标工程的有关数据统计工程类型预期利润/元抹灰量/m2混凝土量/ m3砌筑量/ m3住宅每项5001125 0002804 200工业车间每项80 0004808801 800企业尚有能力108 0003 68013 800试建立此问题的数学模型。解： 设承包
9、商承包X1项住宅工程，X2项工业车间工程可获利最高，依题意可建立如下整数模型：目标是获利最高，故得目标函数为 根据企业工程量能力限制与项目本身特性，有约束： 利用WinSQB建立模型求解：综上，承包商对2项住宅工程，3项车间工程进行投标，可获利最大，目标函数Max z=340022 元。案例7. 高校教职工聘任问题 （建摸） 各类人员承担的工作量、工资及所占比例如下表：变量承担的教学工作量所占教师的百分比年工资本科生 研究生最大 最小x1x2x3x4x5x6x7x8x9y1y2y3y4y51 06学时/周 012 09 09 06 03 00 3学时/周 6 36 33 30 30 3 7%
10、7 15 5 2 1 1% 21 14 232 2 3，000美元 3，000 8，00013，00015，00017，000 2，00030，000 4，00013，00015，00017，000 2，00030，000由校方确定的各级决策目标为： P1 要求教师有一定的学术水平。即：要求75%的教师是专职的。要求担任本科生教学工作的教师中，至少有40%的人具有博士学位。要求担任研究生教学工作的教师中，至少有75%的人具有博士学位。 P2 要求各类人员增加工资的总额不得超过176，000美元，其中x1、x2和x9增加的工资数为其原工资基数的6%，而其他人员为8%。 P3 要求能完成学校的各项
11、教学工作。即学校计划招收本科生1，820名，研究生100名。要求为本科生每周开课不低于910学时。要求为研究生每周开课不低于100学时。要求本科生教师与学生人数比为1：20，即为本科生上课的教师数不超过1820/20=91人。要求研究生教师与学生人数比为1：10，即为研究生上课的教师数不超过100/10=10人。P4 设教师总数，要求各类教学人员有适当比例，如上表。P5 要求教师与行政管理职工之比不超过4：1。P6 要求教师与助研x1之比不超过5：1。P7 设所有人员总的年工资基数为1，850，000美元，要求其尽可能小。试建立其目标规划的数学模型。解：依题意，建立目标规划模型： 案例8. 电
12、缆工程投资资金优化问题有一项工程，要埋设电缆将中央控制室与15个控制点相连通。图中的各线段标出了允许挖电缆沟的地点和距离（单位：百米）。若电缆线每米10元，挖电缆沟（深1米，宽米）土方每立方米3元，其它材料和施工费用每米5元，则该工程预算最少需多少元解：该问题等价于求网络最小支撑树，利用WinSQB建立模型求解：网络最小支撑树为上图加粗线路，所以按照加粗路线挖电缆沟能使工程预算最小，路线总长62米，故最小预算为：62*1*3+62*（10+5）=（元）案例9. 零件加工安排问题已知有六台机床，六个零件；机床可加工零件；可加工零件；可加工零件；可加工零件；可加工零件；可加工零件；现在要求制定一个
13、加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工，试把这个问题化为求网络最大流问题，求出能满足上述条件的加工方案。解: 增设起始点s，终点t,将加工过程化成网络流程（设每段弧上最大流量皆为1）：则尽多安排加工的方案等价于求网络取得最大流时的路径。利用WinSQB建立模型求解如下（点114分别表示 点s，X1X6，y1y6，t）：可以得到两种结果（如上），综上，最佳加工方案为： X1加工y1；X3加工y3；X4加工y2；X5加工y4；X6加工y5或y6 共5个零件。案例10. 房屋施工网络计划问题下面是某公司房屋施工工程作业明细表，请绘制网络图，并确定关
14、键路线。工序工序内容紧前工序完成时间工序工序内容紧前工序完成时间a破土挖槽，浇垫层4l安装厨房设备k1b浇混凝土基a2m安装预制的卫生设备k2c安装构架及屋面b4n完成细木工活k3d砌砖c6o完成屋顶并罩面油漆d2e安装排水管b1p安装天沟及落水管o1f浇地下室地坪e2q安装防暴雨水管b1g敷设主管道e3r地板打磨及上光漆n ，s2h敷设主干电路c2s油漆l ，m3i安装空调设备c ，f4t完成电器作业s1j安装墙板及装饰板g，h，i10u最后平整p ，q2k铺设预制地板j3v铺便道及绿化u5解：依题意，利用WinSQB建立模型求解：网络图如下：所以关键线路为：A B C H J K M S
15、R第二部分：案例设计基于0-1整数规划的公务员招聘指派问题背景：我国公务员制度已实施多年，1993年10月1日颁布施行的国家公务员暂行条例规定：“国家行政机关录用担任主任科员以下的非领导职务的国家公务员，采用公开考试、严格考核的办法，按照德才兼备的标准择优录用”。目前, 我国招聘公务员的程序一般分三步进行：公开考试（笔试）、面试考核、择优录取。如何对公务员选拨中的各方面能力进行定量化, 使人才的录用更加理性化越来越受关注。同时，针对公务员选举的最优方案建立的数学模型和运用的方法对进一步改进我国公务员招聘的运行程序和考核指标越发具有很强的实用价值和参考意义。关键词：公务员招聘 整数规划 指派问题
16、一、问题的提出现有某市直属单位因工作需要，拟向社会公开招聘8名公务员，具体的招聘办法和程序如下：（一）公开考试，根据考试总分的高低排序按1:2的比例（共16人）选择进入第二阶段的面试考核。（二）面试考核：面试考核主要考核应聘人员的知识面、对问题的理解能力、应变能力、表达能力等综合素质。按照一定的标准，面试专家组对每个应聘人员的各个方面都给出一个等级评分，从高到低分成A/B/C/D四个等级，具体结果见表所示。（三）由招聘领导小组综合专家组的意见、笔初试成绩以及各用人部门需求确定录用名单,并分配到各用人部门。该单位拟将录用的8名公务员安排到所属的7个部门，并且要求每个部门至少安排一名公务员。这7个
17、部门按工作性质可分为四类：(1)行政管理、 (2)技术管理、(3)行政执法、(4)公共事业。见表2所示。招聘领导小组在确定录用名单的过程中，本着公平、公开的原则，同时考虑录用人员的合理分配和使用，有利于发挥个人的特长和能力。招聘领导小组将7个用人单位的基本情况（包括福利待遇、工作条件、劳动强度、晋升机会和学习深造机会等）和四类工作对聘用公务员的具体条件的希望达到的要求都向所有应聘人员公布（见表2）。每一位参加面试人员都可以申报两个自己的工作类别志愿（见表1）。现在在已知各应聘人员面试成绩、专家测评和用人单位需求的的情况下, 试根据以下要求探究如何选出适合公务员需求的人员,指派到合适的部门：（1
18、）如果不考虑应聘人员的意愿，择优按需录用，试帮助招聘领导小组设计一种录用分配方案；（2）在考虑应聘人员意愿和用人部门的希望要求的情况下，请你帮助招聘领导小组设计一种分配方案；（3）你的方法对于一般情况，即N个应聘人员M个用人单位时，是否可行表：招聘公务员笔试成绩，专家面试评分及个人志愿 应聘人员笔试成绩申报类别志愿专家组对应聘者特长的等级评分知识面理解能力应变能力表达能力人员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人
19、员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:用人部门的基本情况及对公务员的期望要求用人部门工作类别各用人部门的基本情况各部门对公务员特长的希望达到的要求福利待遇工作条件劳动强度晋升机会深造机会知识面理解能力应变能力表达能力部门1（1）优优中多少BACA部门2（2）中优大多少ABBC部门3（2）中优中少多部门4（3）优差大多多CCAA部
20、门5（3）优中中中中部门6（4）中中中中多CBBA部门7（4）优中大少多二、具体问题分析和建模求解分析：这是一个人多事少的非标准指派问题，适用01整数规划求解。使用01整数规划求解的条件分析： 人员与任务数目和指派要求明确：1、在16个人中选8人，分配于7个部门，每个部门至少一个人，这是本案例的绝对约束条件；2、“择优按需”录用，同时考虑录用人员的合理分配和使用，有利于发挥个人的特长和能力。优先考虑考虑应聘者能力与部门需求“择优按需”确定初步分配方案，再结合应聘人员意愿进行方案优化；3、用人部门对公务员的期望要求和应聘人员的意愿不是绝对约束，但是要尽量满足（实际上这里没有一个应聘者可以完全满足
21、部门1的能力期许）。 系数矩阵应该体现“择优按需”原则，表征每个应聘者能给各个部门到来的效率，在本案例中没有直接给出，需要首先求解出系数矩阵；显见，“择优”要求受聘者的总体综合得分尽量地高，“按需”指人员合理分配，各部门对公务员特长的期望与受聘人员特长尽量吻合，所以系数矩阵是充分合理地结合应聘者的笔试成绩，面试成绩及用人部门要求给每个应聘者打出的综合评分。解：1、数据整理面试环节采用等级评分，不便于分析，给A，B，C，D四个等级分别赋值4、3、2、1，同时，用人部门的基本情况主要用于应聘者参考选择申报志愿，在以下求解中可以忽略，重新整理数据得新表格：表：招聘公务员笔试成绩，专家面试评分及个人志
22、愿应聘人员i笔试成绩ai申报类别志愿专家组对应聘者特长的等级评分bi知识面bi1理解能力bi2应变能力bi3表达能力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）
23、（4）4323人员16273（4）（1）3432表 2:用人部门对公务员的期望要求用人部门j工作类别各部门对公务员特长的希望达到的要求bj知识面bj1理解能力bj2应变能力bj3表达能力bj4部门1（1）3424部门2（2）4332部门3（2）部门4（3）2244部门5（3）部门6（4）2334部门7（4）2、结合每个应聘者的笔试，面试成绩及各部门对公务员的能力期望确定系数矩阵C：由上表可以得到笔试成绩矩阵ai，面试成绩矩阵bi，用人部门要求矩阵bj，设Cij为矩阵第i行第j列元素，代表第i个公务员对应于第j个部门的综合得分，结合ai，bi，bj三个矩阵求解矩阵C，用人部门对应聘者的特长要求在
24、笔试成绩部分无法体现，的值应该包括考虑用人部门要求影响的面试成绩与笔试成绩两部分。j部门k项能力的期望分越高代表这项能力在该部门越被看重，所以将bj看成bi矩阵的权重矩阵，取面试成绩矩阵与用人部门要求矩阵相乘所得矩阵、笔试成绩矩阵分别乘以各自的权重在相加所得矩阵作为系数矩阵：即令，有;k=1、2、3、4，、0为根据实际情况设定的权数，这里暂取,可以得到系数矩阵如下：应聘进入各部门的面试得分Cij人员部门1部门2部门3部门4部门5部门6部门7人员175727269697070人员2人员3人员4人员5人员6人员768656562626363人员869686866666666人员969676768686767人员1059575760605959人员11人员12人员13人员14人员15人员163、用表示决策变量，依题意可建立0-1整数规划模型： 问题就转化为求下面的优化模型：利用WinSQB求解：增设虚部门8，取,得：应聘进入各部门的面试得分Cij人员部门1部门2部门3部门4部门5部门6部门7部门8人员17572726969707069人员2
