総売り上げを最大にするには、何皿ずつ作っておけばよいだろうか?$x_1$:カレーの数、$x_2$:親子丼の数として、標準形で表してみよう。2x_1+3x_2となる。制約条件の1本目は鶏肉に関する条件式、2本目は玉ねぎに関する条件式になっている。この【制約条件】を図示してみよう。この全ての不等式を満たす点の集合(図の〜〜の部分)を許容領域、点のそれぞれを許容解という。許容解のうち、目的関数$f$を最大にする点を最適解という。【制約条件】の不等式を等式化してみよう。今、不等式の左辺の方が右辺に比べて小さいので、その小さい分を補ってあげれば等式にすることができる。ここでは、補う分を$\lambda$として表現しよう。\lambda_1\geq0,\lambda_2\geq0\end{array}\right.この$\lambda$のことをスラック変数という。先ほどの「玉ねぎに関する条件式」について考えてみよう。x_2=-2x_1+8-\lambda_2であった。ここから、x-y平面に描いたときのy切片は$8-\lambda_2$である。0$$\lambda_2>0$のとき、等号成立時の直線より下側$\lambda_2<0$のとき、等号成立時の直線より上側を表現することから、$\lambda_2$の符号によって領域の分割が可能ということになる。標準形を作った時に$\lambda>0$という制約を設けたことから、最適解は「直線上」or「直線より下側半分」に存在しなければならない。この「直線」を一般的に超平面といい、超平面の下側半分を$\lambda_2>0$における半空間という。最適解を求めるために使う定理たち【Th.6.1】許容領域はn次元空間内の凸多面体ここで言葉のチェックをしておこう。【Def.:凸性】凹んでいない。(n=2のときのイメージ)先ほどからでてきている図であるが、確かに許容領域は直線に囲まれていて、その内部に穴がないことがわかる。証明は避けるが凸領域は単連結であるので、許容領域に穴がないことも言える。許容領域の内部の点たち、つまり許容点のうち目的関数を最大にする点が最適解であることから、許容領域が上の性質を満たさないときは最適解を持たないと言えるだろう。書くと、次のようになる。【Lemma.:最適解が存在しないケース】[1]許容領域が有界でなくて、目的関数が発散するとき[2]許容領域が空集合のときここでも、有界についてチェックしておこう。半球Rの超球に含まれる集合(つまり、どの方向にもある一定の距離R以内に制限されている集合)[1]の場合は、目的関数fは右上方向にどんどんずらしていくことができ、その結果$f\to\infty$となっていることがわかる。これでは、最適解が何であるか特定不可能である。[2]の場合は、そもそも許容点が存在しないので最適解も存在しえない。最適解が存在するならば、目的関数は許容領域の頂点で最大値をとる。(n=2のイメージ)2個の超平面(直線)が交わる点(頂点)のいずれかで最適解を得る、という主張である。ここから、n次元で頂点というのは、n個の超平面が交わる点であって、そのどこかで最適解をとる。超平面は、【制約条件】の不等式の等号が成立するときの直線であることから、次の定理が言える。,\dots,x_n^*)$において制約条件m+n本の不等式のうちn個で等式が成立する。ここからは、スラック変数を導入した場合の話をする。c_1x_1+\cdots+c_nx_nである。このとき、【Th.6.3】は次のように書き換えることができる。$のうちn個は0になる。[1,m]$で$\lambda_j=0$ならば、座標軸以外の直線(【制約条件】の等号成立をさせた直線)が最適解を与える頂点をなす直線のうちの1つとなったときである。最適解を求めにかかる以上の定理たちを使って、自然に考えられる解法は次の方法であろう。【Method.1】[1]【制約条件】のm+n個の不等式からn個を選んで等号に置換した連立1次方程式を解く。妥当性』をCheck[3][2]がOKならば、$f$の値を計算[4][1]~[3]を全ての場合についてやる。その結果得られる$f$の値が最大となるものを選ぶ。スラック変数を導入した場合は次のようになる。【Method.2】[1]n+m個の変数$x_i,\lambda_j$からn個を選んで0とおく。その結果得られる連立1次方程式を残ったm個の変数について解く。[2]『解が非負』をCheck[3][2]がOKならば、$f$の値を計算[4][1]~[3]を全ての場合についてやる。その結果得られる$f$の値が最大となるものを選ぶ。通りとなり、mやnが増えて複雑な条件になると一気にコストが急増してしまうところに欠点がある。コストがかかるという欠点を改善する方法の一つとして「シンプレックス法」などがある。PuLPで解く今回は、冒頭紹介したカレーと親子丼の最適化問題を解くことにしよう。一度問題を整理しておく。2x_1+3x_2で、この$f$を最大化しようというものであった。Pythonのコードを全文載せる。problem.solve()print(pulp.LpStatus[status])#結果表示print("Result")print("Curry:",Curry.value())print("Oyako:",Oyako.value())まずは、問題を定義しよう。pulp.LpMaximize)ここでは、線形計画問題に名前を「Curry_Oyako」とつけ、最終的な目標は目的関数$f$を最大化することであるので「pulp.LpMaximize」と指定した。(最小化したいときはpulp.LpMiniimize)とする。次に変数の定義をする。今回はカレーと親子丼の皿数を変数としたので、それらを定義する。小数点の皿数が出ても調理に困るので整数枚となるようにIntegerを指定する(他にはfloat型連続値'Continuous'、2値変数'Binary'が指定できる)。変数の最小値、最大値はそれぞれ0,10で指定した。変数定義まで終わったら制約条件と目的関数を定義しよう。なんと線形計画問題problemに足すだけ。3*Oyako以上で定義はおしまい。Integerとなり、確認することができる。あとは、解いてもらおう。problem.solve()print(pulp.LpStatus[status])解くことの本質はproblem.solve()だけである。これが正確に実行されたかどうかをチェックするためにstatusを表示している。これが"Optimal"と表示されれば、ちゃんと解けたということになる。変数に対して".value()"とするだけである。4.0図的にも(2,4)な気はしていたが、その通り!PuLP本当に楽で直感的でよさげですね!さいごにこの記事は自主ゼミの発表で取り上げた内容をもとに、厳密的な話は置いておいて線形計画法の直感的な理解とPythonで解く演習を兼ねたものであった。PuLPはプログラミングをほぼ知らない人でも使えそうなツールで、とにかく楽そうであった。高校数学でよく見る線形計画法が実際の問題として取り扱われていることも実感できてよかった。Appendix(領域を塗る)本文中の図の描き方をまとめておく。本記事の趣旨とは全く異なるが、自分自身の備忘録的な何かも込めてまとめる。使用したのは、matplotlibとnumpyである。4.5)plt.legend(loc=0)plt.show()x軸の区間[0,5]を100分割して、その値について定義したy1,y2,y3を計算し、それをプロットしたというものである。np.zeros_like(x)は、0を要素とする配列を返す関数。alpha=0.3)は、「y3、つまりy=0」と「各xについてy1とy2の小さい方y4」について、$y_4>y_3=0$を黄色で塗る。alphaは不透明度を指定する。これを実行して得られる図はである。upLoginユーザーは見つかりませんでした。