【エンジニア向け】文系出身エンジニアが数理最適化の本を読んでみた1-基礎編

今回は、タイトルにあるように数理最適化の本を読んでみたら、意外と面白かったので記事にしました。

※前提として、筆者は数学初心者です、同じく数学初心者向けに、私なりに分かりやすく記載する都合上、厳密には違うとか、おかしいなどツッコミがあるかもしれません。なので数理最適の入り口の情報として使ってください。

私のように文系出身のエンジニアの方は、数学という言葉を聞いただけでアレルギーが出て、勉強する意欲がなくなってしまうかもしれません。

しかし、以下の本を読んで、勉強しているのですが文系出身の私でも割と楽しく読めています

あたらしい数理最適化 Python言語とGurobiで解く [ 久保幹雄 ]

価格:3,520円
(2021/9/22 00:06時点)
感想(0件)

というのも、難しい数学の話を理解していなくても分かるような内容だからです。

どういうことなのか?

それは何か解決したい問題があるときに、難しい数式を使うようなアルゴリズムを組む必要がない、ということです。そのため、数学は分からないけど、エンジニア歴がある人なら割と理解しやすいと感じました。

この本では、「Gurobi」というプログラムのライブラリの使い方が説明されています。

例えば、こんな問題がある時に、

「Gurobi」を使って、こんなふうにプログラムを書けば解決できるという例が載っています。

from gurobipy import
model = Model("lo1")
x1 = model.addVar(name="x1")
x2 = model.addVar(name="x2")
x3 = model.addVar(ub=30, name="x3")
model.update()
model.addConstr(2*x1 + x2 + x3 <= 60)
model.addConstr(x1 + 2*x2 + x3 <= 60)
model.setObjective(15*x1 + 18*x2 + 30*x3, GRB.MAXIMIZE)
model.optimize()
print "Opt. Value=", model.ObjVal
for v in model.getVars():
  print v.VarName, v.X

すみません、ブラウザバックするのを少し待ってください・・・笑

分かります、この数式と、pythonコードを見て、なるほどー!と思う文系出身のエンジニアはいないと思います

(これで理解できるのは数学が得意だけど文系に行った人か、嘘をついている理系の方かと思います)

最初にお見せした数式は、決して難しいものではないのですが、xとかyとか書いてあるだけで、もう見る気持ちが起きないというのは私も同じです。

なので、少し例を加えて説明します。

x1とか、x2とか、じゃなくてこの世の中に存在するもので考えてみましょう。

例えば、お金はどうでしょうか?

これで少し数学アレルギーがなくなりましたか?

そして最初の数式の例題を見てみましょう。

最初のmaxmizeは、「目的関数(objective function)」と言って、我々が問題解決するためのゴールです。

数学用語が分かりにくければ、最も、私をお金持ちにする硬貨を選んでくれ!

とも言い換えられます。

私をお金持ちにする場合、皆さんは、どの硬貨を選びますか?

私なら、全て500円玉を選びますね。その場合、以下のようになります。

x1 = 500円
→15x = 15枚の500円玉 = 7,500円

x2 = 500円
→18x = 18枚の500円玉 = 9,000円

x3 = 500円
→30x = 30枚の500円玉 = 15,000円

合計
15x1 + 18x2 + 30x3 = 31,500円

合計で31,500円も貰えます。

しかし、人によっては500円玉じゃなくて、1万円札にしたらもっとお金もらえるじゃないか?

と思うかもしれません。

しかしその上に10万円、100万円と上を設定するとキリがありません、なので制約という概念が出てきます。

それが以下の数式です。

このsubject to から始まる式を「制約式(constraint)」と呼びます。

一つ目の式を見てください。

これを見ると、x1〜x3の合計(x1だけ2倍される)は、60以下である必要があります

別の言い方をすると予算が60円以内ということになります。

そのため、最初のように無邪気に全部500円玉にするとこんなことになってしまいます。

x1 = 500円
2x1 = 2 * 500 = 1,000円

x2 = 500円
x3 = 500円

2x1 + x2 + x3 = 2,000

合計 2,000 ≠< 60

予算の60円を余裕でぶっちぎりました。笑

60円以内にするなら例えばこんな感じでしょうか?

x1 = 1円
2x1 = 2 * 1 = 2円

x2 = 50円
x3 = 5円

2x1 + x2 + x3 = 56円

合計 56 =< 60

なんとか、予算の60円以内に収まりした!(とほほ、お金だいぶ減りましたね。)

しかし、問題はさらに難しくなります。

2つ目の制約式を見てみましょう。

次は、x2が2倍されているではないですか。

先程の硬貨を使ってしまうと

x1 = 1円

x2 = 50円
2x2 = 2 * 50 = 100円

x3 = 5円

2x1 + x2 + x3 = 106円

合計 106 ≠< 60

これだと、1つ目の制約は突破できても、2つ目の制約はルール違反になってしまいます。(泣

それなら、思い切ってx3の数値だけを大きくしちゃいましょうか。

x1 = 1円

x2 = 1円
2x2 = 2 * 1 = 2円

x3 = 50円

2x1 + x2 + x3 = 53円

合計 53 =< 60

最初よりさらにお金が減ってしまいましたが、どうにか制約1と制約2、どちらも突破しました!

3つ目の制約を見てみましょう。

なんと、x3は、30以下にしないとだめのようです。

では、以下のようにしてみましょうか。

x1 = 10円
x2 = 10円
x3 = 30円

制約1の場合、合計60円: OK
制約2の場合、合計60円: OK
制約2の場合、x3 30円: OK

全て条件を満たしました。

最後に、以下の制約も大事なので確認します。

これは、x1、x2、x3それぞれ、0以上(マイナスはダメ!)を意味してます。

0以上の制約のことを「非負制約(non-negative constraint)」と呼びます。

ちなみに、これはpythonで「Gurobi」を使うときに覚えておく必要があるので紹介しますが、このように(非負の)実数全体を取ることができる変数を、「実数変数(real variable)」、もしくは「連続変数(continuous variable)」と呼びます。

今回は、文系出身者向けに、コイン(10円とか、100円)で説明しましたが、実際には、この制約の通り0以上なら、どんな数字も使えます。

例えば、硬貨に7円玉はありませんが、x1に7とか、11とかも自由に設定可能です。

ただし、制約1、制約2、制約3を達成できる範囲でのみ、自由という意味になります。

さて、改めてこの問題の解法ですが、

今、解いたやり方は、自分で、もし10円だったら、500円だったら、のように実際に、x1やx2に数字を入力して、試しましたね。

でも、毎回、色々な値を入力して試すのは面倒なので数学の世界では「線形(linear)」という関数があり、x1、x2、x3の答え = 線形の目的関数を最大化(もしくは最小化)する問題を、「線形最適化問題(linear optimization problem)」と呼びます。

さらに、制約1、制約2、制約3を全て満たす組み合わせを「実行可能解(feasible solution)」と呼びます。

そして、今回の例のようにx1 = 10円、x2 = 10円、x3 = 30円のように、全ての制約を満たしつつ、最も最大化できた解を「最適値(optimal value)」と呼びます。

用語は、そんなものなのかと読み流す程度で大丈夫ですが、大事なのは

「じゃあ、「最適値」= 全ての制約を満たして最大となる値をプログラムしてください」

と言われたときに、「え? 無理です」と感じるかと思います。

というのも、線形問題を解決するのには、やはり数学の知識が必要だからです。

有名なものだと単体法(simplex)や、内点法(interior point)などの方法があります。

しかし、特に内点法は、論文を見ても、数学を勉強してない人には意味不明です。(軽く調べところ東大工学部の人のような秀才が勉強している内容)

しかし、ここで数式が分からなくても解決する手段があります。

それが、冒頭で紹介した書籍にもあった「Gurobi」です。

あたらしい数理最適化 Python言語とGurobiで解く [ 久保幹雄 ]

価格:3,520円
(2021/9/22 00:06時点)
感想(0件)

Gurobi」を使うことで、たった10行くらいで先程の線形問題が解決できます。

正直、言ってかなりありがたいです。

数学が分からないエンジニアでも、線形問題を解決できるツールが用意されているのですから。

これは、数学がごく一部の頭のいい人しか使えなかったのが、みんな使えるようになった。

つまり「数学の民主化」が起きたのだ(しかもだいぶ前に)

私は、そのことに気づいたときに軽い感動すら覚えました。笑

次回は、実際に「Gurobi」を使って、先程の線形問題を解決する方法を記事にしています。

詳しい内容は、本を買っていただくのが一番理解が深まると思いますので、興味を持った方は是非、買ってみてください。

それでは、今回はここまでとします。

「【エンジニア向け】文系出身エンジニアが数理最適化の本を読んでみた1-基礎編」への1件の返信

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です