コラム・特集

1.2 最適化問題の分類

IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第1章 最適化:概観

1.2 最適化問題の分類

最適化問題は目的関数と制約条件の性質によって分類される。図表14.1.1では,まず最初に,最適化問題が,決定変数の制約条件を含んでいるか否かによって分類されている。

明らかに,制約なし問題を解くのは制約条件つき問題よりやさしい。 制約なし問題は,さらに目的関数が1変数を含むか多変数を含むかによって分けられる。 制約なし問題の解法には,基本的に2つの重要なクラスが存在する直接探索法では,目的関数の値が各点で評価できれば十分である。この評価が実験によるものでもかまわない一方,勾配にもとづくほうでは,目的関数の数式とその導関数が必要となる。

制約条件つき問題の重要なクラスに線形計画法(14部第 2章参照)がある。これは目的関数と制約条件のいずれもが一次関数であることが必要である。すべての最適化モデルの中で,線形計画法モデルは最も広く利用され,現実問題に適用されている。非常に大きな線形計画法問題を解くための専門的に作られたソフトウエアが,すべての主要コンピュータ・メーカーにより提供されている。

他の最適化問題では,問題の構造に応じた特殊な解法が必要となるのだが,線形計画法では,すべての型の問題を解くのに,「シンプレックス法」と呼ばれる,ただ1つの共通アルゴリズムだけで十分である。この点は,線形計画法を実際問題に適用するに当たって,本質的にその成功に貢献してきたものと考えられる。整数計画法(14部第4章参照)は ,線形制約問題のもう1つの重要なクラスである。この問題では,決定変数のいくつかが離散的,すなわち整数値であるという制約がついている。

最適化問題の次のクラスは,非線形目的関数・線形制約問題である。このクラスには次のような問題が含まれる。

1.二次計画法一目的関数が二次関数である。
2.凸計画法一目的関数が “凸性”と呼ばれる重要な数学的性質を満足する特殊な非線形関数である。
3.分数線形計画法一目的関数が2つの線形関数の比で与えられている。

これらの問題を解くのには,それぞれの目的関数の特殊な形を利用した,専用アルゴリズムが用意されている。 もっとも一般的な最適化問題は非線形目的関数・非線形制約条件であり,普通,これを「非線形計画法」(14部第 3章参照)と呼んでいる。多くの工学における設計問題が,このクラスに入るのだが,残念なことに,すべてのり F線形計画問題を解くのに最良な単一解法は存在しない。そのため,一般非線形計画問題を解くための,多数のアルゴリズムが用意されている。これらのアルゴリズムは , 基本的には次の3つのクラスに分類できる。

1.変 換法―元の問題を一連の制約なし最適化問題に変換する。
2.線形近似法―問題中の非線形関数を折線線形近似により線形化する。
3.直接探索法―制約なし問題のときの直接探索法と同様に,目的関数と制約条件式が解析的な数式である必要はない。

一般的にいうと,その問題に関するより多くの情報を持っていれば(たとえば目的関数や制約条件式の解析的数式やその導関数),それを解くのに,さらに効率のよい速い解法を考え出すことができる。直接探索法のような情報の少なくてすむ方法は,一般には効率が悪く時間が多くかかる解法である。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー