問題
Ⅲ-27 ある1種類の製品を作るm箇所の工場から、それらの工場で作られた製品をn箇所の販売店に運ぶ必要がある。
工場j (j = 1,…, m) での生産可能量Mj、工場jから販売店i (i = 1,…, n) へ1単位の需要が移動するときにかかる輸送費用cij、販売店iにおける需要量diが与えられているとき、輸送費用の和が最小となる輸送量を求めたい。
xijを工場jから販売店iへの輸送量とするとき、この問題に関する次の記述のうち、最も不適切なものはどれか。
① この問題は、線形計画問題として定式化される。
② この問題の目的関数は \(\sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij}x_{ij}\) と表される。
③ すべての工場において \(\sum_{i=1}^{n} x_{ij} > M_j\) を満たす必要がある。
④ すべての顧客において \(\sum_{j=1}^{m} x_{ij} = d_i\) を満たす必要がある。
⑤ この問題の最適解は単体法（シンプレックス法）を用いて求められる。
解答
正解は 3 になります。
問題概要
この問題は、線形計画法を用いた「輸送問題」に関するものです。輸送問題とは、複数の工場から複数の販売店へ製品を配送する際、輸送コストを最小化するための配送量を求める問題です。
具体的には、以下の条件が設定されています：
- 工場 \(j\) (j = 1,…, m): 各工場には生産可能な製品量（供給量） \(M_j\)が決まっています。
- 販売店 \(i\)(i = 1,…, n): 各販売店には必要な製品量（需要量） \(d_i\)があります。
- 輸送コスト \(c_{ij}\): 工場 \(j\) から販売店 \(i\) へ1単位の製品を輸送する際にかかる費用。
- 変数 \(x_{ij}\): 工場 \(j\) から販売店 \(i\) へ輸送する製品の量。
この問題では、輸送コストの合計を最小化しつつ、供給量と需要量の制約を満たすような輸送計画を立てることが求められています。
各選択肢の詳細解説
① この問題は、線形計画問題として定式化される。
- 解説: 線形計画問題とは、目的関数（例えばコストや利益）を最小化または最大化するために、線形の制約条件下で解を求める数学的手法です。この「輸送問題」は、目的関数（輸送コスト）と制約条件（供給量と需要量）がともに線形であるため、線形計画問題として正しく定式化できます。
- 結論: 適切な記述です。
② この問題の目的関数は \(\sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij}\) と表される。
- 解説: 輸送コストの合計は、「各工場から各販売店への輸送コスト」をすべて足し合わせたものです。したがって、目的関数は
\(
\text{最小化}: Z = \sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij}
\)
と表されます。この式は正しいため、この選択肢も適切です。 - 結論: 適切な記述です。
③ すべての工場において \(\sum_{i=1}^n x_{ij} > M_j\) を満たす必要がある。
- 解説: この記述は誤りです。各工場が供給できる製品量 \(M_j\) を超えて輸送することはできません。正しい制約条件は
\(
\sum_{i=1}^n x_{ij} \leq M_j
\)
と表されます。つまり、「各工場から出荷される総量は、その工場の供給能力以下でなければならない」という制約があります。この選択肢では「超える必要がある」と記述されており、不適切です。 - 結論: 不適切な記述です。（正解）
④ すべての顧客において \(\sum_{j=1}^m x_{ij} = d_i\) を満たす必要がある。
- 解説: この記述は正しいです。各販売店 \(i\) において、「受け取る製品の総量」はその販売店が必要とする需要量 \(d_i\) と一致しなければなりません。これを式で表すと、
\(
\sum_{j=1}^m x_{ij} = d_i
\)
となります。この条件により、需要が確実に満たされることが保証されます。 - 結論: 適切な記述です。
⑤ この問題の最適解は単体法（シンプレックス法）を用いて求められる。
- 解説: シンプレックス法は、線形計画問題を解くための一般的なアルゴリズムであり、この「輸送問題」にも適用可能です。ただし、「輸送問題」には特化した効率的なアルゴリズム（例えば北西隅法やMODI法など）が存在します。しかし、この選択肢では「シンプレックス法を用いる」としており、それ自体は正しい記述です。
- 結論: 適切な記述です。
問題の要点まとめ
この問題では、「輸送問題」の基本的な構造とその制約条件について理解しているかが問われています。不適切な記述は③であり、「供給能力を超えた出荷」が必要とされている点が誤りでした。
要点整理
1．目的関数:
- 輸送コストを最小化するために設定される。
- 数式：\(\sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij}\)
2．制約条件:
- 各工場：供給量以下で出荷（\(\sum_{i=1}^n x_{ij} \leq M_j\)）。
- 各販売店：需要量を満たす（\(\sum_{j=1}^m x_{ij} = d_i\)）。
3．解法:
- シンプレックス法や特化したアルゴリズムで解く。
感想
問題自体はそんなに難しくないかな？
数式の矛盾をつけばいいはずなので。
ワタクシが苦労したのはこの数式の山！
LaTeX使って学生時代に論文書いてました、ではなくワタクシの時代は一太郎だったので・・・。
書いてはエラー確認、書いては確認の連続でこの記事アップするのに相当時間かかりました・・・・。
あと、ワタクシの記事作成環境でバックスラッシュがうまく入力出来ないのも毎回時間がかかる原因。
ここはコピペで逃げよう・・・・。単語登録するにも¥と文字コード同じなので上手く認識してくれなかったし。
関連記事Related articles
