运筹学排课问题 运筹学排序问题

运筹学排队论问题~求解

运筹学是现代管理学的一门重要专业基础课。它是20世纪30年代初发展起来的一门新兴学科，其主要目的是在决策时为管理人员提供科学依据，是实现有效管理、正确决策和现代化管理的重要方法之一。该学科是一应用数学和形式科学的跨领域研究，利用统计学、数学模型和算法等方法，去寻找复杂问题中的或近似的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。 研究运筹学的基础知识包括实分析、矩阵论、随机过程、离散数学和算法基础等。而在应用方面，多与仓储、物流、算法等领域相关。因此运筹学与应用数学、工业工程、计算机科学、经济管理等专业密切相关。

运筹学排课问题 运筹学排序问题

运筹学排课问题 运筹学排序问题

排队论又叫随机服务系统理论。最初是在二十世纪初由丹麦工程师艾尔郎关于电话交换机的效率研究开始的，在第二次世界大战中为了对飞机场跑道的容纳量进行估算，它得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展起来。

一共11个人+排班每天白天6个上班晚上2个人上班+应该怎么排？

这种排班问题是一个常见的运筹学问题。根据你的描述，你有11个人，每天白天需要6个人上班，晚上需要2个人上班。

这里有一个可能的排班方案，考虑到了每个人都有足够的休息时间：

我们可以将这11个人分为两个小组，小组1有5个人，小组2有6个人。

对于小组1的5个人：

天：3人白班，2人晚班。

第二天：2人白班，3人休息。

第三天：5人休息。

对于小组2的6个人：

天：3人白班，2人晚班，1人休息。

第二天：3人白班，2人晚班，1人休息。

第三天：6人休息。

这样每个人都有至少一天的休息时间，而且每天都有6人白班和2人晚班。这是一个最基本的轮班，但实际情况可能需要根据每个人的具体需求进行调整。

请注意，这种排班方案可能并不完美，可能还需要考虑到其他因素，如员工的个人需求、工作强度等。在制定排班时，还是与员工充分沟通，以确保排班既能满足工作需求，又能考虑到员工的。

这是一道管理运筹学的指派问题，求具体，要非常具体，每一步都清清楚楚的，谢谢了

In[1]:= u = 4; z = 6; a = Array[# &, {u}]; b = Array[# &, {z}];

aa = {{3, 5, 4, 5}, { 6, 7, 6, 8}, {8, 9, 8, 10}, { 10, 10, 9,

11}, {12, 11, 10, 12}, {13, 12, 11, 13}};

zz = Map[Table[

ToExpression[StringJoin["z", ToString[#], ToString[i]]], {i, 1,

Length[a]}] &, Array[# &, {z}]];

zh = Map[Table[

ToExpression[StringJoin["z", ToString[i], ToString[#]]], {i, 1,

z}] &, Array[# &, {Length[a]}]];

bb = Map[aa[[#]].zz[[#]] &, b];

t = Maximize[

Flatten[{Total[bb],

Map[Total[zh[[#]]] == 1 &, Array[# &, {Length[a]}]],

Map[Total[zz[[#]]] <= 1 &, Array[# &, {z}]],

Map[{# >= 0, # <= 1} &, Flatten[zz]]}], Flatten[zz], Integers]

Out[6]= {43, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,

z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,

z64 -> 0}}

算出来的结果和你的有点不一样，第1、2个人没有工作，第3个人做第4项工作，第4个人做第2项工作，第3个人做第1项工作，第6个人做第3项工作，总收益为43.工作分配有点不一样，但总收益是一样的。结果是有12组不同的解：

{{z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0, z22 -> 0,

z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0, z34 -> 1,

z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0, z52 -> 1,

z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,

z34 -> 1, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,

z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,

z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,

z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,

z52 -> 1, z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,

z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,

z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,

z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,

z64 -> 1}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,

z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0,

z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,

z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,

z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,

z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,

z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,

z64 -> 1}}

运筹学排班方法

运筹学排班方法：运筹学方法主要是通过把管理问题抽象成一个模型，求解模型来获得解决问题的解，依据解和组织的实际情况来制定的方法。

运筹学方法目前已在市场销售、生产、库存管理、运输问题、财政与会计、人事管理、设备维修、更新和可靠性、项目的选择与评价、工程的优化设计、计算机与信息系统、城市管理等方面得到广泛应用。

存在问题

（1）在究竟是让模型适合问题还是让问题适合模型这一点上，许多运筹学家实际上是在让管理问题"削足适履"。他们将原始问题加以抽象，直到数学难点或计算难点都被舍去为止，从而使问题的解答失去实际应用价值。

（2）运筹学最终要得到问题的解，而从管理实践的角度来看，由于决策目标通常有多个，且各个目标间又存在冲突，因此，最终的解决方案只能是一种折衷。

Python实现基于遗传算法的排课优化

排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，TTP）。设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有 种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火，列表寻优搜索和约束满意等。

Github ：

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索解的方法。遗传算法的流程如下所示：

遗传算法首先针对待解决问题随机生成一组解，我们称之为种群（Population）。种群中的每个个体都是问题的解，在优化的过程中，算计算整个种群的成本函数，从而得到一个与种群相关的适应度的序列。如下图所示：

为了得到新的下一代种群，首先根据适应度对种群进行排序，从中挑选出的几个个体加入下一代种群，这一个过程也被称为精英选拔。新种群余下的部分通过对选的精英个体进行修改得到。

对种群进行修改的方法参考了生物DAN进化的方法，一般使用两种方法： 变异 和 交叉 。 变异 的做法是对种群做一个微小的、随机的改变。如果解的编码方式是二进制，那么就随机选取一个位置进行0和1的互相突变；如果解的编码方式是十进制，那么就随机选取一个位置进行随机加减。 交叉 的做法是随机从种群中选取两个个体，以某个位置为交叉点合成一个新的个体。

经过突变和交叉后我们得到新的种群（大小与上一代种群一致），对新种群重复重复上述过程，直到达到迭代次数（失败）或者解的适应性达到我们的要求（成功），GA算法就结束了。

算法实现

首先定义一个课程类，这个类包含了课程、班级、教师、教室、星期、时间几个属性，其中前三个是我们自定义的，后面三个是需要算法来优化的。

接下来定义cost函数，这个函数用来计算课表种群的冲突。当被测试课表冲突为0的时候，这个课表就是个符合规定的课表。冲突检测遵循下面几条规则：

使用遗传算法进行优化的过程如下，与上一节的流程图过程相同。

init_population ：随机初始化不同的种群。

mutate ：变异作，随机对 Schedule 对象中的某个可改变属性在允许范围内进行随机加减。

crossover ：交叉作，随机对两个对象交换不同位置的属性。

evolution ：启动GA算法进行优化。

实验结果

下面定义了3个班，6种课程、教师和3个教室来对排课效果进行测试。

优化结果如下，迭代到第68次时，课程安排不存在任何冲突。

选择1203班的课表进行可视化，如下所示，算法合理的安排了对应的课程。