こんにちは、システム開発部のちょうです。
最近秋の基本情報技術者試験（FE）を目標にして勉強しています。FEといえば、いろんな分野の問題が出題されます。その中に、OR・IEにおける線形計画問題は個人にとって一番難しかったです。
例えば、平成25年秋、問75
製品X及びYを生産するために2種類の原料A，Bが必要である。製品1個の生産に必要となる原料の量と調達可能量は表に示すとおりである。製品XとYの1個当たりの販売利益が，それぞれ100円，150円であるとき，最大利益は何円か。
| 原料 | 製品Xの一個当たりの必要量 | 製品Yの一個当たりの必要量 | 調達可能量 |
|---|---|---|---|
| A | 2 | 1 | 100 |
| B | 1 | 2 | 80 |
線形計画を分からなくても、問題を読んだら制約条件や目的関数が理解できると思います。
製品Xの生産量を x 、製品Yの生産量を y とする。
制約条件
2x + y <= 100 x + 2y <= 80
最大利益 max の関数
max = 100x + 150y
一見二変数の方程式ですが、不等式のゆえ、そのまま解けてはならないです。でも現実と繋がる生産の問題なので、生産量は0とそれ以上、つまり負数にならないことが分かります。
x, y >= 0
不等式と合わせて、生産量x, yの範囲は計算できそうですが、 x 、 y お互い関連して、それといつ最大利益になるかも分からなくて、範囲を計算しても意味がないかもしれません。
ほかに方法がないでしょうか。
ちからわざ
１つは、生産量は必ず整数であることを利用します。ちなみに、線形計画ではこういう問題を整数計画問題といいます。
試しに、高そうな製品Yを最大個数にすると、
x => 0, y => 40, z => 6000
最大利益は6000円になります。
それ以上利益が上がらないか。 y を10ずつ下げて
x => 20, y => 30, z => 6500 x => 40, y => 20, z => 7000 x => 45, y => 10, z => 6000 x => 50, y => 0, z => 5000
x = 40, y = 20 の時、利益は最大なようです。
実際正解は7000で間違いないが、こういう運任せのやり方は不安です。
図解法
不等式であっても、図にすれば分かりやすいはずです。
有効な生産数（可能解）はX,Y軸と制約条件の直線に囲まれた範囲にあります。 目的関数は傾きが同じの一連なラインになります。緑のラインです。 図からみると、制約条件の交点は最適値になります。 交点の座標を計算すると、ちょうど(40, 20)になって、最大利益は7000だと確定です。ひとまずは安心ですね。
図解法はよさそうですが、二変数以上は難しくなる欠点があります。
シンプレックス法
実際線形計画の対してよく知られているシンプレックス法（単体法）というアルゴリズムがあります。
http://www.cs.tsukuba.ac.jp/~takahito/sys_math/part1.pdf
シンプレックス法では、まず標準型に変換する必要があります。不等式にスラック変数を追加して、等式に変わります。
max: 100x + 150y + 0s1 + 0s2
s.t: 2x + y + s1 = 100
x + 2y + s2 = 80
x, y, s1, s2 >= 0
ここでs1, s2はスラック変数です。maxは目的関数、s.tは制約条件です。
そして、シンプレックス法では、変数を基礎変数（BV）と非基礎変数に分かれます。非基礎変数の値は0とします。
スラック変数は普通非基礎変数と見なされますが、最初の可能解では基礎変数にします。
シンプレックス法は変数を非基礎変数から基礎変数に、基礎変数から非基礎変数に変わることで、最適解を見つかるアルゴリズムです。
標準式から最初の表（行列式）を作ります。
| BV | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| s1 | 2 | 1 | 1 | 0 | 100 |
| s2 | 1 | 2 | 0 | 1 | 80 |
| 100 | 150 | 0 | 0 | max |
この表から最初の可能解は分かります。
非基礎変数 x, y 非基礎変数の値は0 なので、x => 0, y => 0 基礎変数 s1, s2 x = 0, y = 0 なので 2x + y + s1 = 100 x + 2y + s2 = 80 s1 = 100 s2 = 80 つまりRHSの値です。 実際、基礎変数の値はその行のRHSと等しいです。 x = 0, y = 0, s1 = 100, s2 = 80 略して(0, 0, 100, 80)
可能解 (0, 0, 100, 80) の場合、maxは0です。
次は非基礎変数 x, y の中で１つを選んで、基礎変数 s1, s2 と交換します。
もし x と s2 と交換したら、表はこうなります。
| BV | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| s1 | 0 | -3 | 1 | -2 | -60 |
| x | 1 | 2 | 0 | 1 | 80 |
| 0 | -50 | 0 | -100 | max - 8000 |
変換のステップ
- BVにある
s2をxに書き換える xの列[2, 1]を[0, 1]にする
つまり
行1: 2x + y + s1 = 100 行2: x + 2y + s2 = 80
を
行1変換後: 0x + ?y + ?s1 + ?s2 = ? 行2変換後: x + 2y + 0s1 + s2 = 80
に変換する。行2で x は元々 1x ですので、変換する必要がありません。 行2変換後 = 行2
そして、連立方程式のやり方、 行1変換後 = 行1 + 行2変換後 * -2で
行1変換後: 0x - 3y + 1s1 - 2s2 = -60 行2変換後: x + 2y + 0s1 + s2 = 80
- おなじやり方で、
最後の一行変換後 = 最後の一行 + 行2変換後 * -100にすれば、上の表になります。
この表では、可能解は (80, 0, -60, 0) になり、条件 x, y, s1, s2 >= 0 に満たされないので、不正解です。
実際、シンプレックス法で、変換する変数に条件があります。
- 非基礎変数から基礎変数にする場合、表の最後の一行、値が0以上の列
- 基礎変数から非基礎変数にする場合、RHS/新しい基礎変数の列にいる値 のうち0以上かつ一番小さい値の行
| BV | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| s1 | 2 | 1 | 1 | 0 | 100 |
| s2 | 1 | 2 | 0 | 1 | 80 |
| 100 | 150 | 0 | 0 | max |
最初の表を見ると、最後の一行で列 x と列 y の値が0以上なので、基礎変数の候補になります。もし x を選んだら、列 x [2, 1] と RHSの列 [100, 80] の比例、[100/2, 80/1] で一番小さいのは 100/2 のいる行、s1 になります。 s2にしたら、さきのように、変数の値が負数になります。
もう一度 x と s1 を交換してみます。
| BV | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x | 1 | 0.5 | 0.5 | 0 | 50 |
| s2 | 0 | 1.5 | -0.5 | 1 | 30 |
| 0 | 100 | -50 | 0 | max -5000 |
可能解は (50, 0, 0, 30) になります。利益は5000です。
表の最後の一行では0以上の列はまだありますので、 y と min([50/0.5, 30/1.5]) => s2 交換してみます。
| BV | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x | 1 | 0 | 2/3 | -1/3 | 40 |
| y | 0 | 1 | -1/3 | 2/3 | 20 |
| 0 | 0 | -50/3 | -200/3 | max -7000 |
可能解は (40, 20, 0, 0) になります。利益は7000です。
最後の一行では0以上の値はないので、7000は最適解と見られます。
最適解からみると、x, y は基礎変数として0以上の値になり、 s1, s2 は非基礎変数でありながら0になってます。
二変数の問題はシンプレックスを解くのは勿体無い感があるので、ちょっと複雑な三変数問題で試しましょう。
ある工場では表に示す3製品を製造している。実現可能な最大利益は何円か。ここで，各製品の月間需要量には上限があり，また，組立て工程に使える工場の時間は月間200時間までで、複数種類の製品を同時に並行して製造することはできないものとする。
| 製品X | 製品Y | 製品Z | |
|---|---|---|---|
| 一個あたりの利益（円） | 1800 | 2500 | 3000 |
| 一個あたりの製造所要時間（分） | 6 | 10 | 15 |
| 月間需要量上限（個） | 1000 | 900 | 500 |
標準型
max: 1800x + 2500y + 3000z + 0s1 + 0s2 + 0s3 + 0s4
s.t: 6x + 10y + 15z + s1 = 200 * 60
x + s2 = 1000
y + s3 = 900
z + s4 = 500
表
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| s1 | 6 | 10 | 15 | 1 | 0 | 0 | 0 | 12000 |
| s2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| s3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| s4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 1800 | 2500 | 3000 | 0 | 0 | 0 | 0 | max |
基礎変数に入れそうな変数は x, y, z になりますが、実際この問題に罠があります。
もし z を選んだら、
z <-> s4
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| S1 | 6 | 10 | 0 | 1 | 0 | 0 | -15 | 4500 |
| S2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| S3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| Z | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 1800 | 2500 | 0 | 0 | 0 | 0 | -3000 | max -1500000 |
y <-> s1
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| Y | 0.6 | 1 | 0 | 0.1 | 0 | 0 | -1.5 | 450 |
| S2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| S3 | -0.6 | 0 | 0 | -0.1 | 0 | 1 | 1.5 | 450 |
| Z | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 300 | 0 | 0 | -250 | 0 | 0 | 750 | max - 2625000 |
s4 <-> s3
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| Y | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| S2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| S4 | -0.4 | 0 | 0 | -0.066666667 | 0 | 0.666666667 | 1 | 300 |
| Z | 0.4 | 0 | 1 | 0.066666667 | 0 | -0.666666667 | 0 | 200 |
| 600 | 0 | 0 | -200 | 0 | -500 | 0 | max - 2850000 |
x <-> z
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| Y | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| S2 | 0 | 0 | -2.5 | -0.166666667 | 1 | 1.666666667 | 0 | 500 |
| S4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| X | 1 | 0 | 2.5 | 0.166666667 | 0 | -1.666666667 | 0 | 500 |
| 0 | 0 | -1500 | -300 | 0 | 500 | 0 | max - 3150000 |
s3 <-> s2
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| Y | 0 | 1 | -15 | 1 | -0.6 | 0 | 0 | 600 |
| S3 | 0 | 0 | 15 | -1 | 0.6 | 1 | 0 | 300 |
| S4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| X | 1 | 0 | 27.5 | -1.5 | 1 | 0 | 0 | 1000 |
| 0 | 0 | -9000 | 200 | -300 | 0 | 0 | max - 3300000 |
s1 <-> y
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| S1 | 0 | 1 | -15 | 1 | -0.6 | 0 | 0 | 600 |
| S3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| S4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| X | 1 | 1.5 | 5 | 0 | 0.1 | 0 | 0 | 1900 |
| 0 | -200 | -6000 | 0 | -180 | 0 | 0 | max - 3420000 |
この計算量はさておき、最後の可能解 (1900, 0, 0, 600, 0, 900, 500) は不正解です。なぜなら、x は最初の制約条件では1000を超えなければなりません。でも一歩戻して、可能解 (100, 600, 0, 0, 0, 300, 500) は正しい、そして最適解です。
何が起こったというと、これはシンプレックス法の退化という現象です。もし基礎変数に0がいると、基礎変数と非基礎変数はわからなくなります。この問題では、ちょうど最適解において zが0になり、もしシンプレックス法で z を基礎変数に入れたら、この変な可能解に至ります。
でも、最初 z を選んてなかったら、
最初の表
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| s1 | 6 | 10 | 15 | 1 | 0 | 0 | 0 | 12000 |
| s2 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| s3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| s4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 1800 | 2500 | 3000 | 0 | 0 | 0 | 0 | max |
x <-> s2
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| S1 | 0 | 10 | 15 | 1 | -6 | 0 | 0 | 6000 |
| X | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1000 |
| S3 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 900 |
| S4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 0 | 2500 | 3000 | 0 | -1800 | 0 | 0 | max - 1800000 |
y <-> s1
| BV | x | y | z | s1 | s2 | s3 | s4 | RHS |
|---|---|---|---|---|---|---|---|---|
| Y | 0 | 1 | 1.5 | 0.1 | -0.6 | 0 | 0 | 600 |
| X | 1 | 0 | 0 0 | 1 | 0 | 0 | 1000 | |
| S3 | 0 | 0 | -1.5 | -0.1 | 0.6 | 1 | 0 | 300 |
| S4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 500 |
| 0 | 0 | -750 | -250 | -300 | 0 | 0 | max - 3300000 |
ただ二回で最適解を得られました。退化現象もないです。実はシンプレックス法の退化について改善するアルゴリズムがあるらしいですが、ここでわかったのは
- BVに入る変数の選択は重要です。
- 基礎変数に0がいると退化現象は発生する可能性があります。
まとめ
簡単な二変数問題に対しては、図解法のほうが分かりやすいです。制約条件が多く、変数が３つあるいはそれ以上になったら、シンプレックス法をおすすめします。
シンプレックス法には退化現象があり、基礎変数に0がいる場合、注意する必要があります。
いかがでしょうか。たまにはプログラミングの問題以外、数学の問題も解いてみましょうか。
