線形計画問題単語

センケイケイカクモンダイ

  • 9
  • 0
掲示板をみる(5)
  • twitter
  • facebook
  • はてな
  • LINE
  • ほめる(9)
  •  
  •  
  •  
  •  
  • その他

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

概要

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

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

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

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

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

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

Maximize x1+x2+x3
subject to
   5x1+x2+2x3≤20
   2x1+2x2+6x330
   2x1+6x2+4x340
   x1,x2,x3≥0

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

標準形

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

Minimize cTx
subject to
   Ax=b
   x0
x変数からなるベクトル、Aは行列b,cベクトル 

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

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

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

Minimize -x1-x2-x3
subject to
   5x1+x2+2x3+x4=20
   2x1+2x2+6x3+x5=30
   2x1+6x2+4x3+x6=40
   x1,x2,x3,x4,x5,x6≥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以上なので、これが最適。最適解は基底変数と一番右の成分を見ればおk。最適値は右上の成分を-1倍したものとなる。

この場合、最適解は、x1=2,x2=4,x3=3,x4=x5=x6=0であり、最適値は-9。

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

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

二段階法

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

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

Minimize -x1-x2-x3-x4
subject to
   x1+5x2+2x3+x4=13
   2x1+2x2+x3+5x4=14
   x1,x2,x3,x4≥0 

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

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

Minimize x5+x6
subject to
   x1+5x2+2x3+x4+x5=13
   2x1+2x2+x3+5x4+x6=14
   x1,x2,x3,x4,x5,x6≥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であり、基底変数はx2,x4である。

第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

よって、最適解はx1=5,x2=0,x3=4,x4=0で、最適値は-9である。

-⑨「値ったら(ry

双対問題

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

線形計画問題の標準形

Minimize cTx
subject to
   Ax=b
   x0

に対し、その双対問題は

Maximize bTw
subject to
   ATwc 

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

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

Minimize cTx
subject to
   Axb
   x0

に対し、その双対問題は

Maximize bTw
subject to
   ATwc
   w0 

となる。

線型計画問題の図形的な解法です。先程の二段階法の例から、双対問題を考える。

Maximize 13w1+14w2
subject to
    w1+2w2≤-1
    5w1+2w2≤-1
    2w1+w2≤-1
    w1+5w2≤-1

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

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

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

-⑨「値(ry

関連項目

この記事を編集する

掲示板

  • 3expo_one

    2011/07/16(土) 12:50:43 ID: RZg/8y5iHG

    編集者です。最後の例を図形的に解きます。

    図形的解法

    タイトル:図形的解法

  • 4ななしのよっしん

    2014/03/11(火) 20:25:21 ID: /a7scM3biO

    艦これの遠征選びのときによくお世話になる
    具体的な計算はソルバー先生にやってもらってるけど

  • 5ななしのよっしん

    2014/10/21(火) 22:47:22 ID: FRFWbmKN08

    とてもいい記事ですね。

おすすめトレンド

急上昇ワード改

最終更新:2020/09/25(金) 05:00

ほめられた記事

最終更新:2020/09/25(金) 05:00

スマホで作られた新規記事

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

           

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

タグ編集にはログインが必要です。

タグ編集には利用規約の同意が必要です。

TOP