运筹学排班问题大作业.docx

运筹学排班问题的建模和程序设计报告2011级工业工程一班杨添淇1120110892y0. 前言本报告共分为五个部分：1.排班问题的提出2.建模的心路历程3.新的背景与设定4.新的建模5.建模后的思考其中，第二部分与第五部分最为用力，集中体现了作者想要表达的观点。其实这两部分应该写在分析报告里吧？好像搞反了是为序。1. 排班问题的提出某小区组建维修保洁服务，现需要招聘维修保洁人员若干轮班工作。其中包括电工，水管工，和保洁员。工作采用计时制，每人工作满8小时后可以下班，如张三在6点上班，可在下午2点下班。根据统计，小区需求人数如下表：时间电工水管工保洁0点-2点1002点-4点0004点-6点0006点-8点6308点-10点86310点-12点95712点-14点44314点-16点87516点-18点4121018点-20点1216620点-22点58222点-24点320维修保洁服务的收费标准是：电工25元/小时，水工20元/小时，保洁15元/小时。试制定招聘计划和工人的排班表（即：招聘工人的数量和每个工人的上班时间）。2. 建模的心路历程余以为，老师要我们交报告，绝不是走个形式，也不仅仅是要看我们写出的冷冰冰的代码，求解问题的能力，更是要看我们思维的走向：从哪里来，到哪里去，最终形成一条清晰的路径。确实，看这个路径的形成过程是一件非常有趣的事，记录这个过程亦然。是故，我采用了完全写实的笔法，彻头彻尾地记录下了自己的真实想法，怎么想的怎么写的，想怎么写就怎么写。所以，报告的这个部分叫做：建模的心路历程（多么温润而厚重的小标题啊）。问题的最后提到了收费问题，旋即戛然而止，留给了解题人无限的遐想空间。我想老师的本意，是好的。但读完题后，我的第一个问题便出在这最后一句上：“收费标准”中的“收费”二字作何解。从语法角度上来讲，这是一个没有主语的动词做了“标准”二字的定语。“收费”这个动作的主语对我们求解这个问题，起着至关重要的作用。从一个久经考场的学生的角度来看，这个收费标准应该等同于工资来看：因为工资标准在这道问题中是除了用工需求外最应该出现的已知条件，而且与聘用资费优化息息相关。而从一个居民，一个一般人的角度来看，收费应该指的是工作的时候向住户收取的费用。其唯如此，才可以真正称得上是收费。但是转念一想，我交了一年的物业费，中间再有什么问题的话你来维修是不该收取任何费用的。这就像买了保险之后得了病，不能说自己再把医药费全扛下来，那样保险就没用了。再退一步说，就算交了物业费再找电工维修需要再交钱的话，也不应该按照时长收费保洁倒还罢了，水管工要是为了多赚点收入一个阀门拧了一上午，那就太不美好了。所以，我更倾向于第一种观点。毕竟我也是一个久经考场的学生。是故，以下所有建模过程都基于这个假定：即25元每小时是我们付给电工的工钱，水管工保洁工依此类推。有人就会说了，这个收费到底是怎么回事，问老师一下不就清楚了。这就是我一直想说的另一个问题：为什么学生不愿意和老师交流。但这与建模毫无关系，所以我会在我其他的杂文里探讨这个问题，于此不做过多阐述，还是说建模的事。排除了这个歧义项的干扰，这个问题还是有很大的解释空间的。诚然，小小的收费二字没有影响问题本身，这依然是一个开放式的问题，允许我们设定各种各样的环境，来解出各种不同的答案。那么首先最容易想到的情况，一定是三个工种各自招人，每个时段的工作人数都必须大于等于统计需求人数，也就是什么都不加。于是不难得出数学模型如下，以电工为例：依据表格将全天24小时划分成十二个时段，每两小时一段。设每个偶数整点时刻开始工作的人数分别为x1，x2，x3x12，目标值f= x1+x2+x3+x12，求其最小值。则有线性方程组：f= x1+x2+x3+x12x1+x10+x11+x121x1+x2+x11+x120x1+x2+x3+x120x1+x2+x3+x46.x9+x10+x11+x120这是一个典型的线性规划问题（话说这方程组好大）。幸好现代的计算机技术可以帮助我们方便快捷地求解此类问题，不然手动求解这个方程组的情形真的是不敢想象。似乎问题到这里已经被解决的差不多了。可是有一个严重的问题是：我根本不会用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.0000 0.0000 3.4973 3.2640 1.7095 0.5292 2.9713 4.2375 1.5250 3.2662 0.0000 0.0000fval = 21.0000可是作为一个实际问题，尤其是这种涉及到人数的实际问题的时候，是不允许非整数解的存在的，毕竟我们不能叫半个人去工作，这样太不人道，也不好实现。况且0.6个人加上0.4个人也再不能等于一个完整的人了，这个拆分过程是不可逆的。所以我对于机器解出的数据进行了一个最基本的整理，即四舍五入：x=当前工作人数所需工作人数剩余工时0312000033033660288019903945410822104631212009540532fval=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.0000 0.0000 2.5608 3.4392 0.0000 0.0000 2.6816 2.8084 1.1153 2.3946 0.0000 0.0000fval = 15.0000经整理，实际人数如下：x=当前工作人数所需工作人数剩余工时03120000000066600+39810+399039453+398117433+31312107520431依然满足条件，且省下了21-15-3*4/3=2，两个人的工钱。水管工和保洁工运算结果类似，不再粘贴，将在招聘报告中有所体现。5.建模之后的思考余以为，上表只是根据大量数据（或者不是足够大量的数据）得出的需求统计表，并不能说明在相应的时间就一定会出现表中所给的工作人员需求。上面这种建模，也只是我在理想的环境下做出的构想。作为运筹学作业的一部分，勉强可以它也只能作为一个学院派的学生作业存在。而实际情况远远比这复杂得多。正如我在3.新的背景与设定一部分中提到的第二小点中说的那样：“在这个用工荒的大环境下.”（感谢s君激活了这个思路，他提醒我从这里谈起）是的，就算我算出了最优值，依然可能招不到人，甚至可能一个人都招不到。由于农业的机械化，大量被闲置的劳动力从广大的农村走了出来。可是这些被锄櫌棘矜训练出的坚韧躯体并没有被赋予和身体素质相应的劳动技能。他们更多的被建筑工地或者外资血汗工厂所消化，在消耗同等体力的情况下，他们的收入是最少的。与此同时，我国每年还有一个相当庞大的就业群体，他们的名字叫大学毕业生。这群所谓的知识分子是不屑于做这些技术工种的如果去当电工水管工，蓝翔是比大学更好的选择。更何况，四年的大学生活，已经让他们之中很大的一部分人失去了这些真正动手操作的能力。这从这次报告便可见一斑：好多同学的matlab是经过我指点的，所以可以看到很多人的矩阵里系数都是负的，而不会想到在整个矩阵的前面加上一个负号。我是因为线性代数没学好，才这么做的，这是最笨的方法，可是他们都照着学了。我现在知道可以整个加负号，却懒得改了，所以我比他们也强不了多少。接着说用工荒。用工荒并不是所有行业都招不到人。那些薪酬待遇最低端和最高端的行业永远都不会缺人。恰恰就是这些所谓高不成低不就的行业没有人愿意做。为什么没人愿意做？说到底是教育问题和社会意识问题。或许是因为我们的国家太大了，远远超过了柏拉图理想国中理想国家的国土和人口的上限。这直接导致了地区发展差异和城乡发展差异，而差异正是矛盾的根源所在。我朝开国数十年以来，并没有给广大的农村人民带来足够优质的教育。以至于广大的农民兄弟依然在社会的底层挣扎（虽然说我们在封建时代有所谓“士农工商”的排序，但农民还是实质上的底层基础，默默地用劳动维系着社会机器的运转）。薄弱的劳动技能并不能支持他们享受工业革命和科技革命为他们带来的就业机遇。而少数从农村走出来的接受了高等教育的所谓凤凰们，又和他们的同学们一道走向了另一个怪圈：大学之后找工作难。为什么大学生不愿意做这些技术工种？因为他们接受教育的前期投入太大了，成本太高了，技术工种的收获与他们的预期落差太大，收不回成本。回想一下自己念书的过程，真的就是真金白银铺路，才走到了这一步。这就像买股票一样，从一开始就放量买进，结果股票一路下跌，却也舍不得割肉抛售。结果股价越来越低，这种情况，俗称叫套牢。早走的人认清了现实，所以在半路找了个活计，安家立业；认不清实际而又不适合高等教育的人就一路到底的读下去。我不否认有的人真的在大学里做出了推进社会发展的科研结果，但是大多数人并没有做到。结果大量金钱和青春的投入，换来的只是在象牙塔里躲上几年，不必接受社会压力的吹打；最后还放不下身段，嗟叹“时运不齐，命途多舛”，为了考公务员或者进国企搞得头尖如矛，突出了一个挤劲和钻劲。但是为什么上大学是一件性价比如此之低的事情，却又成为了当今中国家庭教育的主流选择呢？余以为，这就是社会权力攫取途径的问题。上