2段階シンプレックス法で貨物積載率が最大になる条件を求めてみた。
制約条件に上限と下限が混じる場合には2段階シンプレックス法
前回の記事でトラックの積載率を最大化するために、比重が異なる4種類の貨物をどう組み合わせれば良いかを線形計画法で求めました。
その時の制約条件は下記の通りでした。
4種類の貨物の合計重量が25t以下(トラックの最大積載重量)
4種類の貨物の合計重量が50m3以下(トラックの最大積載容積)
貨物Aと貨物Bの合計重量が8t以下
貨物Cと貨物Dの合計重量が25m3以下
このように、すべての制約条件は上限を設定しています。
しかし時には下限を設定したい場合もあるでしょう。
例えば、3番目と4番目の条件を下記のようにしたい場合です。
貨物Aと貨物Bの合計重量が8t以上
貨物Cと貨物Dの合計重量が25m3以上
ちょっとした違いですが、線形計画法で解くには工夫が必要です。
なぜなら、線形計画法の標準形は下記のような2パターンのいずれかだからです。
【パターン1】
目的関数の最大化問題の場合 ⇒ 制約条件はすべて上限(式≦定数の形)
【パターン2】
目的関数の最小化問題の場合 ⇒ 制約条件はすべて下限(式≧定数の形)
つまり、制約条件に上限条件と下限条件が混じっていてはいけないのです。
混じっているとどういうことになるかについては後ほど出てきますが、非負条件を満たす初期解が簡単には求まらなくなります。
そこで、まずは①非負条件を満たす初期解をシンプレックス法を使って求め、②その初期解を使って元の問題をシンプレックス法を使って解く、というように2段階でシンプレックス法を使います。
以下、具体例で見ていきましょう。
業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!
非負条件を満たす初期解を求める(第一段階)
制約条件式に上限と下限が混じる貨物積載率最大化の例
今回は次のような状況を想定します。
――――――――――――――――――――――――
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の大型トラックで運ぶ時、容積ベースでも重量ベースでも積載率を最大にするためには、どの貨物をどれだけ積めば良いでしょうか?
但し、諸事情から次の条件を満たさなくてはいけません。
- 貨物Aと貨物Bは6t以上積む
- 貨物Cと貨物Dは合計20m3以上積む
――――――――――――――――――――――――
前回との違いは青字部分だけです。
4つの制約条件を式で表すと、次のようになります。
12x + 10y + 8z + 13w ≦ 25000 ・・・①
0.05x + 0.01y + 0.08z + 0.02w ≦ 50 ・・・②
12x + 10y ≧ 6000 ・・・③
0.08z + 0.02w ≧ 20 ・・・④
このように、①と②は上限を設定していますが、③と④は下限を設定しています。
ちなみに目的関数は重量べース積載率と容積ベース積載率の平均で、これは前回と同じです。
目的関数={(12x + 10y + 8z + 13w) / 25000 + (0.05x + 0.01y + 0.08z + 0.02w) / 50} / 2 ・・・⑤
スラック変数が実行可能な初期解にならない
まずは不等式の制約条件を等式に変えるために、前回と同じようにスラック変数s1~s4を導入して下記のように制約条件式を変換します。
12x + 10y + 8z + 13w + s1 = 25000 ・・・①’
0.05x + 0.01y + 0.08z + 0.02w + s2 = 50 ・・・②’
12x + 10y – s3 = 6000 ・・・③’
0.08z + 0.02w – s4 = 20 ・・・④’
ここで注意すべきは、③と④の不等式では左辺の方が大きいので、非負のスラック変数を引かないといけないことです。
「別に引いてもいいじゃないか」
と思うかもしれませんが、拡大係数行列にすると次のような不都合が起きます。
このようにs3とs4の係数ベクトルが単位ベクトルになりません。
ということはs3とs4が基底変数にならないということです。
(s3=-6000、s4=-20になり、これは非負という条件を満たさない)
つまり、s1=25000、s2=50、s3=-6000、s4=-20は、実行可能な初期解ではありません。
解がゼロになるようなダミー変数を見つける
そこで、あと2つダミーの非負変数t1とt2を次のように導入します。
12x + 10y – s3 + t1 = 6000 ・・・③’’
0.08z + 0.02w – s4 + t2 = 20 ・・・④’’
そして、t1+t2がゼロとなるような変数x、y、z、w、s1~s4、t1~t2の組を求められれば、t1とt2はなかったものとして、その時の変数の組を初期解として元の線形計画法を解くことができます。
そこで、m=-t1-t2を目的関数として、これを下記の制約条件の元で最大化(t1+t2がゼロになるということ)するような問題をまず解きます。
12x + 10y + 8z + 13w + s1 = 25000 ・・・①’
0.05x + 0.01y + 0.08z + 0.02w + s2 = 50 ・・・②’
12x + 10y – s3 + t1 = 6000 ・・・③’’
0.08z + 0.02w – s4 + t2 = 20 ・・・④’’
この連立方程式の拡大係数行列は次のようになります。
ここで、s1とs2は基底変数になっていますが、t1とt2はなっていません。
しかし、最下行のtiの係数をゼロにすれば基底変数になります。
そこで、最下行から3行目と4行目を引くという行基本変形を行います。
すると次のようになります。
ここからはシンプレックス法に従って最下行の成分がすべて非負になるまで掃き出しを行います。
すると次のようになります。

これで、x=500, y=250, s1=17000, s2=5(その他の変数はゼロ)の時、mが0になることが分かりました。
ここでm=-t1-t2、かつt1もt2の非負の変数なので、t1=t2=0ということです。
つまり、x=500, y=250, s1=17000, s2=5(その他の変数はゼロ)の時、ダミー変数t1とt2はなくしても問題ない、即ち元の線形計画法の問題に戻ったことになります。
求まった初期解を使って元の問題を解く(第二段階)
シンプレックス法で解く
それでは、x=500, y=250, s1=17000, s2=5(その他の変数はゼロ)を初期解として元の問題を定式化してみましょう。
拡大係数行列は次のようになります。
さて、ここでまた困ったことになりました。
xとzが基底変数でなくなってしまったのです。
そこで、再び行基本変形によってxとzの最終行を0にします。
最終行に3行目×0.00074と、4行目×0.00096を足します。
すると次のようになります。
これで基底変数が4つできましたので、普通にシンプレックス法で解いていきます。
最終行の成分がすべて非負になるように掃き出しを行うと、次のようになります。
このように最大積載率は94.5%になりました。
スラック変数以外が意味のある解
その時x=500, w=1250, s1=2750, s4=5(その他の変数はゼロ)ですが、s1とs4はスラック変数です。
これは最初の制約条件式①と④において、不等式が等式になるまでの余裕量を表しています。
例えば、
12x + 10y + 8z + 13w ≦ 25000 ・・・①
はスラック変数s1を使って、
12x + 10y + 8z + 13w + s1 = 25000 ・・・①’
のように等式にしました。
ですので、s1=2750ということは、①の不等式が等式になるまで2750の余裕があることを表しています。
従って、4つの基底変数の中で意味のある変数はx=500、w=1250だけです。
つまり、商品Aを500箱、商品Dを1,250箱トラックに積めば、すべての制約条件を満たしながら最大積載率94.5%になります。
確かめてみると、
合計重量=500×12+1,250×13=22,250(重量ベース積載率89%)
(商品Aの重量は6,000kg≧6t)
合計容積=500×0.05+1,250×0.02=50(容積ベース積載率100%)
(商品Dの容積は25m3≧20m3)
となり、制約条件を満たしながらそれらしい値になっていることが確認できます。
Udemyの関連講座
Optimization with Excel: Operations Research without Coding
Optimization with Gurobi, CBC, IPOPT. Linear programming, nonlinear, genetic algorithm. Using Excel, without coding
Assignment and Transportation Problem Operations Research 01
The Hungarian Assignment Problem and Transportation Problem
Optimization with Python: Solve Operations Research Problems
Solve optimization problems with CPLEX, Gurobi, Pyomo… using linear programming, nonlinear, evolutionary algorithms…
業務改善/ロジスティクスエンジニアリングの求人数が多いのはここだ!