2次割当問題

【にじわりあてもんだい (quadratic assignment problem (QAP))】

目的関数が2次式となる割当問題のこと. 設置予定の工場$P_{1},\ldots ,P_{n}\,$とその場所候補構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L_1, \ldots, L_n\,} が与えられており, 工場$P_{i}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P_k\,} 間の輸送量が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle q_{ik}\,} , 場所$L_{j}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L_{\ell}\,} 間の距離が$d_{j\ell }\,$とするとき, 輸送の量と距離の積の総和を最小化する問題は, $P_{i}\,$ を $L_{j}\,$ に設置する際に1となる0-1変数 $x_{ij}\,$ を導入すると, 割当問題の制約に対して目的関数は2次式$\sum _{i,j,k,\ell =1}^{n}q_{ik}d_{j\ell }x_{ij}x_{k\ell }\,$となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.