決められた数字の組み合わせが逆算出来るソフト

質問

• 決められた数字の組み合わせを逆算するソフトやサイトを探しています。商品の組み合わせ方法が決まっており、各商品には在庫があります。
• 商品の種類は10種類で、それぞれ0～9の番号で識別されます。S、M、Lの3種類のセットを作成する際には特定の商品を組み合わせます。
• 500個の商品を無駄なく使い切るために、Sセット、Mセット、Lセットの組み合わせを選びたいと考えています。効率的な組み合わせを自動的に識別できるソフトやサイトを探しています。

回答No.4

ki073

組み合わせの場合数が複雑でないのでしたら、No.2の方法でもよいように思いますが、
複雑になってきて、ある程度最適な組み合わせを見つけたいときには、線形（整数）計画法を使うのが良いかも知れません。
GLPKというフリーのソフトがあり、Unix系OSやWindowsでも使えます。
以前回答したものをリンクしておきますが、はじめて見ると相当手強いと思います。
http://okwave.jp/qa/q7579420.html

実際に質問欄のものでやったプログラムを書いておきます。急いで作ったので間違いがあるようにも思いますが、答えを書いていきます。
まずは制限なしで、セットを最大数作る場合では72セットできるようです。
NumberofSet[L1].val = 0
NumberofSet[L2].val = 0
NumberofSet[L3].val = 17
NumberofSet[M1].val = 15
NumberofSet[M2].val = 19
NumberofSet[M3].val = 12
NumberofSet[S1].val = 9
NumberofSet[S2].val = 0
NumberofSet[S3].val = 0
TotalSetNumber.val = 72

次に制限を加え、LセットとSセットの合計が25個以上になるような条件を加えると69セット
NumberofSet[L1].val = 12
NumberofSet[L2].val = 2
NumberofSet[L3].val = 11
NumberofSet[M1].val = 0
NumberofSet[M2].val = 6
NumberofSet[M3].val = 12
NumberofSet[S1].val = 11
NumberofSet[S2].val = 15
NumberofSet[S3].val = 0
TotalSetNumber.val = 69

使ったプログラムは
#-----------次から
set SetName; # セットの名前
set Index := 1..5; # セットの中の番号
set GoodsID := 0..9; # 詰め合わせる商品の番号

param AssortmentList{SetName, Index}; # 詰め合わせリスト
param assortment{p in SetName, g in Index, gi in GoodsID}, binary, := if gi=AssortmentList[p, g] then 1 else 0 ;
var NumberofSet{SetName}, >=0, integer; # セットごとの数
var requiredNumber{GoodsID}, >=0, integer; # 必要な商品数

maximize TotalSetNumber: sum{p in SetName}NumberofSet[p];
s.t. TotalN{k in GoodsID} : sum{p in SetName, j in Index}assortment[p, j, k]*NumberofSet[p]=requiredNumber[k];
s.t. required{k in GoodsID} : requiredNumber[k]<=50;

solve;
display requiredNumber; # 商品ごとの必要数
display NumberofSet; # セットごとの数
display TotalSetNumber; # 作ることのできるセット数合計

data;
set SetName := L1, L2, L3, M1, M2, M3, S1, S2, S3;
# 詰め合わせリスト
param AssortmentList: 1 2 3 4 5:=
L1 2 5 4 5 7
L2 3 6 5 6 8
L3 3 7 6 7 9
M1 1 4 3 4 7
M2 2 5 4 5 8
M3 2 6 5 6 8
S1 0 3 2 3 6
S2 1 4 3 4 7
S3 0 4 3 4 7
;
end;
#--------この上まで
# glpsol --math program.mod
# コマンド
です。
s.t. SetL : NumberofSet["L1"]+NumberofSet["L2"]+NumberofSet["L3"]>=25;
s.t. SetS : NumberofSet["S1"]+NumberofSet["S2"]+NumberofSet["S3"]>=25;
で条件を追加したのが、二番目の結果です。
このように思うような条件を加えていけば、なんとかなりそうに思います。

興味がありましたら、書き込んでください。要領さえわかれば簡単に改良できます。

お礼

本当に詳しい詳細をご記入頂きありがとう御座います。

制限あり、なしでの作成出来るセット数や計算式も非常に参考になりました。

GLPKのようなソフトも非常に良いものだと思います。こちらも今後とも活用していけたらと思っております。

大変貴重なお時間と適切なご回答を頂き、ありがとう御座いました。