Answer:
The linear program will be :
Σ j∈J Xijg = Sig ∀ i∈I g∈G
Σ i∈I Xijg = Cjg ∀ i∈j g∈G
X ≥ 0
Explanation:
To formulate a linear programming problem whose objective is to assign all students to schools, while minimizing the total distance traveled by all students, we need to consider and let Let xi jg be the amount of students from neighborhood i of grade g travelling to school j.
Then for an assignment of students to schools, the total distance travelled by all students would be given as :
Σ Σ Σ dij Xijg
i∈I j∈J g∈G
Thus, for a feasible assignment, every student of every neighborhood and grade must be assigned to a school which then gives the constraint
Σ . Xijg = Sig ∀ i∈I , g∈G
j∈J
Consequentially, the number of students each school can take in respective grades is bounded by Cjg,
thus
Σ . Xijg = Cjg ∀ i∈I , g∈G
i∈I
Finally there can be no negative numbers of assignments: x ≥ 0. This then gives the following linear program:
min = Σ Σ Σ dij Xijg
i∈I j∈J g∈G
Subject to
Σ j∈J Xijg = Sig ∀ i∈I g∈G
Σ i∈I Xijg = Cjg ∀ i∈j g∈G
X ≥ 0
