During each 4-hour period, the Smalltown police force requires the following num
ID: 3148042 • Letter: D
Question
During each 4-hour period, the Smalltown police force requires the following
number of on-duty police officers: 8 officers from 12 midnight to 4am; 7 officers from
4am to 8am; 6 officers from 8am to 12 noon; 6 officers from 12 noon to 4 pm; 5 officers
from 4 to 8pm and 4 officers from 8pm to 12 midnight. Each officer works two
consecutive 4-hour shifts.
a. Formulate an IP that can be used to minimize the number of police officers
needed to meet Smalltown’s daily requirements.
b. Try to use branch and bound to solve the problem not necessarily to optimality
(branch at least on two nodes if needed, solve each node as an LP, update UB and
LB at each node you have in your B&B tree of each iteration.)
Explanation / Answer
The problem is trying to minimize the number of police; therefore, the decision variables will be the number of police that are working. Since the police must work consecutive shifts, the number of police working will be counted using the start shift.
X1 = Number of police that start work during Shift 1
X2 = Number of police that start work during Shift 2
X3 = Number of police that start work during Shift 3
X4 = Number of police that start work during Shift 4
X5 = Number of police that start work during Shift 5
X6 = Number of police that start work during Shift 6
Each police officer works two consecutive 4-hour shifts. Formulate an LP that can be used to minimize the number of police officers needed to meet Smalltown's daily requirements.
The objective function is to minimize the number of police that start working; therefore, the OF is:
(Minimize) Z = X1+X2+X3+X4+X5+X6
Constraints:
The only constraint type that is seen in this problem is the number of police that must working during each shift. This creates six constraints.
C1: X1+X6 >= 8
C2: X2+X1 >= 7
C3: X3+X2 >= 6
C4: X4+X3 >= 6
C5: X5+X4 >= 5
C6: X6+X5 >= 4
Non-Negative Constraint (all variables non-negative and integer)
The LINDO output for the problem is given below. Based on this solution, the police department should schedule 7 police officers to start at midnight, 6 officers to start at 8am shift, 2 officers to start at noon, 3 officers to start at 4pm shift and 1 officer to start at 8pm shifts resulting in 19 officers to be employed to satisfy the needs.
variable value reduced cost
x1 8 0
x2 1 0
x3 5 0
x4 1 0
x5 4 0
x6 0 0
This solution finds the number of police to be employed to be 19 and their start shifts are shown in the below table.
Shift
Starting Police
1
8
2
1
3
5
4
1
5
4
6
0
Total
19
(b) Shift # Time Period # of officers required
------------------------------------------------------------
1 midnight-4am 8
2 4am - 8am 7
3 8am - noon 6
4 noon - 4pm 6
5 4pm - 8pm 5
6 8pm - midnight 4
1) Defining decision variables:
Argument - the police force's primary decision is not how many officers are working each shift, but rather how many officers BEGIN work during each shift. Therefore, defining the variables as follows:
Xi = number of officers beginning work during shift i (i =1,2,....,6)
2) Formulate the objective function:
Argument - #of officers required = (# of officers who start work on shift 1)+ (# of officers who start work on shift 2) + ....... + (# of officers who start work on shift 6). Since each officer begins work on exactly one shift, this expression does not double-count officers. Therefore, the objective function can be represented as follows:
min z = X1 + X2 + X3 + X4 + X5 + X6
3) Formulate the constraints:
Shift 1 constraint: Who is going to be working on shift 1? Everybody except the employees who begin work on shift 5, or on shift 6, because they only work for 2 continuous shifts. Therefore, X1 + X2 + X3 + X4 >= 8
Shift 2 constraint: Who is going to be working on shift 2? Everybody except the employees who begin work on shift 6, or on shift 1, because they only work for 2 continuous shifts.
Therefore, X2 + X3 + X4 + X5 >= 7
Shift 3 constraint: Who is going to be working on shift 3? Everybody except the employees who begin work on shift 1, or on shift 2, because they only work for 2 continuous shifts.
Therefore, X3 + X4 + X5 + X6 >= 6
Shift 4 constraint: Who is going to be working on shift 4? Everybody except the employees who begin work on shift 2, or on shift 3, because theyonly work for 2 continuous shifts.
Therefore, X4 + X5 + X6 + X1 >= 6
Shift 5 constraint: Who is going to be working on shift 5? Everybody except the employees who begin work on shift 3, or on shift 4, because they only work for 2 continuous shifts.
Therefore, X5 + X6 + X1 + X2 >= 5
Shift 6 constraint: Who is going to be working on shift 6? Everybody except the employees who begin work on shift 4, or on shift 5, because they only work for 2 continuous shifts.
Therefore, X6 + X1 + X2 + X3 >= 4
Thus, I form the following Linear Program whose goal is to minimize the
number of police officers necessary to meet the daily requirements of the
force:
___
min z = X1 + X2 + X3 + X4 + X5 + X6
s.t.
X1 + X2 + X3 + X4 >= 8
X2 + X3 + X4 + X5 >= 7
X3 + X4 + X5 + X6 >= 6
X1 + X4 + X5 + X6 >= 6
X1 + X2 + X5 + X6 >= 5
X1 + X2 + X3 + X6 >= 4.
Shift
Starting Police
1
8
2
1
3
5
4
1
5
4
6
0
Total
19
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.