オペレーションズ・リサーチの問題
2 つの倉庫 から 3 つの営業所 へ、ある部品を輸送する。各倉庫から出荷できる量（上限）は が 、 が であり、各営業所の需要量は が 、 が 、 が である。各営業所には需要量ちょうどを届ける。部品 1 単位あたりの輸送費は次の表のとおりである。
供給量の合計と需要量の合計を比べ、余る分を受け入れるダミーの営業所 （各倉庫からの 1 単位あたりの輸送費は ）を表の右端の列として加えて需給を釣り合わせる。この表（行の順は 、列の順は ）に北西隅法を適用して初期の実行可能解を作るとき、その総輸送費を求めよ。
この問題で使うもの
- 輸送問題の定式化と初期解（説明と入口の問題）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
輸送問題の初期解の作り方を使います。まず供給量の合計と需要量の合計を比べ、ダミーの営業所の需要量を決めましょう。
ヒント 2
北西隅法では、左上のマスから「残りの供給量と残りの需要量の小さい方」を割り当て、行を使い切ったら下へ、列を満たしたら右へ進みます。
ヒント 3
ダミー の需要量は です。最初の 2 つの割り当ては 、 となり、次は に進みます。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
手順 1：需給を釣り合わせる。
供給量の合計は 、需要量の合計は である。供給が だけ余るので、需要量 のダミーの営業所 を加える（輸送費はすべて ）。これで供給と需要の合計はどちらも になる。
| 供給 | |||||
|---|---|---|---|---|---|
| 需要 |
手順 2：北西隅法で割り当てる。 左上のマスから始め、そのマスに「残りの供給量」と「残りの需要量」の小さい方を割り当て、使い切った行は下へ、満たした列は右へ進む。
- ：。 が満たされ、 の残りは 。右へ進む。
- ：。 を使い切り、 の残りは 。下へ進む。
- ：。 が満たされ、 の残りは 。右へ進む。
- ：。 が満たされ、 の残りは 。右へ進む。
- ：。すべての供給と需要が満たされる。
手順 3：総輸送費を計算する。
ダミーへの割り当て は実際には輸送しない（倉庫 に残る）分で、費用は である。
よって、総輸送費は である。
別解
供給の合計は 、需要の合計は なので、ダミーの営業所 の需要量は である。
北西隅法を表の左上から順に適用する。
- : 。 の残りは 、 は充足。
- : 。 は使い切り、 の残りは 。
- : 。 は充足、 の残りは 。
- : 。 は充足、 の残りは 。
- : 。ここで両方とも使い切る。
総輸送費は
。
検算: 行和は が 、 が 。列和は が 、 が 、 が 、 が 。すべて一致する。