ある種の資源配分問題の解法について
スポンサーリンク
概要
- 論文の詳細を見る
つぎの問題を考えてみよう。Q:maximize Σ^^n___<i=1> x_i subject to Z(x)=Σ^^n___<i=1>f_i(x_i)≦R、x_i:非負整数ここでf_iは〔0、∞)上の非減少凸関数であり、次の条件を満たしている。Σ^^n___<i=1>f_i(0)≦R lim___<x_i→∞>f_i(x_i)=∞この問題は次のように定式化される資源配分問題(問題P)において、目的関数と制約条件式の左辺の関数とを交換した問題である。P:minimize Σ^^n___<i=1>f_i(x_i)subject to Σ^^n___<i=1>xi=N、x_i:非負整数ここで、Nは正整数、f_iは〔0、N〕上の凸関数である。このような問題(問題Q)を考えることは、問題Pが重要な役割りを果たす状況においては、問題Pを考えることと同等の意義をもつものと思われ、さらには問題Pの構造をより一層明らかにするのに役立つと考えられる。本論文は問題Qに対する3種のアルゴリズムを提案し、各々の計算手間を評価する。これら3種のアルゴリズムは問題Pに対する従来のアルゴリズムを変形したものであり。その計算手間はf_i(x_i)の値の計算が定数オーダーで済むと仮定すると、各々O(N*logn+n)、O(n^2(logN^^~)^2)、O(b(n、R)十n1ogn)である。ここで、N*は最適解に対する目的関数の値、N^^~はN*の上限、b(n、R)は問題Qにおいて整数条件を落とした問題を解くのに要する計算手間を表わしている。N*がnに比べてそれほど大きくないとき、最初のアルゴリズムが最も優れている。そうでなければ、2番目もしくは3番目のアルゴリズムが優れている。もし、b(n、R)<O(n^2(logN^^~)^2)ならば(たとえばf_i(x_i)=α_ix^k_iのような場合)2番目のアルゴリズムが最も優れている。
著者
関連論文
- (0-1)変数計画問題に対するブール代数的解法 (情報理論・実験計画法における組合せ数学の諸問題 II : 研究会報告集)
- 勤務スケジューリング問題に対する局所探索法(医療・福祉・スケジューリング(2))
- 制約充足問題に対するタブー探索における評価関数の重みの自動調整(数理計画(1))
- 資源制約付きスケジューリング問題に対する近似解法(スケジューリング(2))
- 多重選択ナップザック問題
- 無向ネットワーク内の全ての最小カットを表すカクタス表現の構成について(グラフ理論(1))
- 仮説を利用した推論方式
- 制約充足問題(CSP)に対するタブー探索におけるプログラムパラメータの自動調節(組合せ最適化(2))
- 汎用組合せアルゴリズムとしての制約充足問題(CSP)に対する近似解法(組合せ最適化(2))
- 制約充足問題(CSP)に対するタブー探索の適用(組合せ最適化(3))
- 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法(組合せ(1))
- 劣化システムの最適観測・保全政策
- ネットワークの辺連結度増加問題を解くアルゴリズムの計算機実験(グラフ理論(2))
- 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
- 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
- 配置コストをもつ二次元配置問題に対する局所探索について(組合せ最適化)
- 変分不等式に対する反復解法とその交通流均衡問題への適用
- 最大納期遅れを最小にする1機械処理順序問題に対する6種の近似解法の評価 : 準備時間のある場合
- 藤重, 岩田先生Fulkerson賞受賞のニュース(情報の窓)
- Support Vector Machineにおけるルールの利用(線形計画)
- データ分類におけるノイズ量の評価について(数理計画(1))
- データからの知識獲得における常識ルールと例外ルールについて(数理計画(2))
- On Minimum Edge Ranking Spanning Trees
- 有限の待ち合い室を有するGI/G/1待ち行列システムに対する拡散近似 : II-定常状態における挙動
- 有限の待ち合い室を有するGI/G/I待ち行列システムに対する拡散近似 : I-ファーストオーバーフロー・タイム
- 辺連結度増加関数の計算法(ネットワーク(1))
- ある種の資源配分問題の解法について
- 最適教授項目決定問題の解法
- 列長制限のある複数窓口における集団待ち行列の解析 : 飲食店を例として(待ち行列)
- Arbitration Under Different Information
- Research on Empty-Core Games
- 最終ダブルオファー仲裁(FDOA)の均衡戦略の解析について(ゲーム理論(1))
- Double-Offer Bargaining Rule
- Further Analysis of the Arbitration Procedure FDOA
- Arbitration for Bayesian Collective Choice Problem
- Intrinsic Gap and Final-Double-Offer Arbitration
- Augmenting a (k-1)-Vertex-Connected Multigraph to an l-Edge-Connected and k-Vertex-Connected Multigraph
- Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
- Augmenting edge-connectivity and vertex-connectivity simultaneously
- タブー探索による直交ラテン方陣の構成(組合せ最適化(2))
- 区間信頼度を最大にする最適予防保全方策のまとめ
- コンテナターミナルにおけるシフト計画
- 無向ネットワークの最小カットを求める実用的高速アルゴリズム(グラフ・ネットワーク)
- A Tight Upper Bound on the Number of Small Cuts in Undirected Networks
- 変動する環境下での1機械スケジューリング問題に対する遺伝アルゴリズムの適用について(組合せ最適化(3))
- カッティングストック問題におけるパターン生成法について(組み合わせ最適化(2))
- パターン数最小化を目的とするカッテイングストック問題について
- ブロッキングを伴うある待ち行列網の安定条件について(待ち行列理論とその応用)
- リリースタイムとハンドリングタイムを考慮した木状経路における搬送スケジューリング(スケジューリング)
- 三進算術演算装置
- 大阪湾の水質汚濁機構の解明と水質評価に関する研究III(環境行政)
- 大阪湾の水質汚濁機構の解明と水質評価に関する研究II(地域・都市・環境)
- Optimal Scheduling Policies in Time Sharing Service Systems
- Learning Algorithm for 2×2 Stochastic Games with Incomplete Information
- 数理計画法研究会(RAMP)報告
- 正決定木によるデータ解析(組合せ最適化(1))
- 一般化2次割当問題に対する大規模近傍探索法の適用について(数理計画(1))
- 一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用(組合せ最適化)
- 多資源一般化割当問題に対する大規模近傍探索法の適用について(組合せ最適化)
- 時間枠制約付き配送計画問題に対する局所探索法の適用について(数理計画(3))
- 集合被覆問題に対する局所探索法について(数理計画(3))
- 経済指標データの論理的解析とその回帰分析への適用について(金融(1))
- 集合被覆問題に対する局所探索について(組合せ最適化(2))
- 種々のポートフォリオ選択問題と数値実験による考察(金融)
- メタ戦略のロバスト性について(メタ戦略(1))
- 組合せ最適化問題に対する遺伝的アルゴリズムの適用について(組合せ最適化)
- Extensions of Partially Defined Boolean Functions with Missing Data
- Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions
- 鎖パッキング問題について(アルゴリズムの数学的基礎理論とその応用)
- 無向グラフの第K最短単純路を求めるO(Kn2)アルゴリズム
- ミニマックス型目標関数をもつある巡回セ-ルスマン問題
- 数値データの論理的分析(組合せ最適化(3))
- 学会の法人化(「信頼性」Vol.30にあたり)
- OR発展への期待 : ORの先達からのメッセージ(OR : 21世紀に向けて)
- 機械故障を考慮したトランスファー・ラインの最適制御(待ち行列理論とその周辺)
- パケット交換システムにおける最適チャンネル割当政策(待ち行列理論とその周辺)
- 理論と実際のギャップ
- 中国訪問記
- 多品種流問題に対する主双対近接点法(グラフ・ネットワーク(1))
- 線形制約凸計画問題に対する主双対近接点法(数理計画)
- 無向グラフにおけるκ-辺分割問題の一般化について(組合せ最適化(3))
- データの論理的解析におけるルール集合の生成について(数理計画(1))
- データの論理的解析における階層的分解構造について(数理計画(1))
- データの論理的解析における分解構造について(情報・通信)
- ポートフォリオ選択問題における資産の収益率の確率順序(金融(1))
- 単調な変分不等式問題に対する近接点法(数理計画)
- アメリカン・コールオプションにおける権力行使時期の最適政策
- Nashの交渉ゲームにおけるKalai & Smorodinsky解に対するプレイヤーの危険回避性の影響(ゲーム理論)
- Optimal Scheduling for Multiple Servers Queueing Systems with Customer Deadlines II : Homogeneous Servers Case
- Optimal Scheduling for Multiple Servers Queueing Systems with Customer Deadlines I : Heterogeneous Servers Case
- Double Horn Functions
- Double Horn Functions
- データマイニングプロセスにおける属性の生成と選択について(マーケッティング)
- 特集にあたって (アルゴリズム工学)
- Interior and Exterior Functions of Positive Boolean Functions
- Optimal Visiting Policies in Symmentric Polling Systems
- 強単調な相補性問題に対するニュートン法(数理計画)
- A Globally Convergent Newton Method for Solving Monotone Variational Inequalities