総数制限付きナップザック問題の最適解の作る構造

概要

論文の詳細を見る
この論文では、総数制限付きナップザック問題の最適解の作る構造について研究している。総数制限付きナップザック問題とは通常の(等号制約の)ナップザック問題(〔6〕)に使用する変数の個数を制限する条件を付け加えたものである。ナップザック問題を研究するのに用いられたアプローチ〔6、7〕をこの場合にも応用している。等号制約のナップザック問題のときと同様、この場合も実行可能性は自明ではない。先ずこの問題の特殊構造を利用して実行可能性の必要十分条件を求めている。次にその連続緩和問題の双対実行可能基底で、その列ベクトルの張る凸錐に相対費用係数が0となる列が含まれないものをすべて求めている。実行可能な問題の右辺のベクトルの張る凸錐がその双対実行可能基底の列ベクトルの張る凸錐で分解されることがすぐ分かる。各双対実行可能基底に関連して群緩和問題が対応している。単一制約の整数計画問題の場合と違って、本問題の場合、その群緩和問題をすべて解いてもなお無限に多くの右辺のベクトルに関する問題が未解決のまま残っているのが普通である。この困難を解決するために新しい緩和問題を導入した。群緩和問題は双対実行可能基底の列ベクトルに対応する二つの基底変数の非負性条件を緩めて作ったのに対し、この新しい緩和問題はその一方の基底変数だけの非負性条件を緩めて作ったものである。この緩和問題が元の問題を解決する場合、できない場合を確定している。この緩和問題から導かれる元の問題の持つ性質を利用して、この緩和問題をすべて解くことにより有限個の右辺のベクトルに関する問題が未解決のまま残ることが示されている。すべての右辺のベクトルに関する問題が解決された後、各双対実行可能基底の張る凸錐の中に含まれる右辺のベクトルに対する問題の最適解の間に木構造が定義されている。
社団法人日本オペレーションズ・リサーチ学会の論文

総数制限付きナップザック問題の最適解の作る構造

スポンサーリンク

概要

著者

関連論文

スポンサーリンク