Satoshi's Data Labo            
Road to Clearing Master : Open Item 消込へのナップサック問題解法の応用 (その1)

偶には本業の経理業務に回帰して、何かやってみたいと思う。 計算複雑性理論の典型例にナップサック問題(容量の決まったナップサックに収まるように色んなサイズの荷物を上手く詰め合わせる命題)というのがあるが、特に帳簿の消込のように、Open Item群から合計が指定値となる複数の組み合わせを抽出する命題のことを、Subset-Sum Problemという。

今回はWebで見つけたSubset-Sum Problem解決プログラムを活用しつつ、エクセルVBAやPHPを使ったソリューションを考えてみたい。


Excel VBA版

インドのプログラマーが開発したナップサック問題解決コードを、ニュージーランドのプログラマーが改良したものがネットにアップされていたので、それを拝借してサブセットサム問題解決用に手直ししたもの。

ダウンロードはこちらから ➡ Subset-Sum.xlsm

使い方は自明だと思うので細かい説明は割愛しますが、50件までのOpen Itemをシートにエントリーすれば、合計がゼロになる組み合わせを全て書き出してくれる仕組みです。

N件の母集団について、全ての組み合わせを確認するためには、2のN乗 のシミュレーションが必要なので、PC上のエクセルVBA では50件程度が処理能力の限界に近いのだろう。
(2^10=千、  2^20=百万、 2^30=十億、 2^40=一兆、 2^50=千兆、 2^60=百京...)

こうしたエクセルVBAの限界を取り払うため、隣のページではPHP を使ったソリューションも作成してみた。 狙いとしては、PCよりも処理能力の高いサーバーの処理能力を利用するため、ユーザがOpen Itemを入力できるPHPベースのシステムをサーバー上に構築したもの。

番外編 : Excel Solver版

実務に使えるものではないが、Excel のSolverアドインを活用したプロトタイプです。 使い方が面倒だし、複数解が存在する場合の対応に課題があるが、VBA版にも共通することですが SumProduct関数の基本的な活用方法を理解するうえではいい素材だと思うのでついでにアップしておきます。 一般にExcel 関数の中でも、vlookup関数とSumProduct関数は便利関数の双頭と言われている割に、vlookup程は活用されていないような気がするので、ご参考まで。

ダウンロードはこちらから ➡ Solver_Version.xlsx

おまけ : 参考文献

利益計画でのソルバーの利用と限界.pdf
Excel で始める数理最適化.pdf

 
 
Copyright © 2017 Satoshi Ashikari All Rights Reserved.