Excel で切手組み合わせ問題を整数計画問題として解く

2025/07/17 19:44 整数計画問題
当サイトでは任意の額面を手持ちの切手を組み合わせて用意する 切手組み合わせ計算ツール を公開しています。
その内部では整数計画問題ソルバである GLPK (Gnu Linear Programming Kit) を使って切手の使用枚数が最小となる最適解を求めていますが、同様のことを Microsoft Excel を使って求めてみようと思います。

準備

  1. Excel のオプション -> アドイン -> 管理 -> Excel アドイン -> ソルバーアドイン があるのを確認 -> 設定ボタンをクリック
    excel-option.png
  2. ソルバーアドイン にチェック -> OK ボタンをクリック
    excel-add-in.png

入力フォーマットや数式の入力

  1. 例えば次のようなフォーマットを用意します。
    excel-main-formula.png

    Excel ファイルは こちら
    xlsx_icon.png
    kitte.xlsx     です。
  2. C2 セルに 組み合わせたい金額を入力します
  3. B5 セルから B24 セルには切手の単価を入力します。とりあえず現在発売中の切手の金額を入力します。
  4. D5 セルから D24 セルに手持ちの枚数を入力します。
  5. F5 セルから F24 セルに後ほど結果が代入されます。なんでもいいのですが、とりあえず 0 で埋めておきます。
  6. C26 セルは組み合わせ試行中の合計金額を表します。数式 =SUMPRODUCT(B5:B24,F5:F24) を入力します。この数式は (単価×枚数) の総和を意味します。
  7. C27 セルは組み合わせ試行中の合計枚数を表します。数式 =SUM(F5:F24) を入力します。これがこの問題の最小化させたい目的関数となります。

ソルバーの設定

  1. メニューの データ タブ -> 分析 -> ソルバー をクリック
    excel-menu-solver.png

    excel-solver-setting.png
  2. 目的セルを C27 に設定します。このセルは合計枚数を示すものです。
  3. 目標値は 最小値 を選択します。合計枚数を最小にする解を得たいからです。
  4. 変数セルは F5:F24 にします。ソルバーによってこの範囲に各切手の枚数が代入されていきます。
  5. 制約条件の対象 に3つ条件を追加します。
    • (1) C26 = C2
      これによって合計金額が指定の金額と等しくなるように制約します。
      excel-subject-to-total.png
    • (2) F5:F24 <= D5:D24
      これによって各切手の使用枚数が各々の在庫数以下であることを制約します。
      excel-subject-to-stock.png
    • (3) F5:F24 = 整数
      これによって切手の使用枚数が整数しか取り得ないことを制約します。
      整数に制約したいときには真ん中のセレクトボックスで int を選択します。
      excel-subject-to-integer.png
  6. 制約のない変数を非負数にする にチェックします。切手の使用枚数はマイナスにはならないからです。
  7. 解決方法の選択 では シンプレックスLP を選択します。ここで解決したい問題が線形を示す問題だからです。
  8. 最後に 解決　ボタンをクリックします。

結果を読む

  1. 「整数解が見つかりました」と出たら成功です。
    excel-solver-found.png
    • ソルバーの解の保持 を選択して OK ボタンをクリックします。
    • F5:F24 セル範囲に代入されている枚数が答えです。
  2. 「実行可能解が見つかりませんでした」と出たら、手持ちの切手では合計金額ちょうどの組み合わせが作れなかったということです。
    excel-solver-not-found.png
    • 計算前の値に戻す を選択して OK ボタンをクリックして戻り、在庫枚数などの条件を見直しましょう。

参考

  1. Wikipedia日本語版「整数計画問題」: https://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E8%A8%88%E7%94%BB%E5%95%8F%E9%A1%8C
  2. Wikipedia日本語版「切手問題」：https://ja.wikipedia.org/wiki/%E5%88%87%E6%89%8B%E5%95%8F%E9%A1%8C