Question

QUESTION 1 15 Marks A post office requires different numbers of full-time employees on different days of the week. Each full-time employee must work five consecutive days and then receive two days off. In Table 1, the number of employees required on each day of the week is specified. Table 1: Employee work schedule Day 1=Monday 2=Tuesday 3=Wednesday 4=Thursday S=Friday 6=Saturday 7=Sunday Number of full-time Employees Required 17 13 15 19 16 Formulate a linear programming (LP) model that the post office can use to minimize the number of full-time employees who are needed to satisfy these constraints. Clearly discuss the following basic optimization formulation steps relative to the aforementioned problem statement: i. ii. 111. Defining the decision variables Choosing an objective function Identifying the constraints

Optimization Problem

Answer 1

The given Linear programming model can be formulated as described below:

1. Defining decision variables

The decision variables, in this case, must be the number of employees receiving off on each possible consecutive pair of days. For simplicity of understanding, let us denote the number of employees who get weekly of on Monday & Tuesday by variable 'mt' , similarly those receiving off on Tuesday & Wednesday by the variable 'tw'. In this way define 7 variables namely: mt , tw, wt, tf, fs, ss & sm to denote the number of employees receiving week off on respective days. These 7 are our decision variables.

2. Choosing an objective function

This is clear in the given problem as we need to minimize the total number of full-time employees, So if we denote Z as the total number of full-time employees, we can write the objective function as:

Minimize Z where

Z = mt + tw + wt + tf + fs + ss + sm

3. Identifying the constraints

The constraints are also simple, as we just need to set the total working employees on any given day equal to or more than the required numbers given. For example, the number of employees working on Monday will be equal to the total number of full-time employees less the employees who take off on Sunday & Monday and also those who take off on Monday & Tuesday i.e.

1: Z - sm - mt >= 17

Similarly, we can write other constraints as :

(Note that we can also set these to be exactly equal to the numbers given, but that will not give any feasible solution for the given problem. So we are setting the number of employees greater than or equal to the required numbers)

2: Z - mt - tw >= 13

3: Z - tw - wt >= 15

4: Z - wt - tf >= 19

5: Z - tf - fs >= 14

6: Z - fs - ss >= 16

7: Z - ss - sm >= 11

8. mt, tw, wt, tf, fs, ss, sm >= 0

These equations & inequalities represent the complete formulation. These can be solved with any standard method or software & it gives 23 as the minimum number of employees. As stated above, if we set the constraints exactly equal to the required numbers, that will not yield a feasible solution, still, this is also a valid interpretation of the given constraints.

(**Please up-vote, If any doubt then please let me know in the comments.)