利用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等软件，这将大大提高我们的工作效率。
升级会员 