カーマーカー法 - 版の履歴

2008年11月7日 (金) 05:54にAlbeit-Kunによる

2008-11-07T05:54:55Z

Orsjwiki: "カーマーカー法" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T23:09:17Z

"カーマーカー法" を保護しました。 [edit=sysop:move=sysop]

2007年7月11日 (水) 07:56に131.112.125.102による

2007-07-11T07:56:09Z

122.17.2.240: 新しいページ: ''''【かーまーかーほう (Karmarkar's algorithm)】''' 1984年にカーマーカーが提案した, 初めての内点法. 「$\mbox{min.} \ c^{\top}x \ \mbox{s. t.} ...'

2007-07-09T14:29:12Z

新しいページ: ''''【かーまーかーほう (Karmarkar's algorithm)】''' 1984年にカーマーカーが提案した, 初めての内点法. 「$\mbox{min.} \ c^{\top}x \ \mbox{s. t.} ...'

新規ページ

'''【かーまーかーほう (Karmarkar's algorithm)】'''

1984年にカーマーカーが提案した, 初めての内点法. 「$\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0$ ($A$は$m \times n$行列, $c \in \mbox{{\bf R}}^n$, $e \in \mbox{{\bf R}}^n$は要素がすべて$1$のベクトル)」の線形計画問題に対して, 「(1) $A$の階数は$m$, (2)$A(e/n)=0$, (iii)最適値は$0$」の仮定の下で, 初期点 $x^0 =e/n$ から最適解に収束する点列 $\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\}$ を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.

← 古い版		2008年11月7日 (金) 05:54時点における版
2行目:		2行目:

	1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.		1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.
		+
		+	[[Category:線形計画\|かーまーかーほう]]
		+
		+	[[Category:非線形計画\|かーまーかーほう]]

← 古い版		2007年7月11日 (水) 07:56時点における版
1行目:		1行目:
	'''【かーまーかーほう (Karmarkar's algorithm)】'''		'''【かーまーかーほう (Karmarkar's algorithm)】'''

−	1984年にカーマーカーが提案した, 初めての内点法. 「$\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0$ ($A$は$m \times n$行列, $c \in \~~mbox{~~{~~\bf~~ R}}^n$, $e \in \~~mbox~~{~~{\bf~~ R}}^n$は要素がすべて$1$のベクトル)」の線形計画問題に対して, 「(1) $A$の階数は$m$, (2)$A(e/n)=0$, (iii)最適値は$0$」の仮定の下で, 初期点 $x^0 =e/n$ から最適解に収束する点列 $\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\}$ を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.	+	1984年にカーマーカーが提案した, 初めての内点法. 「<math>\mbox{min.} \ c^{\top}x \ \mbox{s. t.} \ Ax = 0, \ e^{\top}x = 1, \ x \geq 0 \,</math> (<math>A \,</math>は<math>m \times n \,</math>行列, <math>c \in \mathbf{R}^n \,</math>, <math>e \in \mathbf{R}^n \,</math>は要素がすべて<math>1 \,</math>のベクトル)」の線形計画問題に対して, 「(1) <math>A \,</math>の階数は<math>m \,</math>, (2)<math>A(e/n)=0 \,</math>, (iii)最適値は<math>0 \,</math>」の仮定の下で, 初期点 <math>x^0 =e/n \,</math> から最適解に収束する点列 <math>\{x^k: \ Ax^k=0, \ e^{\top}x =1, \ x^k > 0\} \,</math> を生成する多項式時間解法. 任意の線形計画問題から, 上記の仮定を満す人工問題が生成でき, 元の問題の最適性が判定できる.

← 古い版	2007年7月19日 (木) 23:09時点における版
(相違点なし)