9781118041581

Formulation and Computer Solution for Larger LP Problems 735

The formulation begins with recognizing that a busing plan has 12 decision

variables: the number of children from each of four neighborhoods bused to

each of three schools. For instance, the variable N1 denotes the number of stu-

dents from the north neighborhood bused to school 1, and so on. Remember

that the city wants to minimize the total number of kid-miles traveled. As the

formulation shows, the objective function is found by multiplying the number

of students along a given route by the distance along the route (2.0N1, for

5

E

3

S

4

W 2

N

1

1 2 3 5

4

3

2

1

0

Distance Scale (Miles)

School Busing Map

6

Distance Scale (Miles)

Neighborhood

Distances from

(in miles) to

(360) School 1

(400) School 2

(260) School 3

(200)

South

3.2

2.0

2.2

(400)

West

1.4

2.0

3.0

(120)

East

3.0

2.4

1.4

(240)

North

2.0

3.2

3.6

FIGURE 17.7

Data for a School

Busing Problem

The number of

elementary school

children in the

neighborhoods and

the student capacities

of the schools are

listed in parentheses.

c17LinearProgramming.qxd 9/26/11 11:05 AM Page 735