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

=== 概要 ===
「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,

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

と表現される. ここで, <math>F \,</math> は <math>n \,</math> 次元ベクトル空間 <math>\mathbf{R}^n \,</math> の部分集合(実行可能集合)で, <math>f \,</math> は <math>\mathbf{R}^n \,</math> で定義された実数値関数(目的関数).

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

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

のように表現される. ここで, <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> は,

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

のように表現されることが多い. ただし, <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.

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

基礎編：項目一覧

2008-08-22T06:44:51Z

Tamura: /* 線形計画 */

===線形計画===

[[最適化問題]]　[[線形計画]]　[[単体法]]　[[楕円体法]]　[[内点法]]　[[半正定値計画]]

=== 非線形計画 ===

[[《非線形計画》]]　[[《最適性条件》]]　[[《双対性理論》]]　[[《制約なし最適化》]]　[[《制約付き最適化》]]　[[《大域的最適化》]]　[[《相補性問題》]]　[[《大規模問題の分解法》]]　[[《凸解析》]]　[[《高速微分法》]]　[[《多項式最適化問題》]]

=== 組合せ最適化 ===

[[《整数計画》]]　[[《組合せ最適化問題》]]　[[《多面体理論》]]　[[《アルゴリズム》]]　[[《データ構造》]]　[[《計算の複雑さ》]]　[[《パーフェクトグラフ》]]　[[《グレブナー基底》]]

===グラフ・ネットワーク===

[[《グラフ・ネットワーク》]]　[[《グラフの連結度》]]　[[《最短路問題》]]　[[《最小木問題》]]　[[《巡回セールスマン問題》]]　[[《ネットワーク・フロー問題》]]　[[《マッチング問題》]]　[[《マトロイド》]]　[[《劣モジュラ最適化》]]　[[《離散凸解析》]]　[[《複雑ネットワーク》]]

===スケジューリング===

[[《スケジューリング理論》]]　[[《スケジューリング問題》]]　[[《スケジューリングアルゴリズム》]]

===計算幾何===

[[《凸多面体》]]　[[《アレンジメント》]]　[[《ボロノイ図》]]　[[《三角形分割》]]　[[《幾何グラフ》]]　[[《バケット法》]]　[[《双対変換》]]　[[《木》]]　[[《ランダマイゼーション》]]　[[《ロバスト化技術》]]　[[《計算幾何学》]]

===動的・確率・多目的計画===

[[《動的計画》]]　[[《両的計画》]]　[[《多段確率決定樹表(ツリーテーブル)》]]　[[《不変埋没原理》]]　[[《多目的計画》]]　[[《最適停止》]]　[[《確率計画》]]　

===近似・知能・感覚的手法===

[[《近似アルゴリズム（ヒューリスティックアルゴリズム）》]]　[[《メタヒューリスティクス》]]　[[《ファジイ理論》]]　[[《ソフトコンピューティング》]]
[[《ラフ集合》]]　[[《ファジィランダム変数》]]
[[《ニューラルネットワーク》]]　[[《制約充足問題》]]　[[《人工知能》]]　[[《論理プログラミング》]]　[[《サポート・ベクター・マシン》]]

===ゲーム理論===

[[《ゲーム理論》]]　[[《非協力ゲーム理論》]]　[[《戦略形ゲーム》]]　[[《展開形ゲーム》]]　[[《進化と学習のゲーム理論》]]　[[《協力ゲーム理論》]]　[[《交渉ゲーム》]]　[[《提携形ゲーム》]]　[[《ゲームと実験》]]　[[《ゲーム理論の応用》]]　[[《ゲームの解の計算》]]　[[《生物学における進化ゲーム理論》]]

===確率と確率過程===

[[《確率論》]]　[[《確率過程》]]　[[《マルコフ連鎖》]]　[[《ポアソン過程と出生死滅過程》]]　[[《ランダム・ウォークとブラウン運動》]]　[[《マルコフ決定過程》]]　[[《マルコフ連鎖の数値解法》]]

===統計===

[[《回帰分析》]]　[[《クラスター分析》]]　[[《判別関数》]]　[[《多次元尺度構成法》]]　[[《数量化法》]]　[[《多変量解析》]]

===予測===

[[《予測》]]　[[《指数平滑法》]]　[[《季節調整法》]]　[[《自己回帰和分移動平均(ARIMA)モデル》]]　[[《カルマンフィルター》]]　[[《非集計行動モデル》]]　[[《生態学モデル》]]　[[《バス(Bass)モデル》]]
[[《複雑系による予測モデル》]]

===シミュレーション===

[[《シミュレーション》]]　[[《離散型シミュレーション》]]　[[《モンテカルロ法》]]　[[《一様乱数》]]　[[《非一様乱数》]]　[[《離散型シミュレーションの統計的側面》]]　[[《シミュレーションソフトウェア》]]　[[《シミュレーションモデルの検証》]]　[[《ペトリネット》]]

===待ち行列===

[[待ち行列モデル|《待ち行列》]]　[[《待ち行列モデルの標準形》]]　[[《待ち行列の各種モデル》]]　[[待ち行列モデル M/M/c]]　[[《待ち行列における関係式》]]　[[待ち行列モデル M/G/1]]　
[[《待ち行列に対するアルゴリズム的解法》]]
[[待ち行列のバケーションサーバモデル]]　[[《待ち行列における近似》]]　[[《待ち行列における希少事象の評価》]]　[[《待ち行列の極限モデル（流体近似と拡散近似）》]]

===待ち行列ネットワーク===

[[待ち行列ネットワーク]]　[[ジャクソンネットワーク|《待ち行列ネットワーク(ジャクソン型とその応用)》]]　[[BCMPネットワーク|《待ち行列ネットワーク(BCMP型とその応用)》]]　
[[《積形式解ネットワークとなるための条件》]]　[[《待ち行列ネットワークの近似解析》]]　[[《待ち行列ネットワークの安定性》]]

===待ち行列の応用===

[[待ち行列の通信への応用]]　[[待ち行列のコンピュータへの応用]]　[[待ち行列の生産システムへの応用]]

===信頼性・保全性===

[[《信頼性》]]　[[《寿命分布》]]　[[《保全性》]]　[[《予防保全》]]　[[《システムの安全性》]]　[[《故障データ解析》]]　[[《ベイズ信頼性》]]　[[《システムの信頼性》]]　[[《フォールトトレランス》]]　[[《ソフトウェア信頼性》]]

===探索理論===

[[《探索理論》]]　[[《目標存在分布の推定》]]　[[《センサーの探知論》]]　[[《探索モデルと探索の運動学》]]
[[《静止目標物の最適探索》]]
[[《移動目標物の最適探索》]]
[[《探索ゲーム》]]
[[《ランデブー探索》]]
[[《探索理論の応用と実例》]]

===経営・経済性工学===

[[《経営戦略》]]　[[《経営モデル》]]　[[《分権管理》]]　[[《経営意思決定》]]　[[《利益計画》]]　[[《経営分析》]]　[[《間接費管理》]]　[[《経済計算》]]　[[《投資案件の評価》]]　[[《財務管理》]]　[[《企業価値評価》]]

===マーケティング===

[[《マーケティング概説》]]　[[《マーケティングモデル》]]　[[《マーケティング・リサーチ》]]

===生産・在庫・ロジスティクス===

[[《生産管理》]]　[[《JIT生産システム》]]　[[《ラインバランシング》]]　[[《在庫管理》]]　[[《経済発注量モデル(EOQモデル)》]]　[[《動的ロットサイズ決定問題》]]　[[《ロットスケジューリング》]]　[[《ロジスティクス》]]　[[《運搬経路問題(配送計画問題, トラック配送問題, 配送問題, 輸送経路問題)》]]　[[《施設配置問題》]]　[[《ロジスティクスネットワーク設計問題》]]
[[《APS》]]

===企画・開発・プロジェクト・品質・ヒューマン===

[[《製品企画開発》]]　[[《研究開発》]]　[[《プロジェクト管理》]]　[[《総合的品質管理》]]　[[《QC手法》]]　[[《人的資源管理》]]　[[《勤務スケジューリング》]]

===ファイナンス===

[[《モダンポートフォリオ理論(概論)》]]　[[《資産評価理論》]]　[[《企業財務》]]　[[《資産運用モデル》]]　[[《株価変動モデル》]]　[[《証券市場モデル》]]　[[《金利変動モデルと債券価格》]]　[[《金融派生証券(デリバティブ)(概論)》]]　[[《デリバティブ評価モデル》]]
[[《行動ファイナンス》]]
[[《証券化》]]
[[《倒産確率の推計》]]
[[《リアルオプション》]]
[[《CAPM》]]
[[《無裁定価格理論》]]

===公共システム===

[[《選挙制度》]]　[[《議員定数配分問題》]]　[[《投票理論》]]　[[《公共政策OR-I》]]　[[《公共政策OR-II》]]　[[《産業連関分析》]]　[[《エネルギー・環境政策》]]　[[《軍事モデル》]]

===都市システム===

[[《積分幾何学》]]　[[《都市構造分析》]]　[[《地理的最適化》]]　[[《ウォードロップの原理》]]　[[《地域間相互作用モデル》]]　[[《ODの調査》]]　[[《地理情報システム》]]

===システム分析・意思決定支援・特許===

[[《システム分析》]]　[[《リエンジニアリング》]]　[[《意思決定支援システム》]]　[[《効用関数》]]　[[《データマイニング》]]　[[《過程決定計画図》]]　[[《発想法》]]　[[《モデル管理》]]　[[《アルゴリズム特許》]]
[[《モデリング》]]

===AHP(階層的意思決定法)===

[[《AHP》]]　[[《AHP一対比較法》]]　[[《AHP重要度算出法》]]　[[《AHP整合性尺度》]]　[[《拡張型AHP》]]　[[《AHP重要度評価法》]]　[[《グループAHP》]]　[[《ANP》]]　[[《AHPの諸問題》]]　[[《大規模AHP》]]　[[《AHPの誤差》]]　[[《AHPの理論的解釈》]]

===DEA(包絡分析法)===

[[《DEA(包絡分析法)》]]　[[《CCRモデル》]]　[[《BCCモデル》]]　[[《効率性》]]　[[《規模の収穫》]]　[[《SBMモデル》]]