課題（第1回）：p-median 問題のモデリング¶

この課題では、スーパーマーケットの配置計画を題材に、p-median 問題という最適化問題を自分の手で数式にする（モデリングする）ことに挑戦する。

この資料には考え方と記号の定義だけが書いてある。数理モデル（数式）は書いていない。
資料を読んだうえで、目的関数と制約条件を自分で数式にして、レポート雛形（pmedian_課題_学籍番号_氏名.docx）に記入して提出すること。
数式は必ず Word の数式ツールで入力すること（雛形の注意事項を参照）。
次回（第2回）は、今回作った数理モデルをプログラム（pulp）で実装して実際に解く。

1. どこにスーパーを置くべきか？¶

ある地域に住民が住んでいる街（需要点）がいくつかあり、スーパーマーケットを建てられる候補地（配置点）もいくつかあるとする。会社の予算の都合で、店舗は決められた数しか建てられない。

さて、どの候補地に店舗を建てるのが「良い」配置だろうか。

「良い」を決めるには基準が必要である。ここでは「地域全体の住民が、店までの移動で苦労しないこと」を基準にする。これを数値で表したものが、次に説明する重み付き総移動距離である。

2. 重み付き総移動距離¶

住民は自分の街から一番近い（正確には、配置された店舗のうち一番使いやすい）店舗まで移動する。このとき、地域全体の「移動の苦労」は

（街の人口）×（その街から利用する店舗までの距離）を全部の街について足したもの

で表せる。これを重み付き総移動距離と呼ぶ。人口を掛けるのは、100人の街が2km 移動するのと、1000人の街が2km 移動するのとでは、地域全体としての負担が10倍違うからである。単位は [km] ではなく[人/km]（全住民の移動距離の合計、延べ移動距離）になることに注意すること。

2.1 手を動かして確認しよう¶

小さな例で実際に計算してみよう。街が3つ（A, B, C）、店舗の候補地が2つ（候補地1, 候補地2）ある地域を考える。建てられる店舗は1つだけとする。

街	人口	候補地1までの距離	候補地2までの距離
A	100人	1 km	4 km
B	300人	2 km	1 km
C	200人	3 km	2 km

候補地1に建てた場合：全員が候補地1を使うしかないので

$100 \times 1 + 300 \times 2 + 200 \times 3 = 1300$ [人/km]

候補地2に建てた場合：

$100 \times 4 + 300 \times 1 + 200 \times 2 = 1100$ [人/km]

候補地2に建てた方が重み付き総移動距離が小さい、つまり地域全体にとって「良い」配置だと分かる。 Aの住民だけを見ると遠くなるが、人口の多いBとCが近くなるので全体では得をしているわけである。

このように、すべての置き方の中で重み付き総移動距離が最小になるように、決められた数の店舗を配置する問題をp-median 問題と呼ぶ。

上の例は「3つの街、2つの候補地、店舗1つ」なので2通りを比べれば済んだが、候補地が20か所で店舗が5つなら置き方は15,504通りもある。だからこそ、問題を数式で書いてコンピュータに解かせる必要がある。その「数式で書く」作業＝モデリングが今回の課題である。

3. 最適化問題の形¶

最適化問題は、次の2つの部品でできている。

目的関数 … 最小化（または最大化）したい指標
制約条件 … 解が満たさなければいけない条件

p-median 問題の場合、それぞれは言葉で書くと次のようになる。

目的関数（最小化）

重み付き総移動距離

制約条件

各需要点の住民は、ちょうど1つの店舗を利用する
店舗が配置されていない配置点は利用できない
配置する店舗の数はちょうど $k$ 個

課題では、この言葉で書かれた目的関数と制約条件を、次節で定義する記号を使って数式にする。

4. 記号の定義¶

数式で書くために、記号を用意する。課題で使ってよいのはここにある記号だけである。

4.1 記号（添字）¶

$i$ … 需要点（街）の番号。需要点は全部で $n$ 個あり、$i = 1, 2, \cdots, n$
$j$ … 配置点（店舗の候補地）の番号。配置点は全部で $m$ 個あり、$j = 1, 2, \cdots, m$

4.2 定数（あらかじめ与えられている値）¶

$p_i$ … 需要点 $i$ の人口
$d_{ij}$ … 需要点 $i$ から配置点 $j$ までの距離
$k$ … 配置する店舗の数

4.3 変数（コンピュータに決めてもらう値）¶

どちらも0 か 1 しか取らない変数（0-1変数）である。

$x_{ij}$ … 需要点 $i$ の住民が配置点 $j$ の店舗を利用するなら 1、しないなら 0
$y_j$ … 配置点 $j$ に店舗を配置するなら 1、しないなら 0

例えば「需要点3の住民が配置点2の店舗を利用する」ことは $x_{3,2} = 1$ と表せる。

4.4 記法の復習¶

総和記号 $\sum$：$\sum_{i=1}^{3} a_i = a_1 + a_2 + a_3$ のように「足し合わせる」ことを表す。

「すべての〜について」$\forall$：同じ形の式がたくさんあるとき、1本ずつ書く代わりに

$（式）, \quad \forall i \in \{1, 2, \cdots, n\}$

と書くと「この式が $i = 1$ から $n$ のすべてについて成り立つ」という意味になる。

5. 課題：p-median 問題をモデリングしよう¶

第4節の記号を使って、第3節の目的関数と制約条件1〜3を数式で書き、レポート雛形（pmedian_課題_学籍番号_氏名.docx）の各欄に記入すること。雛形では、数式そのものに加えて式の意味の説明（式を展開して具体的に解説すること）も求めている。

いきなり全体を書くのは難しいので、次の順で考えるのがおすすめである。

5.1 目的関数を組み立てるステップ¶

1組だけ考える：需要点 $i$ の住民が配置点 $j$ の店舗を利用するときの「人口 × 距離」を、$p_i$ と $d_{ij}$ で書いてみる。
変数を掛ける：ステップ1の式は「利用するとき」しか成り立たない。利用しないときは 0 になってほしい。0 か 1 を取る変数 $x_{ij}$ をうまく使うと、 1つの式で両方の場合を表せる。
全部足す：ステップ2の式を、すべての需要点 $i$ とすべての配置点 $j$ について $\sum$ で足し合わせる。それが重み付き総移動距離＝目的関数。

5.2 制約条件を組み立てるヒント¶

制約条件1（住民はちょうど1店舗を利用）：需要点1だけについて考えると「$x_{1,1}, x_{1,2}, \cdots, x_{1,m}$ のうちちょうど1つだけが 1」。これは総和を使うと1本の式で書ける。それを $\forall$ ですべての需要点に広げる。
制約条件2（店舗がない配置点は利用できない）：「$y_j = 0$ ならば $x_{ij}$ も 0 でなければならない」を、不等号（$\leq$）1本で表すことができる。$y_j = 0$ の場合と $y_j = 1$ の場合をそれぞれ代入して、狙い通りの意味になるか確かめること。
制約条件3（店舗はちょうど $k$ 個）：「$y_1, y_2, \cdots, y_m$ のうち 1 になっているものの個数が $k$」を総和で書く。
変数制約：$x_{ij}$ と $y_j$ が 0 か 1 しか取らないことも、忘れずに制約として書くのが数理モデルの作法。（例：$x_{ij} \in \{0, 1\}$ のように書く）

5.3 検算のすすめ¶

数式が書けたら、第2節の小さな例（街3つ、候補地2つ、店舗1つ、$n=3, m=2, k=1$）を自分の数式に当てはめてみること。候補地2に建てる解（$y_1 = 0, y_2 = 1$、全員が候補地2を利用）がすべての制約を満たし、目的関数の値が 1100 [人/km] になれば、モデルは正しくできている。

6. 提出方法¶

レポート雛形 pmedian_課題_学籍番号_氏名.docx のすべての欄を埋めて提出すること。
ファイル名の「学籍番号」と「氏名」は自分のものに書き換えること（例：24B00000_日大太郎）。
数式は必ず Word の数式ツールで入力すること（雛形冒頭の注意事項を参照）。

6.1 提出前チェックリスト¶

記号、定数、変数の定義がすべて具体的に書けている
目的関数に「最小化する」ことが明示されている
制約条件1〜3がすべて数式で書けていて、$\forall$ の範囲も書けている
変数が 0-1 変数であることが制約として書けている
各式について、展開した具体例つきの意味の説明が書けている
第2節の小さな例で検算した