2次割当問題とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 2次割当問題の意味・解説 

2次割当問題

読み方にじわりあてもんだい
【英】:quadratic assignment problem (QAP)

目的関数2次式となる割当問題のこと. 設置予定工場P_1, \ldots, P_n\,その場候補L_1, \ldots, L_n\,与えられており, 工場P_i\,, P_k\,間の輸送量q_{ik}\,, 場所L_j\,, L_{\ell}\,間の距離がd_{j \ell}\,とするとき, 輸送の量と距離の積の総和最小化する問題は, P_i\,L_j\,設置する際に1となる0-1変数 x_{ij}\,導入すると, 割当問題制約に対して目的関数2次式\textstyle \sum_{i,j,k,\ell = 1}^n q_{ik} d_{j \ell} x_{ij} x_{k \ell}\,となる. 巡回セールスマン問題施設配置問題などの多くNP困難問題が, 2次割当問題に帰着できる.

「OR事典」の他の用語
組合せ最適化:  0-1整数計画  2次割当問題  AVL木  NP困難  TDI性  アルゴリズム  オンラインアルゴリズム



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「2次割当問題」の関連用語

2次割当問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



2次割当問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2024 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2024 GRAS Group, Inc.RSS