Linear Programming - Formulation Technique

(Problems and Solutions)

Question 1: A firm manufactures two types of products A and B and sells them at a profit of ₹ 2 on type A and ₹ 3 on type B. Each product is processed on two machines G and H. Type A requires one minute of processing time on G and two minutes on H. Type B requires one minute on G and one minute on H.
The machine G is not available for not more than 6 hours 40 minutes while machine H is available for 10 hours during any working day.

Formulate the problem as linear programming problem.

Solution:

Let number of products of type A =  x₁
and no. of products of type B = x₂

According to information given, it can be summarized as:

 Machine Time On products Available Time (in minutes) Type A (x₁ units) Type B (x₂ units) G 1 1 400 H 2 1 600 Profit per unit ₹2 ₹1

Profit on selling x₁ units (type A) = 2x₁
Profit on selling x₂ units (type B) = 3x₂

Total profit z = 2x₁ + 3x₂                           (objective function)

∵ Machine G takes 1 minute on type A and 1 minute on type B.
∴ Total no. of minutes required on machine G = x₁ + x₂
and Total no. of minutes required on machine H = 2x₁ + x₂

Machine G not available more than 6 hr 40 min (400 minutes)
⇒  x₁ + x₂  ≤ 400

and machine H not avialble more that 10 hrs(600 minutes).
⇒  2x₁ + x₂  ≤ 600

Since there can't be negative quantities ⇒ x₁ ≥ 0 and x₂ ≥ 0

Thus the allocation problem can be finally put in the form:
Find x₁ and x₂ such that profit
z = 2x₁ + 3x₂
is maximum, subject to conditions
x₁ + x₂  ≤ 400
2x₁ + x₂  ≤ 600
x₁, x₂ ≥ 0

Question 2: A city hospital has the following minimal daily requirements for nurses:

____________________________________________________________________________________
Shift Clock time (24 hrs day) Minimum no.
of nurses reqd.
____________________________________________________________________________________

1 6 am - 10 am 2
2 10am -  2 pm 7
3 2 pm -  6 pm 15
4 6 pm -  10 pm  8
5 10pm -  2 am 20
6 2 am -  6 am 6
__________________________________________________________________________________

Nurses report to the hospital at the beginning of each shift and work for 8 consecutive hours. The hospital wants to determine the minimum number of nurses be employed so that there would be sufficient nurses available for each shift.
Formulate this problem as as linear programming problem by setting up objective functions along with appropriate constraints.

Solution:
Let xj(where j = 1, 2, 3, ... ,6) be the number of nurses  to be employed by the hospital for the given shift j.
Since no. of nurses can't be -ve. ⇒  xj ≥ 0

The objective is to minimize total number of nurses i.e.

z = x₁ + x₂ + x₃ + x₄ + x₅ + x₆

In 8 hour duration, the number of nurses reporting at the beginning of shift and number of nurses continuing from earlier shift should be at least equal to the minimum requirement.
x₁ + x₂ ≥ 7,
x₂ + x₃ ≥ 15,
x₃ + x₄ ≥ 8,
x₄ + x₅ ≥ 20,
x₅ + x₆ ≥ 6 and
x₆ + x₁ ≥  2

Thus the linear programming problem can be finally put in the form:

Minimize z = x₁ + x₂ + x₃ + x₄ + x₅ + x₆
subject to constraints,
x₁ + x₂ ≥ 7, x₂ + x₃ ≥ 15, x₃ + x₄ ≥ 8, x₄ + x₅ ≥ 20,
x₅ + x₆ ≥ 6, x₆ + x₁ ≥  2
and x₁ ≥  0, x₂ ≥  0, x₃ ≥  0, x₄ ≥  0, x₅ ≥  0, x₆ ≥  0