２段階シンプレックス法で貨物積載率が最大になる条件を求めてみた。

2022年1月10日2022年11月6日

制約条件に上限と下限が混じる場合には２段階シンプレックス法

前回の記事でトラックの積載率を最大化するために、比重が異なる４種類の貨物をどう組み合わせれば良いかを線形計画法で求めました。

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

 

その時の制約条件は下記の通りでした。

 

４種類の貨物の合計重量が２５ｔ以下（トラックの最大積載重量）

４種類の貨物の合計重量が５０ｍ^３以下（トラックの最大積載容積）

貨物Aと貨物Bの合計重量が８ｔ以下

貨物Cと貨物Dの合計重量が２５ｍ^３以下

 

このように、すべての制約条件は上限を設定しています。

しかし時には下限を設定したい場合もあるでしょう。

例えば、３番目と４番目の条件を下記のようにしたい場合です。

 

貨物Aと貨物Bの合計重量が８ｔ以上

貨物Cと貨物Dの合計重量が２５ｍ^３以上

 

ちょっとした違いですが、線形計画法で解くには工夫が必要です。

なぜなら、線形計画法の標準形は下記のような２パターンのいずれかだからです。

 

【パターン１】

目的関数の最大化問題の場合　⇒　制約条件はすべて上限（式≦定数の形）

 

【パターン２】

目的関数の最小化問題の場合　⇒　制約条件はすべて下限（式≧定数の形）

 

つまり、制約条件に上限条件と下限条件が混じっていてはいけないのです。

混じっているとどういうことになるかについては後ほど出てきますが、非負条件を満たす初期解が簡単には求まらなくなります。

そこで、まずは①非負条件を満たす初期解をシンプレックス法を使って求め、②その初期解を使って元の問題をシンプレックス法を使って解く、というように２段階でシンプレックス法を使います。

以下、具体例で見ていきましょう。

 

業務改善／ロジスティクスエンジニアリングの求人数が多いのはここだ！

 

非負条件を満たす初期解を求める（第一段階）

制約条件式に上限と下限が混じる貨物積載率最大化の例

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

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

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

貨物A

１箱の重量：12kg

１箱の容積：0.05m³

貨物B

１箱の重量：10kg

１箱の容積：0.01m³

貨物C

１箱の重量：8kg

１箱の容積：0.08m³

貨物D

１箱の重量：13kg

１箱の容積：0.02m³

 

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

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

1. 貨物Aと貨物Bは６ｔ以上積む
2. 貨物Cと貨物Dは合計２０ｍ^３以上積む

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

 

前回との違いは青字部分だけです。

４つの制約条件を式で表すと、次のようになります。

 

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　・・・⑤

 

スラック変数が実行可能な初期解にならない

まずは不等式の制約条件を等式に変えるために、前回と同じようにスラック変数s₁～s₄を導入して下記のように制約条件式を変換します。

 

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

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

12x + 10y – s₃ = 6000　・・・③’

0.08z + 0.02w – s₄ = 20　・・・④’

 

ここで注意すべきは、③と④の不等式では左辺の方が大きいので、非負のスラック変数を引かないといけないことです。

「別に引いてもいいじゃないか」

と思うかもしれませんが、拡大係数行列にすると次のような不都合が起きます。

 

このようにs₃とs₄の係数ベクトルが単位ベクトルになりません。

ということはs₃とs₄が基底変数にならないということです。

（s₃=－6000、s₄=－20になり、これは非負という条件を満たさない）

つまり、s₁=25000、s₂=50、s₃=－6000、s₄=－20は、実行可能な初期解ではありません。

 

解がゼロになるようなダミー変数を見つける

そこで、あと２つダミーの非負変数t₁とt₂を次のように導入します。

12x + 10y – s₃ + t₁ = 6000　・・・③’’

0.08z + 0.02w – s₄ + t₂ = 20　・・・④’’

 

そして、t₁+t₂がゼロとなるような変数x、y、z、w、s₁～s₄、t₁～t₂の組を求められれば、t₁とt₂はなかったものとして、その時の変数の組を初期解として元の線形計画法を解くことができます。

そこで、m=-t₁-t₂を目的関数として、これを下記の制約条件の元で最大化（t₁+t₂がゼロになるということ）するような問題をまず解きます。

 

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

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

12x + 10y – s₃ + t₁ = 6000　・・・③’’

0.08z + 0.02w – s₄ + t₂ = 20　・・・④’’

 

この連立方程式の拡大係数行列は次のようになります。

 

ここで、s₁とs₂は基底変数になっていますが、t₁とt₂はなっていません。

しかし、最下行のt_iの係数をゼロにすれば基底変数になります。

そこで、最下行から３行目と４行目を引くという行基本変形を行います。

すると次のようになります。

 

ここからはシンプレックス法に従って最下行の成分がすべて非負になるまで掃き出しを行います。

すると次のようになります。

 

これで、x=500, y=250, s₁=17000, s₂=5（その他の変数はゼロ）の時、mが０になることが分かりました。

ここでm=-t₁-t₂、かつt₁もt₂の非負の変数なので、t₁=t₂=0ということです。

つまり、x=500, y=250, s₁=17000, s₂=5（その他の変数はゼロ）の時、ダミー変数t₁とt₂はなくしても問題ない、即ち元の線形計画法の問題に戻ったことになります。

 

求まった初期解を使って元の問題を解く（第二段階）

シンプレックス法で解く

それでは、x=500, y=250, s₁=17000, s₂=5（その他の変数はゼロ）を初期解として元の問題を定式化してみましょう。

拡大係数行列は次のようになります。

 

さて、ここでまた困ったことになりました。

xとzが基底変数でなくなってしまったのです。

そこで、再び行基本変形によってxとzの最終行を0にします。

最終行に３行目×0.00074と、４行目×0.00096を足します。

すると次のようになります。

 

これで基底変数が４つできましたので、普通にシンプレックス法で解いていきます。

最終行の成分がすべて非負になるように掃き出しを行うと、次のようになります。

 

このように最大積載率は９４.５％になりました。

 

スラック変数以外が意味のある解

その時x=500, w=1250, s₁=2750, s₄=5（その他の変数はゼロ）ですが、s₁とs₄はスラック変数です。

これは最初の制約条件式①と④において、不等式が等式になるまでの余裕量を表しています。

例えば、

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

はスラック変数s₁を使って、

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

のように等式にしました。

ですので、s₁=2750ということは、①の不等式が等式になるまで2750の余裕があることを表しています。

従って、４つの基底変数の中で意味のある変数はx=500、w=1250だけです。

つまり、商品Aを５００箱、商品Dを１,２５０箱トラックに積めば、すべての制約条件を満たしながら最大積載率９４.５％になります。

確かめてみると、

合計重量＝５００×１２＋１,２５０×１３＝２２,２５０（重量ベース積載率８９％）

（商品Aの重量は６,０００ｋｇ≧６ｔ）

合計容積＝５００×０.０５＋１,２５０×０.０２＝５０（容積ベース積載率１００％）

（商品Dの容積は２５ｍ³≧２０ｍ³）

となり、制約条件を満たしながらそれらしい値になっていることが確認できます。

 

 

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…

 

業務改善／ロジスティクスエンジニアリングの求人数が多いのはここだ！