《最適化問題》 - 版の履歴

2007年7月25日 (水) 04:50にOrsjwikiによる

2007-07-25T04:50:08Z

2007年7月24日 (火) 05:25にOrsjwikiによる

2007-07-24T05:25:35Z

2007年7月24日 (火) 05:23にOrsjwikiによる

2007-07-24T05:23:05Z

2007年7月24日 (火) 05:21にOrsjwikiによる

2007-07-24T05:21:01Z

Orsjwiki: "《最適化問題》" を保護しました。 [edit=sysop:move=sysop] [カスケード]

2007-07-19T12:48:42Z

"《最適化問題》" を保護しました。 [edit=sysop:move=sysop] [カスケード]

2007年7月14日 (土) 09:56にOrsjwikiによる

2007-07-14T09:56:56Z

Orsjwiki: 新しいページ: ''''【さいてきかもんだい (optimization problem)】''' 　最適化問題（optimization problem）（数理計画問題）は, 「与えられた制約条件...'

2007-07-03T07:48:10Z

新しいページ: ''''【さいてきかもんだい (optimization problem)】''' 　最適化問題（optimization problem）（数理計画問題）は, 「与えられた制約条件...'

新規ページ

'''【さいてきかもんだい (optimization problem)】'''

　[[最適化問題]] （optimization problem）（[[数理計画問題]]）は, 「与えられた制約条件の下でより良い目的を達成するための数理モデル」で, 数学的には,

: <math>\mbox{max.} \quad f(x) \mbox{(}</math>あるいは, <math>\mbox{min.}\quad f(x))</math>
: <math>\mbox{s.t.} \quad\quad x = (x_1,x_2,\ldots,x_n) \in F,</math>

のように表現される. ここで, <math>F\, </math> は <math>n\, </math>次元ベクトル空間 <math>\mathbf {R}^n</math>の部分集合で[[実行可能集合]]（feasible region）（[[許容集合]]）と呼ばれ,<math>f\, </math> は <math>\mathbf {R}^n</math> で定義された実数値関数で[[目的関数]]（objective function）と呼ばれる. また, <math>x \in F</math> を[[実行可能解]]（[[許容解]]）, 実行可能解の中で目的関数の最大（あるいは, 最小）を達成する<math>x\, </math>を[[最適解]]（optimal solution）と呼ぶ. 実行可能集合 <math>F\, </math> は,

: <math>F = \{ x \in S : g_i(x) \leq 0 \ (i=1,2,\ldots,m) \}</math>

のように表現されることが多い. ただし, <math>g_i\, </math> は <math>\mathbf {R}^n</math> で定義された実数値関数である. また, <math>S\, </math> は対象とする最適化問題を記述するのに用いられる基礎となる空間と考えればよい. 基礎となる空間 <math>S\, </math>, 実行可能領域 <math>F\, </math> を表現するのに使われる関数 <math>g_i (i=1,2,\ldots,m),</math> および, 目的関数 <math>f\, </math> に種々の条件を課した多くのクラスの最適化問題が研究されている. 最適化問題は,

:* <math>S = \mathbf {R}^n</math>（より一般的には, <math>S\, </math> は <math>\mathbf {R}^n</math> の開集合）
:* 関数 <math>g_i (i=1,2,\ldots,m)</math> は連続（多くの場合, 微分可能）

が仮定され, 変数ベクトル <math>x\, </math> が連続的な値をとる[[連続最適化問題]]（continuous optimization problem）と,

:* <math>S\, </math> は有限集合, または, 離散的な集合, たとえば, <math>S = \{ x \in \mathbf {R}^n : x_j = 0</math> または <math>\mathrm{1}\, </math><math>\}\, </math>（有限集合）, <math>S =\, </math> あるグラフの部分グラフの集まり（有限集合）, <math>S = \{ x \in \mathbf {R}^n : x_j =</math> 自然数<math>\}\, </math>（離散無限集合）.

が仮定され, 変数ベクトル <math>x\, </math> が離散的な値をとる[[離散最適化問題]]（discrete optimization problem）に, 大きく分けることができる. 関数 <math>f, \ g_i (i=1,2,\ldots,m)</math> に連続性（あるいは, 微分可能性）のみを仮定する非線形離散最適化問題のクラスも考えることができるが, そのような問題は非常に難しく, 関数 <math>f, \ g_i (i=1,2,\ldots,m)</math> が線形（あるいは, 高々２次）関数である場合に限定することが多い. このように限定したとしても, 離散最適化問題には広範な応用がある. 個々の最適化問題は, それが定式化された元の（現実）問題と結びつけた名前で呼ばれることも多い. たとえば, 最小費用フロー問題, 最大フロー問題, 巡回セールスマン問題, グラフ分割問題等である. また, 上記の最適化問題に関する分類は厳密ではなく, 連続最適化と離散最適化の両方の特徴を共有する問題（たとえば, 施設配置問題, 線形混合整数計画問題）や, それらからはみ出た最適化問題も存在する.

----

'''参考文献'''

[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.

← 古い版		2007年7月25日 (水) 04:50時点における版
47行目:		47行目:
	[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.		[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.

−	[[Category:線形計画\|~~せんけいけいかく~~]]	+	[[Category:線形計画\|さいてきかもんだい]]

← 古い版		2007年7月24日 (火) 05:25時点における版
47行目:		47行目:
	[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.		[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.

−	[[Category:線形計画\|~~０１．線形計画~~]]	+	[[Category:線形計画\|せんけいけいかく]]

← 古い版		2007年7月24日 (火) 05:23時点における版
47行目:		47行目:
	[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.		[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.

−	[[Category:線形計画\|~~１．線形計画~~]]	+	[[Category:線形計画\|０１．線形計画]]

← 古い版		2007年7月24日 (火) 05:21時点における版
46行目:		46行目:

	[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.		[1] 福島雅夫, 『数理計画法入門』, 朝倉書店, 1996.
		+
		+	[[Category:線形計画\|１．線形計画]]

@@ 4行目: / 4行目: @@
-: <math>\mbox{max.}  \quad  f(x)   \mbox{(}</math>あるいは, <math>\mbox{min.}\quad f(x))</math>
+<table align="center">
-: <math>\mbox{s.t.} \quad\quad x = (x_1,x_2,\ldots,x_n) \in F,</math>
+<tr>
@@ 11行目: / 17行目: @@
-: <math>F = \{ x \in S : g_i(x) \leq 0 \ (i=1,2,\ldots,m) \}</math>
+<table align="center">

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