9781118041581

Formulation and Computer Solution for Larger LP Problems 737

instance) and summing. The first three constraints pertain to school capacities:

The total number of students going to each school cannot exceed the school’s

capacity. The last four constraints pertain to neighborhood enrollments: For

each neighborhood, all school-age children ride the bus to some school. (If

the left-hand side of the equality fell short of the right-hand side, many happy

children would be left on street corners without being picked up for school.)

Table 17.2 shows the computer solution. Note that the north and east chil-

dren go to the schools closest to them, and the west and south students go to

either their nearest or second-nearest schools. School 3 has extra spaces. The

city pays for the minimum number of kid-miles: 1,792. The table also lists

shadow prices associated with each school and each neighborhood. For

instance, the shadow price associated with busing an extra child from the north

neighborhood is 2.8; this results from busing the student to school 1 (2 miles).

Because school 1 already is at capacity, however, the extra north child displaces

a west child who goes to school 2 instead of school 1 (an extra distance of .6

mile). In turn, the extra west child going to school 2 displaces a south child who

now travels an extra distance of .2 mile to school 3. Thus, the listed shadow

price represents a total increase in miles of: 2.0 .6 .2 2.8.

CHECK

STATION 5

Confirm that the shadow prices associated with school 1 and the west neighborhood are

correct.

An Investment

Problem

Revisited

Recall that the manager wants to construct a portfolio of securities that offers the high-

est expected after-tax return, subject to the following requirements: (1) The portfolio’s

average quality rating is at least 3.5, and (2) the portfolio’s average maturity is at least 1.5

years but no greater than 2.5 years.

Bond Category Quality Rating Maturity (Years) Yield (Percent)

Treasury bills 5 .4 4.0

Treasury bonds 5 4.0 6.0

Corporate bonds 3.5 3.2 4.4

Municipal bonds 3 2.0 5.6

Junk bonds 1 2.5 8.0

The LP formulation is

Maximize: 4.0B + 6.0T + 4.4C + 5.6M + 8.0J

Subject to: 5B + 5T + 3.5C + 3M + 1J 3.5

.4B + 4.0T + 3.2C + 2.0M + 2.5J 1.5

.4B + 4.0T + 3.2C + 2.0M + 2.5J 2.5

B + T + C + M +J = 1.0.

All decision variables are nonnegative.

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