optimization - 如何安排不同类型的木板来形成桥梁

Question

假设我们想从地方$A$步行到地方$B$，但它们之间有几条河流。为了从地方 $A$ 步行到地方 $B$，我们需要为每条河流 build 一座桥。

我们有几种类型的木板。不同类型的木板具有不同的成本和长度，但相同类型的木板具有相同的成本和长度。我们可以用木板来搭建桥梁。但是，可用木板的数量是有限的。我们的目标是为每条河流 build 一座桥梁，同时最大限度地减少木板的总成本。

为了更好的描述问题，我们画一个图来描述我们的问题。

有 3 条河流，需要的桥梁长度分别为 $d_1$、$d_2$ 和 $d_3$。

我们有 $4$ 类型的木板。设 $l_i$ 和 $c_i$ 表示第 $i$ 种木板的长度和成本。设 $\delta_i$ 表示第 i$ 种木板的可用数量。设 $n_{ij}$ 表示用于 build 桥梁 $j$ 的木板数量。

那么问题可以表述如下:

Minimize $\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$

s.t.

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

我认为这个问题应该是 NP-Hard，因为它是一个整数规划问题。这是真的？有谁知道如何解决这个问题？即使是不是最优的解决方案。

Answer 1

如果你可以分割木板，并在多座桥上使用这些木板，并且你可以在一座桥上使用不同类型的木板，那么它就不是 NP 完全的，因为你只是先使用每米最便宜的木板然后继续。

否则它可能是 NP-complete，因为它也是一个 bin packing 问题。例如，如果您不能分割木板以在多座桥上使用这些碎片，假设您有这个数据集:

• 河流 1 有 7 米的落差
• 河流 2 有 6 米的落差

用木板:

• 10 block 木板，每 block 7 米。价格:每 block 木板 60 美元。即每米 8.57 美元。
• 10 block 6 米厚的木板。价格:每 block 木板 40 美元。即每米 6.66 美元。

最便宜的选择是以总计 100 美元的价格购买 1 block 木板，而不是以总计 120 美元的价格购买 3 block 最便宜的木板。

至于解决方案:研究元启发式算法(禁忌搜索、模拟退火、延迟接受)和 OptaPlanner 等软件(java，开源)。