本稿では、ファジィの考え方に基づいた曖昧性を線形計画法（LP）に組み込む方法について紹介します。
線形計画法は次のような問題。
この線形計画法では、少なくとも単点に最適解がある（もし最適解があるならば）という性質があります。 すなわち、得られた最適解はいくつかの制約をタイトに成立させるものになっているということです。 これは定式化した側から見れば、条件ギリギリの解が得られるわけなので、言い換えると、それは極端な解であると捉えることもできます。 (例えば予算内で栄養基準を満たす野菜を購入する問題を解いて、人参ばっかり購入するような解がでたり。)
また、制約を作るさいに、その制約を曖昧にしたい場合もあります。例えばx + y <= 100という制約にしたけれども、本当はx + y <= 110でもまぁ許容できなくもないかなぁ、という場合。
このような、極端な解を避けたい、もしくは曖昧な制約を表現したい、その場合にこれから紹介するファジィLPの考え方が役に立ちます。
問題例
本稿で扱う問題例をこちらから引用させていただきました。
http://www.fujilab.dnj.ynu.ac.jp/lecture/system2.pdf
ハンバーグの生産量 x1、オムレツの生産量 x2 目的関数が売上の合計、それぞれの料理に必要な食材は次の3種類でその量には上限があるので、 料理の生産量には次のように制約がつけられます。 最小化 z = −400x1 − 300x2 (1) 制約条件 60x1 + 40x2 ≤ 3800 ひき肉の制約式 20x1 + 30x2 ≤ 2100 タマネギの制約式 20x1 + 10x2 ≤ 1200 ケチャップの制約式 x1 ≥ 0, x2 ≥ 0
floptでモデリングするとこう。
import flopt x1 = flopt.Variable("x1", lowBound=0) x2 = flopt.Variable("x2", lowBound=0) prob = flopt.Problem(sense="Maximize") prob += 400 * x1 + 300 * x2 prob += 60 * x1 + 40 * x2 <= 3800 prob += 20 * x1 + 30 * x2 <= 2100 prob += 20 * x1 + 10 * x2 <= 1200
最適解を確認すると
prob.solve() print("obj", prob.getObjectiveValue()) for var in prob.getVariables(): print(var.name, "=", var.value()) for const in prob.getConstraints(): print(const.expression.name, "=", const.value())
obj 27000.0 x1 = 30.0 x2 = 50.0 60*x1+40*x2-3800 = 0.0 20*x1+30*x2-2100 = 0.0 20*x1+10*x2-1200 = -100.0
こんな感じで、最適解は(x1, x2) = (30, 50)、 目的関数値は-27000、一つ目と二つ目の制約がタイトになっています。
ファジィによる緩和
ここで、例えば、ひき肉は本当は3500までの使用量にとどめたいけど、頑張れば3800までは使える、という状況だとします。 その3500まではokでそれ以上3800以下は渋々しょうがないかな、というのを次のような帰属度関数を用いて表します。
数式にするとこう。1であれば完全に制約を満たした状態、0であれば完全に制約を満たしていない状態、それ以外は制約を曖昧に満たしている状態を表しています。
またひき肉の制約を厳しくする分だけ目的関数が悪くなるわけですが、元の問題の最適値27000.0と比べて25000以上でなるべく売り上げを保ちたいということを同様に帰属度で表現します。
そしてその帰属値が全体で高くなるように目的関数を設定します。ここでは最小の帰属値が最大になるようにしてみましょう。
この二つの制約を満たしたままなるべく変数rを大きくします。
最大化 r 制約条件 r <= 1 - (60x1 + 40x2 - 3500) / 300 r <= 1 - (27000 - (400x1 + 300x2)) / 2000 20x1 + 30x2 ≤ 2100 タマネギの制約式 20x1 + 10x2 ≤ 1200 ケチャップの制約式 x1 ≥ 0, x2 ≥ 0
floptでモデリングをするとこう。
import flopt x1 = flopt.Variable("x1", lowBound=0) x2 = flopt.Variable("x2", lowBound=0) r = flopt.Variable("r", lowBound=0, upBound=1) prob = flopt.Problem(sense="Maximize") prob += r prob += r <= 1 - (60*x1 + 40*x2 - 3500) / 300 prob += r <= 1 - (27000 - (400*x1 + 300*x2)) / 2000 prob += 20 * x1 + 30 * x2 <= 2100 prob += 20 * x1 + 10 * x2 <= 1200
解を確認
prob.solve() print("obj", prob.getObjectiveValue()) for var in prob.getVariables(): print(var.name, "=", var.value())
obj 0.5263157894736846 x2 = 53.157894736842096 x1 = 25.263157894736853 r = 0.5263157894736846
r = 0.52...となりました。目的関数値とひき肉の使用量は
print((400*x1 + 300*x2).value()) print((60*x1 + 40*x2).value())
26052.63157894737 3642.105263157895
ということで目的関数値は27000 → 26052.63...、ひき肉の使用量は3800 → 3642.10...となりました。元々の目的関数値をそれほど変わらずにひき肉の使用量を減らすような結果を取得できています。
まとめ
本稿ではファジィLPを用いて制約や目的関数を曖昧に表現する方法とfloptを用いたサンプルコードを紹介しました。
floptについて
