トップ > 数理計画用語集 > 集合被覆問題

数理計画用語集

集合被覆問題

読み:しゅうごうひふくもんだい

集合をその部分集合で被覆するとき,その費用を最小化(または最大化)する問題.具体的には,集合equationとその部分集合の族equationであって,

equation

となるもの(equationの被覆という),および関数

equation

が与えられたときに構成される,以下の問題のことを言う.

equation

集合被覆問題は,0-1 整数変数を用いた整数線形計画問題として定式化できる.すなわち,equationを 0-1 整数変数の集合として,以下のように定式化できる.

equation

集合被覆問題は,施設配置問題割当問題など,様々な問題の中に現れる,基本的な構造である.