研究紹介 (山田 修司)
研究テーマ: 非線形計画問題に対する逐次近似解法

1最適化問題

最適化問題は, 自然科学, 工学, 社会科学などの分野で発生する基本的な問題の1 つであり, 政府機関の政策決定や企業における経営方針決定などの現実社会で生じる意思決定問題に対する科学的アプローチとして重要な役割を果たしています。
例えば, 企業経営においては, 売れる製品を設計して製造することが重要であるが,その他にも次の問題にも注意しなければなりません。

(1) 品切れや売れ残りを最小にする。
(2) 商品の保管費・流通経費を最小にする。
したがって, 上記のような最適化問題を解くことによって, 的確な意思決定方針を企業に提案することができます。また, 多くの最適化問題は数理モデルで表わすことができ, 数理モデルで表わされた問題は数理計画問題と呼ばれます。数理計画問
題の中で, すべての関数が線形関数で表わされる問題は線形計画問題と呼ばれ, 一方, 1 つでも線形でない関数 (非線形関数) が含まれている問題は非線形計画問題は呼ばれます。一般に, 非線形計画問題は線形計画問題に比べて解くのが難しいものとされています。私達の研究室では, 非線形計画問題に対する解法について研究しています。

2非線形計画問題
ここでは, 次の例を用いて非線形計画問題を説明します。

1例



ある電力会社は，所有する 2 台の発電機 G1 , G2 を用いてその地区で必要とする電力 100 MW を発生している。それぞれの発電機は, 発電方式（石油火力,石炭火力）, 規模, 建設時期が異なるため, 発電に要する燃料費の特性も発電機ごとに異なっている。したがって, その発電機にどれだけの発電すべき負荷を割り当てるかによって, 発電に要する総燃料費は変化する。
単位時間当たりの発電機 G1 , G2 の出力をそれぞれ x1 , x2 MW とする。このとき, 発電機 G1 , G2 の燃料費はそれぞれ x1 , x2 を変数とする関数 f1 (x1 ), f2 (x2 )として, 次のように与えられる。

f1 (x1 ) = 9x21 + 4x1 + 3f2 (x2 ) = x22 + 4x2 + 7[千円/MW · h]

また, 各出力 x1 , x2 に対して, 最低出力値と最大出力値が次のように与えられているものとする。
0.3 5 x1 5 0.8

0.2 5 x2 5 0.7
電力会社としては, 総燃料費を最小にしたいので, 次の問題を考える。
問題: 総燃料費を最小にするには, 発電機 G1 , G2 の出力 x1 , x2 をどのように決定すればよいか。

※ 上記例は参考文献 [3] を参照していますが, 目的関数の係数等の数値は変更しています。
上記例の問題は次の数理モデルで表わすことができます。
目的関数 f (x1 , x2 ) = f1 (x1 ) + f2 (x2 )
= 9x21 + 4x1 + x22 + 4x2 + 10 → 最小化
制約条件 x1 + x2 = 1
0.3 5 x1 5 0.8





0.2 5 x2 5 0.7
上記モデルは, 目的関数が非線形な関数 (一次式ではない関数) で表わされているので, 非線形計画問題と呼ばれます。ここで, すべての制約条件を満たす (x1 , x2 )は上記モデルの実行可能解と呼ばれ, 実行可能解の集合, すなわち, S = {(x1 , x2 ) :x1 + x2 = 1, 0.3 5 x1 5 0.8, 0.2 5 x2 5 0.7} は上記モデルの制約集合 (または,2実行可能領域) と呼ばれます。また, 上記モデルを解決する実行可能解, すなわち,S 上で目的関数の値を最小にする (x1 , x2 ) は最適解と呼ばれます。

3

解析的な解法

ここでは, 前章で考えた数理モデルの最適解を解析的に求めてみます。
まず, 制約集合 S は変数 λ (0 5 λ 5 1) を用いて次のように表わすことができます。
S = {(0.3λ + (1 − λ)0.8, 0.7λ + (1 − λ)0.2) : 0 5 λ 5 1}
次に, 目的関数の x1 に 0.3λ + (1 − λ)0.8, x2 に 0.7λ + (1 − λ)0.2 を代入します。

f (x1 , x2 )= 9x21 + 4x1 + x22 + 4x2 + 10
= 9(0.3λ + (1 − λ)0.8)2 + 4(0.3λ + (1 − λ)0.8) + (0.7λ + (1 − λ)0.2)2+ 4(0.7λ + (1 − λ)0.2) + 10= 2.5λ2 − 7λ + 19.8
ここで, F (λ) = 2.5λ2 − 7λ + 19.8 とすると, この関数の導関数は, F ′ (λ) = 5λ − 7となります。したがって, 0 5 λ 5 1 の範囲で F ′ (λ) < 0 となるので, λ = 1 のとき, 関数 F (λ) は最小値 15.3 をとります。また, 最適解は x1 = 0.3, x2 = 0.7 となります。すなわち, 発電機 G1 では 0.3 MW, G2 では 0.7 MW の電力を発電すれば, 燃料費が最小になります。

4

図による解法

まずは, 制約集合を考えます。制約集合 S は図 1 のように, 直線 x2 = −x1 + 1上にあり, 点 (0.3, 0.7) と (0.8, 0.2) を結んだ線分と一致します。
次に, 目的関数 f (x1 , x2 ) の等高線を考えます。制約条件 x1 + x2 = 1 より x2 =−x1 + 1 が得られるので, 目的関数 f (x1 , x2 ) の x2 に −x1 + 1 を代入すると次式を得ます。

f (x1 , x2 ) = 9x21 + 4x1 + x22 + 4x2 + 10
= 9x21 + 4x1 + (−x1 + 1)2 + 4(−x1 + 1) + 10
= 10x21 − 2x1 + 153

図 1: 制約集合 S

表 1: 関数 g の増減表
x10.1′g (x1 ) −0+g(x1 ) ↘ 極小 ↗
ここで, g(x1 ) = 10x21 − 2x1 + 15 とすると, 導関数 g ′ (x1 ) = 20x1 − 2 は x1 = 0.1
で g ′ (x1 ) = 0 となります。さらに, 関数 g の増減表は次のとおりです。
よって, 直線 x2 = −x1 + 1 上で, 目的関数 f (x1 , x2 ) は点 (x1 , x2 ) = (0.1, 0.9) において最小となり, そのときの目的関数値は 14.9 となります。これは, 図 2 のように, 目的関数 f (x1 , x2 ) = 14.9 の等高線が直線 x2 = −x1 + 1 に 点 (0.1, 0.9) で接することを意味します。
しかしながら, 点 (0.1, 0.9) は制約集合 S に含まれていません。そこで, 制約集
合 S 上で目的関数 f (x1 , x2 ) の等高線を考えると, (0.3, 0.7) で最小の関数値の等高線と交わります。したがって, この問題の最適解は x1 = 0.3, x2 = 0.7 であることがわかります。

5

おわりに

ここでは, 2 章の例で与えられた非線形計画問題に対して, 3, 4 章で解析的な手法や図を使って最適解を求める方法を説明しました。しかし, 変数の数がもっと多かったり, 目的関数や制約条件が複雑な場合 (次数が大きかったり, 三角関数や対数を含んでいる場合), このような方法では最適解を求めることは困難であるため,コンピュータを使って最適解を求めることを試みます。コンピュータは与えられた命令を繰り返す計算しかできませんので, 最適解を求めるためには対象問題に適した計算手順 (アルゴリズム) が必要になります。そこで, 私達の研究室では,

4

図 2: 図による解法

1. 既存のアルゴリズムでは解けない非線形計画問題に対するアルゴリズムの開発,
2. 既存のアルゴリズムよりも高速な新たなアルゴリズムの開発の研究を行っています。

参考文献[1] 栗原謙三, 明石吉三: 経営情報処理のためのオペレーションズ・リサーチ, コロナ社, 2000.
[2] 近藤次郎: オペレーションズ・リサーチ, 日科技連, 1973.
[3] 玉置久: システム最適化, オーム社, 2005.
[4] 田村明久, 村松正和: 最適化技法, 共立出版株式会社, 2002.
[5] 福島雅夫: 非線形最適化の基礎, 朝倉書店, 2001.
[6] 矢部博, 八卷直一: 非線形計画法, 朝倉書店, 1999.
[7] 矢部博: 工学基礎 最適化とその応用, 数理工学社, 2002.

5