quadratic assignment problemとは何？わかりやすく解説 Weblio辞書

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事典」の他の用語

組合せ最適化：

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.