利用matlab软件求解线性规划问题Word文档格式.docx

1、运用matlab软件，能够轻松快捷地求解。2 线性规划在招聘和排班问题中的具体应用 案例：某小区组建维修保洁服务，现在需要招聘维修保洁人员若干名轮班进行工作。其中包括电工、水管工和家政保洁工满足维修保洁工作。工作采用每人计时上班，即每个工人都可以根据值班表在规定时间上班，满八小时后下班。例如张三在早晨6点上班，将可以在下午2点下班，李四在上午10点上班则需要在下午6点下班。根据实际情况和多年统计数据，小区电工维修和水管维修的需求如下表：每个时段的人员需要情况表时间电工水管工保洁10点-2点22点-4点34点-6点46点-8点658点-10点810点-12点9712点-14点14点-16点16点

2、-18点121018点-20点161120点-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点。建模：我们首先以电

3、工的招聘和排班为例，研究如何在使电工满足客户需求的同时使公司成本最低，即工资最低。确定该线性规划模型的三要素：- -优化对象：变量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=04点-6点：x1+x2+x3+x126点-

4、8点：x1+x2+x3+x4=68点-10点：x2+x3+x4+x5=810点-12点：x3+x4+x5+x6=912点-14点：x4+x5+x6+x7=414点-16点：x5+x6+x7+x816点-18点: x6+x7+x8+x918点-20点：x7+x8+x9+x10=1220点-22点：x8+x9+x10+x11=522点-24点：x9+x10+x11+x12=3非负约束：xi=0,i=1,2,3,4,5,6,7,8,9,10,11,12 -目标函数：用Z表示每小时支付给电工的工资，则Min Z=25*（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12）Ma

5、tlab求解：运用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=-1 0 0

6、0 0 0 0 0 0 -1 -1 -1; -1 -1 0 0 0 0 0 0 0 0 -1 -1; -1 -1 -1 0 0 0 0 0 0 0 0 -1; -1 -1 -1 -1 0 0 0 0 0 0 0 0; 0 -1 -1 -1 -1 0 0 0 0 0 0 0; 0 0 -1 -1 -1 -1 0 0 0 0 0 0; 0 0 0 -1 -1 -1 -1 0 0 0 0 0; 0 0 0 0 -1 -1 -1 -1 0 0 0 0; 0 0 0 0 0 -1 -1 -1 -1 0 0 0; 0 0 0 0 0 0 -1 -1 -1 -1 0 0; 0 0 0 0 0 0 0 -1

7、-1 -1 -1 0; 0 0 0 0 0 0 0 0 -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.2662fval =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,在满足客户需求的

8、同时，达到成本最少525X8=4200元/天对于水管工，保洁工，同理可得。水管工：Min Z=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

9、=0,在满足客户需求的同时，可使成本最小为440X8=3520元/天。保洁工：Min Z=15*（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12）=-10=-0c=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元/天。综上所述，每个时间节点的人员分配情况如下表：保洁工14182022电工需招聘21人，水管工需招聘22人，保洁工需招聘13人此即为该线性规划问题的最优解，成本为4200+3520+1560=9280元/天。3. 总结线性规划模型对于解决很多实际问题都很作用，而线性规划问题的求解我们更多地可以借用Excel,matlab等软件，这将大大提高我们的工作效率。