最適化問題 - 版の履歴

2008年11月9日 (日) 09:00にAlbeit-Kunによる

2008-11-09T09:00:11Z

Tamura: 最小費用フロー問題，最大フロー問題（ネットワークフロー問題にはる），巡回セールスマン問題にリンクをはった

2008-08-22T06:55:28Z

最小費用フロー問題，最大フロー問題（ネットワークフロー問題にはる），巡回セールスマン問題にリンクをはった

Imahori: 基礎編と用語編のマージ

2008-03-13T13:34:27Z

基礎編と用語編のマージ

2007年8月8日 (水) 11:19にKanda.kによる

2007-08-08T11:19:04Z

Orsjwiki: "最適化問題" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:27:55Z

"最適化問題" を保護しました。 [edit=sysop:move=sysop]

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

2007-07-17T04:41:32Z

2007年7月12日 (木) 14:52に124.144.188.143による

2007-07-12T14:52:55Z

2007年7月12日 (木) 06:31に122.17.2.240による

2007-07-12T06:31:05Z

2007年6月28日 (木) 07:53に122.26.167.76による

2007-06-28T07:53:39Z

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

2007-06-27T02:28:55Z

新しいページ: ''''【さいてきかもんだい　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.

← 古い版		2008年11月9日 (日) 09:00時点における版
69行目:		69行目:

	[[Category:線形計画\|さいてきかもんだい]]		[[Category:線形計画\|さいてきかもんだい]]
		+
		+	[[Category:非線形計画\|さいてきかもんだい]]

← 古い版		2008年8月22日 (金) 06:55時点における版
58行目:		58行目:


−	が仮定され, 変数ベクトル <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> が線形（あるいは, 高々２次）関数である場合に限定することが多い. このように限定したとしても, 離散最適化問題には広範な応用がある. 個々の最適化問題は, それが定式化された元の（現実）問題と結びつけた名前で呼ばれることも多い. たとえば, 最小費用フロー問題, 最大フロー問題, 巡回セールスマン問題, グラフ分割問題等である. また, 上記の最適化問題に関する分類は厳密ではなく, 連続最適化と離散最適化の両方の特徴を共有する問題（たとえば, 施設配置問題, 線形混合整数計画問題）や, それらからはみ出た最適化問題も存在する.	+	が仮定され, 変数ベクトル <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行目: / 1行目: @@
 '''【さいてきかもんだい (optimization problem)】'''
 「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,
@@ 19行目: / 20行目: @@
 と表現される. ここで, <math>F \,</math> は <math>n \,</math> 次元ベクトル空間 <math>\mathbf{R}^n \,</math> の部分集合(実行可能集合)で,  <math>f \,</math> は <math>\mathbf{R}^n \,</math> で定義された実数値関数(目的関数).
-詳しくは[[《最適化問題》|基礎編：最適化問題]]を参照.

← 古い版		2007年8月8日 (水) 11:19時点における版
18行目:		18行目:

	と表現される. ここで, <math>F \,</math> は <math>n \,</math> 次元ベクトル空間 <math>\mathbf{R}^n \,</math> の部分集合(実行可能集合)で, <math>f \,</math> は <math>\mathbf{R}^n \,</math> で定義された実数値関数(目的関数).		と表現される. ここで, <math>F \,</math> は <math>n \,</math> 次元ベクトル空間 <math>\mathbf{R}^n \,</math> の部分集合(実行可能集合)で, <math>f \,</math> は <math>\mathbf{R}^n \,</math> で定義された実数値関数(目的関数).
		+
		+	詳しくは[[《最適化問題》\|基礎編：最適化問題]]を参照.

@@ 3行目: / 3行目: @@
 「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,
-<math>
+<table align="center">
- \mbox{s.t.} x = (x_1,x_2,\ldots,x_n) \in F,
+<tr>
-\,</math>
+<td><math>\mbox{max.} \, </math></td>
 と表現される. ここで, <math>F \,</math> は <math>n \,</math> 次元ベクトル空間 <math>\mathbf{R}^n \,</math> の部分集合(実行可能集合)で,  <math>f \,</math> は <math>\mathbf{R}^n \,</math> で定義された実数値関数(目的関数).

← 古い版	2007年7月20日 (金) 01:27時点における版
(相違点なし)

@@ 3行目: / 3行目: @@
 「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,
-\[
+<math>
- \begin{array}{llll}
+  \mbox{max.} f(x)  \ \,</math>(あるいは, min. <math>f(x) \,</math>)
-と表現される. ここで, $F$ は $n$ 次元ベクトル空間 ${\bf R}^n$ の部分集合(実行可能集合)で,  $f$ は ${\bf R}^n$ で定義された実数値関数(目的関数).
+<math>

@@ 1行目: / 1行目: @@
-'''【さいてきかもんだい　optimization problem）】'''
+'''【さいてきかもんだい (optimization problem)】'''
 　[[最適化問題]] （optimization problem）（[[数理計画問題]]）は, 「与えられた制約条件の下でより良い目的を達成するための数理モデル」で, 数学的には,
@@ 17行目: / 17行目: @@
-* <math>S = \mathbf {R}^n</math>（より一般的には, <math>S\, </math> は <math>\mathbf {R}^n</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>g_i (i=1,2,\ldots,m)</math> は連続（多くの場合, 微分可能）
@@ 24行目: / 24行目: @@
-* <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>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>（離散無限集合）.