ITパスポート 2016年秋期問28

問題文

倉庫A, Bにある在庫の全量を店舗C, Dに輸送する。倉庫A, Bの在庫量がそれぞれ35個、15個、店舗C, Dの必要量がそれぞれ20個、30個であり、各倉庫から各店舗への1個当たりの輸送費が表のとおりであるとき、最小となる総輸送費は何万円か。

🖊️ 解答を隠して解いてみる

選択肢

ア：85

イ：100

ウ：110（正解）

エ：125

🔒 解説は解答すると表示されます

倉庫から店舗への輸送費の最小化【ITパスポート解説】

問題の要点を簡単にまとめます。
倉庫A、Bの在庫はそれぞれ 35個、15個。店舗C、Dの必要量はそれぞれ 20個、30個。
1個あたりの輸送費（単位：万円／個）は次の通りです。

倉庫A → 店舗C：4
倉庫A → 店舗D：2
倉庫B → 店舗C：2
倉庫B → 店舗D：1

この条件で「総輸送費を最小にする配分」を考えます。求める最小合計は 110 万円で、選択肢ではウが正解です。以下で理由をやさしく説明します。

正解の理由

単位当たりの費用が安い経路に単純に多く振り分ければよい、という直感は一見正しそうですが、倉庫ごとの在庫（供給）と店舗ごとの必要量（需要）という制約を同時に満たす必要があります。ここでは、B倉庫の在庫を店舗C（単価2）に充てれば、A倉庫が店舗Cに高い単価4で送る必要が減り、全体として費用が下がります。最適な割当を計算すると総費用は 110 万円になり、これが最小です。

具体的な最適配分の一例：

倉庫A → 店舗C：5個（4万円／個） → 5×4 = 20 万円
倉庫A → 店舗D：30個（2万円／個） → 30×2 = 60 万円
倉庫B → 店舗C：15個（2万円／個） → 15×2 = 30 万円
合計 = 20 + 60 + 30 = 110 万円

この配分は供給・需要の合計（A:35, B:15, C:20, D:30）を満たします。

解法ステップ

まず総供給と総需要が一致することを確認します。
A + B = 35 + 15 = 50、C + D = 20 + 30 = 50 → バランスしている（合計が等しい）。
変数を使って一般形に置きます（分かりやすくするため）。
- $x_{A C}$ = 倉庫A→店舗Cの個数
- $x_{A D}$ = 倉庫A→店舗Dの個数
- $x_{BC}$ = 倉庫B→店舗Cの個数
- $x_{B D}$ = 倉庫B→店舗Dの個数
供給・需要の式を書く：
- $x_{A C} + x_{A D} = 35$ （Aの供給）
- $x_{BC} + x_{B D} = 15$ （Bの供給）
- $x_{A C} + x_{BC} = 20$ （Cの需要）
- $x_{A D} + x_{B D} = 30$ （Dの需要）
上の式をいくつか整理して、自由変数１つで表せることを示します。例えば $x_{A C}$ を自由にすると：
- $x_{BC} = 20 - x_{A C}$
- $x_{B D} = x_{A C} - 5$ （導出は本文中の式参照）
  範囲は $5 \leq x_{A C} \leq 20$ （非負の制約より）。
総費用を $x_{A C}$ で表します。単価を掛け合わせて合計：
$4 x_{A C} + 2 x_{A D} + 2 x_{BC} + 1 x_{B D}$ に変数代入すると、
総費用 $= x_{A C} + 105$ （万円）になります。
よって $x_{A C}$ を最小にするのが得策です。
$x_{A C}$ の最小値は 5（範囲より）。これを代入すると総費用は $5 + 105 = 110$ 万円となり、これが最小。

（式の変形は上のステップで示した通りです。もし式操作に不安があれば、後で式の導出を順を追って解説します。）

選択肢別の誤答解説

ア: 85 万円
→ 85 は実行可能な配分から外れます。A→C の高コスト（4万円）をほとんど避けることができないので、総額がそこまで低くなることはありません。
イ: 100 万円
→ 100 は今回の需要・供給の制約下では達成不可です。総費用は 105 を下回ることができず、さらに $x_{A C}$ の寄与で 110 が最小となります。
ウ: 110 万円
→ 上で示した配分（A→C 5、A→D 30、B→C 15）が成り立ち、総費用 110 万円を実現します。したがって正解です。
エ: 125 万円
→ これは単純に「安い順（貪欲法）」で割り当てた場合に出てくる結果（例：B→D に全量、A→D に残り、A→C に残り…）の一つです。貪欲に最安路線から埋めると 125 になることがありますが、全体最小ではありません。

よくある誤解

「単に単価が安い経路から順に割り当てれば最小になる」
→ 部分的には有効ですが、倉庫ごとの供給制約と店舗ごとの需要制約を無視すると誤答になります。本問はまさにその典型です。
「各倉庫は1店舗にしか送れない」と誤解する
→ 実際は倉庫は複数店舗に分配できます。問題文に分配の制限がない限り、任意に分けるのが普通です。
「個別の最安経路だけ見れば良い」と考える
→ ある倉庫の安い経路が他方の倉庫の高コスト経路を代替できるかを評価する必要があります（今回のようにBをCに回すことでAの高コスト分を減らす）。

補足コラム（輸送問題の考え方）

この問題は「輸送問題（Transportation Problem）」という古典的な最適化問題の一例です。
ポイントは「供給（倉庫）」「需要（店舗）」「単価（コスト）」の三つを表にして、全体の費用を最小化すること。手計算での代表的な解法には次があります（参考名）：

最安費用から順に割当てる方法（貪欲）…簡単だが必ずしも最適にならない場合がある
Vogelの近似法（Vogel’s Approximation）…良い初期解を作る実務的手法
MODI法（Modified Distribution method）や単体法…厳密な最適化を行う手法

本問は小規模なので変数で整理して式を作る方法が分かりやすく確実です。

FAQ

Q. なぜ最初に「B→D（単価1）」へ全量割当てしてはいけないのですか？
A. B→D に全量割当てすると、店舗Cへの分をAから多く送る必要があり、A→C の単価が高いため総額が上がります。全体最小は局所的最安のみを見ると見落とします。

Q. どうして

x_{A C}

を 5 にできるのですか？
A. 需要・供給の式から

x_{B D} = x_{A C} - 5

が導けます。非負制約より

x_{A C} \geq 5

です。また Cの需要 20 の制約から

x_{A C} \leq 20

。したがって範囲は

5 \leq x_{A C} \leq 20

。総費用は

x_{A C} + 105

なので最小は

x_{A C} = 5

です。

Q. 同じ考え方は他の問題にも使えますか？
A. はい。特に供給・需要がバランスしている「輸送問題」では、変数を1つに減らして総費用を単純な関数にする手法が有効です。大きな問題では専用アルゴリズムを使います。

関連キーワード: 輸送問題、最適化、線形計画、需要と供給、最小費用配分、アルゴリズム入門

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

ITパスポートを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！