Question

(High school busing problem) The Arden County, Maryland, superintendent of education is responsible for assigning students to the three high schools in his county. He recognizes the need to bus a certain number of students, for several sectors of the county are beyond walking distance to a school. The superintendent               partitions the county into three geographic sectors as he attempts to establish a plan that will minimize the total         number of student miles traveled by bus. He also recognizes that if a student happens to live in a certain sector             and is assigned to the high school in that sector, there is no need to bus that student because he or she can walk               to school. The three schools are located in sectors B, C, and D.

              The following table reflects the number of high-school-age students living in each sector and the distance in               miles from each sector to each school:

Distance to School
Sector	Schools in Sector B	Schools is Sector C	Schools in Sector D	Number of Students
B	0	4	12	500
C	4	0	7	100
D	7	2	0	800

              Each high school has a capacity of 500 students. Please define variables and set up the objective function and constraints of this problem using Linear Programming (LP) so that the total number of student miles traveled by bus is minimized. (5 points)

Answer 1

Let the no. of students from Sector B assigned to Schools in Sector B be Xbb, in Sector C be Xbc and so on. Hence, we get the decision variables as Xbb, Xbc, Xbd, Xcb, Xcc, Xcd, Xcb, Xdc, and Xdd.

Total distance travelled = 0*Xbb + 4*Xbc + 12*Xbd + 4*Xcb + 0*Xcc + 7*Xcd + 7*Xdb + 2*Xdc + 0*Xdd

We have to minimize this total distance

Hence, we get the objective function as:

Minimize 0*Xbb + 4*Xbc + 12*Xbd + 4*Xcb + 0*Xcc + 7*Xcd + 7*Xdb + 2*Xdc + 0*Xdd

Total capacity = 500 * 3 = 1500 students

Total Students available = 500 + 100 + 800 = 1400

Since Total capacity > Total Students available, this is an unbalanced problem. hence, there will be "<=" sign in Capacity constraints

Subject to Constraints:

Demand constraints

Xbb + Xbc + Xbd = 500.........Constraint for no. of students in Sector B

Xcb + Xcc + Xcd = 100.........Constraint for no. of students in Sector C

Xdb + Xdc + Xdd = 800.........Constraint for no. of students in Sector D

Capacity Constraints:

Xbb + Xcb + Xdb <= 500.........Constraint for capacity of schools in Sector B

Xbc + Xcc + Xdc <= 500.........Constraint for capacity of schools in Sector C

Xbd + Xcd + Xdd <= 500.........Constraint for capacity of schools in Sector D

Xbb, Xbc, Xbd, Xcb, Xcc, Xcd, Xcb, Xdc, and Xdd >= 0...........Non-negativity constraints as no. of students cannot be negative.

This is our formulation:

Decision Variables = Xbb, Xbc, Xbd, Xcb, Xcc, Xcd, Xcb, Xdc, and Xdd.

Objective function = Minimize 0*Xbb + 4*Xbc + 12*Xbd + 4*Xcb + 0*Xcc + 7*Xcd + 7*Xdb + 2*Xdc + 0*Xdd

Constraints:

Xbb + Xbc + Xbd = 500

Xcb + Xcc + Xcd = 100

Xdb + Xdc + Xdd = 800

Xbb + Xcb + Xdb <= 500

Xbc + Xcc + Xdc <= 500

Xbd + Xcd + Xdd <= 500

Xbb, Xbc, Xbd, Xcb, Xcc, Xcd, Xcb, Xdc, and Xdd >= 0

-----------------------------------------------------------------------------------------------------------------------

In case of any doubt, please ask through the comment section before Upvote/downvote.

If you liked the answer, please give an upvote. This will be quite encouraging for me, thank-you!!!