利用matlab软件求解线性规划问题Word文档格式.docx
- 文档编号:3569141
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:11
- 大小:21.82KB
利用matlab软件求解线性规划问题Word文档格式.docx
《利用matlab软件求解线性规划问题Word文档格式.docx》由会员分享,可在线阅读,更多相关《利用matlab软件求解线性规划问题Word文档格式.docx(11页珍藏版)》请在冰点文库上搜索。
运用matlab软件,能够轻松快捷地求解。
2线性规划在招聘和排班问题中的具体应用
案例:
某小区组建维修保洁服务,现在需要招聘维修保洁人员若干名轮班进行工作。
其中包括电工、水管工和家政保洁工满足维修保洁工作。
工作采用每人计时上班,即每个工人都可以根据值班表在规定时间上班,满八小时后下班。
例如张三在早晨6点上班,将可以在下午2点下班,李四在上午10点上班则需要在下午6点下班。
根据实际情况和多年统计数据,小区电工维修和水管维修的需求如下表:
每个时段的人员需要情况表
时间
电工
水管工
保洁
1
0点-2点
2
2点-4点
3
4点-6点
4
6点-8点
6
5
8点-10点
8
10点-12点
9
7
12点-14点
14点-16点
16点-18点
12
10
18点-20点
16
11
20点-22点
22点-24点
维修保洁服务的收费标准是:
电工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>
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>
16点-18点:
x6+x7+x8+x9>
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函数只能解决形如
的线性规划,所以先要将线性规划变为如下形式:
s.t.
-x1-x10-x11-x12<
=-1
-x1-x2-x11x-12<
-x1-x2-x3-x12<
-x1-x2-x3-x4<
=-6
-x2-x3-x4-x5<
=-8
-x3-x4-x5-x6<
=-9
-x4-x5-x6-x7<
=-4
-x5-x6-x7-x8<
-x6-x7-x8-x9<
-x7-x8-x9-x10<
=-12
-x8-x9-x10-x11<
=-5
-x9-x10-x11-x12<
=-3
然后建立程序如下:
c=[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;
-6;
-8;
-9;
-4;
-12;
-5;
-3];
aeq=[];
beq=[];
vlb=[0;
0];
[x,fval]=linprog(c,A,b,aeq,beq,vlb)
在命令窗口中输入上程序可得结果:
x=
0.0000
3.4973
3.2640
1.7095
0.5292
2.9713
4.2375
1.5250
3.2662
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)
=-7
-x7-x8-x9-x10<
=-16
=-2
建立程序:
c=[20;
20;
20];
b=[0;
-3;
-7;
-16;
-2];
在窗口中输入上程序可得:
0.6394
2.3138
1.7707
1.2761
4.3900
5.1366
4.2225
2.2509
0.0000
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)
=-10
=-0
c=[15;
15;
15];
-10;
-2;
可得结果:
1.4621
0.6332
0.9047
4.0000
1.6604
2.0028
2.3368
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元/天。
综上所述,每个时间节点的人员分配情况如下表:
保洁工
14
18
20
22
电工需招聘21人,水管工需招聘22人,保洁工需招聘13人
此即为该线性规划问题的最优解,成本为4200+3520+1560=9280元/天。
3.总结
线性规划模型对于解决很多实际问题都很作用,而线性规划问题的求解我们更多地可以借用Excel,matlab等软件,这将大大提高我们的工作效率。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 利用 matlab 软件 求解 线性规划 问题