Unit 5: Optimization Techniques

Introduction of Linear Programming, Formulation and Solution of LPP, PERT and CPM.

LINEAR PROGRAMMING PROBLEM (LPP):

Definition – The general linear programming problem calls for optimizing
(maximizing/ minimizing) a linear function of variables called the ‘Objective Function’
subject to a set of linear equations and/or inequalities called the ‘Constraints’ or
‘Restrictions’.

Objective Function – Maximize / Minimize Z=c 1 x 1 +c 2 x 2 +…+ c n x n

Constraints – a 11 x 1 +a 12 x 2+ …+a1 n x n ( ≤/¿ /≥ ) b 1

a 21 x 1+ a22 x 2 +…+a 2 n x n ( ≤/¿/≥ ) b2
………… ……………………………………
………… ……………………………………
a m 1 x 1+ am 2 x2 + …+amn x n ( ≤/¿ /≥ ) b m

Non-negative restrictions – x 1 , x 2 , x 3 , … , x n ≥0

Structure of LPP:
Maximize / Minimize Z=c 1 x 1 +c 2 x 2 +…+ c n x n
Subject to a 11 x 1 +a 12 x 2+ …+a1 n x n ( ≤/¿ /≥ ) b 1
a 21 x 1+ a22 x 2 +…+a 2 n x n ( ≤/¿/≥ ) b2
………… ……………………………………
………… ……………………………………
a m 1 x 1+ am 2 x2 + …+amn x n ( ≤/¿ /≥ ) b m
and x 1 , x 2 , x 3 , … , x n ≥0 .

Example 1: A firm manufactures two types of products A and B, and sells them at a profit
₹ 2 on type A and ₹ 3 on type B. Each product is processed on two machines G and H. Type
A requires on 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 available for not more than 6 hour 40
minutes while machine H is available for 10 hours during any working day. Formulate the
problem as a linear programming problem.
Solution: Let x 1 and x 2 be the number of products of Type A and B respectively.
Time of products (minutes)
Machine Type A ( x 1 units) Type B ( x 2 units) Available time (minutes)
G 1 1 400
H 2 1 600
 Profit per unit ₹2 ₹3

Since per unit profit of type A is ₹2 per unit and of type B is ₹3 per unit. So, total profit
of type A is ₹ 2 x1 and of type B is ₹ 3 x 2. Therefore, the objective function is
Z=2 x 1 +3 x 2
As the objective function is a profit function hence, we can write the objective function
as
Max . Z=2 x 1+ 3 x 2
Now, since machine G takes 1-minute time on type A and 1-minute time on type B, the
total time required on machine G is given by x 1+ x2 . But machine G is not available more
than 400 minutes, therefore (first constraint)
x 1+ x2 ≤ 400
Also, the machine H is takes 2-minutes time on type A and 1-minute time on type B, the
total time required on machine H is given by 2 x1 + x 2. But machine H is not available
more than 600 minutes, therefore (second constraint)
2 x1 + x 2 ≤600
Since it is not possible to produce negative quantities, therefore (non-negative
restrictions)
x 1 ≥ 0∧x2 ≥ 0
Hence, Max . Z=2 x 1+ 3 x 2
Subject to x 1+ x2 ≤ 400
2 x1 + x 2 ≤600
and x 1 , x 2 ≥ 0.
is the required LPP.

Example 2: A company produces two types of hats. Each hat of the first type requires
twice as much labour time as the second type. If all hats are of the second type only, the
company can produce a total of 500 hats a day. The market limits daily sales of the first
and second type to 150 and 250 hats. Assuming that the profits per hat are ₹8 for type A
and ₹5 for type B. Formulate the LPP in order to determine the number of hats to be
produced of each type so as to maximize the profit.
Solution: Let the company produce x 1 hats of type A and x 2 hats of type B each day.
The profit after selling these two types of hats is given by
Z=8 x 1+5 x 2
Since the company can produce at the most 500 hats in a day and type A hats require
twice as much time a that of type B hats.
So, the production restriction is given by 2 t x 1+ t x 2 ≤ 500 t , where t is the labour time per
unit of type B hat i.e.
2 x1 + x 2 ≤500
But, there limitations on the sale of hats, therefore further restrictions are:
x 1 ≤ 150 and x 2 ≤ 250
Also, since the company cannot produce negative quantities, therefore
x 1 ≥ 0 and x 2 ≥ 0
Hence, the final LPP is:
Max . Z=8 x 1 +5 x2
Subject to 2 x1 + x 2 ≤500
x 1 ≤ 150
x 2 ≤ 250
and x 1 , x 2 ≥ 0.

Example 3: The manufacturer of patent medicines is proposed to prepare a production

plan for medicines A and B. There are sufficient ingredient available to make 20,000
bottles of medicine A and 40,000 bottles of medicine B, but there are only 45,000 bottles
available into which either of the medicines can be filled. Further, it takes three hours to
prepare enough material to fill 1000 bottles of medicine A and one hour to prepare
enough material to fill 1000 bottles of medicine B, and there are 66 hours available for
this operation. The profit if ₹8 per bottle for medicine A and ₹7 per bottle for medicine B.
Formulate this problem as LPP.
Solution: Let the manufacturer produces x 1 and x 2 thousands of bottles of medicines A
and B respectively.
Since it takes three hours to prepare 1000 bottles of medicine A, the time required to fill
x 1 thousands of bottles of medicine A will be 3 x 1 hours. Similarly, the time required to
prepare x 2 thousand bottles of medicine B will be x 2 hours. Therefore, total time
required to prepare x 1 thousand bottles of medicine A and x 2 thousand bottles of
medicine B will be 3 x 1+ x 2 hours.
Now, since the total time available for this operation is 66 hours, so 3 x 1+ x 2 ≤66
There are only 45000 bottles are available for filling medicines A and B, so x 1+ x2 ≤ 45
There are sufficient ingredients available to make 20000 bottles of medicine A and
40000 bottles of medicine B, hence x 1 ≤ 20 and x 2 ≤ 40
Number of bottles being non-negative, x 1 ≥ 0 and x 2 ≥ 0
At the rate of ₹8 per bottle for type A medicine and ₹7 per bottle for type B medicine,
the total profit on x 1 thousand bottles of medicine A and x 2 thousand bottles of medicine
B will become Z=8 ×1000 x 1+ 7× 1000 x2 ⇒ Z=8000 x 1+7000 x 2
Thus, the required LPP is
Maximize Z=8000 x 1+ 7000 x 2 subject to the constraints 3 x 1+ x 2 ≤66 , x 1 + x 2 ≤ 45 ,
x 1 ≤ 20 , x2 ≤ 40 and x 1 , x 2 ≥ 0.

Example 4: A toy company manufactures two types of doll, a basic version – doll A and a
deluxe version – doll B. Each doll of type B takes twice as long to produce as one of type A
and the company would have time to make a maximum of 2000 per day. The supply of
plastic is sufficient to produce 1500 dolls per day (both A and B combined). The deluxe
version requires a fancy dress of which there are only 600 per day available. If the
company makes a profit of ₹3 and ₹5 per doll respectively on doll A and B, then how many
of each doll should be produced per day in order to maximize the total profit. Formulate
the LPP.
Solution: Let x 1 and x 2 be the number of dolls produced per day of type A and B
respectively. Let the doll A require t hours so that the doll B require 2 t hours. So the
total time to manufacture x 1 and x 2 dolls should not exceed 2000 t hours. Therefore,
t x 1 +2 t x 2 ≤ 2000 t i.e. x 1+ 2 x 2 ≤2000
The availability of raw material (plastic) is sufficient to produce 1500 dolls per day of
both A and B type, x 1+ x2 ≤1500
Fancy dress is available for only 600 deluxe version dolls, therefore the dress constraint
is x 2 ≤ 600
The company makes a profit of ₹3 per doll on type A and ₹5 per doll on type B, so
equation of the profit function is 3 x 1+5 x 2
The production of dolls cannot be negative, therefore x 1 ≥ 0 and x 2 ≥ 0
Thus, the required LPP is:
Maximize Z=3 x 1+5 x 2
Subject to x 1+ 2 x 2 ≤2000
x 1+ x2 ≤1500
x 2 ≤ 600
 and x 1 , x 2 ≥ 0.

Example 5: In a chemical industry, two products A and B are made involving two
operations. The production of B also results in a by-product C. The product A can be sold at
₹3 profit per unit and B at ₹8 profit per unit. The by-product C has a profit of ₹2 per unit,
but it cannot be sold as the destruction cost is ₹1 per unit. Forecasts show that up to 5
units of C can be sold. The company gets 3 units of C for each unit of A and B produced.
Forecasts show that they can sell all the units of A and B produced. The manufacturing
times are 3 hours per unit for A on operation one and two respectively, 4 hours and 5
hours per unit for B on operation one and two respectively. Because the product C results
from producing B, no time is used in producing C. The available times are 18 and 21 hours
of operation one and two respectively. The company question: how much A and B should
be produced keeping C in mind to make the highest profit. Formulate the LP model for this
problem.
Solution: Let x 1 , x 2 , x 3 be the number of units produced of product A, B, C respectively.
Then the profit gained by the industry is given by Z=3 x1 +8 x 2 +2 x 3
Here it is assumed that all the units of product A and B are sold.
In first operation, A takes 3 hours of manufacturer’s time and B takes 4 hours of
manufacturer’s time, therefore total number of hours required in first operation
becomes 3 x 1+ 4 x 2
In second operation, A takes 3 hours of manufacturer’s time and B takes 5 hours of
manufacturer’s time, therefore the total number of hours used in second operation
becomes 3 x 1+5 x 2
Since there are 18 hours available in first operation and 21 hours in second operation,
the restrictions become: 3 x 1+ 4 x 2 ≤ 18 , 3 x 1+5 x 2 ≤ 21

Also, the company gets 3 units of by-product C for each unit of B produced, therefore the
total number of units of product B and C produced becomes: x 2+ 3 x 3
But, the maximum number of units of C can be sold is 5, therefore x 2+ 3 x 3 ≤5
The quantity cannot be negative, therefore x 1 ≥ 0 , x 2 ≥ 0 and x 3 ≥ 0
Thus the required LPP is
Maximize Z=3 x 1+ 8 x 2 +2 x 3
Subject to 3 x 1+ 4 x 2 ≤ 18
3 x 1+5 x 2 ≤ 21
x 2+ 3 x 3 ≤5
 and x 1 , x 2 , x 3 ≥ 0.

Example 6: A farmer has 100 acres farm. He can sell all tomatoes, lettuce, or radishes he
can raise. The price he can obtain is ₹1 per kg for tomatoes, ₹0.75 a head for lettuce and
₹2 per kg for radishes. The average yield per acre is 2000 kg of tomatoes, 3000 heads of
lettuce and 1000 kg of radishes. Fertilizer is available at ₹0.50 per kg and the amount
required per acre is 100 kg each for tomatoes and lettuce, and 50 kg for radishes. Labour
required for sowing, cultivating and harvesting per acre is 5 man-days for tomatoes and
radishes, and 6 man-days for lettuce. A total of 400 man-days of labour are available at
₹20 per man-day. Formulate this problem as a linear programming model to maximize
the farmer’s total profit.
Solution: Let x 1 , x 2 , x 3 be the acre of land to grow tomatoes, lettuce and radishes
respectively. So the farmer will produce 2000 x 1 kg of tomatoes, 3000 x 2 heads of lettuce
and 1000 x 3 kg of radishes.
Therefore, total sale will be = ₹ [ 2000 x 1+ 0.75× 3000 x2 +2 ×1000 x 3 ]

Fertilizer expenditure will be = ₹ [ 0.50 {100 ( x 1+ x 2 ) +50 x 3 }]

Labour expenditure will be = ₹ [ 20 ( 5 x 1+ 6 x2 +5 x 3 ) ]

Farmer’s net profit will be = Total Sale (₹) – Total expenditure (₹)

[ ]
Z=[ 2000 x1 +0.75 × 3000 x 2 +2 ×1000 x 3 ] − 0.50 {100 ( x1 + x 2 ) +50 x 3 } − [ 20 ( 5 x1 +6 x 2 +5 x3 ) ]

⇒ Z=1850 x1 +2080 x 2+ 1875 x 3

Since total area of the farm is restricted to 100 acre, therefore x 1+ x2 + x 3 ≤100
Also, the total man-days labour is restricted to 400 man-days, so 5 x 1+6 x 2 +5 x 3 ≤ 400
Land allocation cannot be negative, therefore x 1 ≥ 0 , x 2 ≥ 0 and x 3 ≥ 0
Hence, the final LPP is
Maximize Z=1850 x 1+2080 x 2 +1875 x3
Subject to x 1+ x2 + x 3 ≤100
5 x 1+6 x 2 +5 x 3 ≤ 400
and x 1 , x 2 , x 3 ≥ 0.

Example 7: A manufacturer produces three models (I, II and III) of a certain product. He
uses two types of raw material (A and B) of which 4000 and 6000 units respectively are
available. The raw material requirements per unit of the three models are given below:
Requirement per unit of given model

Raw Material I II III

 A 2 3 5

B 4 2 7

The labour time for each unit of model I is twice that of model II and three times that of
model III. The entire labour force of the factory can produce the equivalent of 2500 units
of model I. A market survey indicates that the minimum demand of the three models are
500, 500 and 375 units respectively. However, the ratios of the number of units produced
must be equal to 3:2:5. Assume that the profit per unit of models I, II and III are ₹ 60, 40
and 100 respectively. Formulate the problem as a linear programming model in order to
determine the number of units of each product which will maximize profit.
Solution: Let x 1 , x 2 , x 3 be the number of units produced by the manufacturer of model I,
II and III respectively. Then the raw material constraints will be
2 x1 +3 x 2 +5 x 3 ≤ 4000 (for A)
4 x1 +2 x 2+ 7 x 3 ≤ 6000 (for B)
Suppose it takes labour time t for producing one unit of model I, so by the given
condition it will take t /2 and t /3 labour time for producing one unit of model II and III
respectively.
As the factory can produce 2500 units of model I, so the restriction on the production
t t 1 1
time will be t x 1 + x 2+ x 3 ≤2500 t i.e. x 1+ x 2 + x 3 ≤ 2500
2 3 2 3
Also, since at least 500 units of model type I and II each and 375 units of model III are
demanded, the constraints of market demand needs.
x 1 ≥ 500 , x2 ≥500 and x 3 ≥ 375
But the ration of the number of units of different types of models is 3 : 2 : 5, we have
1 1 1 1
x= x and x= x
3 1 2 2 2 2 5 3
Since the profit per unit on model I, II and III are ₹60, ₹40 and ₹100 respectively, the
objective function is to maximize the profit Z=60 x 1+ 40 x2 +100 x 3
Hence the LPP is
Maximize Z=60 x 1+ 40 x 2+100 x 3
Subject to 2 x1 +3 x 2 +5 x 3 ≤ 4000
4 x1 +2 x 2+ 7 x 3 ≤ 6000
1 1
x 1+ x 2 + x 3 ≤ 2500
2 3
 1 1 1 1
x 1= x 2 , x 2= x 3
3 2 2 5
and x 1 ≥ 500 , x2 ≥500 , x 3 ≥375 .

Example 8: One of the interesting problems in linear programming is that of balanced

diet. Dieticians tell us that a balanced diet must contain quantities of nutrients such as
calories, minerals, vitamins, etc. Suppose that we are asked to find out the food that should
be recommended from a large number of alternative sources of these nutrients so that the
total cost of food satisfying minimum requirements of balanced diet is the lowest.
The medical experts and dieticians tell us that it is necessary for an adult to
consume at least 75 g of proteins, 85 g of fats, and 300 g of carbohydrates daily. The
following table gives the food items (which are readily available in the market), analysis,
and their respective costs.
Food value (gms.) per 100 g
Food Type Proteins Fats Carbohydrates Cost per kg (₹)
1 8.0 1.5 35.0 1.00
2 18.0 15.0 - 3.00
3 16.0 4.0 7.0 4.00
4 4.0 20.0 2.5 2.00
5 5.0 8.0 40.0 1.50
6 2.5 - 25.0 3.00
Minimum daily requirements 75 85 300

Solution: Let x 1 , x 2 , x 3 , x 4 , x 5 and x 6 units of food types respectively be used per day in a
diet and the total diet must at least supply the minimum requirements. The object is to
minimize total cost of diet. The objective function thus becomes
Z=x 1+3 x 2 +4 x 3 +2 x 4 +1.5 x 5+ 3 x 6
Since 8, 18, 16, 4, 5 and 2.5 gm of proteins are available from 100 gm unit of each type of
food respectively, total proteins available from x 1 , x 2 , x 3 , x 4 , x 5 and x 6 units of each food
respectively will be 8 x 1+ 18 x 2 +16 x 3+ 4 x 4 +5 x 5 +2.5 x 6 gm daily.
But minimum daily requirement of proteins as prescribed in 75 gms. Hence, the protein
requirement constraint is 8 x 1+ 18 x 2 +16 x 3+ 4 x 4 +5 x 5 +2.5 x 6 ≥ 75
Similarly, fats and carbohydrates requirement constraints are obtained respectively as
given below:
1.5 x 1+15 x 2 +4 x 3 +20 x 4 +8 x 5 ≥ 85
35 x 1+7 x 3 +2.5 x 4 + 40 x 5 +25 x 6 ≥ 300
Further, x 1 , x 2 , x 3 , x 4 , x 5 , x 6 are all non-negative quantities, i.e.
 x 1 ≥ 0 , x 2 ≥ 0 , x 3 ≥ 0 , x 4 ≥ 0 , x5 ≥ 0 , x 6 ≥ 0
Thus, the LPP is
Minimize Z=x 1 +3 x 2+ 4 x 3 +2 x 4 + 1.5 x 5 +3 x 6
Subject to 8 x 1+ 18 x 2 +16 x 3+ 4 x 4 +5 x 5 +2.5 x 6 ≥ 75
1.5 x 1+15 x 2 +4 x 3 +20 x 4 +8 x 5 ≥ 85
35 x 1+7 x 3 +2.5 x 4 + 40 x 5 +25 x 6 ≥ 300
and x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥0 .

Graphical Solution of LPP:

Simple LPP of two decision variables can be easily solved by graphical method by
following steps:
Step 1 – Consider each inequality constraint as equation.
Step 2 – Plot each equation on the graph, as each one will geometrically represent a
straight line.
Step 3 – Shade the feasible region. Every point on the line will satisfy the equation of the
line. If the inequality constraint corresponding to that line is ‘≤’ then the region
below the line lying in the first quadrant (due to non-negativity of variables) is
shaded. For the inequality constraints with ‘≥’ sign, the region above the line in
the first quadrant is shaded. The points lying in common region will satisfy all
the constraints simultaneously. The common region thus obtained is called the
feasible region.
Step 4 – Choose the convenient value of Z (say 0) and plot the objective function line.
Step 5 – Pull the objective function line until the extreme points of the feasible region.
In the maximization problem, this line will stop farthest from the origin and
passing through at least one corner of the feasible region. In the minimization
problem, this line will stop nearest to the origin and passing through at least
one corner of the feasible region.
Step 6 – Read the coordinates of the extreme point(s) selected in Step 5, and find the
maximum or minimum (as the problem may be) value of Z.

Types of graphical solutions: (for two inequalities)

i) Bounded solution –
ii) Unbounded solution –

iii) Unique solution –

iv) Infinite many solutions –

v) No solution –

Example 1: Find the solution of the following LPP by graphical method.

Maximize Z=3 x 1+5 x 2 subject to x 1+ 2 x 2 ≤2000 , x 1+ x 2 ≤1500 , x 2 ≤ 600 and
x 1 , x 2 ≥ 0.
Solution: Consider the inequalities in the constraint as equations and identify the
values of the variables to draw the graph, i.e.
x 1+ 2 x 2=2000 x 1+ x2 =1500 x 2=600
x1 0 2000 x1 0 1500 x1 0 500

x2 1000 0 x2 1500 0 x2 600 600

For point B: For point C:

x 1+ 2 x 2=2000 x 1+ 2 x 2=2000

¿ x 1+ x2=1500 x 2=600
---------------------------------------- -----------------------------------

For A (1500, 0) Z=3 ( 1500 ) +5 ( 0 )=4500

For B (1000, 500) Z=3 ( 1000 ) +5 ( 500 )=3000+2500=5500

For C (800, 600) Z=3 ( 800 ) +5 ( 600 )=2400+3000=5400

For D (0, 600) Z=3 ( 0 ) +5 ( 600 )=0+3000=3000

Maximize Z = 5500, x 1=1000 , x2 =500

Example 2: Consider the problem

Maximize Z=8000 x 1+ 7000 x 2 subject to 3 x 1+ x 2 ≤66 , x 1 + x 2 ≤ 45 , x 1 ≤ 20 ,
x 2 ≤ 40 and x 1 , x 2 ≥ 0.
Solution: First plot the lines 3 x 1+ x 2 ≤66 , x 1 + x 2 ≤ 45 , x 1 ≤ 20 , x 2 ≤ 40 and then
identify the feasible region, i.e.
3 x 1+ x 2=66 x 1+ x2 =45 x 1=20 x 2=40
x1 0 22 x1 0 45 x1 20 20 x1 0 20

x2 66 0 x2 45 0 x2 0 40 x2 40 40

For A (20, 0) Z=8000 ( 20 ) +7000 ( 0 ) =160000

For B (20, 6) Z=8000 ( 20 ) +7000 ( 6 ) =160000+42000=202000

For C (10.5, 34.5) Z=8000 ( 10.5 ) +7000 ( 34.5 )=84000+241500=325500

For D (5, 40) Z=8000 ( 5 ) +7000 ( 40 )=40000+ 280000=320000

For E (0, 40) Z=8000 ( 0 ) +7000 ( 40 )=280000

Maximize Z = 325500, x 1=10.5 , x2 =34.5

Example 3: Old hens can be bought at ₹2 each and young ones at ₹5 each. The old hens
lay 3 eggs per week and the young ones lay 5 eggs per week, each egg being worth 30
paise. A hen (young or old) costs ₹1 per week to feed. I have only ₹80 to spend for hens,
how many of each kind should I buy to give a profit of more than ₹6 per week, assuming
that I cannot house more than 20 hens.
Solution: Let x 1 be the number of old hens and x 2 the number of young hens to be
bought.
Since old hens lay 3 eggs per week and the young ones lay 5 eggs per week, the total
number of eggs obtained per week will be 3 x 1+5 x 2
Consequently, the cost of each egg being 30 paise, the total gain will be ₹ 0.30 ( 3 x 1+ 5 x 2 )
Total expenditure for feeding ( x 1 + x 2) hens at the rate of ₹1 each will be ₹ 1 ∙ ( x 1 + x 2 )
Thus, total profit Z earned per week will be Z=Total Gain−Total Expenditure
or Z=0.30 ( 3 x 1+5 x 2 )−( x 1 + x 2 ) or Z=0.50 x 2−0.10 x 1
Since old hens can be bought at ₹2 each and young ones at ₹5 each and there are only
₹80 available for purchasing hens, the constraint is: 2 x1 +5 x 2 ≤ 80
Also, since it is not possible to house more than 20 hens at a time, x 1+ x2 ≤ 20
Also, since the profit is restricted to be more than ₹6, this means that the profit function
Z is to be maximized. Thus there is no need to add one more constraint, i.e.
0.50 x 2−0.10 x 1 ≥ 6
Again it is not possible to purchase negative quantity of hens, therefore x 1 ≥ 0 , x 2 ≥ 0.
Hence the LPP is:
Maximize Z=0.50 x 2−0.10 x 1 subject to 2 x1 +5 x 2 ≤ 80 , x 1+ x 2 ≤20
and x 1 , x 2 ≥ 0.
Graphical solution –
2 x1 +5 x 2=80 x 1+ x2 =20
x1 0 40 x1 0 20

x2 16 0 x2 20 0

At point C, x 1=20 and x 2=0

20 40
On solving the equations for point E, x 1= and x 2=
3 3
At point B, x 1=0 and x 2=16
For C ( 20 , 0 ) Z=0.50 ( 0 ) −0.10 ( 20 )=−2

For E ( 203 , 403 ) Z=0.50 ( 403 )−0.10 ( 203 )= 203 − 23 = 183 =6

For B ( 0 ,16 ) Z=0.50 ( 16 ) −0.10 ( 0 )=8−0=8

Maximize Z = 8, x 1=0 , x 2=16.

Example 4: Solve the following LPP by graphical method:

Minimize Z=1.5 x 1 +2.5 x2 subject to x 1+ 3 x 2 ≥3 , x 1+ x2 ≥ 2
and x 1 , x 2 ≥ 0.
Solution: x 1+ 3 x 2=3 x 1+ x2 =2
x1 0 3 x1 0 2

x2 1 0 x2 2 0

For A ( 32 , 12 ) Z=1.5 ( 32 )+2.5 ( 12 )=3.5

For B ( 3 ,0 ) Z=1.5 ( 3 ) +2.5 ( 0 )=4.5

For C ( 0 , 2 ) Z=1.5 ( 0 ) +2.5 ( 2 )=5

3 1
Minimize Z = 3.5, x 1= , x 2= .
2 2

Example 5: Solve the following LPP by graphical method:

Maximize Z=3 x 1+ 2 x 2 subject to x 1−x 2 ≤ 1 , x 1 + x 2 ≥ 3 and x 1 , x 2 ≥ 0.
Solution: x 1−x 2=1 x 1+ x2 =3
 x1 0 1 x1 0 3

x2 -1 0 x2 3 0

Here Z can be made arbitrarily large, and the problem has no finite maximum value of Z.
Such problems are said to have unbounded solution.

Example 6: Solve the following LPP by graphical method:

Maximize Z=3 x 1−2 x 2 subject to x 1+ x2 ≤1 , 2 x1 +2 x 2 ≥ 4 and x 1 , x 2 ≥ 0.
Solution: x 1+ x2 =1 2 x1 +2 x 2=4
x1 0 1 x1 0 2

x2 1 0 x2 2 0
There is no point which satisfies both the constraints simultaneously. Hence the
problem has no solution because the constraints are inconsistent.

Example 7: Solve the following LPP by graphical method:

Maximize Z=5 x 1+3 x 2 subject to 3 x 1+5 x 2=15 , 5 x1 +2 x 2=10 and x 1 , x 2 ≥ 0.
Solution: 3 x 1+5 x 2=15 5 x 1+2 x 2=10
x1 0 5 x1 0 2

x2 3 0 x2 5 0

Since there is only a single solution point A ( 2019 , 1945 ), there is nothing to be maximized.
Such problem can arise only when the number of equations in the constraints is at least
equal to the number of variables. If the solution is feasible, it is optimal. If it is not
feasible, the problem has no solution.

Example 8: A firm plans to purchase at least 200 quintals of scrap containing high quality
metal X and low-quality metal Y. It decides that the scrap to be purchased must contain at
least 100 quintal of X metal and not more than 35 quintals of Y metal. The firm can
purchase the scrap from two suppliers (A and B) in unlimited quantities. The percentage
of X and Y metals in terms of weight in the scraps supplied by A and B is given below:
Metals Supplier A Supplier B

X 25% 75%

Y 10% 20%

The price of A’s scrap is ₹200 per quintal and that of B’s is ₹400 per quintal. Formulate
the LPP and solve it to determine the quantities that the firm should buy from the two
supplies so as to minimize total purchase cost.
Solution:

Minimize Z = ₹ 60000, x 1=100 , x2 =100.

Example 9: A local travel agent is planning a charter trip to a major sea resort. The eight-
day seven-night package includes the fare for round trip travel, surface transportation,
board and lodging, and selected tour options. The charter trip is restricted to 200 persons
and past experience indicates that there will not be any problem for getting 200 persons.
The problem for the travel agent is to determine the number of Deluxe, Standard, and
Economy tour packages to offer for this charter. These three plans each differ according to
seating and service for the flight, quality of accommodation meal plans and tour options.
The following table summarizes the estimated prices for the three packages and the
corresponding expenses for the travel agent. The travel agent has hired an aircraft for the
flat fee of ₹200000 for the entire trip.
Price and cost for four packages per person
Tour plan Price (₹) Hotel costs (₹) Meals and other expenses (₹)

Deluxe 10000 3000 4750

Standard 7000 2200 2500

Economy 6500 1900 2200

In planning the trip, the following considerations must be taken into account:
(i) At least 10% of the packages must be of the deluxe type.
(ii) At least 35% but not more than 70% must be of the standard type.
(iii) At least 30% must be of the economy type.
(iv) The maximum number of deluxe packages available in any aircraft is restricted to
60.
(v) The hotel desires that at least 120 of the tourists should be on the deluxe and
standard packages together.
The travel agent wishes to determine the number of packages to offer in each type so as to
maximize the total profit.
a) Formulate the above as a LPP.
b) Restate the above LPP in terms of two decision variables, taking advantage of the fact
that 200 packages will be sold.
c) Find the optimum solution using graphical methods for the restated LPP and interpret
your results.
Solution: Let x 1 , x 2 , x 3 be the number of Deluxe, Standard and Economy tour packages
restricted to 200 persons only to maximize the profit of the concern.
The contribution (per person) arising out of each type of tour package offered is as
follows:
Package type Price (₹) Hotel Cost (₹) Meals, etc. (₹) Net Profit (₹)
offered
(1) (2) (3) (4) = (1) –(2)-(3)

Deluxe 10000 3000 4750 2250

 2500

Standard 7000 2200 2200 2300

Economy 6500 1900 2400

Since the travel agent has to pay the flat fee of ₹ 200000 for the chartered aircraft for
the entire trip, the profit function will be:
Maximize Z=2250 x 1+ 2300 x 2 +2400 x 3−200000
The constraints according to given conditions (i) to (v) are as follows:
x 1 ≥ 20 from (i) x 3 ≥ 60 from (iii) x 1+ x2 + x 3=200
x 2 ≥ 70 from (ii) x 1 ≤ 60 from (iv)
x 3 ≤ 140 from (ii) x 1+ x2 ≥120 from (v) and x1 , x2 , x3 ≥ 0
Therefore,
20 ≤ x1 ≤ 60 ,70 ≤ x2 ≤ 140 , x 3 ≥60 , x 1+ x2 ≥120 , x 1 + x 2+ x 3=200 and
x1 , x2 , x3 ≥ 0
(a) The linear programming formation is given above.
(b) Since x 1+ x2 + x 3=200 , i.e. x 3=200−x 1−x2 , substitute the value of x 3 in the above
relations to get the following reduced LPP:
Maximize Z=−150 x 1−100 x 2+280000 , subject to 20 ≤ x1 ≤ 60 ,70 ≤ x2 ≤ 140 ,
120 ≤ x 1 + x 2 ≤ 140 and x1 , x2 ≥ 0
(c) Graphical solution: The representation of the LPP in (b) is
Maximize Z=267000 , x 1=20 , x 2=100 and x 3=80 .

Example 10: Solve the following LPP Graphically:

Maximize Z=3 x1 +5 x 2

Subject to x 1+ 2 x 2 ≤2000 , x 1+ x2 ≤1500 x 2 ≤ 600 and x 1 , x 2 ≥ 0

Solution:

x 1+ 2 x 2=2000 x 1+ x2 =1500 x 2=600

x1 0 2000 x1 0 1500 x1 0 500

x2 1000 0 x2 1500 0 x2 600 600
For A (1500, 0) Z=3 ( 1500 ) +5 ( 0 )=4500

For B (1000, 500) Z=3 ( 1000 ) +5 ( 500 )=3000+2500=5500

For C (900, 600) Z=3 ( 900 ) +5 ( 600 ) =2700+3000=5700

For D (0, 600) Z=3 ( 0 ) +5 ( 600 )=0+3000=3000

x 1=900 , x 2=600 and Maximize Z = 5700.