时间戳

首页 > 解决方案 > 关于将问题表述为线性规划的问题

algorithm - 关于将问题表述为线性规划的问题

问题描述

我有以下问题：

我们有180名学生。每个学生都必须选择 6 门课程中的一门才能获得学位。任何课程的学生人数不得超过 30 人。此外，学生必须指定三门具有不同偏好的课程：pij = [0, 100]。
目标是通过以下方式为学生分配课程：

第一个问题是将问题表述为线性规划 (LP)。我的配方如下：

最大化\sum_{i, j} x_{i, j} p_{i, j}，

受制于：

我的配方正确吗？

问题的第二部分如下：

假设我们有一个解决最小成本流问题的黑匣子（https://en.wikipedia.org/wiki/Minimum-cost_flow_problem）。如何使用这个黑匣子来解决我们的赋值问题？

谢谢，

问候。

标签： algorithmlinear-programming

解决方案

您的整数线性规划 (ILP) 公式并不完全正确，在您的最后一个约束中，您写道所有班级正好有 30 名学生，但这是不正确的，一个班级不能有超过 30 名学生。

所以公式应该是这样的：

最大化∑ ij x ij p ij
服从：
    ∑ j x ij =1, ∀i
    ∑ i x ij ≤30, ∀j

至于最大流，您可以将每个学生表示为网络中的一个节点，将每个班级表示为一个节点，例如对于四个学生和三个班级，图表如下所示：

具有四个学生和三个班级的示例网络

这里s对学生s i的容量为1，因为每个学生最多可以做出一个选择，所以c(s, s i )=1。一个教室的容量是 30，这意味着对于每个班级c j，它保持c(c i , d)=30。此外，每个s i和c j之间的容量也为 1（尽管更大的容量不会产生影响），因此c(s i , c j )=1。

在这里，我们在s i和c j之间的边上添加一个“成本” ，等于a(s i , c j )=-p ij，因此如果偏好越高，成本就越低。其他边的成本为零，因此a(s, s i )=a(c j ,d)=0。所以在这里我们将分配流量（基于每个学生的容量，使得到教室的总流量小于 30），并最小化成本，因此最小化-p ij的总和。给定一个流，使得从源s到每个学生s i的流为 1，那么我们就可以给每个学生一个选择，总成本就会得到优化。

推荐阅读