演習 — 線形計画法の応用

第1章 No.6 ／ 飼料の混合問題・輸送問題

課題 1 — 利益のパラメータ変化

課題で与えた製品 A、製品 B の 1 kg 当たりの利益が、以下の表の (1)〜(5) のように変化したとき、それぞれの場合について利益を最大にする (x, y) を求めよ (単位は千円とする)。

▶ 解説のページ

飼料の混合問題

この問題を線形計画法を使って定式化すると以下のようになる。

• 2x₁ + 3x₂ ≧ 120
• x₁ + 3x₂ ≧ 90
• 4x₁ + x₂ ≧ 80
• 2x₁ + 2x₂ ≧ 50
• x₁ ≧ 0, x₂ ≧ 0
• 4x₁ + 3x₂ → min

課題 2

穀類 2 の価格が 5 千円に値上がりしたときにはどうなるか。

輸送問題

ある会社が 1 種類の製品を m 個の倉庫から n 個の販売店に輸送しようとしている。

• a_i: 倉庫 i にある製品の総量
• b_j: 販売店 j での製品の必要量
• c_ij: 倉庫 i から販売店 j への製品 1 単位あたりの輸送費用

とする。輸送費にかかる総費用を最小化する問題を定式化しよう。倉庫 i から販売店 j への輸送量を x_ij で表す。

倉庫 i から積み出される製品の総量は a_i より大きくなれないから：

∑_j=1ⁿ x_ij ≦ a_i   (i = 1,…,m)

販売店 j は製品 b_j 以上輸送しなければならないため：

∑_i=1^m x_ij ≧ b_j   (j = 1,…,n)

さらに非負条件：

x_ij ≧ 0   (i = 1,…,m; j = 1,…,n)

上の制約条件のもとで輸送にかかる総費用：

∑_i=1^m ∑_j=1ⁿ c_ij · x_ij

を最小にすればよい。

課題 3

a_i、b_j、c_ij が以下の表で表されるとき、その輸送問題を解け。