利用matlab软件求解线性规划问题.docx
- 文档编号:1871419
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:11
- 大小:21.82KB
利用matlab软件求解线性规划问题.docx
《利用matlab软件求解线性规划问题.docx》由会员分享,可在线阅读,更多相关《利用matlab软件求解线性规划问题.docx(11页珍藏版)》请在冰点文库上搜索。
利用matlab软件求解线性规划问题
利用
matlab软件
求解
线性规划问题
2013年4月17日
利用matlab软件求解线性规划问题
摘要:
线性规划被广泛地应用于工业、交通、国防、经济、管理等领域,已成为现代科学管理的重要手段和管理决策的有效方法。
本文给出运用线性规划求解,解决维修保洁服务员工的招聘和排班问题,使得在满足客户需求的前提下,达到成本最低。
其中,线性规划的求解是运用matlab软件,方便快捷。
关键词:
线性规划排班matlab
Absract:
Linearprogramminghasbeenappliedinindustry,traffic,economyandmanangementwidely,andithasbecomeanimportantandefficientmeansofmodernscientificmanangement.Settlemengbyprogrammingisexplainedinthisarticle,whichisusedtogivethemostreasonablenumberofpeopleineachshiftintheconsumerservicecenter,inpurposeofusingthelowestcosttomeettheconsumers.Weusematlabtosettletheproblem,whichisconvenientandshortcut.
Keywords:
linearprogrammingstuffshiftarrangementmatlab
1引言
线性规划作为运筹学的一个分支,它的应用已越来越深入到社会生产和经济活动的各个领域。
线性规划有三要素:
优化对象,目标函数,约束条件。
我们把时间问题抽象成数学模型,然后再利用相关理论求解,即寻求满足约束条件的目标函数的最优解。
数学中常用的方法有图解法和单纯形法,图解法只适用于两个变量的目标函数,单纯形法计算量大,步骤繁多,容易出错。
运用matlab软件,能够轻松快捷地求解。
2线性规划在招聘和排班问题中的具体应用
案例:
某小区组建维修保洁服务,现在需要招聘维修保洁人员若干名轮班进行工作。
其中包括电工、水管工和家政保洁工满足维修保洁工作。
工作采用每人计时上班,即每个工人都可以根据值班表在规定时间上班,满八小时后下班。
例如张三在早晨6点上班,将可以在下午2点下班,李四在上午10点上班则需要在下午6点下班。
根据实际情况和多年统计数据,小区电工维修和水管维修的需求如下表:
每个时段的人员需要情况表
时间
电工
水管工
保洁
1
0点-2点
1
0
0
2
2点-4点
0
0
0
3
4点-6点
0
0
0
4
6点-8点
6
3
0
5
8点-10点
8
6
3
6
10点-12点
9
5
7
7
12点-14点
4
4
3
8
14点-16点
8
7
5
9
16点-18点
4
12
10
10
18点-20点
12
16
6
11
20点-22点
5
8
2
12
22点-24点
3
2
0
维修保洁服务的收费标准是:
电工25元/时,水管工20元/时,保洁15元/时。
请制定招聘计划和工人的排班表(即:
招聘工人的数量和每个工人的上班时间)。
分析:
这实际是个成本效益平衡问题。
公司在向客户提供满意服务的同时要控制成本,因此必须寻找成本与效益的平衡。
由于每节工作小时2,一天被分为12班,每人连续工作8小时,即连续工作4班。
由于工人的需求是以2小时为单位的,因此我们工人的分配也应以2小时为单位,每班工作开始时间为0点(24点)、2点、4点、6点、8点、10点、12点、14点、16点、18点、20点、22点。
建模:
我们首先以电工的招聘和排班为例,研究如何在使电工满足客户需求的同时使公司成本最低,即工资最低。
确定该线性规划模型的三要素:
--优化对象:
变量xi分别表示分派到第i班的电工人数(i=1,2,3,4,,5,6,7,8,9,10,11,12)
--约束条件:
以0点-2点为例,只有第10、11、12、1时间段内的电工才能在该时间段内工作,即只要18点,20点,22点,24点开始上班的电工才能在0点-2点段内工作,而其他时间节点开始工作的电工不会在0点-2点内工作,由此可得:
0点-2点:
x1+x10+x11+x12>=1(最低可接受水平)
2点-4点:
x1+x2+x11+x12>=0
4点-6点:
x1+x2+x3+x12>=0
6点-8点:
x1+x2+x3+x4>=6
8点-10点:
x2+x3+x4+x5>=8
10点-12点:
x3+x4+x5+x6>=9
12点-14点:
x4+x5+x6+x7>=4
14点-16点:
x5+x6+x7+x8>=8
16点-18点:
x6+x7+x8+x9>=4
18点-20点:
x7+x8+x9+x10>=12
20点-22点:
x8+x9+x10+x11>=5
22点-24点:
x9+x10+x11+x12>=3
非负约束:
xi>=0,i=1,2,3,4,5,6,7,8,9,10,11,12
--目标函数:
用Z表示每小时支付给电工的工资,则
MinZ=25*(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12)
Matlab求解:
运用matlab优化工具箱中的linprog函数来求解,考虑到linprog函数只能解决形如
的线性规划,所以先要将线性规划变为如下形式:
MinZ=25*(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12)
s.t.
-x1-x10-x11-x12<=-1
-x1-x2-x11x-12<=0
-x1-x2-x3-x12<=0
-x1-x2-x3-x4<=-6
-x2-x3-x4-x5<=-8
-x3-x4-x5-x6<=-9
-x4-x5-x6-x7<=-4
-x5-x6-x7-x8<=-8
-x6-x7-x8-x9<=-4
-x7-x8-x9-x10<=-12
-x8-x9-x10-x11<=-5
-x9-x10-x11-x12<=-3
然后建立程序如下:
c=[25;25;25;25;25;25;25;25;25;25;25;25];
A=[-100000000-1-1-1;
-1-100000000-1-1;
-1-1-100000000-1;
-1-1-1-100000000;
0-1-1-1-10000000;
00-1-1-1-1000000;
000-1-1-1-100000;
0000-1-1-1-10000;
00000-1-1-1-1000;
000000-1-1-1-100;
0000000-1-1-1-10;
00000000-1-1-1-1;
];
b=[-1;0;0;-6;-8;-9;-4;-8;-4;-12;-5;-3];
aeq=[];beq=[];
vlb=[0;0;0;0;0;0;0;0;0;0;0;0];
[x,fval]=linprog(c,A,b,aeq,beq,vlb)
在命令窗口中输入上程序可得结果:
x=
0.0000
0.0000
3.4973
3.2640
1.7095
0.5292
2.9713
4.2375
1.5250
3.2662
0.0000
0.0000
fval=
525.0000
做适当的调整,可以令x1=0,x2=0,x3=3,x4=3,x5=2,x6=1,x7=3,x8=4,x9=2,x10=3,x11=0,x12=0,在满足客户需求的同时,达到成本最少525X8=4200元/天
对于水管工,保洁工,同理可得。
水管工:
MinZ=20*(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12)
s.t.
-x1-x10-x11-x12<=0
-x1-x2-x11x-12<=0
-x1-x2-x3-x12<=0
-x1-x2-x3-x4<=-3
-x2-x3-x4-x5<=-6
-x3-x4-x5-x6<=-5
-x4-x5-x6-x7<=-4
-x5-x6-x7-x8<=-7
-x6-x7-x8-x9<=-12
-x7-x8-x9-x10<=-16
-x8-x9-x10-x11<=-8
-x9-x10-x11-x12<=-2
建立程序:
c=[20;20;20;20;20;20;20;20;20;20;20;20];
A=[-100000000-1-1-1;
-1-100000000-1-1;
-1-1-100000000-1;
-1-1-1-100000000;
0-1-1-1-10000000;
00-1-1-1-1000000;
000-1-1-1-100000;
0000-1-1-1-10000;
00000-1-1-1-1000;
000000-1-1-1-100;
0000000-1-1-1-10;
00000000-1-1-1-1;
];
b=[0;0;0;-3;-6;-5;-4;-7;-12;-16;-8;-2];
aeq=[];beq=[];
vlb=[0;0;0;0;0;0;0;0;0;0;0;0];
[x,fval]=linprog(c,A,b,aeq,beq,vlb)
在窗口中输入上程序可得:
x=
0.0000
0.6394
2.3138
1.7707
1.2761
0.0000
4.3900
5.1366
4.2225
2.2509
0.0000
0.0000
fval=
440.0000
做适当的调整,可令
x1=0,x2=1,x3=2,x4=2,x5=2,x6=0,x7=4,x8=5,x9=4,x10=2,x11=0,x12=0,
在满足客户需求的同时,可使成本最小为440X8=3520元/天。
保洁工:
MinZ=15*(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12)
s.t.
-x1-x10-x11-x12<=0
-x1-x2-x11x-12<=0
-x1-x2-x3-x12<=0
-x1-x2-x3-x4<=0
-x2-x3-x4-x5<=-3
-x3-x4-x5-x6<=-7
-x4-x5-x6-x7<=-3
-x5-x6-x7-x8<=-5
-x6-x7-x8-x9<=-10
-x7-x8-x9-x10<=-6
-x8-x9-x10-x11<=-2
-x9-x10-x11-x12<=-0
建立程序:
c=[15;15;15;15;15;15;15;15;15;15;15;15];
A=[-100000000-1-1-1;
-1-100000000-1-1;
-1-1-100000000-1;
-1-1-1-100000000;
0-1-1-1-10000000;
00-1-1-1-1000000;
000-1-1-1-100000;
0000-1-1-1-10000;
00000-1-1-1-1000;
000000-1-1-1-100;
0000000-1-1-1-10;
00000000-1-1-1-1;
];
b=[0;0;0;0;-3;-7;-3;-5;-10;-6;-2;0];
aeq=[];beq=[];
vlb=[0;0;0;0;0;0;0;0;0;0;0;0];
[x,fval]=linprog(c,A,b,aeq,beq,vlb)
可得结果:
x=
0.0000
0.0000
1.4621
0.6332
0.9047
4.0000
1.6604
2.0028
2.3368
0.0000
0.0000
0.0000
fval=
195.0000
对以上结果作适当的调整,可以令x1=0,x2=0,x3=1,x4=1,x5=1,x6=4,x7=1,x8=2,x9=3,x10=0,x11=0,x12=0,这样在满足客户需求的同时,可以使保洁工的成本达到最低为195X8=1560元/天。
综上所述,每个时间节点的人员分配情况如下表:
时间
电工
水管工
保洁工
1
0
0
0
0
2
2
0
1
0
3
4
3
2
1
4
6
3
2
1
5
8
2
2
1
6
10
1
0
4
7
12
3
4
1
8
14
4
5
2
9
16
2
4
3
10
18
3
2
0
11
20
0
0
0
12
22
0
0
0
电工需招聘21人,水管工需招聘22人,保洁工需招聘13人
此即为该线性规划问题的最优解,成本为4200+3520+1560=9280元/天。
3.总结
线性规划模型对于解决很多实际问题都很作用,而线性规划问题的求解我们更多地可以借用Excel,matlab等软件,这将大大提高我们的工作效率。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 利用 matlab 软件 求解 线性规划 问题
![提示](https://static.bingdoc.com/images/bang_tan.gif)