Question

(a) (1 pointd What type of problem, hence model ls this? (b) [14 pointa] Formulate the LP for the problem 3. The management of a hospital is trying to find an optimal schedule for its 60 nurses. There are three shifts everyday: Night (24:00-8:00), Day (8:00-16:00) and Swing (16:00-24:00). Minimum number of nurses who must be on duty each shift is given below: [16 points) Shift Mon Tue Wed Thu Fri Sat Sun Night 5324 3 22 Day795 725 Swing 007122 Page: 2 of 3 A nurse can be assigned to one shit (either night day or swing) and will have to work during the same shift whenever she's on duty. Furthermore, each nurse has to work four consecutive days during a week and will receive three days off. We would like to formulate an LP to minimize the total number of nurses scheduled for a week. (a) (1 point) What type of problem, hence model. 's this? (b) [15 points] Formulate the LP 15 points] A student is planning the coming semester, in partcular, he s attempting to allocate the weekly number of hours of study to our ot stuy il increase his grade by a certain quantity (starting at zero). Table

Answer 1

a. This is a Linear Programming Model

b. Answer

Variables:

Let:

Monday be day 1, Tuesday be day 2, Wednesday be day 3, Thursday be day 4, Friday be day 5, Saturday be day 6 and Sunday be day 7

Night be shift 1, Day be shift 2, swing be shift 3

then the variables are:

N_ij the number of workers starting their four consecutive work days on day i (i=1,...,7) and shift j (j=1,...,3)

These variables should be integer but, in order to formulate the problem as a linear program we allow them to take fractional values.

Constraints:

• upper limit on the total number of workers of 60

SUM{i=1 to 7} SUM{j=1 to 3} N_ij <= 60

since each nurse can start her working week only once during the seven days, three shifts, week.

• lower limit on the total number of nurses required for each day/shift period

let D_ij be the (known) number of nurses required on day i (i=1,...,7) and shift period j (j=1,...,3) e.g. D₅₃=11 (Friday, Swing)

then the constraints are:

Monday: N_1j + N_7j + N_6j + N_5j >= D_1j   j=1,...,3

Tuesday: N_2j + N_1j + N_7j + N_6j >= D_2j   j=1,...,3

Wednesday: N_3j + N_2j + N_1j + N_7j >= D_3j   j=1,...,3

Thursday: N_4j + N_3j + N_2j + N_1j >= D_4j   j=1,...,3

Friday: N_5j + N_4j + N_3j + N_2j >= D_5j   j=1,...,3

Saturday: N_6j + N_5j + N_4j + N_3j >= D_6j   j=1,...,3

Sunday: N_7j + N_6j + N_5j + N_4j >= D_7j   j=1,...,3

The logic here is straightforward, for example for Wednesday (day 3) the nurses working shift j on day 3 either started on Wednesday (day 3, N_3j) or on Tuesday (day 2, N_2j) or on Monday (day 1, N_1j) or on Sunday (day 7, N_7j) - so the sum of these variables is the total number of nurses on duty on day 3 in shift j and this must be at least the minimum number required (D_3j).

Objective function:

Minimize SUM{i=1 to 7} SUM{j=1 to 3} N_ij

where all variables N_ij>=0 and continuous (i.e. can take fractional values).