Exercise 1.9 (Distance to school and student distribution)

Question

Consider a school district with $I$ neighborhoods, $J$ schools, and $G$ grades at each school. Each school $j$ has a capacity of $C_{j g}$ for grade $g .$ In each neighborhood $i$, the student population of grade $i$ is $S_{i g}$. Finally, the distance of school $j$ from neighborhood $i$ is $d_{i j}$. Formulate a linear programming problem whose objective is to assign all students to schools, while minimizing the total distance traveled by all students. (You may ignore the fact that numbers of students must be integer.)

Elu Thingol · Accepted Answer

Students are characterised by three degrees of freedom: the neighbourhoods $i$ they come from, the schools $j$ they go to and their grades $g$. Thus, we denote each student by $s_{ijg}$ for $1 \leq i \leq I$, $1 \leq j \leq J$ and $1 \leq g \leq G$. Our goal is to minimize the total distance travelled by all students

$$\sum_{i=1}^{I} \sum_{j=1}^{J} \sum_{g=1}^{G} s_{ijg} \cdot d_{ij}$$

under the condition that each student is assigned to some school

$$\sum_{j=1}^{J} s_{ijg} = S_{ig}
\quad 	ext{for} \quad \begin{array}{l}
i = 1,\ldots,I\
g = 1,\ldots,G
\end{array}
$$

and each school can take no more than a certain amount of students to certain grades

$$\sum_{i=1}^{I} s_{ijg} \leq C_{jg}
\quad 	ext{for} \quad \begin{array}{l}
j = 1,\ldots,J\
g = 1,\ldots,G
\end{array}.
$$

This results in the following linear optimization problem:
\begin{equation*}
\begin{array}{llll}
	ext{minimize} \quad & \sum_{i=1}^{I} \sum_{j=1}^{J} \sum_{g=1}^{G} s_{ijg} \cdot d_{ij}\
	ext{subject to} \quad
&\sum_{j=1}^{J} s_{ijg} = S_{ig} &i = 1,\ldots,I &g = 1,\ldots,G\
&\sum_{i=1}^{I} s_{ijg} \leq C_{jg} &j = 1,\ldots,J &g = 1,\ldots,G\
&s_{ijg} \geq 0 &i = 1,\ldots,I &j = 1,\ldots,J &g = 1,\ldots,G.\
\end{array}
\end{equation*}

Exercise 1.9 (Distance to school and student distribution)

Answers

Comments

Exercise 1.9 (Distance to school and student distribution)

Answers

Comments

Add answer