# Linear Programming: Allocation Problems — How can we Maximize the profit?

Question 1 (Allocation problem).

A cooperative society of farmers has 50 hectare of land to grow two crops X and Y. The profit from crops X and Y per hectare are estimated as USD10,500 and USD9,000 respectively. To control weeds, a liquid herbicide has to be used for crops X and Y at rates of 20 litres and 10 litres per hectare. Further, no more than 800 litres of herbicide should be used in order to protect fish and wild life using a pond which collects drainage from this land. How much land should be allocated to each crop so as to maximise the total profit of the society?

Solution:
Let x hectare of land be allocated to crop X and y hectare to crop Y. Obviously, x≥0,y≥0.
Profit per hectare on crop X=USD10500
Profit per hectare on crop Y=USD9000
Therefore, total profit=USD(10500x+9000y)
The mathematical formulation of the problem is as follows:
Maximise Z=10500x+9000y
subject to the constraints:

x+y≤50…(1) (constraint related to land)
20x+10y≤800…(÷10)
2x+y≤80…(2) (constraint related to use of herbicide)
x≥0, y≥0…(3) (non negative constraint)

Let us draw the graph of the system of inequalities (1) to (3). The feasible region OABC is shown (shaded) in the Fig-1. Observe that the feasible region is bounded.

The coordinates of the corner points 0, A, B and C are (0, 0), (40, 0), (30, 20) and (0, 50) respectively. Let us evaluate the objective function Z=10500x+9000y at these vertices to find which one gives the maximum profit.

 Corner Point Z=10500x+9000y O (0, 0) A (40, 0) B (30, 20) C (0, 50) 0 420000 495000 ← Maximum 450000

[Fig-1]

Hence, the society will get the maximum profit of USD4,95,000 by allocating 30 hectares for crop X and 20 hectares for crop Y.

Question 2. An aeroplane can carry a maximum of 200 passengers. A profit of \$1000 is made on each executive class ticket and a profit of \$600 is made on each economy class ticket.
The airline reserves at least 20 seats for executive class. However, at least 4 times as many passengers prefer to travel by economy class than by the executive class. Determine how many tickets of each type must be sold in order to maximize the profit for the airline. What is the maximum profit?
Solution:
Let the airline sell x tickets of executive class and y tickets of economy class.
The mathematical formulation of the given problem is as follows.
Maximize z=1000x+600y…(1)
subject to the constraints,

x+y≤200…(2)
x≥20…(3)
y-4x≥0…(4)
x,y≥0…(5)

The feasible region determined by the constraints is as follows.

The corner points of the feasible region are A(20, 80), B(40, 160), and C(20, 180).
The values of z at these corner points are as follows.

 Corner point z=1000x+600y A(20, 80) 68000 B(40, 160) 136000 → Maximum C(20, 180) 128000

The maximum value of z is 136000 at (40, 160).
Thus, 40 tickets of executive class and 160 tickets of economy class should be sold to maximize the profit and the maximum profit is \$136000.