gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:53:08 30 4
gpt4 key购买 nike

我有以下问题:

我们有 180 名学生。每个学生必须选择 6 门类(class)中的一门才能获得学位。任何类(class)的学生人数不得超过 30 人。此外,学生必须指定三门具有不同偏好的类(class):pij = [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 xij pij
受制于:
jxij=1,∀i
ixij≤30,∀j

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

example network with four students and three classes

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

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

关于algorithm - 关于将问题表述为线性规划的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53683060/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com