Question

A city police department has the following minimal daily requirement for policeman. Note, you are to consider period 1 as following immediately after period 6. Each policeman works eight consecutive hours. Let X denote the number of men starting work in period t everyday. The police department seeks a daily manpower schedule that employs the least number of policemen, provided that each of the above requirements is met. Formulate linear programming model to find an optimal schedule.

Answer 1

To formulate a linear programming model to find an optimal schedule for the city police department, we must first identify the decision variables, objective function, and constraints.

Decision variables:

Let X_t be the number of policemen starting work in period t each day, where t = 1, 2, ..., 6.

Objective function:

Minimize the total number of policemen required each day, which can be expressed as:

Minimize Z = X_1 + X_2 + X_3 + X_4 + X_5 + X_6

Constraints:

Each period must meet the minimum requirement for policemen:

X_1 + X_2 + X_3 + X_4 + X_5 + X_6 >= 20

X_2 + X_3 + X_4 + X_5 + X_6 + X_1 >= 22

X_3 + X_4 + X_5 + X_6 + X_1 + X_2 >= 18

X_4 + X_5 + X_6 + X_1 + X_2 + X_3 >= 16

X_5 + X_6 + X_1 + X_2 + X_3 + X_4 >= 19

X_6 + X_1 + X_2 + X_3 + X_4 + X_5 >= 23

Non-negativity constraints:

X_t >= 0, for t = 1, 2, ..., 6

Therefore, the linear programming model can be formulated as follows:

Minimize Z = X_1 + X_2 + X_3 + X_4 + X_5 + X_6

subject to:

X_1 + X_2 + X_3 + X_4 + X_5 + X_6 >= 20

X_2 + X_3 + X_4 + X_5 + X_6 + X_1 >= 22

X_3 + X_4 + X_5 + X_6 + X_1 + X_2 >= 18

X_4 + X_5 + X_6 + X_1 + X_2 + X_3 >= 16

X_5 + X_6 + X_1 + X_2 + X_3 + X_4 >= 19

X_6 + X_1 + X_2 + X_3 + X_4 + X_5 >=