ユニファ開発者ブログ

ユニファ株式会社システム開発部メンバーによるブログです。

線形計画とシンプレックス法

こんにちは、システム開発部のちょうです。

最近秋の基本情報技術者試験(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の範囲は計算できそうですが、 xy お互い関連して、それといつ最大利益になるかも分からなくて、範囲を計算しても意味がないかもしれません。

ほかに方法がないでしょうか。

ちからわざ

1つは、生産量は必ず整数であることを利用します。ちなみに、線形計画ではこういう問題を整数計画問題といいます。

試しに、高そうな製品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で間違いないが、こういう運任せのやり方は不安です。

図解法

不等式であっても、図にすれば分かりやすいはずです。

f:id:unifa_tech:20171002155710p:plain

有効な生産数(可能解)はX,Y軸と制約条件の直線に囲まれた範囲にあります。 目的関数は傾きが同じの一連なラインになります。緑のラインです。 図からみると、制約条件の交点は最適値になります。 交点の座標を計算すると、ちょうど(40, 20)になって、最大利益は7000だと確定です。ひとまずは安心ですね。

図解法はよさそうですが、二変数以上は難しくなる欠点があります。

シンプレックス法

実際線形計画の対してよく知られているシンプレックス法(単体法)というアルゴリズムがあります。

シンプレックス法 - Wikipedia

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 の中で1つを選んで、基礎変数 s1, s2 と交換します。

もし xs2 と交換したら、表はこうなります。

BV x y s1 s2 RHS
s1 0 -3 1 -2 -60
x 1 2 0 1 80
0 -50 0 -100 max - 8000

変換のステップ

  1. BVにある s2x に書き換える
  2. 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
  1. おなじやり方で、 最後の一行変換後 = 最後の一行 + 行2変換後 * -100 にすれば、上の表になります。

この表では、可能解は (80, 0, -60, 0) になり、条件 x, y, s1, s2 >= 0 に満たされないので、不正解です。

実際、シンプレックス法で、変換する変数に条件があります。

  1. 非基礎変数から基礎変数にする場合、表の最後の一行、値が0以上の列
  2. 基礎変数から非基礎変数にする場合、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にしたら、さきのように、変数の値が負数になります。

もう一度 xs1 を交換してみます。

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以上の列はまだありますので、 ymin([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になってます。

二変数の問題はシンプレックスを解くのは勿体無い感があるので、ちょっと複雑な三変数問題で試しましょう。

平成28年秋期 問71

ある工場では表に示す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

ただ二回で最適解を得られました。退化現象もないです。実はシンプレックス法の退化について改善するアルゴリズムがあるらしいですが、ここでわかったのは

  1. BVに入る変数の選択は重要です。
  2. 基礎変数に0がいると退化現象は発生する可能性があります。

まとめ

簡単な二変数問題に対しては、図解法のほうが分かりやすいです。制約条件が多く、変数が3つあるいはそれ以上になったら、シンプレックス法をおすすめします。

シンプレックス法には退化現象があり、基礎変数に0がいる場合、注意する必要があります。

いかがでしょうか。たまにはプログラミングの問題以外、数学の問題も解いてみましょうか。