Problem Set A (Model Formulation)

Problem 1: Blending problem

A manufacturer of animal feed is producing feed mix for dairy cattle. The feed mix contains
two active ingredients and a filler to provide bulk. One kg of feed mix must contain a
minimum quantity of each of four nutrients as below:
Nutrient A B C D
gram 90 50 20 2

The ingredients have the following nutrient values and cost

A B C D Cost/kg (₹)
Ingredient 1 (gram/kg) 100 80 40 10 40
Ingredient 2 (gram/kg) 200 150 20 - 60
Formulate a linear program for the given problem. What should be the amounts of active
ingredients and filler in one kg of feed mix?

Solution to Problem 1:

Decision Variables
x1 = amount (kg) of ingredient 1 in one kg of feed mix
x2 = amount (kg) of ingredient 2 in one kg of feed mix
x3 = amount (kg) of filler in one kg of feed mix.

Objective: minimise cost

Zmin = 40X1 + 60X2

Subject to the constraints:

(a) nutrient constraints
100X1 + 200X2 ≥ 90 (nutrient A)
80X1 + 150X2 ≥ 50 (nutrient B)
40X1 + 20X2 ≥ 20 (nutrient C)
10X1 ≥ 2 (nutrient D)
(b) balancing constraint (an implicit constraint due to the definition of the variables)
X1 + X2 + X3 = 1
(c) non-negativity: X1, X2, X3 ≥0

Problem 2: Production planning problem

A company manufactures four variants of the same product and in the final part of the
manufacturing process there are assembly, polishing and packing operations. For each variant
the time required for these operations is shown below (in minutes) as is the profit per unit
sold.
Assembly Polish Pack Profit (₹)
Variant 1 2 3 2 1.50
2 4 2 3 2.50
3 3 3 2 3.00
4 7 4 5 4.50
  Given the current state of the labour force the company has estimated that, each year,
they have 100000 minutes of assembly time, 50000 minutes of polishing time and
60000 minutes of packing time available. How many of each variant should the
company make per year and what is the associated profit?
 Suppose now that the company is free to decide how much time to devote to each of
the three operations (assembly, polishing and packing) within the total allowable time
of 210000 (= 100000 + 50000 + 60000) minutes. How many of each variant should
the company make per year and what is the associated profit?

Solution to Problem 2:

Decision Variables
Let:
Xi be the number of units of variant i (i=1,2,3,4) made per year

Objective: maximise profit

Zmax = 1.5X1 + 2.5X2 + 3.0X3 + 4.5X4

Subject to constraints
(a) operation time
Assembly time, Tassy: 2X1 + 4X2 + 3X3 + 7X4 ≤ 100000
Polishing time, Tpol: 3X1 + 2X2 + 3X3 + 4X4 ≤ 50000
Packing time, Tpac: 2X1 + 3X2 + 2X3 + 5X4 ≤ 60000
(b) non-negativity
Xi ≥ 0 ; i = 1,2,3,4

In the second situation, where the only limitation is on the total time spent on all operations,
we simply have:

Tassy + Tpol + Tpac ≤ 210000 (total time) i.e. 7X1 + 9X2 + 8X3 + 16X4 ≤ 210000

Problem 3: Factory planning problem

Under normal working conditions a factory produces up to 100 units of a certain product in
each of four consecutive time periods at costs which vary from period to period as shown in
the table below. Additional units can be produced by overtime working. The maximum
quantity and costs are shown in the table below, together with the forecast demands for
the product in each of the four time periods.

Time Demand Normal Overtime Overtime

period (units) production costs production production costs
Rs (‘000)/unit capacity (Rs (‘000)/unit
(units)
1 130 6 60 8
2 80 4 65 6
3 125 8 70 10
4 195 9 60 11

It is possible to hold up to 70 units of product in store from one period to the next at a cost of
₹1.5K per unit per period. (This figure of ₹1.5K per unit per period is known as a stock-
holding cost and represents the fact that we are incurring costs associated with the storage of
stock).

It is required to determine the production and storage schedule which will meet the stated
demands over the four time periods at minimum cost given that at the start of period 1 we
have 15 units in stock. Formulate this problem as an LP.

Solution to Problem 3:

The decisions that need to be made relate to the amount to produce in normal/overtime
working each period. Hence let:

Xt = number of units produced by normal working in period t (t = 1,2,3,4) where Xt ≥ 0

Yt = number of units produced by overtime working in period t (t = 1,2,3,4) where Yt ≥ 0
It = number of units in stock at the end of period t (t = 0,1,2,3,4)

Objective: To minimise cost - which consists of the cost of ordinary working plus the cost of
overtime working plus the cost of carrying stock over (1.5K per unit).

Zmin = (6X1 + 4X2 + 8X3 + 9X4) + (8Y1 + 6Y2 + 10Y3 + 11Y4) + (1.5I0 + 1.5I1 + 1.5I2 +
1.5I3 + 1.5I4)

Subject to the constraints

(a) production limits
Xt ≤ 100 t = 1,2,3,4
Y1 ≤ 60
Y2 ≤ 65
Y3 ≤ 70
Y4 ≤ 60

(b) limit on space for stock carried over

It ≤ 70 t = 1,2,3,4

(c) we have an inventory continuity/balance equation of the form

closing stock at the end of the month = opening stock at the beginning of the month +
production in the month – demand for the month

I1 = I0 + (X1 + Y1) - 130

I2 = I1 + (X2 + Y2) - 80
I3 = I2 + (X3 + Y3) - 125
I4 = I3 + (X4 + Y4) - 195
where I0 = 15
Note:

I. inventory continuity equations of the type shown above are common in production
planning problems involving more than one time period. Essentially the inventory
variables (It) and the inventory continuity equations link together the time periods
being considered and represent a physical accounting for stock.
 II. These equations can be viewed in another way. Considering the inventory continuity
equations, we have that the above equations which ensure that demand is always met
can be rewritten as:
I1 ≥ 0
I2 ≥ 0
I3 ≥ 0
I4 ≥ 0

Problem 4: Workforce scheduling problem

Evening shift resident doctors in a government hospital work five consecutive days and have
two consecutive days off. Their five days of work can start on any day of the week and the
schedule rotates indefinitely. The hospital requires the following minimum number of doctors
from Monday to Sunday: 16, 12, 15, 14, 16, 18, 20.
No more than 10 doctors can start their five working days on the same day.
 Formulate the hospital's problem as a linear program to minimize the number of
doctors employed by the hospital.
 Comment upon the advantages/disadvantages you foresee of formulating and solving
this problem as a linear program.

Solution to Problem 4:

Decision Variables
Let
X1 = number of doctors starting their 5-days work week on Monday
X2 = number of doctors starting on Tuesday
X3 = number of doctors starting on Wednesday
X4 = number of doctors starting on Thursday
X5 = number of doctors starting on Friday
X6 = number of doctors starting on Saturday
X7 = number of doctors starting on Sunday

The above information could have been captured in compact form by following statement:
Let
Xi = number of doctors starting their 5-days work week on day i (i =1,...,7)
Monday be day 1, Tuesday be day 2, ..., Sunday be day 7

Objective Function (Minimize the total number of employees hired)

Minimize Z = X1 + X2 + X3 + X4 + X5 + X6 + X7

Constraints: (We need to determine the total number of employees available on each day.
For instance, on Monday, employees who began their 5-day work week on Thursday, Friday,
Saturday, Sunday, and Monday will be available. The same logic applies to the other days,
with availability based on the start of each employee’s 5-day shift.)
X1 + X4 + X5 + X6 + X7 ≥ 16 (Monday)
X1 + X2 + X5 + X6 + X7 ≥ 12 (Tuesday)
X1 + X2 + X3 + X6 + X7 ≥ 15 (Wednesday)
X1 + X2 + X3 + X4 + X7 ≥ 14 (Thursday)
X1 + X2 + X3 + X4 + X5 ≥ 16 (Friday)
X2 + X3 + X4 + X5 + X6 ≥ 18 (Saturday)
X3 + X4 + X5 + X6 + X7 ≥ 20 (Sunday)

X1 ≤ 10
X2 ≤ 10
X3 ≤ 10
X4 ≤ 10
X5 ≤ 10
X6 ≤ 10
X7 ≤ 10

Non-negativity Constraints
Xi ≥ 0 ; i =1 to 7

Some of the advantages and disadvantages of solving this problem as a linear program
are:

 need variable values which are integer

 some doctors will always end up working weekends
 how do we choose the doctors to use, e.g., if X3=7, which 7 doctors do we choose to
begin their work week on day 3?
 what happens if doctors fail to report in (e.g., if they are sick) - we may fall below the
minimum number required
 the approach above enables us to deal with the problem in a systematic fashion
 have the potential to reduce the size of the workforce by more effectively matching
the resources to the needs

Problem 5: Workforce scheduling problem

A super bazaar in a city daily needs between 22 to 30 workers depending on time of day. The
rush hrs are between noon & 2pm. The table below indicates the number of workers needed
at various hours:-

Time Period Number of Workers Needed

9am to 11am 22
11am to 1pm 30
1pm to 3pm 25
3pm to 5pm 23

The super bazaar now employs 24 full time workers but needs a few part time workers
also. A part time worker must put in exactly 4 hrs a day but can start at any hour between
9am to 1pm. Full time workers work from 9am to 5pm but are allowed an hour for lunch
(half can eat at 12 noon, & the balance half at 1pm). Full timers thus provide 35 hours per
week of production labor time.
The management of the super bazaar limits part time hours to a maximum of 50% of the
days total requirement.
Part time workers earn Rs 300/- per day on the average, while full timers earn Rs 900/-
per day in salary and other benefits.

Formulate the problem as an LP model to minimize total daily manpower cost.

Solution to Problem 5:

Decision Variables

Let:
X = Number of full-time workers assigned (integer, but we’ll treat as continuous for LP
formulation).
Y1 = Number of part-time workers starting at 9am
Y2 = Number of part-time workers starting at 10am
Y3 = Number of part-time workers starting at 11am
Y4 = Number of part-time workers starting at 12 noon
Y5 = Number of part-time workers starting at 1pm (no need to hire part-timeworkers after 1
pm as they will not be able to complete 4 hrs)

Half of the full time workers have lunch between 12:00 pm -1:00 pm and the remaining half
have lunch during 1:00 pm - 2:00 pm. So better to split into hourly slots and then
reconstruct.

Availability of workers
Time Full workers workers workers workers workers Workers
time starting starting starting starting at starting required
workers at 9am at 10am at 11am 12 pm at 1pm
9 am-10 am X Y1 22
10 am-11 am X Y1 Y2 22
11 am-12 pm X Y1 Y2 Y3 30
12 pm-1 pm X/2 Y1 Y2 Y3 Y4 30
1 pm-2 pm X/2 Y2 Y3 Y4 Y5 25
2 pm-3 pm X Y3 Y4 Y5 25
3 pm-4 pm X Y4 Y5 23
4 pm-5 pm X Y5 23

Objective Function (Minimize daily labor cost)

Minimize Z = 900X + 300(Y1 + Y2 + Y3 + Y4 + Y5)

1. Hourly Coverage Constraints

X + Y1 ≥ 22 (9 am-10 am)
X + Y1 + Y 2 ≥ 22 (10 am-11 am)
X + Y1 + Y 2 + Y 3 ≥ 30 (11 am-12 pm)
X/2 +Y1 + Y2 + Y3 + Y4 ≥ 30 (12 pm-1 pm)
X/2 +Y2 + Y3 + Y4 + Y5 ≥ 25 (1 pm-2 pm)
X + Y3 + Y 4 + Y 5 ≥ 25 (2 pm-3 pm)
X + Y4 + Y5 ≥ 23 (3 pm-4 pm)
X + Y5 ≥ 23 (4 pm-5 pm)
X ≤ 24
 2. Part-Time Limit Constraint
Total part-time hours = 4(Y1 + Y2 + Y3 + Y4 + Y5)
Total labor hours required = 22 + 22 + 30 + 30 + 25 + 25 + 23 + 23 = 200

Maximum part-time hours = 50% of 200 = 100

So:
4(Y1 + Y2 + Y3 + Y4 + Y5) ≤ 100 or (Y1 + Y2 + Y3 + Y4 + Y5) ≤ 25

Non-negativity
X,Y1,Y2,Y3,Y4,Y5 ≥ 0