線形計画問題

線形計画問題とは、目的関数と制約条件が共に1次式で表すことのできる最適化問題である。

概要

最適化についてよく知っている方には上記の説明だけで済んでしまうので、ここでは、そうでない方のために例を挙げ、その例に沿って説明することにする。

生産ライン	A	B	C
電気(kWh)	5	1	2
ガス(m3)	2	2	6
水(m3)	2	6	4

例題：ある工場では、同じ製品を作るのに3種類の生産ラインを用いている。製品1kg分を作るのに消費する電気、ガス、水の量は生産ラインによって異なっており、右の表の通りであるとする。1日に消費することのできる電気、ガス、水の上限がそれぞれ20kWh、30m³、40m³であるとき、どの生産ラインをどれだけ稼働させれば多くの製品を作ることができるか。

まず、これを式で表す。
生産ラインA,B,Cで1日に作られる製品の量(kg)を、それぞれx₁,x₂,x₃とする。1日に作られる製品の量の合計は、(x₁+x₂+x₃)kgである。この値を大きくするのが目的である。

1日に消費する電気、ガス、水の量とその上限との関係は、それぞれ次の通りである。
　　　5x₁+x₂+2x₃≤20
　　　2x₁+2x₂+6x₃≤30
　　　2x₁+6x₂+4x₃≤40
また、当然のことながらx₁,x₂,x₃はいずれも負にはならない。 

これらをまとめて書くと、次のようになる。

Maximize x₁+x₂+x₃
subject to
　　　5x₁+x₂+2x₃≤20
　　　2x₁+2x₂+6x₃≤30
　　　2x₁+6x₂+4x₃≤40
　　　x₁,x₂,x₃≥0

この、Maximizeのあとの式を目的関数、subject toのあとの式を制約条件という。どちらも1次式で書かれているので、これは線形計画問題である。

標準形

線形計画問題は、次の条件を満たす形に直すことができる。この形を線形計画問題の標準形という。

Minimize c^Tx
subject to
　　　Ax=b
　　　x≥0
※xは変数からなるベクトル、Aは行列、b,cはベクトル 

これは、目的関数、制約条件が1次式であることに加え、次の条件を満たす必要がある。

• 最小化問題である。
• 制約条件が、等式で書かれている。
• 各変数は、0以上の実数である。

上記の例題は、最大化問題であり、制約条件は不等式で書かれている。最大化問題は、目的関数に-1を掛けることで最小化問題にできる。制約条件が不等式である場合、新たに変数を設け、小さいほうの辺に足すことで等式にできる。この変数をスラック変数という。例題を標準形に直したのがこちら。

Minimize -x₁-x₂-x₃
subject to
　　　5x₁+x₂+2x₃+x₄=20
　　　2x₁+2x₂+6x₃+x₅=30
　　　2x₁+6x₂+4x₃+x₆=40
　　　x₁,x₂,x₃,x₄,x₅,x₆≥0

ここでのスラック変数は、使っていない電気、ガス、水の量を表しているとも言える。

例題は、変数がすでに0以上であったが、変数が任意の値をとる場合でも、0以上の変数2つの差として表すことで、標準形にできる。 

用語

線形計画問題の用語についてまとめる。原理を知るためには必須の知識であるが、計算するだけなら必ずしも必要ではない。

実行可能解

制約条件を満たす各変数の値。

実行可能領域

実行可能解全体の集合。

基底変数

変数ごとに制約条件の係数でベクトルをとったとき、1次独立になるものの組み合わせ。制約条件の(1次独立な)式の数だけ存在する。

非基底変数

基底変数を定めたとき、それに属さないもの。

基底行列

基底変数の係数のベクトルを列とした行列。正則行列である。

非基底行列

非基底変数の係数のベクトルを列とした行列。

基底解

基底変数を定めたとき、非基底変数の値をすべて0にすると、基底変数の値も一意的に定まる。これを基底解という。実行可能解である必要はない。

実行可能基底解

実行可能解で、かつ基底解になるようなもの。

最適解

実行可能解で、目的関数の値を最適にするもの。

最適値

最適解での、目的関数の値。

シンプレックス法

線形計画問題を解くアルゴリズムのひとつ。「最適解は実行可能基底解にある」という定理を元にしたものである。

1. 実行可能基底解を1つ求める。
2. それが最適解かどうか判定し、最適解なら6へ飛ぶ。
3. 基底変数のうち、次のステップで非基底変数にするものをひとつ選ぶ。
4. 非基底変数のうち、次のステップで基底変数にするものをひとつ選ぶ。
5. 2へ戻る。
6. 最適値を求める。

最適解の判定方法及び次のステップでの基底変数、非基底変数の決め方は、編集者が原理をあまり理解していないので詳しく書けない次のタブロー表現の項目を参照。

タブロー表現

シンプレックス・タブローという行列を用いる方法。計算するだけなら原理がわからなくてもできる。前述の例題で説明する。

まず、第1行に目的関数の係数、第2行以降に制約条件の係数を書く。一番右の列は、第1行は0、第2行以降は制約条件の右辺の定数とする。

-1	-1	-1	0	0	0	0
5	1	2	1	0	0	20
2	2	6	0	1	0	30
2	6	4	0	0	1	40

基底変数を選び、行の基本変形を用いて基底行列を単位行列にする。ここでは基底行列を太字で書くことにする。この場合はスラック変数のおかげで既に単位行列になっている。

そのあと、第1行の基底変数の列を0にする。この場合はスラック変数のおかげで(ry

第1行の一番右以外の各成分が0以上なら、最適解が求められたことになる。そうでなければ、負になっている列のうち、最も数が小さいものを1つ選ぶ(ピボット列という)。この列に対応する変数が次のステップで基底変数となる。この場合は第1列を選ぶ。

第2行以降の一番右の成分を、同じ行のピボット列の成分で割り、最も数が小さいものを1つ選ぶ(ピボット行という)。この行の成分のうち、1であるような基底行列の成分の列に対応する変数が、次のステップで非基底変数となる。この場合は、第2行から順に4,15,20なので第2行を選ぶ。

ピボット行とピボット列の交差する成分をピボット成分という。行の基本変形により、ピボット成分を1にし、ピボット列のその他の成分を0にする。

この例でいうと、まず第2行を1/5倍する。その2倍を第3行から引く。同じく2倍を第4行から引く。第1列にはそのまま足す。

0	-4/5	-3/5	1/5	0	0	4
1	1/5	2/5	1/5	0	0	4
0	8/5	26/5	-2/5	1	0	22
0	28/5	16/5	-2/5	0	1	32

第1行で最小の成分は-4/5なので、ピボット列は第2列。
第7列の成分を第2列の成分で割ると、第2行から順に20,55/4(≒13.8),40/7(≒5.7)なので、ピボット行は第4行。
第4行を5/28倍する。その1/5倍を第2行から引く。8/5倍を第3行から引く。4/5倍を第1行に足す。

0	0	-1/7	1/7	0	1/7	60/7
1	0	2/7	3/14	0	-1/28	20/7
0	0	30/7	-2/7	1	-2/7	90/7
0	1	4/7	-1/14	0	5/28	40/7

第1行の最小の成分は-1/7なので、ピボット列は第3列。
第7列の成分を第3列の成分で割ると、第2行から順に10,3,10なので、ピボット行は第3行。
第3行を7/30倍する。その2/7倍を第2行から引く。4/7倍を第4行から引く。1/7倍を第1行に足す。

0	0	0	2/15	1/30	2/15	9
1	0	0	7/30	-1/15	-1/60	2
0	0	1	-1/15	7/30	-1/15	3
0	1	0	-1/30	-2/15	13/60	4

第1行の一番右以外を見ると、すべて0以上なので、これが最適。最適解は基底変数と一番右の成分を見ればおｋ。最適値は右上の成分を-1倍したものとなる。

この場合、最適解は、x₁=2,x₂=4,x₃=3,x₄=x₅=x₆=0であり、最適値は-9。

-9は標準形での最適値であり、元は最大化問題であったため、この問題の最適値は9となる。つまり、生産ラインAで2kg,Bで4kg,Cで3kgだけ製品を作ればよい。その合計の9kgが最適値である。

⑨「値(あたい)ったら最適ね」

二段階法

シンプレックス法では、最初に実行可能基底解をひとつ求める必要がある。前述の例のように、スラック変数のあるものは簡単に基底変数を見つけることができる。しかし、スラック変数のないものは、変数や式の数が多いものほど基底変数が見つけづらくなる。しかし、補助問題と呼ばれる線形計画問題を解くことによって、基底変数を機械的に求めることができる。このように、補助問題→本問題(本来解こうとしている問題)という流れで問題を解くことを二段階法という。

以下、次の例に沿って解説する。

Minimize -x₁-x₂-x₃-x₄
subject to
　　　x₁+5x₂+2x₃+x₄=13
　　　2x₁+2x₂+x₃+5x₄=14
　　　x₁,x₂,x₃,x₄≥0 

補助問題は、補助変数という変数を用いて作られる。まず、本問題の制約条件の(一次独立な)式の本数だけ新たに変数を設ける。本問題の制約条件の左辺に補助変数を1つずつ足したものが補助問題の制約条件である。補助問題の目的関数は、補助変数の和である。

上記の例では、補助問題は次のようになる。

Minimize x₅+x₆
subject to
　　　x₁+5x₂+2x₃+x₄+x₅=13
　　　2x₁+2x₂+x₃+5x₄+x₆=14
　　　x₁,x₂,x₃,x₄,x₅,x₆≥0

第1段階

補助問題の目的は、最適値を0にすることである。最適値が0になれば、補助変数の値がすべて0となり、本問題の変数の中で基底変数を見つけることができる。ここでは、タブローを使って解く。

0	0	0	0	1	1	0
1	5	2	1	1	0	13
2	2	1	5	0	1	14

見てわかる通り、補助変数を基底変数とすることができ、基底行列は既に単位行列になっている。第1行の基底変数に該当する成分を0にする。

-3	-7	-3	-6	0	0	-27
1	5	2	1	1	0	13
2	2	1	5	0	1	14

第2列をピボット列、第2行をピボット行とする。

-8/5	0	-1/5	-23/5	7/5	0	-44/5
1/5	1	2/5	1/5	1/5	0	13/5
8/5	0	1/5	23/5	-2/5	1	44/5

第4列をピボット列、第3行をピボット行とする。

0	0	0	0	1	1	0
3/23	1	9/23	0	5/23	-1/23	51/23
8/23	0	1/23	1	-2/23	5/23	44/23

よって、補助問題の最適値は0であり、基底変数はx₂,x₄である。

第2段階

本問題の制約条件は、このタブローの成分をそのまま使うことができる。

-1	-1	-1	-1	0
3/23	1	9/23	0	51/23
8/23	0	1/23	1	44/23

第1行の、基底変数にあたる成分を0にする。

-12/23	0	-13/23	0	95/23
3/23	1	9/23	0	51/23
8/23	0	1/23	1	44/23

第3列をピボット列、第2行をピボット行とする。

-1/3	13/9	0	0	22/3
1/3	23/9	1	0	17/3
1/3	-1/9	0	1	5/3

第1列をピボット列、第3行をピボット行とする。

0	4/3	0	1	9
0	8/3	1	-1	4
1	-1/3	0	3	5

よって、最適解はx₁=5,x₂=0,x₃=4,x₄=0で、最適値は-9である。

-⑨「値ったら(ry」

双対問題

線形計画問題では、元の問題(主問題と呼ぶ)の係数を用いて別の問題を考えることができる。これは単にもうひとつの問題ができるというだけでなく、主問題と表裏一体な関係を作っている。

線形計画問題の標準形

Minimize c^Tx
subject to
　　　Ax=b
　　　x≥0

に対し、その双対問題は

Maximize b^Tw
subject to
　　　A^Tw≤c 

である。この変数は負であってもよい。双対問題の最適値は主問題のそれと等しい。

また、標準形ではないが、

Minimize c^Tx
subject to
　　　Ax≥b
　　　x≥0

に対し、その双対問題は

Maximize b^Tw
subject to
　　　A^Tw≤c
　　　w≥0 

となる。

例

先程の二段階法の例から、双対問題を考える。

Maximize 13w₁+14w₂
subject to
　　　 w₁+2w₂≤-1
　　　 5w₁+2w₂≤-1
　　　 2w₁+w₂≤-1
　　　 w₁+5w₂≤-1

これは2変数なので、平面上にグラフを描くことで図形的に求めることができる。

横軸をw₁、縦軸をw₂とし、実行可能領域を黄色で、目的関数を赤で描く。赤い直線は傾きを保ちながら動き、y切片が大きいほど目的関数の値が大きくなる。

黄色い領域と共有点をもち、かつy切片が最大となるものを求める。最適解は右図の通りとなり、目的関数に代入すると最適値は-9になる。確かに主問題と最適値が一致する。

-⑨「値(ry」

関連項目

• 数学
• 最短経路問題
• 最大流問題