【線形計画法②】シンプレックス法でトラックの積載率が最大になる条件を求めてみた

2022年1月10日

トラックには容積重量という2つの制約があり、積載量が限られます。

そして、貨物の比重によってどちらの制約に引っかかるかが決まります。

布団のような軽い貨物ばかりを積めば、荷台は満杯でも重量は半分くらい余裕があるかもしれません。

逆に、水のように重たい貨物ばかりを積めば、重量ギリギリまで積んでも荷台は半分くらい余ってしまうかもしれません。

どちらの場合もトラックの使い方としてはムダがあり、軽い貨物と重たい貨物をミックスして、容積としても重量としても100%に近い積載率にするのが効率の良い積み方です。

 

そのために軽い貨物と重たい貨物をどの比率でミックスすれば良いかについては、下記の記事で解説しています。

容積勝ち貨物と重量勝ち貨物、混載して物流コスト削減になる条件を一次方程式で解く

簡単な一次方程式で解く方法ですが、この方法は貨物の種類が2種類の場合にしか使えません。

経験と勘」でも何とかなります。

ところが、これが4種類くらいになってくるとそうはいきません。

無数にある組み合わせから最適解を見つけるのは「経験と勘」では困難です。

 

今回は「経験と勘」では絶対に無理な、貨物の種類がいくつあっても解ける方法を紹介します。

そのために、OR(オペレーションズリサーチ)の一手法である線形計画法を使います。

前回の記事で線形計画法を掃き出し法で解く方法を紹介しました。

【初心者向け】線形計画法を使ってコンテナ混載最適化問題を解いてみた

 

今回は変数が多いため、より効率良く解くための手法であるシンプレックス法を使って解いていきます。

 

定式化する

次のような状況を想定します。

――――――――――――――――――――――――

4種類の貨物があります。

貨物A

1箱の重量:12kg

1箱の容積:0.05m3

貨物B

1箱の重量:10kg

1箱の容積:0.01m3

貨物C

1箱の重量:8kg

1箱の容積:0.08m3

貨物D

1箱の重量:13kg

1箱の容積:0.02m3

 

これらの貨物を最大積載容積50m3、最大積載重量25tの大型トラックで運ぶ時、容積ベースでも重量ベースでも積載率を最大にするためには、どの貨物をどれだけ積めば良いでしょうか?

但し、諸事情から次の条件を満たさなくてはいけません。

  1. 貨物Aと貨物Bの合計重量は8t以内
  2. 貨物Cと貨物Dの合計容積は25m3以内

――――――――――――――――――――――――

 

たった4種類の貨物しかありませんが、この問題をすぐに解ける人はまずいないでしょう。

しかし線形計画法を使えば、40種類でも400種類でも解けます。

それではまず線形計画法の問題に定式化していきます。

貨物A~Dの積載箱数をそれぞれx、y、z、wとすると、最大積載重量(25t)と最大積載容積(50m3)の制約から次の不等式が成り立ちます。

 

12x + 10y + 8z + 13w ≦ 25000 ・・・①

0.05x + 0.01y + 0.08z + 0.02w ≦ 50 ・・・②

 

また、おまけの2つの制約条件は次のような不等式で表せます。

 

12x + 10y ≦ 8000 ・・・③

0.08z + 0.02w ≦ 25 ・・・④

 

そして重量ベース、容積ベースそれぞれの積載率は、次のように計算できます。

 

重量ベースの積載率= (12x + 10y + 8z + 13w) / 25000

容積ベースの積載率= (0.05x + 0.01y + 0.08z + 0.02w) / 50

 

そして今回はこれら2つの積載率を同時に最大化したいので、2つの平均目的関数とします。

 

目的関数={(12x + 10y + 8z + 13w) / 25000 + (0.05x + 0.01y + 0.08z + 0.02w) / 50} / 2 ・・・⑤

 

これで線形計画法の問題に定式化できました。

 

拡大係数行列を作る

次に、この問題を連立方程式の形にします。

そのために、非負の変数s1~s4を使って式①~④を次のように書き替えます。(s1からs4スラック変数といいます)

 

12x + 10y + 8z + 13w + s1 = 25000 ・・・①’

0.05x + 0.01y + 0.08z + 0.02w + s2 = 50 ・・・②’

12x + 10y +s3 = 8000 ・・・③’

0.08z + 0.02w +s4 = 25 ・・・④’

 

また目的関数の値をmと置くと、式⑤は次のような式で表すことができます。

 

m = {(12x + 10y + 8z + 13w) / 25000 + (0.05x + 0.01y + 0.08z + 0.02w) / 50} / 2

m – (12/25000+0.05/50)/2*x – (10/25000+0.01/50)/2*y – (8/25000+0.08/50)/2*z – (13/25000+0.02/50)/2*w = 0 ・・・⑤’

 

これで式①’~⑤’による連立方程式ができました。

ここでの注意点は、

「変数が3つあるなら式は最低でも3つないと解は定まらない」

と中学で習ったことを覚えている人もいると思いますが、変数の数より式の数の方が多くないと解が一意に定まらないということです。

今回の問題では、変数が9個あるのに式は5式しかないので、解は一意に決まりません

無数にある解の中から、目的関数の値が最大になるような変数を見つけるところに難しさがあります。

 

このような難しさはありますが、普通の連立方程式を解くように掃き出し法が使えますので、まずは5つの式から拡大係数行列を作成します。

定数項を右辺に集めて、変数ごとに列を揃えて書くと次のようになります。

ここでa1a4はそれぞれ式⑤’中のx、y、z、wの係数です。

 

シンプレックス法を実行する

後は、この行列を単位行列が部分的にできるように行基本変形していくのですが、よく見ると下記のように既に単位行列ができています。

(列を並び替えていますが、行基本変形と同じように列基本変形をしても連立方程式の解は変わりません)

 

従って、

S1 = 25000

S2 = 5000

S3 = 8000

S4 = 2500

m = 0

は、この連立方程式の無数にある解の中の1つになっています。

そして、残りの変数x、y、z、wを0にすると、制約条件で囲まれる図形の頂点の1つの座標になります。(基底解といいます)

つまり、(s1, s2, s3, s4, m, x, y, z, w) = (25000, 5000, 8000, 2500, 0, 0, 0, 0, 0)の点は、制約条件で囲まれる図形の1つの頂点になっているということです。

では頂点は何個あるのかというと、この問題では126個あります。

なぜでしょうか?

次の拡大係数行列を見て下さい。

 

単位行列になっている部分は、列ごとに見ると、各変数が単位ベクトルになっています。

このように単位ベクトルになっている変数のことを基底変数というのですが、9個の変数のうちどの5個を基底変数にするかの組み合わせの数は9C5通り(=126)あります。

組み合わせの数の計算方法については、こちらを参照して下さい。

【順列と組み合わせを学びなおす!】具体例を使ってわかりやすく解説します。

 

ここで基底変数の解は、拡大係数行列の最右列に計算される値になります。

一方、非基底変数はこの行列では求まらないのですが、これらをすべてゼロとすると制約条件で囲まれる図形の頂点になります。

従って、この問題では合計126個の頂点があり、その中からm(目的関数の値)が最大になる頂点を探すという最適化問題になります。

 

ですので、拡大係数行列を何百回も行基本変形して126通りの解を求めてもいいのですが、それでは余りにも時間がかかりすぎます。

そこでムダな解はスキップして、意味のある解だけを選択的に調べるためのアルゴリズムがシンプレックス法です。

このアルゴリズムは1947年に開発され、現在でも様々なシーンで使われている優れものです。

 

このアルゴリズムは簡単にいうと、掃き出し法を行う順番を決めるためのものです。

掃き出し法は、解を求めたい変数の列が単位ベクトルになるように行基本変形することでした。

単位ベクトルにするということは、その列のいずれかの成分を1にして、残りはすべて0にすることです。

シンプレックス法は、どの列(つまりどの変数)のどの行(つまりその列のどの成分)を1にすべきかということを順番に教えてくれます。

 

以下で具体的に手順を見てみましょう。

まず最初に最下行を見ます。

この中で一番小さい成分を探します。(ステップ①)

すると-0.00096です。

この成分は4列目にあります。

次に4列目の成分で最右列の成分を割ります。

例えば1行4列の成分はですが、これで1行10列の成分25000を割るのです。

すると3125になります。

これを4列目のすべての成分について行うと、3行目はゼロ割りになってしまい解がありませんが、残りは3125625312.5と求まります。

この中で最小値は312.5で、それは4行目にあります。(ステップ②)

ステップ①で4列目が、ステップ②で4行目が選ばれました。

この場合、4行4列の成分である0.08を1になるように行基本変形しなさいというのがシンプレックス法が教えてくれる順番です。

 

実際にこの列の掃き出しを終了すると、次のようになります。

そうしたら今やった①から③までのステップを繰り返します。

その結果、今度は2列目を掃き出し処理することになります。

これを最下行の成分がすべて非負になるまで繰り返します。

今回の例では4回繰り返したところで下記のように終了しました。

 

答えの見方は次の通りです。

s1=750、x=447.4、y=263.2、w=1250の時、目的関数mは最大値0.985になるということです。

この中でs1は不等式を等式で表すために導入したスラック変数なので無視すると、商品Aを447.4箱、商品Bを263.2箱、商品Dを1250箱積めば、重量ベースと容積ベースの積載率の平均値が98.5%となり、これが最大積載率になります。

2つの積載率を分けて計算すると重量ベースで97%、容積ベースで100%ですので、ほぼ満載できていることになります。

  1. 貨物Aと貨物Bの合計重量は8t以内
  2. 貨物Cと貨物Dの合計容積は25m3以内

という面倒な制約条件付きでここまでの積載率になるようにするのは「経験と勘」では難しいはずで、線形計画法の有用性が分かります。

 

またシンプレックス法を使うことで、少ない回数の行基本変形で最適解に辿り着くことができました。

126通りの組み合わせの中からピンポイントに効率良く計算した結果です。

このように、まともに解いていたら計算量が膨大になってしまう線形計画法を、少ない計算量で効率良くためのアルゴリズムがシンプレックス法です。