Question

Consider a school district with I neighborhoods, J schools, and G grades at each school. Each school j has a capacity of Cig for grade g. In each neighborhood i, the student population of grade g is Sig. Finally, the distance of school j from ncighborhood i is dij. Formulate a lincar programming problem whose objcctive is to assign all students to schools, while minimizing the total distance traveled by all students. (Hint: you need three-index decision variables)

Answer 1

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