学校分配学生(深入研究)PPT课件.pptx

深入研究 学校分配学生 张金凝朱厚涛 2020 3 22 1 管理学案例 学校分配学生 斯普林菲尔德 Springfield 学校董事会打算在年底关闭它的一所中学 包括6 7 8年级 并在下一年将这些年级的学生分配到另外三所中学去 学校为离校距离超过1英里的所有学生提供上下课的接送服务 因此 为了节省公交费用 学校将对学生进行分配 从该城市的六个居住区到各所学校 每个学生的一年的公交费用如下表所示 表中还给出了下一年的其他一些基本数据 其中 0表示不需要校车服务 而 表示这种分配不可能 学校的董事会规定每个学校里 每一年级的学生人数必须在总人数的30 36 之间 上表显示了第二年每个地区学校的各年级的学生比例 可以划出学生上学的地区界限 以便于在多所学校之间分配学生 但是 不管如何分配 上表所要求的每所学校的各年级的比例必须保持 假设学校雇用你作为管理科学的顾问 帮助学校决定如何在各所学校之间分配学生 2 2020 3 22 a 为该问题建立线性规划模型 并求解该问题 b 你给学校董事会的建议是什么 在看了你的建议之后 学校董事会对将所有的居民区都在各个学校间划分开来这一点表示疑虑 他们认为 应该尽可能的让邻里的学生在同一所学校里 c 根据这一点调整你的建议 使同一个地区尽可能的分配在同一所学校里 加人这一限制可能会使你不得不取消另外一些约束 这样做会增加多少公交成本 学校董事会正考虑减少一些公交以减低成本 选项1是仅仅取消1 1 5英里的学生的公交服务 这些学生的单位成本如上表所示为 200 选项2是同时取消1 5 2英里距离的学生的公交服务 这些学生的估计年成本为 300 3 2020 3 22 d 将a中的模型加入选项1重新考虑 并求解 将结果与c中的结果想比较 包括公交总成本的减少 e 以选项2代替选项1重复步骤e 现在 学校董事会将在三种计划 目前的这一选项 和选项1 选项2 中做出选择 其中 最重要的是因素是成本 但是 学校对另一个因素也给予了同等的重视 即 因为迫使一些学生步行或骑车上学 超过1英里 特别是超过1 5英里 所引起的不方便和安全问题 因此 学校决定选择能使两个因素达到最好的平衡的计划 f 从b d e的结果中总结出与学校董事会要做出决策的两个因素有联系的重要的信息 g 你认为应该做出怎样的决策 为什么 4 2020 3 22 第一回成立决策变量矩阵该问题的实质是如何将6个区的学生分别分配到3个学校中去 故分配方案中至少有6 3 18个参数 又由于学校的董事会规定每个学校里 每一年级的学生人数必须在总人数的30 36 之间 由此每个方案中还要指明三个年级的分配明细 故需要有18 3 54个参数又由于第2 4 5区分别不能向A C B校分配学生 故最后 各分配方案共有54 3 51个参数 见右表绿色区域根据绿色区域的学生按校分配方案可各区各年级实际人数 学校分配学生 5 2020 3 22 将上页各区每个年级人数分别相加 得到本页左表最右栏的橙色区域 根据已知条件 斯普林菲尔德学校 所在城市6个区各年级的人数比例 我们得到各区6 7 8年级的实际人数 见本页左表 右起第二栏中的数字 由上述两条所得的两列数字显然应该分别相等 故得到第一组约束条件 各区6 7 8年级人数 各区各年级实际人数再由上页各区每个年级人数按分别对应的学校来相加求和 得到本页右表左栏的 各区 校人数和合计该组数据与右表右栏 各区 校公交成本 相对应上述两栏中的数据依次相乘的结果再求和 得到该校的学生公交总费用 既 目标函数 第二回建立模型 6 2020 3 22 根据已知题意 第2 4 5区分别不能向第1 3 2学校分配学生 故该区各年级向这些学校的分配学生均为 0 三个年级的合计自然也为 0 用橙色背景表示 如左表最右列所示 这三个等于 0 的等式为第二组约束条件 学校的董事会规定每个学校里 每一年级的学生人数必须在总人数的30 36 之间 因此我们需要求出每个学校里每一年级的学生人数 见右表最下面三行中的数字 将此三行表格展开成一列 如下页如示 第三回中间变量 7 2020 3 22 上页表格展开后见左上表 左侧第三列 人数 所示 根据各校总人数计算出 各年级人数比例 如左上表 右侧第二列橙色背景表格表示 根据已知条件 所有比例都应限定在30 36 之间 此为第三组约束条件 由于学生数只能是整数 故最后一组约束条件是决策变量均为整数 根据上述四组约束建立完整数学模型如所附 案例3 3 工作簿所示 其中工作表 规划求解表C 用于求解问题C 规划求解表A 用于求解其它各解 用Excel中的 规划求解 建模后的表达式组如左下表所示 第四回规划表达式 8 2020 3 22 问题a d e的结果分别显示左表右下角的蓝色背景的表格中 解b 如第5页右表绿色背景中的决策变量数值所示 该组分配方案成本最低 且派出的车次最少 注1 求解d e时 依题意分别将左表最左侧栏的蓝色数字 蓝色与棕色数字都换为 0 注2 每问的解虽是唯一的 但每个解对应的分配方案有很多种 解f 如解d e所示 适当减小公交服务可明显减少成本 但大量减少公交服务 非但成本减少不再明显 还大大增加了安全隐患 g 决策为d 第五回解答 一 9 2020 3 22 解C 根据学校的要求 将各区只按一个学校分配学生 并保持其它结束不变 但无解