エクセルで残額が最小となるように選び出したい

質問

手形が50枚ほどあり、それを一部仕入先に裏書譲渡し、残額は現金で支払います。
現金で支払う額を少なくするように手形（何枚でも可）を自動的に選び出せるようにしたいのですが、計算式など
方法はありますでしょうか？

例
手持ちの手形金額50,000、200,000、300,000、400,000、500,000

支払価額　630,000【裏書譲渡（200,000＋400,000）＋現金30,000】

実際には数字はもっと細かくてこの方法の支払先が10社ほどあり、いつも最適な組み合わせを考えなければならずどの手形の組み合わせで現金支払が最小で済むのか悩んでいます。検索？や統計？で一気に探せたらと思うのですが、もし方法がありましたら、教えてください。
エクセルの数式は結構好きなので、できればうれしいのですが。

回答No.6

ki073 · ベストアンサー

続きです。
金額が最適なものを選んでくれるのは良いのですが、特定の手形を除外せずに使いたい場合は、
手形１～１０を必ず使いたいとき
s.t. seiyaku7{t in {1..10}}: sum{s in Shiharaisaki}tegata_shiharai_maisuu[t, s]=1;
逆に除外したいとき
s.t. seiyaku8{t in {1..10}}: sum{s in Shiharaisaki}tegata_shiharai_maisuu[t, s]=0;
を追加します。
いろいろと条件を付けられそうです。

制限を加えると多分手形での支払い金額は減ってくると思いますので、適宜使用者が判断するのが良いように思います。

さて、計算結果をエクセルに戻したい時には出力をタブ区切りで出した方が便利なように思います。
やり方は分かりますか？

お礼

親切に色々教えてくださってありがとうございました。

家のＰＣではうまく起動したのですが、会社のＰＣでは上手く起動しませんでした（セキュリティとか色々入れられているからかもしれません）

教えていただいた方法は私には難しいのでこれをヒントに違う方法を考えたいと思います。

今回は「コマンドプロンプト」が初体験でワクワクしましたしとても勉強になりました。
（私も自分でプログラムできたらいいなと思いました）
貴重なお時間を割いて色々お考え頂きありがとうございました。

回答No.5

ki073

手形をまとめる方法を考えてみましたが、手動でやるのが良いように思います。
やり方ですが、
まず全部の手形リストを作って計算します。その答えが一番現金を少なくする分け方です
（同じ金額の他の分け方があるかもしれませんが、金額は最適条件です）

一つの方法としては、excelでまとめた金額の表を作り直してもう一度計算し直すというのもあります。
手形には１から番号を振っていますが、アルファベットが混ざっていてもよいし番号順になっていなくても良いです。

別の方法として、制約条件を加えていく方法があります。こちらの方が簡単かもしれません。
プログラムにs.t.から始まる行がありますが、その下あたり(solve;の前まで)に追加します。

例えば手形2と3を同じ取引先にしたい場合は次の行を追加します。
s.t. seiyaku4{s in Shiharaisaki}: tegata_shiharai_maisuu[2, s]=tegata_shiharai_maisuu[3, s];
2と3～5までを同じにしたい場合には
s.t. seiyaku5{s in Shiharaisaki, t in {3..5}}: tegata_shiharai_maisuu[2, s]=tegata_shiharai_maisuu[t, s];
のような書き方も出来ますし、数字が飛んでいる場合には
s.t. seiyaku6{s in Shiharaisaki, t in {3,4,5,9}}: tegata_shiharai_maisuu[2, s]=tegata_shiharai_maisuu[t, s];
のような書き方も出来ます。

制約条件は他にも使い道があって、手形1をDに割り当てたい場合は(数字はそのまま入れるが、文字は""で囲むこと)
s.t. seiyaku1: tegata_shiharai_maisuu[1, "D"]=1;
逆に手形2をDに割り当てたくない場合は
s.t. seiyaku2: tegata_shiharai_maisuu[2, "D"]=0;
とします。

それと、s.t. seiyaku1のようにs.t.の後のラベルseiyaku1が他の条件のラベルと同じになっていたらエラーになりますので、適当に変えてください。
もう一つ、行の始めに#をつけるとコメントになりますので、適宜追加して分かりやすくしてみてください。

回答No.4

ki073

補足欄からすると、まとめたい特定の手形があるのではなく、小額のものはなるべくまとめたいということでしょうか。
特定の手形があるのかと思っていました。もう少し考えてみます。

入力方法を少し改良したものを載せておきます。
paramと重なっていた
set Tegata:=
set Shiharaisaki:= A B C D;
の部分がなくなりました。
データ部分はエクセルからそのままコピーしてみてください。できるはずです。

set Tegata;
param tegata_kingaku{Tegata};

set Shiharaisaki;
param shiharaigaku{Shiharaisaki};

var tegata_shiharai_maisuu{Tegata, Shiharaisaki} ,binary;

maximize TegataTotal: sum{s in Shiharaisaki, t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s];
s.t. TegataShiharai{s in Shiharaisaki}: sum{t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s]<= shiharaigaku[s];
s.t. uniq{t in Tegata}: sum{s in Shiharaisaki}tegata_shiharai_maisuu[t, s]<=1;

solve;
# Output
printf " Tegata Kingaku";
for {s in Shiharaisaki} {printf "%5s", s;} printf "\n";
for {t in Tegata} {
printf "%5s %10d ", t, tegata_kingaku[t];
for {s in Shiharaisaki} {
printf " %3s ", tegata_shiharai_maisuu[t, s];
}
printf "\n";
}
printf "\n";
printf "Tegata shiharai total: %d\n", sum{t in Tegata, s in Shiharaisaki}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s];
printf "Shiharaisaki betu\n";
for {s in Shiharaisaki} {
printf "%5s %10s\n",s ,sum{t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s];
}

data;
param : Tegata : tegata_kingaku:=
1 50000
2 200000
3 300000
4 400000
5 500000
6 20000
7 1200000
;
param : Shiharaisaki : shiharaigaku:=
A 630000
B 1250000
C 20000
D 0
;
end;

回答No.3

ki073

>貴重なお時間を割いて教えてくださってありがとうございます。
いえいえ気にしなくて結構です。すこし難しそうな質問でしたので、パズル解きのようなつもりで楽しんでやってます。

フォルダはw32でした。すみません。w32がありますので解凍は終わっています。
普段はほとんどWindowsを使っていませんので、適切な説明ができないかも知れませんが、XPでは次のようにすれば計算できます。

まずは、正常に動くか確認してください。
No.2の下のプログラム部分を「メモ帳」などのソフトにコピーして、w32フォルダにtagata.modの名前で保存してください。
アクセサリの中に「コマンドプロンプト」のソフトがありますので起動してください。
黒いWindowがでますので、キーボードからCDに続けてスペースを入れ、マウスでw32フォルダを文字を入れた黒いウインドウ上にドラッグしてボタンを離してください。そうすると１行程度の文字列が入るはずです。改行キーを押して、
glpsol.exe -m tagata.mod（改行キー）と入れてください。
直ぐに答えが返ってくるはずです。手形の使用合計金額は同じになるはずですが、割り振りは少し違う結果になるかもしれません。

手形のことはほとんど分からないので、質問ですが、
＞例：５万の手形が１０枚あっても１０社にバラして使うのではなく何社かにまとめて使い、裏書先を少なくする
同じ金額が複数枚あるのでしょうか、それとも金額が違う場合が多いのでしょうか？

＞手持手形は80枚程度ある
この場合、上の１０枚は出来るだけバラしたくはないが10枚と数えて８０枚程度なのでしょうか。それともとりあえずバラしたくないので１枚と数えた数字なのでしょうか？
（80種類の手形があるとするのか、まとめたいのでもっと少ないとして処理するのか）

＞１回使った手形は他の支払先には使えない
既に支払いにあてた手形は使えないということですよね。普通のお金と一緒の考えですよね。
それとも上の出来るだけまとめたいということと関係あるのでしょうか？
５万の手形が１０枚まとめてあって、そのうち８枚を支払いに使ってしまった場合に、残りの２枚は裏書きには使えないという意味ではないですよね。裏書きの手間さえ厭わなければ２枚も使えますよね。
このように１０枚まとめてあったときにはどのような形で裏書きをするのでしょうか？一枚ずつ分かれていなくて、つながったような形をしているのでしょうか？（素人ですみません、興味本位ですが）

少し考えてみます。できそうな気がしますので。
通勤時間の暇つぶしにちょうどいいのです。

補足

早速のお返事ありがとうございます。助かります。
計算結果は
Tegata Kingaku A B C D
1 50000 0 1 0 0
2 200000 1 0 0 0
3 300000 0 0 0 0
4 400000 1 0 0 0
5 500000 0 0 0 0
6 20000 1 0 0 0
7 1200000 0 1 0 0
（空白が無くなって見にくいですが、実際の出力は見やすいです）
Shiharaisaki betu
A 620000
B 1250000
C 0
D 0
↑この様に出ました。ご丁寧に説明していただいてありがとうございます。
実際数字を入力して確かめてみます。

同じ金額が複数枚あるのでしょうか、それとも金額が違う場合が多いのでしょうか？→金額が違うものが80枚（80種類）です。（同じ金額のものは2-3枚ありますが現状況では無視していいと思います。）５万の手形が１０枚ということは現実にはありませんが、それくらい少ない金額のものが多数あれば、支払先すべてにバラまくのではなくできるだけ支払先をまとめたいという意味です。

既に支払いにあてた手形は使えないということですよね。普通のお金と一緒の考えですよね。→そうです。

それとも上の出来るだけまとめたいということと関係あるのでしょうか？
→関係ありません。たとえばエクセルで「この中から残金額が最小のものを選ぶ」と条件指定した場合、同じ手形があちこちに使われる可能性があると思い
ルールに入れました。

５万の手形が１０枚まとめてあって、そのうち８枚を支払いに使ってしまった場合に、残りの２枚は裏書きには使えないという意味ではないですよね。裏書きの手間さえ厭わなければ２枚も使えますよね。→
手形で支払いが出来る先は10社程度なので
支払い金額が少なくて今月は8枚しか使えず、来月以降残り2枚は使えます。
急いで全部使う必要はありません。
10社の支払いに80枚の手形の中から使えるものを使う、残りの手形は
別の用途で使えます。

このように１０枚まとめてあったときにはどのような形で裏書きをするのでしょうか？一枚ずつ分かれていなくて、つながったような形をしているのでしょうか？→手形は金額の書かれた紙1枚なので裏に銀行印を押して支払先に送ります。10枚の手形の裏に印を押して送ります。
つながっていません。バラバラの紙です。

回答No.2

ki073

No.1です。
>実際には数字はもっと細かくてこの方法の支払先が10社ほどあり、
10社程度を全体を見ながら割り振りたいということでしょうか？

先に紹介しましたExcelによる方法ですが、できないことは無いでしょうが、一遍にやってしますのは結構大変だと思います。やられるのでしたらまず一社ずつ順番に処理していくようにして、仕組み自体を理解した後で、一気にやってしまう方法を考えた方が良いように思います。少し考えてみたのですがExcelでやるのは結構大変なように思います。私の頭ではコンガラガってしまいました。

glpkでやる方法を紹介しておきます。基本的には何社でも処理できます。
Windowsのようですので
http://sourceforge.jp/projects/sfnet_winglpk/
からwinglpk-4.47.1.zip（今日時点）をダウンロードして解凍してください。中にwin32というフォルダがありますので、そこにプログラムが入っています。
glpsol.exe -m tagata.mod
をコマンドプロンプトで実行すれば計算できます。こちらはXPで確認しました。
計算結果は
Tegata Kingaku A B C D
1 50000 0 1 0 0
2 200000 1 0 0 0
3 300000 0 0 0 0
4 400000 1 0 0 0
5 500000 0 0 0 0
6 20000 1 0 0 0
7 1200000 0 1 0 0
（空白が無くなって見にくいですが、実際の出力は見やすいです）
Shiharaisaki betu
A 620000
B 1250000
C 0
D 0

プログラムは下記のとおりです
data;より下に計算するためのデータを入れてください。（それより上は変えないように）
set Tegata:=からは手形の名前（とりあえず数字にしています）
param tegata_kingaku:=からは手形の名前と金額
set Shiharaisaki:= A B C D;支払い先の名称（とりあえずアルファベットに）
param shiharaigaku:=からは支払い先の名称と支払い金額です。
それぞれ空白か改行で区切ればよいので、入力しやすいように入れてください。Excelなどからコピーして方が良いように思います。
そうそうデータの塊の最後のセミコロン(;)は忘れないように。
支払先ごとに上限金額や上限枚数などの条件も簡単に追加できます。
もし分からないことがありましたら、書き込んでください。
#-----------次の行からtagata.modのファイル名で保存
set Tegata;
set Shiharaisaki;
param tegata_kingaku{Tegata};
param shiharaigaku{Shiharaisaki};
var tegata_shiharai_maisuu{Tegata, Shiharaisaki} ,binary;

maximize TegataTotal: sum{s in Shiharaisaki, t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s];
s.t. TegataShiharai{s in Shiharaisaki}: sum{t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s]<= shiharaigaku[s];
s.t. uniq{t in Tegata}: sum{s in Shiharaisaki}tegata_shiharai_maisuu[t, s]<=1;

solve;
# Output
printf " Tegata Kingaku ";
for {s in Shiharaisaki} {
printf "%5s", s;
}
printf "\n";
for {t in Tegata} {
printf "%10s %10d ", t, tegata_kingaku[t];
for {s in Shiharaisaki} {
printf " %3s ", tegata_shiharai_maisuu[t, s];
}
printf "\n";
}
printf "\n";
printf "Shiharaisaki betu\n";
for {s in Shiharaisaki} {
printf "%5s %10s\n",s ,sum{t in Tegata}tegata_kingaku[t]*tegata_shiharai_maisuu[t, s];
}

data;
set Tegata:=
1
2
3
4
5
6
7;
param tegata_kingaku:=
1 50000
2 200000
3 300000
4 400000
5 500000
6 20000
7 1200000;
set Shiharaisaki:= A B C D;
param shiharaigaku:=
A 630000
B 1250000
C 20000
D 0;
end;

補足

貴重なお時間を割いて教えてくださってありがとうございます。
私はＰＣに詳しくありませんので手間取っていまして
＞からwinglpk-4.47.1.zip（今日時点）をダウンロードして解凍してください。中にwin32というフォルダがありますので、そこにプログラムが入っています。

のwin32が見つかりません。Ｗ32でしたらありましたがこれでしょうか？
申し訳ないのですが解凍の方法も教えてください。

10社程度を全体を見ながら割り振りたいということでしょうか→そうなんです。
自動的に条件に合う組合せを抽出できるようにしたいのですができますでしょうか？
ルールはまとめると、
支払先に手形の裏書譲渡をする。端数は現金（小切手）で支払う。
手形は何枚使ってもよい
現金の支払が一番少なくなるように手形を選ぶ
１回使った手形は他の支払先には使えない
手持手形は80枚程度ある、裏書先は１０社程度
該当の裏書手形がない場合は振込にしている
裏書先はまとめる（裏書の準備が手間なので）
例：５万の手形が１０枚あっても１０社にバラして使うのではなく何社かにまとめて使い、裏書先を少なくする

A社 1,831,200 例⇒手形 \942,069と\886,897 残額2,234（現金）

B社 2,062,200 例⇒手形 \463,776と \608,929と\970,000 残額19,495（現金）
・
・
・
・
となります。（ややこしくてすいません）

回答No.1

ki073

こういう場合には整数計画ソルバー（線形計画ソルバー）を使います。実際にはExcelでやったことは無いのですが、次のものを見る限り可能な様です。
http://lab.mgmt.waseda.ac.jp/intro_a/logistics/how2solver.pdf

Excelが得意なようですので、ヒントだけにしておきます。
まず、手形の金額の表をつくります。
目的セル 現金の支払額の計算値（支払額-支払いに使う手形総額）
目標値は現金の支払額ですので最小にする
制約条件は現金がマイナスになってはいけませんので、現金の支払額の計算値が0か正になるようにします。
もうひとつ大事なことですが、各手形に対してそれを使うか使わないかを示すセルが必要ですので、そこに0または1に制限されるようにします。

ご参考に

私自身はglpkという専用のフリーソフトでやりました。きれいに解けますよ。
ただし、答えは最小の組み合わせが複数有っても1つしか返ってきませんので