2次割当問題 - 版の履歴

2008年11月5日 (水) 07:12にAlbeit-Kunによる

2008-11-05T07:12:59Z

Orsjwiki: "2次割当問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T14:04:06Z

"2次割当問題" を保護しました。 [edit=sysop:move=sysop]

2007年7月17日 (火) 07:17に122.17.2.240による

2007-07-17T07:17:33Z

2007年7月12日 (木) 18:10に211.9.162.254による

2007-07-12T18:10:54Z

122.17.2.240: 新しいページ: '【にじわりあてもんだい (quadratic assignment problem (QAP))】目的関数が2次式となる割当問題のこと. 設置予定の工場$P_1, \ldots, P_n$とそ...'

2007-07-12T14:48:28Z

新しいページ: '【にじわりあてもんだい (quadratic assignment problem (QAP))】目的関数が2次式となる割当問題のこと. 設置予定の工場$P_1, \ldots, P_n$とそ...'

新規ページ

【にじわりあてもんだい (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次式$\sum_{i,j,k,\ell = 1}^n q_{ik} d_{j \ell} x_{ij} x_{k \ell}$となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.

← 古い版		2008年11月5日 (水) 07:12時点における版
2行目:		2行目:

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

← 古い版		2007年7月17日 (火) 07:17時点における版
1行目:		1行目:
−	【にじわりあてもんだい (quadratic assignment problem (QAP))】	+	'''【にじわりあてもんだい (quadratic assignment problem (QAP))】'''

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

← 古い版		2007年7月12日 (木) 18:10時点における版
1行目:		1行目:
	【にじわりあてもんだい (quadratic assignment problem (QAP))】		【にじわりあてもんだい (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次式$\sum_{i,j,k,\ell = 1}^n q_{ik} d_{j \ell} x_{ij} x_{k \ell}$となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.	+	目的関数が2次式となる割当問題のこと. 設置予定の工場<math>P_1, \ldots, P_n\,</math>とその場所候補<math>L_1, \ldots, L_n\,</math>が与えられており, 工場<math>P_i\,</math>, <math>P_k\,</math>間の輸送量が<math>q_{ik}\,</math>, 場所<math>L_j\,</math>, <math>L_{\ell}\,</math>間の距離が<math>d_{j \ell}\,</math>とするとき, 輸送の量と距離の積の総和を最小化する問題は, <math>P_i\,</math> を <math>L_j\,</math> に設置する際に1となる0-1変数 <math>x_{ij}\,</math> を導入すると, 割当問題の制約に対して目的関数は2次式<math>\sum_{i,j,k,\ell = 1}^n q_{ik} d_{j \ell} x_{ij} x_{k \ell}\,</math>となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.