$A$ の場所から $B$ の場所まで歩きたいとしますが、その間にいくつかの川があります。$A$ の場所から $B$ の場所まで歩くには、川ごとに橋を架ける必要があります。
数種類の板をご用意しております。厚板の種類が異なればコストと長さも異なりますが、同じ種類の厚板は同じコストと長さです。厚板を使って橋を架けることができます。ただし、利用できる板の数は限られています。私たちの目的は、厚板の総コストを最小限に抑えながら、各川に橋を架けることです。
問題をよりよく説明するために、問題を説明する図を描きます。
必要な橋の長さがそれぞれ $d_1$、$d_2$、$d_3$ の 3 つの川があります。
$4$ 種類の厚板があります。$l_i$ と $c_i$ は、$i$ 番目のタイプの厚板の長さとコストを示します。$\delta_i$ が利用可能な $i$ 番目の種類の厚板の数を表すとします。$n_{ij}$ が橋 $j$ を構築するために使用される厚板の数を表すとします。
次に、問題は次のように定式化できます。
$\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$ を最小化
st
$\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 である必要があると思います。これは本当ですか？この問題を解決する方法を知っている人はいますか？最適ではないソリューションでさえ。