运筹学排班问题的建模和程序设计报告2011级工业工程一班杨添淇1120110892********************** 0.前言本报告共分为五个部分：1.排班问题的提出2.建模的心路历程3.新的背景与设定4.新的建模5.建模后的思考其中，第二部分与第五部分最为用力，集中体现了作者想要表达的观点。
其实这两部分应该写在分析报告里吧？好像搞反了…是为序。
1.排班问题的提出某小区组建维修保洁服务，现需要招聘维修保洁人员若干轮班工作。
其中包括电工，水管工，和保洁员。
工作采用计时制，每人工作满8小时后可以下班，如张三在6点上班，可在下午2点下班。
根据统计，小区需求人数如下表：时间电工水管工保洁0点-2点 1 0 02点-4点0 0 04点-6点0 0 06点-8点 6 3 08点-10点8 6 310点-12点9 5 712点-14点 4 4 314点-16点8 7 516点-18点 4 12 1018点-20点12 16 620点-22点 5 8 222点-24点 3 2 0维修保洁服务的收费标准是：电工25元/小时，水工20元/小时，保洁15元/小时。
试制定招聘计划和工人的排班表（即：招聘工人的数量和每个工人的上班时间）。
2.建模的心路历程余以为，老师要我们交报告，绝不是走个形式，也不仅仅是要看我们写出的冷冰冰的代码，求解问题的能力，更是要看我们思维的走向：从哪里来，到哪里去，最终形成一条清晰的路径。
确实，看这个路径的形成过程是一件非常有趣的事，记录这个过程亦然。
是故，我采用了完全写实的笔法，彻头彻尾地记录下了自己的真实想法，怎么想的怎么写的，想怎么写就怎么写。
所以，报告的这个部分叫做：建模的心路历程（多么温润而厚重的小标题啊）。
问题的最后提到了收费问题，旋即戛然而止，留给了解题人无限的遐想空间。
我想老师的本意，是好的。
但读完题后，我的第一个问题便出在这最后一句上：“收费标准”中的“收费”二字作何解。
从语法角度上来讲，这是一个没有主语的动词做了“标准”二字的定语。
“收费”这个动作的主语对我们求解这个问题，起着至关重要的作用。
从一个久经考场的学生的角度来看，这个收费标准应该等同于工资来看：因为工资标准在这道问题中是除了用工需求外最应该出现的已知条件，而且与聘用资费优化息息相关。
而从一个居民，一个一般人的角度来看，收费应该指的是工作的时候向住户收取的费用。
其唯如此，才可以真正称得上是收费。
但是转念一想，我交了一年的物业费，中间再有什么问题的话你来维修是不该收取任何费用的。
这就像买了保险之后得了病，不能说自己再把医药费全扛下来，那样保险就没用了。
再退一步说，就算交了物业费再找电工维修需要再交钱的话，也不应该按照时长收费——保洁倒还罢了，水管工要是为了多赚点收入一个阀门拧了一上午，那就太不美好了。
所以，我更倾向于第一种观点。
毕竟我也是一个久经考场的学生。
是故，以下所有建模过程都基于这个假定：即25元每小时是我们付给电工的工钱，水管工保洁工依此类推。
有人就会说了，这个收费到底是怎么回事，问老师一下不就清楚了。
这就是我一直想说的另一个问题：为什么学生不愿意和老师交流。
但这与建模毫无关系，所以我会在我其他的杂文里探讨这个问题，于此不做过多阐述，还是说建模的事。
排除了这个歧义项的干扰，这个问题还是有很大的解释空间的。
诚然，小小的收费二字没有影响问题本身，这依然是一个开放式的问题，允许我们设定各种各样的环境，来解出各种不同的答案。
那么首先最容易想到的情况，一定是三个工种各自招人，每个时段的工作人数都必须大于等于统计需求人数，也就是什么都不加。
于是不难得出数学模型如下，以电工为例：依据表格将全天24小时划分成十二个时段，每两小时一段。
设每个偶数整点时刻开始工作的人数分别为X1，X2，X3…X12，目标值F= X1+X2+X3+…+X12，求其最小值。
则有线性方程组：F= X1+X2+X3+…+X12X1+X10+X11+X12>1X1+X2+X11+X12>0X1+X2+X3+X12>0X1+X2+X3+X4>6...X9+X10+X11+X12>0这是一个典型的线性规划问题（话说这方程组好大…）。
幸好现代的计算机技术可以帮助我们方便快捷地求解此类问题，不然手动求解这个方程组的情形真的是不敢想象。
似乎问题到这里已经被解决的差不多了。
可是有一个严重的问题是：我根本不会用matlab……后来，在花掉了n个积攒多年的百度文库财富值之后，终于学会了matlab中基本线性规划问题的求解方法：即应用matlab中的linprog函数。
由于linprog函数只能求解约束条件为balabala小于等于某定值的方程，所以将各个约束条件进行了变形处理，最终得到以下的指令：Matlab中的指令如下：F=[1;1;1;1;1;1;1;1;1;1;1;1];a=[-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 -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 -1 -1 -1 0;0 0 0 0 0 0 0 0 -1 -1 -1 -1];b=[-1;0;0;-6;-8;-9;-4;-8;-4;-12;-5;-3];vbl=[0;0;0;0;0;0;0;0;0;0;0;0];[x,fval]=linprog(F,a,b,[],[],vbl)运行结果如下：Optimization terminated.x =0.00000.00003.49733.26401.70950.52922.97134.23751.52503.26620.00000.0000fval =21.0000可是作为一个实际问题，尤其是这种涉及到人数的实际问题的时候，是不允许非整数解的存在的，毕竟我们不能叫半个人去工作，这样太不人道，也不好实现。
况且0.6个人加上0.4个人也再不能等于一个完整的人了，这个拆分过程是不可逆的。
所以我对于机器解出的数据进行了一个最基本的整理，即四舍五入：X= 当前工作人数所需工作人数剩余工时0 3 1 20 0 0 03 3 0 33 6 6 02 8 8 01 9 9 03 94 54 10 8 22 10 4 63 12 12 00 9 5 40 5 3 2fval=21以上解决方案满足需求条件。
水管工与保洁工运算过程类似。
建模过程不再粘贴，凑字数什么的最讨厌了。
可是我们不难发现，机器明显不够智能的地方。
具体体现在四点到六点上：明明没有人需要电工却叫人家大早上四点来上班，呆上两个小时再工作。
如果是我的话，我一定会把老板骂个满头大包，就算你给我工钱也不能这么欺负人。
更严重的问题在于工时的浪费。
为了满足十点到十二点，十八点到二十点两个略显变态的时段，造成了大量的工时浪费：工人在这两个时间段干完工作之后，剩下的时间会闲下来喝茶看报纸。
这样无形中造成了人员的冗余。
浪费是可耻的。
尤其是在现在这种用工荒的大环境下，对于劳动力的闲置何止是可耻，简直应该说是犯罪。
而我们又不得不满足这些上帝客户们的需求。
因此，为了支持建设节约集约型社会，我们必须要改变问题的背景设定和先决条件。
3.新的背景与设定1.作为一个贪心的老板的话，我一定会考虑招聘既能当电工又能当水管工还能兼职保洁的工人。
这样的话请一个人再怎么说也一定比请三个人便宜，毕竟他只吃一份盒饭，只要养活一个家庭。
但是，暂且不论有没有这样一专多能的人才技工，工作时间的冲突和连续工作带来的疲劳也成了这种兼职的巨大障碍。
所以，虽然很贪心，我还是放弃了这种又想马儿跑，又想马儿少吃草的天真想法。
2.如果是作为一个为了降低成本可以无所不用其极的提供服务的一方的话，首先想到的是：急什么急，有问题人手不够就让他们等一会，得了呗。
对此我实在是不敢苟同。
且不论人们对于脏乱差环境的容忍程度有多强，保洁是不是一种对于服务速度要求特高的服务项目；正常住户一般最忍不了的两件事就是停电停水或者漏电漏水（物理老师说电和水性质相似，呜呼诚不我欺）。
所以，余以为，抢险维修服务一类的工种，性质和保镖类似，失误一次就可以辞职回家了。
任谁也不能容忍家里的水管如喷泉般肆虐。
是故这两种问题的解决必须要及时，即不能等待。
3.排除了上面这两种可能性之后，我们似乎已经无计可施了。
但是，如果把思路逆转过来的话，是不是就会好很多——我可以改变工人的工作方式，让一部分人跳着工作，以零代整，削减高峰时段的用人数避免浪费，再其他时段浪费出来的工时的填补高峰时段的空缺。
这样就减少了工时的浪费。
中国的廉价劳动力们没有那么大的大爷脾气，非八小时连续不干；他们要的也不多，有的只需求温饱即可。
况且题干中说的只是“工作采用计时制，每人工作满8小时后可以下班，如张三在6点上班，可在下午2点下班。
”其中“可以”二字，最其妙者——又没说一定要满八小时才能下班，不满八小时按八小时计多不退少要补。
但是如果把所有工人的工作时间都拆成零零碎碎的话，似乎有点太无赖了，那就不要规划了。
这像是钻了题目表述的空子。
那么我们不妨再逆转一下思路：每个工种选出一到数个队长/模范/红旗手/小标兵/灵活机动岗，多付三分之一的工钱，然后全天值班待命，哪里需要哪里搬。
这就是我的第二种建模方案，它真真切切地减小了用工高峰时段的需求值。
4.新的建模根据初步估量，暂拟订设立三个值班岗。
此三人的八个小时分成四部分，分摊在几个高峰值上。
将八点到十点，十点到十二点，十四点到十六点，十八点到二十点，四个时段的需求人数分别减去3，由活动岗代替。
Matlab 指令如下：f=[1;1;1;1;1;1;1;1;1;1;1;1];a=[-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 -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 -1 -1 -1 0;0 0 0 0 0 0 0 0 -1 -1 -1 -1];b=[-1;0;0;-6;-5;-6;-4;-5;-4;-9;-5;-3];vbl=[0;0;0;0;0;0;0;0;0;0;0;0];[x,fval]=linprog(f,a,b,[],[],vbl)运行结果如下：x =0.00000.00002.56083.43920.00000.00002.68162.80841.11532.39460.00000.0000fval =15.0000经整理，实际人数如下：X= 当前工作人数所需工作人数剩余工时0 3 1 20 0 0 00 0 0 06 6 6 00+3 9 8 10+3 9 9 03 94 53+3 9 8 11 7 4 33+3 13 12 10 7 5 20 4 3 1依然满足条件，且省下了21-15-3*4/3=2，两个人的工钱。