9781118041581

Formulation and Computer Solution for Larger LP Problems 731

The formulation of this decision problem is as follows.

Minimize:

Subject to:

All decision variables are nonnegative.

Here x 1 , x 2 ,. ., x 6 denote the number of officers who beginduty with shift 1,

2,. ., 6. The objective function lists the total number of regular-time salaries of

the force. (The city pays an officer beginning duty in shift 1 regular time for

8 hours. One beginning in shift 2 receives 4 hours of regular-time pay and 4 hours

at time and a quarter; overall, he or she counts as a 1.125 officer. We similarly cal-

culate the pay for officers beginning shifts 3 through 6.) The left-hand side of the

first constraint lists the number of police on duty during the 8 A.M. to 12 P.M.

period. (This is the sum of x 1 and x 6 , the number of officers beginning shifts at

8 A.M. and ending shifts at noon.) This number must be no fewer than the 150-

person requirement. We express the other five constraints in the same way.

The manager enters the objective function and the relevant constraints

into the spreadsheet. Table 17.1 shows the completed spreadsheet (including

the problem’s optimal solution and shadow prices). In the table, the decision

variables appear in row 6 and are in colored type for easy identification. We

can vary these as we wish and observe the effect on the objective. The values

shown here are the optimal values generated by executing Excel’s optimiza-

tion program, Solver. In actual practice, the user is free to enter any initial val-

ues. For instance, the user could begin by setting all six variables at 300

officers—values that far exceed required staffing levels. The manager can also

experiment with other values. Cell I5 lists the objective, the total number of

regular-time police officers (the value of which the manager wants to mini-

mize). The value in this cell has been computed by using the objective function

equation in the LP formulation.

Rows 8 and 10 represent the constraints. The fixed values in row 10 denote

the required number of officers on the six shifts (the right side of the preced-

ing inequalities). The computed values in row 8 list the number of officers actu-

ally present during the time periods. For instance, the value in cell C8 is the

sum of cells B6 and C6, and so on. Finally, each value in row 12, the so-called

extra officers, is the difference between the actual (row 8) and required (row

10) number of personnel.

x 6 x 5  175

x 5 x 4  500

x 4 x 3  400

x 3 x 2  250

x 2 x 1  100

x 1 x 6  150

x 1 1.125x 2 1.25x 3 1.375x 4 1.5x 5 1.25x 6

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