コラム・特集

3.4 非線形計画問題のさまざまな形

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

第3章 非線形最適化


3.4 非線形計画問題のさまざまな形

もしある関数Z′(x)を,いくつかの制約条件のもとで最大化することが求められたとすれば,その問題はまた,同じ制約条件のもとでZ(x)=-Z′ (x)を最小化する問題と同値である。このように,どの最大化問題もそれと同値な最小化問題に置き替えることができるので,ここでは最小化に関するアルゴリズムだけを述べておく。

制約の無い最小化問題

目的関数:θ (x )一最小化                      (1)

線形等式制約つき最小化問題

目的関数:θ (x )    →  最小化

制約条件:Ax =b                               (2)

ここでAは与えられた階数mのm×n行列である。式(2)のn―n個の特定の許容解(x^1 ,… …,x^n-m  }を見つけることができる。すると,ある実数α1,・・・・,αn-mに対して式(2)のすべての許容解xはα1×1+・・・+αn-mx^n-m と表わすことができる。

と表わすことができる。この″の式をθ(″ )に代入すると,式(2)は αl,… …,α ″ _″ の関数 (″ 1,… … ,″ ″ ~″ は既知の点であるから)であるθ (α l′ :+… …十α”” χ “″ )の最小化問題に変換されたことになる。この方法を使えば,式121のような問題は,すべて制約条件無しの最小化アルゴリズムで解くことができる。

一般の線形制約つき非線形問題

目的関数:θ (x)     →          最小化
制約条件:                                   Ax=b
Dx≧d                                            (3)

ここで,A,b,D,dはそれぞれ与えられた, m×n , m×1,p×n,p×1の行列である。不等式制約の中に変数の上界が含まれている場合もある。

非線形等式制約の最適化問題

目的関数:θ (x)         →       最小化
制約条件:hi (x)=0,t=1からp,まで           (4)

hi(x)のうちで,少なくとも 1つは非線形である。さらに変数が有界である場合もある。

一般の非線形制約の非線形問題

目的関数:θ (x)            →                最小化
制約条件:gi,(x)≧0, i=1からmまで             (5)
hi (x)=0  i=1からpまで

非線形方程式を解く問題       ここでは連立方程式 ,

hi(x)=0,t=1からpまで                           (6)

を満足する点xを求めることを考える。ここで,hi(x ) のうち少なくとも1つ は非線形である。 通常は,p=πで , 変数の個数と同数の方程式が存在する。しかし ,時には , pくn(このような連立法方程式は 「不足決定系」と呼ばれる)や,p>n(このような連立方程式は「過剰決定系」と 呼ばれる )となることがある。問題(6)は次の制約無しの最小化問題 ,

ƒ(x)=∑[ht(x)]^2       → 最小化       (7)

と数学的には同値である 。もし問題 (6)が 許容解を持でぎ,その解が式(7)に対して最適となり,式(7) のƒ(x)の最小値はゼロである。もし式 (7)のƒ(x)の最小値がゼロよりも大ならば,問題(6)は許容解を持たない。逆に問題 (6)が許容解を持たないならば,式(7)のƒ(x)の最小値は 0よりも大きい式 (7)の最小値が正であったとしても ,その値が小さければ ,式(ηの最適解は問題 (0の近似解として使うことができる式 (7)を介して問題 (6)を解くのは,最小二乗法によるものである。実際上は,この手法は後に14.3.9節で述べるように十分なものではない。

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

関連記事一覧

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

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

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

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