运筹学应用实例分析可编辑范本.docx
《运筹学应用实例分析可编辑范本.docx》由会员分享，可在线阅读，更多相关《运筹学应用实例分析可编辑范本.docx（41页珍藏版）》请在冰点文库上搜索。
运筹学应用实例分析可编辑范本
第一部分小型案例分析建模与求解2
案例2。
生产计划问题3
案例3。
报刊征订、推广费用的节省问题6
案例4． 供电部门职工交通安排问题7
案例６.工程项目选择问题10
案例7。
高校教职工聘任问题（建摸）1２
案例8。
电缆工程投资资金优化问题14
案例9。
零件加工安排问题１5
案例10.房屋施工网络计划问题１6
第二部分:
案例设计18
问题背景:
１8
一、问题的提出18
二、具体问题分析和建模求解19
三、模型的建立对于N个应聘人员Ｍ个用人单位的指派是可行的。
24
第一部分 小型案例分析建模与求解
案例1。
杂粮销售问题
一贸易公司专门经营某种杂粮的批发业务，公司现有库容５０1１担的仓库。
一月一日,公司拥有库存100０担杂粮,并有资金20000元。
估计第一季度杂粮价格如下所示：
一月份，进货价2.85元,出货价3.１０元；二月份,进货价3．0５元，出货价3。
25元;三月份,进货价2。
90元,出货价2.95元；如买进的杂粮当月到货,需到下月才能卖出，且规定“货到付款”。
公司希望本季度末库存为20０0担,问应采取什么样的买进与卖出的策略使三个月总的获利最大,每个月考虑先卖后买?
解：
设第i月出货
担,进货
担,i=1,2，3；可建立数学模型如下:
目标函数:
约束条件：
利用WinＳQB求解（x1，x２,x３，x4，x5,x6分别表示x1０，x11，x21，ｘ21,ｘ3０，x3１）:
所以最优策略为:
１月份卖出1０0０担，进货501１担;2月份卖出501１担,不进货；3月份不出货，进货20０0担.此时,资金余额为20０00—6９5.6０=１930４。
40（元）,存货为２０00担。
案例２。
生产计划问题
某厂生产四种产品．每种产品要经过Ａ,B两道工序加工.设该厂有两种规格的设备能完成A工序，以 A1 ， A2表示;有三种规格的设备能完成B工序，以B1, B２，Ｂ3 表示．产品D可在Ａ,B任何一种规格的设备上加工。
产品E可在任何规格的A设备上加工，但完成B工序时只能在B１设备上加工。
产品F可在Ａ2及B2，Ｂ3上加工。
产品G可在任何一种规格的Ａ设备上加工,但完成B工序时只能在B1，B2设备上加工。
已知生产单件产品的设备工时，原材料费,及产品单价，各种设备有效台时如下表,要求安排最优的生产计划，使该厂利润最大？
设备 设
产品
设备有效台时
1
2
3
4
A１
Ａ2
Ｂ１
B2
B3
5
7
6
4
７
1０
9
8
12
11
1０
6
8
１0
8
6011
10000
4000
70０0
40０0
原料费（元／件）
单价（元/件）
０。
25
1。
25
0。
35
２。
00
０.50
２。
80
0.４
2。
4
解:
设Ｘｉａ（b）ｊ为i产品在a（b）j设备上的加工数量，i=1,2,３，4;j=1，２，３，得变量列表如下:
设备 设
产品
设备有效台时Ta（b）j
1
2
3
4
A1
A2
B1
Ｂ2
B3
X1a１
X1a２
X１b1
X1ｂ2
Ｘ1ｂ3
Ｘ2ａ1
X2a２
X2b1
X３b2
X3b３
X３ａ１
Ｘ3a2
X3b１
X3b2
Ｘ3b3
Ｘ4ａ1
X4a2
Ｘ４b1
X４b2
Ｘ４b3
6０1１
１0０0０
4000
７0００
400０
原料费Ci（元/件）
单价Ｐｉ（元/件）
0.25
1。
25
０．３5
2.00
0。
50
２.80
0．4
2．4
其中，令X3a1，X3b１，Ｘ3b２,X３b3，Ｘ４ｂ3＝0
可建立数学模型如下：
目标函数:
=1.０0*（Ｘ1ａ1+Ｘ１ａ2）+1。
6５＊（X2a１＋X2ａ2）+２。
３０*Ｘ3a2+2。
0０*（X4a１+Ｘ4a2）
约束条件:
利用ＷinSQＢ求解（X１～X4,X5～X8，X9～X12，X13~X１７,Ｘ１８~X20分别表示各行变量）:
综上，最优生产计划如下:
设备设
产品
１
2
3
4
Ａ1
A2
B１
B2
B3
７7
423
５00
４0０
4０0
8７３
2
８75
目标函数
=3４95,即最大利润为3495
案例3. 报刊征订、推广费用的节省问题
解:
该问题可以看成是求费用最小的产销平衡运输问题，
日本
香港特别行政区
韩国
产量
中文书刊出口部
１0。
２0
７
2０
15000
深圳分公司
12．50
４
１4
７500
上海分公司
6
8
７．5
７500
销量
15000
１000０
5０00
利用WinＳＱB求解
得最优分配方案为:
即最优任务分配如下：
日本
香港特别行政区
韩国
中文书刊出口部
12500
25０0
深圳分公司
7５０0
上海分公司
2５00
50０0
采用此方案费用最小，为22７500（元）.
案例4．供电部门职工交通安排问题
我们把通勤费作为优化的目标．ai （ｉ=1,２,...。
．.18）表示住地的职工人数,用bj（ｊ=1,2,。
．.。
。
．.8）表示工作地点的定员，cij （i=1，2,。
．。
。
.18；j＝１,2,。
.。
...8）表示每个职工从住地到各工作地点的月通勤费（单位：
元），有关数据列表如下表，试建立此问题的数学模型并求解。
解：
根据题意,以员工住地为产地,工作地点为销地,将问题转化为求月总通勤费最小的运输方案
利用WinＳQＢ建立模型求解：
得分配结果如下:
即为最优执勤分配方案如下，最小总月通勤费用为：
３４3．2０（元）
案例5.篮球队员选拔问题
某校篮球队准备从十名预备队员中选择五名作为正式队员,队员的各种情况如下表:
队员号码
身高（厘米）
月薪（元）
技术分
位置
１
1８５
2411
8。
2
中锋
2
186
３000
9
中锋
3
1９2
２60０
８.4
中锋
4
190
35０0
9．５
中锋
5
182
２50０
８。
3
前锋
6
1８4
１800
8
前锋
７
１８8
2200
８。
1
前锋
8
１86
１900
7。
8
后卫
9
19０
2400
8。
2
后卫
10
19２
３２００
9。
2
后卫
队员的挑选要满足下面条件:
（1）至少补充一名中锋。
（2）至多补充2名后卫。
（3）1号和3号队员最多只能入选1个.
（４）平均身高要达到187厘米。
（5）技术分平均要求不低于8．４分。
由于经费有限，希望月薪总数越少越好。
试建立此问题的数学模型。
解:
依题意,建立0-1整数规划:
目标函数为:
约束为：
利用WinSQB建立模型求解:
综上，应该选拔第 2，6，7,8,１0号队员为正式队员，共需支付月薪12 １00（元）
案例6。
工程项目选择问题
某承包企业在同一时期内有八项工程可供选择投标。
其中有五项住宅工程,三项工业车间。
由于这些工程要求同时施工，而企业又没有能力同时承担，企业应根据自身的能力，分析这两类工程的盈利水平,作出正确的投标方案。
有关数据见下表：
表1可供选择投标工程的有关数据统计
工程类型
预期利润/元
抹灰量/ｍ2
混凝土量/ｍ3
砌筑量/ｍ3
住宅每项
500１1
25 0０0
28０
4 2０0
工业车间每项
80０00
48０
880
1８0０
企业尚有能力
10８000
３680
13 8００
试建立此问题的数学模型。
解:
设承包商承包X1项住宅工程,X２项工业车间工程可获利最高,依题意可建立如下整数模型：
目标是获利最高，故得目标函数为
根据企业工程量能力限制与项目本身特性，有约束：
利用WinSQB建立模型求解：
综上，承包商对2项住宅工程,3项车间工程进行投标，可获利最大,目标函数Max z=3400２2元．
案例7.高校教职工聘任问题（建摸）
各类人员承担的工作量、工资及所占比例如下表:
变量
承担的教学工作量
所占教师的百分比
年工资
本科生研究生
最大最小
x1
x2
x3
x4
ｘ5
x6
ｘ７
x8
x9
y1
y2
y3
y４
y5
10
6学时/周 ０
1２0
9 0
9 ０
6 0
3 0
0 3学时／周
－—
6 ３
6 3
3 ３
0 3
0 3
——
7％ —
7 －
1５—
５-
2—
1 —
- 1％
—-
- ２1
－14
—2３
2 -
— ２
３,000美元
３,0００
8,00０
13，000
15，0００
17,000
2,000
30，0００
4,０00
13，000
1５,０00
1７，000
2，０0０
30，000
由校方确定的各级决策目标为:
Ｐ1要求教师有一定的学术水平。
即:
要求75％的教师是专职的。
要求担任本科生教学工作的教师中，至少有4０％的人具有博士学位。
要求担任研究生教学工作的教师中，至少有75%的人具有博士学位.
Ｐ２要求各类人员增加工资的总额不得超过1７6,000美元,其中x1、x2和ｘ9增加的工资数为其原工资基数的6％，而其他人员为8%。
P3要求能完成学校的各项教学工作．即学校计划招收本科生１，820名,研究生１00名．要求为本科生每周开课不低于910学时。
要求为研究生每周开课不低于100学时。
要求本科生教师与学生人数比为1：
20,即为本科生上课的教师数不超过1820/20=９1人。
要求研究生教师与学生人数比为1：
１0,即为研究生上课的教师数不超过100／10=1０人。
P４设教师总数
要求各类教学人员有适当比例，如上表。
Ｐ5要求教师与行政管理职工之比不超过４：
1。
P6要求教师与助研x1之比不超过５：
1。
P7设所有人员总的年工资基数为1,850,000美元,要求其尽可能小。
试建立其目标规划的数学模型。
解：
依题意，建立目标规划模型：
案例8.电缆工程投资资金优化问题
有一项工程，要埋设电缆将中央控制室与15个控制点相连通.图中的各线段标出了允许挖电缆沟的地点和距离（单位：
百米）。
若电缆线每米１0元,挖电缆沟（深1米，宽0。
6米）土方每立方米3元,其它材料和施工费用每米5元,则该工程预算最少需多少元?
解：
该问题等价于求网络最小支撑树,利用ＷinSＱB建立模型求解：
网络最小支撑树为上图加粗线路，所以按照加粗路线挖电缆沟能使工程预算最小，路线总长62米，
故最小预算为：
62*1＊0．6*３+6２*（10＋5）=１041。
6（元）
案例９.零件加工安排问题
已知有六台机床
，六个零件
;机床
可加工零件
;
可加工零件
；
可加工零件
；
可加工零件
;
可加工零件
;
可加工零件
；现在要求制定一个加工方案,使一台机床只加工一个零件，一个零件只在一台机床上加工,要求尽可能多地安排零件加工,试把这个问题化为求网络最大流问题,求出能满足上述条件的加工方案。
解：
增设起始点ｓ，终点t,将加工过程化成网络流程（设每段弧上最大流量皆为1）：
则尽多安排加工的方案等价于求网络取得最大流时的路径.
利用ＷinSQB建立模型求解如下（点1~14分别表示点s,Ｘ１～Ｘ６，y１~ｙ6，t）:
可以得到两种结果（如上）,
综上，最佳加工方案为:
X１加工ｙ1;X3加工y3；X４加工ｙ２；X5加工y4;X6加工y5或ｙ6共5个零件.
案例10.房屋施工网络计划问题
下面是某公司房屋施工工程作业明细表,请绘制网络图,并确定关键路线。
工序
工序内容
紧前
工序
完成
时间
工序
工序内容
紧前
工序
完成
时间
a
破土挖槽,浇垫层
－
4
l
安装厨房设备
k
1
b
浇混凝土基
a
２
m
安装预制的卫生设备
k
２
c
安装构架及屋面
b
4
ｎ
完成细木工活
k
3
d
砌砖
c
6
o
完成屋顶并罩面油漆
d
2
e
安装排水管
b
１
ｐ
安装天沟及落水管
ｏ
1
f
浇地下室地坪
ｅ
2
ｑ
安装防暴雨水管
b
1
g
敷设主管道
e
3
r
地板打磨及上光漆
n,ｓ
2
h
敷设主干电路
c
2
ｓ
油漆
l,ｍ
3
i
安装空调设备
c,f
4
t
完成电器作业
s
1
ｊ
安装墙板及装饰板
g,h,i
10
ｕ
最后平整
p ,ｑ
2
k
铺设预制地板
ｊ
3
ｖ
铺便道及绿化
u
5
解：
依题意,利用ＷinSQB建立模型求解：
网络图如下：
所以关键线路为:
A Ｂ Ｃ Ｈ J K Ｍ ＳＲ
第二部分：
案例设计
基于０—1整数规划的公务员招聘指派
问题背景：
我国公务员制度已实施多年，1９93年10月1日颁布施行的《国家公务员暂行条例》规定:
“国家行政机关录用担任主任科员以下的非领导职务的国家公务员，采用公开考试、严格考核的办法,按照德才兼备的标准择优录用"。
目前，我国招聘公务员的程序一般分三步进行:
公开考试（笔试）、面试考核、择优录取。
如何对公务员选拨中的各方面能力进行定量化,使人才的录用更加理性化越来越受关注．同时，针对公务员选举的最优方案建立的数学模型和运用的方法对进一步改进我国公务员招聘的运行程序和考核指标越发具有很强的实用价值和参考意义。
关键词:
公务员招聘 整数规划指派问题
一、问题的提出
现有某市直属单位因工作需要,拟向社会公开招聘8名公务员,具体的招聘办法和程序如下:
（一）公开考试,根据考试总分的高低排序按1:
2的比例（共1６人）选择进入第二阶段的面试考核。
（二）面试考核：
面试考核主要考核应聘人员的知识面、对问题的理解能力、应变能力、表达能力等综合素质.按照一定的标准，面试专家组对每个应聘人员的各个方面都给出一个等级评分,从高到低分成A/Ｂ/C／D四个等级,具体结果见表１所示。
（三）由招聘领导小组综合专家组的意见、笔初试成绩以及各用人部门需求确定录用名单,并分配到各用人部门。
该单位拟将录用的8名公务员安排到所属的7个部门,并且要求每个部门至少安排一名公务员。
这７个部门按工作性质可分为四类：
（１）行政管理、（２）技术管理、（3）行政执法、（4）公共事业。
见表2所示。
招聘领导小组在确定录用名单的过程中,本着公平、公开的原则,同时考虑录用人员的合理分配和使用，有利于发挥个人的特长和能力。
招聘领导小组将７个用人单位的基本情况（包括福利待遇、工作条件、劳动强度、晋升机会和学习深造机会等）和四类工作对聘用公务员的具体条件的希望达到的要求都向所有应聘人员公布（见表２）.每一位参加面试人员都可以申报两个自己的工作类别志愿（见表１）.
现在在已知各应聘人员面试成绩、专家测评和用人单位需求的的情况下，试根据以下要求探究如何选出适合公务员需求的人员，指派到合适的部门:
（1）如果不考虑应聘人员的意愿,择优按需录用，试帮助招聘领导小组设计一种录用分配方案；
（2）在考虑应聘人员意愿和用人部门的希望要求的情况下,请你帮助招聘领导小组设计一种分配方案;
（３）你的方法对于一般情况,即Ｎ个应聘人员M个用人单位时，是否可行?
表１：
招聘公务员笔试成绩，专家面试评分及个人志愿
应聘
人员
笔试
成绩
申报类别志愿
专家组对应聘者特长的等级评分
知识面
理解能力
应变能力
表达能力
人员1
290
（２）
（３）
Ａ
A
B
Ｂ
人员2
2８8
（３）
（１）
A
B
A
Ｃ
人员3
28８
（1）
（2）
B
A
D
Ｃ
人员4
285
（4）
（3）
A
B
Ｂ
B
人员５
２83
（３）
（２）
Ｂ
A
Ｂ
C
人员6
2８3
（3）
（４）
B
D
Ａ
Ｂ
人员7
280
（４）
（1）
A
Ｂ
C
Ｂ
人员8
280
（２）
（4）
B
A
A
C
人员9
２80
（1）
（3）
B
Ｂ
A
B
人员１0
280
（3）
（1）
D
B
Ａ
Ｃ
人员1１
27８
（4）
（１）
Ｄ
C
B
A
人员1２
2７7
（3）
（4）
A
B
C
A
人员13
2７5
（２）
（1）
B
C
D
A
人员１4
２75
（1）
（３）
D
B
Ａ
B
人员15
2７４
（1）
（4）
Ａ
B
C
B
人员１６
273
（4）
（1）
B
A
B
C
表2:
用人部门的基本情况及对公务员的期望要求
用人
部门
工作
类别
各用人部门的基本情况
各部门对公务员特长的希望达到的要求
福利待遇
工作条件
劳动强度
晋升机会
深造机会
知识面
理解能力
应变能力
表达能力
部门１
（1）
优
优
中
多
少
B
Ａ
Ｃ
A
部门2
（2）
中
优
大
多
少
A
B
B
C
部门3
（2）
中
优
中
少
多
部门4
（３）
优
差
大
多
多
C
C
Ａ
Ａ
部门5
（3）
优
中
中
中
中
部门6
（4）
中
中
中
中
多
Ｃ
Ｂ
Ｂ
A
部门7
（４）
优
中
大
少
多
二、具体问题分析和建模求解
分析:
这是一个人多事少的非标准指派问题，适用0—1整数规划求解。
使用０—１整数规划求解的条件分析：
●人员与任务数目和指派要求明确：
1、在16个人中选8人,分配于7个部门,每个部门至少一个人，这是本案例的绝对约束条件;
2、“择优按需”录用,同时考虑录用人员的合理分配和使用,有利于发挥个人的特长和能力.优先考虑考虑应聘者能力与部门需求“择优按需”确定初步分配方案，再结合应聘人员意愿进行方案优化;
3、用人部门对公务员的期望要求和应聘人员的意愿不是绝对约束,但是要尽量满足（实际上这里没有一个应聘者可以完全满足部门1的能力期许）。
●系数矩阵应该体现“择优按需"原则,表征每个应聘者能给各个部门到来的效率,在本案例中没有直接给出,需要首先求解出系数矩阵;显见,“择优”要求受聘者的总体综合得分尽量地高,“按需"指人员合理分配，各部门对公务员特长的期望与受聘人员特长尽量吻合，所以系数矩阵是充分合理地结合应聘者的笔试成绩，面试成绩及用人部门要求给每个应聘者打出的综合评分。
解:
1、数据整理
面试环节采用等级评分,不便于分析,给A，Ｂ,Ｃ,D四个等级分别赋值４、３、２、１，同时,用人部门的基本情况主要用于应聘者参考选择申报志愿,在以下求解中可以忽略,重新整理数据得新表格：
表１:
招聘公务员笔试成绩,专家面试评分及个人志愿
应聘
人员i
笔试
成绩
aｉ
申报类别志愿
专家组对应聘者特长的等级评分bi
知识面bi1
理解能力bｉ2
应变能力bi3
表达能力bi４
人员1
29０
（2）
（3）
4
4
3
３
人员2
２88
（３）
（1）
4
３
4
2
人员3
28８
（1）
（2）
３
4
１
2
人员4
2８５
（4）
（3）
4
３
3
3
人员５
283
（3）
（２）
3
4
３
2
人员6
28３
（3）
（４）
3
1
4
3
人员７
280
（4）
（１）
4
3
2
3
人员８
28０
（2）
（４）
3
4
4
2
人员9
28０
（1）
（3）
3
3
4
３
人员１０
28０
（3）
（1）
1
3
4
2
人员1１
278
（4）
（1）
1
２
3
４
人员１2
277
（3）
（4）
4
３
2
4
人员13
2７５
（2）
（１）
3
2
1
4
人员14
27５
（1）
（3）
1
3
４
3
人员1５
２74
（１）
（4）
4
3
２
3
人员16
273
（4）
（１）
3
４
３
２
表2：
用人部门对公务员的期望要求
用人
部门j
工作
类别
各部门对公务员特长的希望达到的要求bj
知识面ｂj1
理解能力bj2
应变能力bｊ３
表达能力
ｂj４
部门1
（1）
3
4
２
４
部门2
（2）
4
3
３
2
部门3
（2）
部门4
（3）
2
2
4
４
部门５
（3）
部门６
（4）
2
３
3
４
部门７
（4）
2、结合每个应聘者的笔试,面试成绩及各部门对公务员的能力期望确定系数矩阵Ｃ:
由上表可以得到笔试成绩矩阵aｉ，面试成绩矩阵bi，用人部门要求矩阵ｂj,设Ｃij为矩阵第ｉ行第j列元素，代表第i个公务员对应于第j个部门的综合得分，结合ai,ｂｉ,bj三个矩阵求解矩阵Ｃ,用人部门对应聘者的特长要求在笔试成绩部分无法体现,
的值应该包括考虑用人部门要求影响的面试成绩与笔试成绩两部分。
j部门k项能力的期望分越高代表这项能力在该部门越被看重，所以将bj看成bi矩阵的权重矩阵,取面试成绩矩阵与用人部门要求矩阵相乘所得矩阵、笔试成绩矩阵分别乘以各自的权重在相加所得矩阵作为系数矩阵:
即令
有
;k＝１、2、3、4，
、
〉0为根据实际情况设定的权数,这里暂取
可以得到系数矩阵如下:
应聘
进入各部门的面试得分Ciｊ
人员
部门1
部门2
部门3
部门4
部门5
部门6
部门7
人员１
７5
７2
72
69
６9
70
70
人员２
68。
8
69.8
69。
8
66。
8
6６。
8
65.8
65。
8
人员３
63。
8
59。
8
59.8
５4.8
54。
8
57。
升级会员 