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

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

转载作者：塔克拉玛干更新时间：2023-11-03 04:53:08

我有以下问题:

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

每个学生都被分配到一门类(class)。
没有一门类(class)的学生人数超过 30 人。
最大化学生偏好的总和。

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

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

受限于:

> $x_{i, j} \in { 0, 1 }$ .
> $\sum_{j = 0}^{5} x_{i, j} = 1, \forall i$ .
> $\sum_{i = 0}^{179} x_{i, j} = 30, \forall j$ .

我的表述是否正确？

问题的第二部分如下:

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

谢谢，

问候。

最佳答案

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

所以公式应该是这样的:

最大化∑_ij x_ij p_ij
受制于:
∑_jx_ij=1,∀i
∑_ix_ij≤30,∀j

至于最大流，您可以将每个学生表示为网络中的一个节点，将每个类(class)表示为一个节点，例如四个学生和三个类(class)，图形如下所示:

这里 s 到学生 s_i 的容量是 1，因为每个学生可以在大多数选择，所以 c(s, s_i)=1。教室的容量是 30，这意味着对于每个类(class) c_j，它认为 c(c_i , d)=30。此外，每个 s_i 和 c_j 之间的容量也是 1(尽管更大的容量不会差), 所以c(s_i, c_j)=1.

这里我们在 s_i 和 c_j 之间的边上添加一个“cost” 等于 a(s_i, c_j)=-p_ij，所以鉴于偏好越高，成本越低。其他边的成本为零，因此 a(s, s_i)=a(c_j,d)=0。所以在这里我们将分配流量(基于每个学生的容量，这样一个教室的总流量小于 30)，并最小化成本，因此最小化 -p_{ij 的总和} 的。假设存在一个流，从源 s 到每个学生 s_i 的流为 1，那么我们可以给每个学生一个选择，总成本将得到优化。