# Linear Programming - Formulation Technique (Problems and Solutions)

## Linear Programming - Formulation Technique

**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 x

_{j}(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. ⇒ x

_{j}≥ 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**