輸送問題

輸送問題は、複数の供給地から複数の需要地へ品物を送る量を決め、各供給量と需要量を満たしながら、$\text{単位輸送費}\times\text{輸送量}$の総和を最小化する線形計画問題です。

■ 試験で押さえるポイント

• 供給地iから需要地jへの輸送量をxij、単位費用をcijとし、目的関数$\sum_i\sum_jc_{ij}x_{ij}$を最小化します。

• 各供給地からの出荷量合計は供給能力以下、各需要地への到着量合計は需要量と一致し、$x_{ij}\ge0$という制約を置きます。

• 総供給量と総需要量が等しい平衡問題が基本で、異なる場合は不足・余剰を表すダミー需要地又は供給地を加えて平衡化できます。

• 最安経路だけへ全量を送ると供給・需要制約を破る場合があります。全体の組合せとして費用最小になるかを確認します。

■ 選択肢での判断ポイント

行を供給地、列を需要地とする費用表で、供給・需要を消し込みます。割当量×単位費用を全経路で合計します。

例: 供給$A=30$、$B=20$、需要$X=10$、$Y=40$、費用$c_{AX}=1$、$c_{AY}=4$、$c_{BX}=3$、$c_{BY}=2$なら、AX10、AY20、BY20で満たせ、総費用は$10\times1+20\times4+20\times2=130$です。