0

我有一个我想解决的问题，但我不知道如何对其建模在问这里之前，我进行了研究并找到了一些有用的东西，但我无法理解它。我在下面遇到的问题示例

所以我有很多项目，比如说 40 个，每个项目都有 2 或 3 个功能，每个功能只有在有 3、4、5、...时才有用，具体取决于功能。

目标是通过 10 个不同的项目获得最大数量的不同有用功能

示例（如果 3 个或更多不同的项目包括 a，则特征 a 很有用，如果 5 个或更多不同的项目包括 b、c 8 个或更多项目等，则特征 b 很有用）

Items   Features (a,b,c,...)
item1   a,c,d
item2   a,b
item3   a,b,e,
item4   a,c
item5   b,e,f
item6   b,d,e
item7   b,c,d
item8   c,f
item9   c,d,e
item10  d,f
...     ...

一个示例组合

item1+item2+...+item10 = a(3), b(5)

所以 a 和 b 有用的特性（c 没有用，因为有 5 个我们需要 8 个才能使它有用）

我想我想建模一个混合整数线性程序并用分支定界求解器解决它目标是每个项目和每个特征的特征权重的数量（？）我考虑将其建模为背包问题，但后来我想不出出如何应用这个像容量是 10 但价值和重量？对有用的功能有最低要求，我需要一些指导或通用算法来解决这个问题，如果我有什么要开始的，我可以进一步调查

4

1 回答 1

2

我的方法是：

第一步：建立数学模型

拿一张纸，写下一个数学模型。例如：

数据：

 a(i,f) = 1   if item i has feature f
          0   otherwise
 K(f)   = number of items with feature f needed to be useful
 N      = number of items to select

二进制变量：

 x(i) = 1    if item i is selected
        0    otherwise

 u(f) = 1    if feature f is useful in selection
        0    otherwise

模型：

  maximize sum(f,u(f))
  subject to 
       sum(i,x(i)) = N
       u(f)*K(f) <= sum(i, a(i,f)*x(i))   for all f

第 2 步：实施

这现在应该是微不足道的。这是首先写下数学模型的目的。

于 2019-11-29T23:49:54.033 回答