40

OPERATIONS AESEAROH
decision variable must be known and fixed. In other words, this assumption means that
coefficients in the objective function as well as in the constraints are completely known
and do not change during the period of study. with al the
(b) Divisibility (or continuity). This implies that solution values of the decision
certainy
resources can take on any non-negative valucs, including fractional values of the decision variables
For instance, it is possible to produce 4.35 quintals of wheat or 17.35 thousand kilometers of varvables
6.52 thousand kilolitres of milk, so these variables are divisible. But it is not possible cloth
refrigerators. Such variables are not divisible and hence are to be assigned integer [Link] produce
necessary to have integer variables, the integer programming problem is considered to atto: When
desired values.
(c) Proportionality. This requires the contribution of cach decision variable in both
function and the constraints to be directly proportional to the value the
of the variable. For objective
production of one unit of a particular product uses 3 hours of a
particular resource,exampl
production of 6 units of that product uses 3x 6, i.e., 18 hours of that resource.
e, it
then the
(d) Additivity. The value of the objective function for the given values of decision
the total sum of resources used, must be equal to the sum of the variables and
from each decision variable and the sum of the resources used by
contributions (profit or Cost) eaned
For example, the total profit earned by the sale of two products each decision variable respectively.
the profits earned separately from A and B. A and B must be equal to the sum
Similarly, the amount of a resource consumed by Aand
B must be equal to the sum of resources used for A and B individually.

2:3. MATHEMATICAL FORMULATION OF THE

PROBLEM
The procedure for mathematical formulation of a linear
following major steps : programming problem consists of the
Step 1. Study the given situation to find the key decisions to be made.
Step 2. Identify the variables involved and designate them by symbols x; (G =
1, 2, ...).
Step 3. State the feasible alternatives which generally are : x; 20, for allj.
Step 4. Identify the constraints in the problem and express them as linear
inequalities or
equations, LHS of which are linear functions of the decision variables.
Step 5. Identify the objective function and express it as a linear function of the decision
variables.

2:4. ILLUSTRATIONS ON MATHEMATICAL FORMULATION OF LPPs

Here are some problems from real life, which have been put in the mathematical format.
SAMPLE PROBLEMS

201. (Product Allocation Problem). A company has three operational departments (weaving.
processing and packing) with capacity to produce three different types of clothes namely suitings,
shirtings and woollens yielding a profit of Ks. 2, Rs. 4 and Rs. 3 per metre respectively. One metre of
suiting requires 3 minutes in weaving, 2 minutes in processing and lminute in packing. Similarly one
metre of shirting requires 4 minutes in weaving, I minute in processing and 3 minutes in packing.
One metre of woollen requires 3 minutes in each department. In a week, total run time of each
department is 60, 40 and 80 hours for weaving, processing and packing respectively.
Fornulate the linear programming problem to find the product nix to maximize the profi.
 41
LINEAR PRNGRAMAN HORE- AATHEMATKAL FOAMULATION
Mtathematiral Formuatin
I data t the whem is smmarizet olow:
Profit
(Rs, peF metre)
Pcking
( Ne (N MNtes) (in mimutes)
Suings
Shitings
Wakns
Arahv (mùns)
e . The key deisin is o detemine the weekly rate of production for the three types of
clxhes
Se t us designate the weekly pouction of suitings, shirtings and woollens by x, metres,

e Sine it is not mssible ondue negative quntities, feasible alternatives are sets of
values of , nd , stistyìng , Q ;0and x; 0.
Step 4 The constraints ar the limited availability of three operational departments. One metre of
suiting rquires 3minutes of weaving. The quanity being a, metres, the requirement for suiting alone
will de , units Similarly, a, metres of shiting and a; metres of woollen will require 4x, and 3x,
mimues reseiely. Thus, the total rquirement of weaving will be 3u, + 4i, + 3i}, which should
S 3600.
NN eXAdthe available 3600mimuteS, So, the labour constraint becomes 3x, + 4i, + 3x,
Similarly, the constraints tor the processing department and packing departments are
2, + + i; s 400 and + t i; s 4800 respectively.
that whatever is
Step 5. The objective is to maximize the total protit from sales. Assuming + 3x3
produced is sold in the market, the total protit is given by the linear relation ¿= 2r, + 4r,
mathematical format :
The linear programming problem can thus be put in the following
Find x,, , and x; so as to nmaximize

subject to the constraints :

2ij t + i; s 2400

20 0 and 0.

202. (Product Mix Problem). Consider the following problem faced by a production planner in
for 8-ounce bottles and B for
asoft drinkplant. He has wo botling machùnes Aand B. Ais designed loss of eficiency. The following
l6-ounce botles. However, each can be used on both types with some
data is available:
S-ounce boles l6-ounce bottles
Machine
100minute 40minute
6Qminute 75/ninute
paise
Each machine can be rn 8-hours per day, S days per week. Profir on a 8-ounce bottle is 25
3,00,000 ounces
and on al6-ounce bottle is 35 paise. Weekly production of the drink cannot exceed
and the market can absorb 25,000 8-ounce botles and 7,000 16-ounce bottles per week. The planner
wishes to marimize his profë subject, of course, to all the production and marketing restrictions.
JMeerut [Link]. (Math.) 1998)
Formulate this as a linear programming problem.
 42 OPERATIONS RESEARCH

Mathematical Formulation
The data of the problem is summarized as follows :
Resource/ Production
Availability
constraint 8-ounce bottle 16-ounce bottle

Machine Atime 100/minute 40/minute 8 x 5 x 60 = 2400 minutes

Machine B time 60/minute 75/minute 8 x 5 x 60 = 2400 minutes
Production 3,00,000 ounces/week
Marketing 25,000 units/week
7,000 units/week
Profit/unit (Rs.) 0.25 0.35

Step 1. The key decision to be made is to determine the number of bottles (8-0unce and
16-ounce) to be produced per week. Let x and y be the number of 8-ounce and 16-ounce bottles
respectively, produced per week.
Step 2. Feasible alternatives are the sets of values x 0, y > 0.
Step 3. Constraints are on the availability of machine time and production.
() Machine-time constraints. An &-ounce bottle takes 1/100 minutes on machine A and 1/60
minutes on machine B, while a 16-ounce bottle takes 1/40 minutes on machine A and 1/75 minutes on
machine B. Since both the machines can run 8 hours per day for 5 days per week, the time available
on both the machines is 2,400 minutes per week individually. Thus. the two machine time constraints
are :

100 40
s2,400 (Machine A)

60
+ S2,400 (Muchine B)
(ii) Production constraints. It is given that the weekly production of the drink should not exceed
3,00,000 ounces and the market can absorb only u to 25,000 (&-ounce bottles) and 7,000 (16-ounce
bottles) per week. Therefore, the two production constraints are :
8x + 16y s 3,00,000 (Production)
xS 25,000 and ys 7,000 (Market)
Step 4. The objective is to maximize the total profit, viz., 0.25x + 0.35y.
The linear programming problem, therefore, can be put in the following mathematical format :
Maximize z = 0.25x + 0.35y
subject to the constraints :
4x + 10y s 9,60,000
15x + 12y < 21,60,000
8x + 16y s 3,00,000
xs25,000 and ys 7,000
x >0, y 0.

203. (Production Problem). An electronic company is engaged in the production of two

components C; and C, used in T.V. sets. Each unit of C, costs the company Rs. 25 in wages and
Rs. 25 in material, while each unit of C, costs the company Rs. 125 in wages and Rs. 75 in material.
The company sells both products on one-period credit terms, but the company 's labour and material
expenses must be paid in cash. The selling price of C; is Rs. 150per unit and of C, is Rs. 350 per
nit. Because of the strong monopoly of the company for these components, it is assumed that the
company can sell at the prevailing prices as many units as it produces. The company's production
 43
INEAR PROGRAMMING PROBLEM-MATHEMATICAL FORMULATION

capaciy is, however, limited by two considerations, First, t the beginning of period 1. he co
has an initial balance of Rs. 20,000 (cash plus bonk creit plus collections from past credin saes
Second, the company has available in each period 4.000 bours of machine time and 2,800 hours o
assembly tinme. The production of cach C, requires 6 hours of nachine time and 4 hours ssen
riìme, whereas the production of each Crequires 4 hows of machine time and6 hours of asemiiy
tiìne. Formulate this problenm as an Linear Programming model so as to maximize the total proju
the conpany.
Mathematical Formulation
The data of the problem is sunmarised as below :
Resourcelconstraint Components Toral availability
C; C;
Machine time (hours) 6 4 4,000 hours
Assembly time (hours) 4 2,800 hours
Budget (Rs.) 50 200 Rs. 20,000
Selling price (Rs.) 150 350
Cost (= Wages + Material) price in Rs. (25 + 25) (125 + 75)

Step 1. The key decision is to determine the number of units of C, and C, to be produced.
Step 2. Decision variables: Let x = number of units of C, and y = number of units of C.
Step 3. Feasible alternatives : x0 and y 0.
Step 4. Constraints are on the availability of time and budget as under : (Machine time)
6r + 4y s 4,000
4x + 6y s 2,800 (Assembly time)
50r + 200y s 20,000 (Budget)
two type of components.
Step 5. The objective is to maximize the total profit from the sale of relation
Assuming that whatever is produced is sold in the market, the total profit is given by the
Z= (150 - 50)x +(350 200)y or : 100x + 150y
The LPP in mathematical format, therefore, is :
Maximize = 100x + 150y
subject to the constraints :
6x + 4y s 4,000, 4r + 6y s 2,800;
50x + 200y S 20,000; and x 2 0, y 20.
for
204. (Product Allocation Problem). An Electronics Company produces three types of parts finishes
foundry and then
automatic washing machine. purchases casting of the parts from a local
the part of drilling, shaping and polishing machines.
and Rs. 14. All parts made
The selling prices of part A, B and C respectively are Rs. 8, Rs. 10 and
Rs. 6 Rs. 10.
can be sold. Castings for parts A, and Crespectively cost Rs. 5,
The shop possesses only one of each type of machine. Costs per hour
to run each of the three
30 for polishing. The capacities (parts
machines are Rs. 20 for drilling, Rs. 30 for shaping and [Link]
in the table:
per hour) for each part on each machine are shown
Capacity per hour
Machine Part B Part C
Part A
25 40 25
Drilling 20
25 20
Shuping 30 40
40
Polishing
 44 OPERATIONS RESEARCH
The management of the shop wants to know how many parts of each type it should produce Per
hour in order to maximize profit for an hour's run. Formulate this problem as an Linear
Programming model so as to maximize total profit to the company. (Delhi M.B.A. (Nov.), 2003,
Mathematical Formulation
Step I. The key decision is to produce the three tyne of parts for the automatic washing machine.
Step 2. Decision variables : Let x, x, and x, = number of type A, B and C pars to be produced
per hour, respectively.
Step 3. Feasible alternatives : x, 2 0, x, 2 0 and x, 2 0.
parts are to be processed On each of the
SIep 4. The constraints are on the time. All the three
consumes 1/25th of the availabe hour, a
unee machines. On the drilling-machine, one type A part dr1lling-machine
consumes 1/25th of an hour. Thus the
Ype b part consumes 1/40th, and type C part
constraint is
+ 2sI, i.e., 0.04x, + 0.025x, + 0.04x, S 1
25 40 25
Similarly, the other two constraints are:
1
S l, i.e., 0.04x + 0.05x, + 0.05x, S 1 (Shaping-machine)
25 1 02 +
(Polishing-machine)
and
1
30 2 +
40 sl, i.e., 0.025x + 0.033x, + 0.025x, s1
40
casting but for the cost of drilling, shaping.
Step 5. Profit must allow not only for the cost of the
run on the drilling machine at a cost of Rs. 20.
and polishing. Since, 25 type A parts per hour can be
Similar reasoning for shaping and
then Rs. 20 x = Re. 0.80 is the drilling cost per type Apart.
polishing gives 30 30
20 = 3 - 2.75 = 0.25
Profit per type A part = (8 - 5) - 25*
25
+
40
20 30 = 4 - 3.00 = 1.00
Profit for type B part = (10 - 6) 40 20
+

20 30 30 =4 - 3.05 = 0.95
+ +
Profit for type Cpart = (14 - 10) -|6 20 40

The objective is to maximize the total profit from sales, viz., 0.25x; + x, + 0.95x3.
The linear programming problem, therefore, can be put in the following mathematical format :
Maximize z = 0.25x + x, t 0.95x3
subject to the constraints :
0.04x + 0.025x, + 0.04x, S 1,
0.04r + 0.05x, + 0.05xg S I,
0.025x + 0.0331, + 0.025x; S 1,
and x 0, x2 0, xg 0.

205. (Blending Problem). The manager of an oil refinery must decide on the optimum mix of
twopossible blending processes of which the input and output production runs are as follows
Process Input Output
Crude A Crude B Gasoline X Gasoline Y
6 4 6
2 6
INEAR PROGRAMMING PROBLEM-MATHEMATICAL FORMULATION 45

The maximum amounts available of crudes A and B are 250 wnits and 200 units respecively.
Market demand shows that at least 150 nits of gasoline X and 130 units of gasoline Ymust be
produced. The profits per production run from process 1 and process 2 are Ks. 4 and KS.
respectively. Formulate the problem for maximising the profit.
Mathematical Formulation
Step 1. The key decision is to determine the number of units of gasoline produced from process 1 and
process 2.
Step 2. Decision variables: Let x,, x, = number of units of gasoline produced from process 1and
2respectively.
Step 3. Feasible alternatives: x, 20 and x, 2 0.
Step 4. The constraints are on the availability of crude oil and demand of crude oil, viz.
6x + 5x, S 250 (Availability of crude A)
4x + 6x, S 200 (Availability of crude B)
6x + 5x, 2 150 (Demand of gasoline X)
and 9x + 5x 2 130 (Demand of gasoline )
Step 5. The objective is to maximize the total profit from the production of gasoline, vic.,
4x, + 5r:
The required linear programming problem, therefore, is
Maximize z = 4x + 5r
subject to the constraints :
6x + 5x, S 250, 4x + 6x, S 200,
6x + 5x 2 150, 9x + 5x 130,
X 20 and x, 0.
206. (Production Problem), A complete unit of a certain product consists of four units of
manufactured from
component A and three units of component B. The two components (A and B) are
available. Three
two different raw materials of which 100 units and 200 units, respectively, are
departments are engaged in the production process with each department using a different method for
manufacturing the components per production run and the recoulting units of each
component are
given below :
Input per run (units) Output per run (units)
Department Raw material Raw material Component Component
B
4
7
4 8 8
2 7 7 3
3
of
Formulate this problem as a linear programming model so as to determine the number the
production runs for each department which will maximize the total number of complete
units of
final product.
Mathematical Formulation
Decision variables : Let x = number of production runs for department 1,
x, = number of production runs for department 2, and
=number of production runs for department 3.
46 OPERATIONS RESEARCH
Objective function:
Since each unit of the final product requires 4 units of component A and 3 units of component B
therefore, maximum number of units of the final product cannot exceed the smaller value of
Total number of units A produced Total number of units B produced
4 3

i.e., Minimum of
+ 5t + 7x3 4x t+ 8r, + 3r,
4 3

Constraints : (i) If y is the number of component unitsof final product, then obviously, we have
4x + &r, + 3x?
2y and
4 3
(ii) Constraints on raw material are :
7x + 4x) + 2r3 S 100 (Raw material I
and Sx + 8r + 7x, S 200 (Raw material I
The LPP, therefore, is expressed as follows:
Maximize = Minimum of 6x + 5', + 7r3 4x1 + 8, + 3x3
4
subject to the constraints :
6x + 5x + 7x3 - 4y 2 0 (Nunber of components
4x + 8x + 3x3 - 3y > 0 of final product)
7x + 4r, + 2r; S 100 (Raw material D)
Sx + 8x, + 7x3 S 200 (Raw material II)
X 2 0. x, 0 and x 2 0. (Non-negative restrictions)
207. (Advertisement Problem). The owner of Metro Sports wishes to determine how many
advertisements to place in the selected three monthly magazines A, B and C. His objective is to
advertise in such a way that total exposure to principal buyers of expensive sports good is maximized.
Percentages of readers for each magazine are known. Exposure in any particular magaine is the
number of advertisements placed multiplied by the number of principal buyers. The following data
may be used :
Mugazine
A B C
Readers Ilakh 0.6 laklh 0.4 laklh
Principal Buyers 20% 15% 8%
Cost per Advertisement (Rs. ) 8000 6000 5000

The budgeted amount is at most Rs. Ilakh for the advertisenents. The owner has already decided
that magazine A should have no nore than 15 advertisements and that B and C euch have at least 80
advertisements. Formulate on LP model for the problem.
Mathematical Formulation
Decision variables : Let x = number of insertions in magazine A,
x, = number of insertions in magazine B, and
x, = number of insertions in magazine C.
Objective function :
Maximize (total exposure)
¿=(20% of 1,00,000) x + (15% of 60,000) x, + (8% of 40,000) x3
=20,000 x + 9,000 x + 3,200 .x3
 PROGRAMMING 47
LINEAR PROBLEM-MATHEMATICAL FORMULATION
Constraints : 8,000 x + 6,000 x, + 5,000xS I.00,000 (Bndgeting)
IS 15, N) 2 8, X 2 8 (Advertisement)
Also, (Non-negative restrictions)
A 20, xy 2 0 and x 2 0.
208. (Agriculturist Problem). An agricuturist has a farm with 125 acres. He produces KadisM.
Muttar and Potato. Whatever he raises is fully soldin the market. He gets Rs. 5for Radish per kg..
Rs. 4for Muttar per kg. and Rs. 5 for Potato per kg. The average yield is 1,500 kg. of Radish per
acre. I,800 kg. of Muttar per acre and 1,200 kg. of Potato per acre. To produce each l00 kg
Radish and Muttar and to produce each 80 kg. of Potato, a sum of Rs. 12.50 has to be used jor
manure. Labour required for each acre to raise the crop is 6 man-days for Radish and Potato each
ond 5 man-days for Muttar. Atotal of S00 man-days of labour at a rate of Rs. 40 per man -day are
available.
Formulate this as a Linear Programming model to maximize the Agriculturist's total profit.
(Delhi M.B.A. (PT) 2002]
Mathematical Formulation
Decision variables : Let x = acreage for Raddish in kg.,
y = acreage for Muttar in kg., and
3 = acreage for Potato in kg.
Objective function : We are given the following information :
Radish Muttar Potato

1,500 1,800 1.200

Output (in kg.)
12.50 12.50 12.50
= 0.125 = 0.125 = 0.156
Cost of manure (in Rs. per kg.) 100 100 80
5 x 40 = 200 6 x 40 = 240
Labour cost (in Rs.) 6x 40 = 240
Rs. 5 Rs. 4 Rs. 5
Selling price (per kg.) 0.156 x 1.200 + 240
Total cost 0.125 x 1,500 + 240 0.125 x 1,800 + 200
= 427,50 = 425.00 = 427.20
4 x 1.800 = 7.200 5 X 1,200 = 6.000
Total Revenue 5 x 1,500 = 7,500
Since, total profit = revenue - cost; the objective function is to maximize
2 = (7,500 427.5) x + (7,200 425) , + (6,000 427.2) x;
= 7.072.5x, + 6,775x, + 5,572.&r,.
Constraints : Constraints on the availability of land and man-days are :
(Land)
6x + 5x) + 6x; S S00 (Man-days)
x 2 0, 20 and x 2 0 (Non-negative restrictions)
Also,
land and has
209, (Crop and Livestock Problem). Acooperative farm owns 100 acres of
3,500 man
Rs. 25,000 in funds available for investment. The farm members can produce a total ofJune-August.
hours wornh of labour during the months September-May and 4,000 man-hours during
ihe farm will use them to work on a
If any of these man-hours are not needed, sOme menbers of
neighbouring fam for Rs. 2/hour during September-May and Rs. 3/hour during June-August. Cash
income can be obtained from the three main crops and wo types of livestock: dairy cOWs and laying
hens. No investment funds are needed for the crops. However, each cow will reguire an investment
outlay of Rs. 3,200 and each hen will require Rs. 15.
Moreover, each cow will require 1.5 acres of land, 100 man-hours of
work during
September-May and another 50 man-hours during the summer. Eàch cow will produce a net annual
cash income of Rs. 3,500 for the farnn. The corresponding figures for each hen are : no acreage,
 48
OPERATIONS AESEARCH

0.6 man-hours during September-May, 0.4 man-hours during June-August, and an annual ner Cot
income of Rs. 200. The chicken house can accommodate a maximum of 4.000 hens and the sie of
cattle-shed limits the numbers to a maximum of 32 cows.
Estimated man-hours and income per acre planned in each of the three crops are :
Paddy Bajra Jowar
Man-hours:
September-May 40 20 25
June-August S0 35 40
Net annual cash income (Rs.) 1,200 800 850

The cooperative farm wishes to determine how much acreage should be planted of each of the
crops and how many cows and hens should be kept to maximise its net cash income.
Formulate this problem as LPP to maximize net annual cash income.
Mathematical Formulation
The data of the problem is summarised below :
Extra hours Total
Constraints Cows Hens Crop
Paddy Bajra Jowar Sept.-May June-Aug. availabiliy
Man-hours:
Sept.-May 100 0.6 40 20 25 3,500
June-Aug. 50 0.4 50 35 40 4,000
Land 1.5 1 100
Cow 32
Hens 1 4,000
Net annual cash 3,500 200 1.200 800 850 2 3
income (Rs.)

Decision variables : Let x, and x, = number of cowS and hens respectively;

3, Iy and x, = acreage planting of paddy, bajra and jowar respectively.
, and x, = extra man-hours utilized during Sept.-May and May-June respectively.
Objective function : Maximization of net annual cash, viz.,
z=3,500x, + 200x, + 1,200x, + 800x4 + 850x; + 2x% + 3x7
Constraints:
(i) 100x + 0.6x, + 40x; + 20x4 + 25rç + = 3,500
(Mun-hours)
50x + 0,4x2 + 5013 + 35x4 + 4015 + xy = 4.000
(i) (Land availability)
1.5* + X3 t x4 t xs S 100
(iii) (Livestock constraints)
X S 32 and x, s 4,000
x 2 0, x, >0, x3 2 0, x4 0. x5 20, A% 0 and x 0 (Non-negative restrictions)
210. (Trim Loss Problem). Rolls of paper having a fixed length and width of l80 cm are being
manufaciured by a paper mill. These rolls have to be cut to satisfy the following demand:
Width : 80 cim 45 Cm 27 cm
No. of rolls : 200 120 130
Obtain he linear programming formulation of the problem to determine the cutting patter1n, so
that the demand is satisfied and wastage of paper is aminimum.
Mathematical Formulation
Here, the key decision is to determine how the paper rolls be cut to the required width so that trim
loss (wastage) is a minimum.
 INEAR PROGRAMMING PROBLEM-MATHEMATICAL FORMULATION 49

Various alternatives for the number of rolls are given below :

Feasible patterns No. of rolls Rolls obtained from each roll of width
of cuting
Wastage
Cut per roll 27 cm
80 cm 45 cm
80 + 80 2
20
80 + 45 + 45 1 2
10
80 + 45 + 27 + 27 1 2
80 + 27 + 27 + 27 19 1 3
45 + 45 + 45 + 45 0 4
45 + 45 + 45 + 27 18 3 1

45 + 45 + 27 + 27 + 27 2 3
45 + 27 + 27 + 27 + 27 + 27 0 5
27 + 27 + 27 + 27 + 27 + 27 18 6

Decision variables : Let X, ( = 1. 2.... 9) represent the number of times each cutting
alternative is to be used.
Objective function : The objective is to minimize the wastage produced, i.e.,
Minimize z = 20x + 10x, + 3 + 19x, + 18x6 + 9x, + 18i
Constrainus : Constraints on the availability of rolls and the requirement of desired width of rolls are :
2x + x t Xy t X4 = 200 (80 cm rolls)
2r + X3 + 4xs + 3x; + 2x t xg = 120 (45 cm rolls)
2x3 + 3x t x6 + 3x, + 5xg + 6x = 130 (27 cm rolls)
x; > 0; j = 1, 2, 3, ... 9. (Non-negativity)
211. (Marketing Problem). The PQR Stone Company sells stone secured from any of the three
adjacent quarries. The stone sold by the company must conform to the following specifications :
Material X equal to 30 per cent; Material Y equal to or less than 40 per cent ; Material Z
between 30 per cent and 40 per cent.
Stone from quarry A costs Rs. 100 per tonne and has the following properties :
Material X:20 per cent, material Y: 60 per cent, and material Z: 20 per cent.
Stone from quarry B costs Rs. 120 per tonne and has the following properties :
Material X: 40 per cent, material Y: 30 per cent, and material Z: 30 per cent.
Stone from quarry Ccosts Rs. I50 per tonne and has the following properties:
Material X: 10per cent, material Y: 40per cent, and material Z: 50 per cent.
Formulate the above as an LPP to minimise cost per tonne.
Mathematical Formulation
The data of the problem is summarised below:
Quarry Specification
Material
A C

X 20% 40% 10% 30%

60% 30% 40% less than or equal to 40%
20% 30% 50% between 30% and 40%

Cost per tonne (Rs.) 100 120 150

Decision variables : Let x, , x represent the proportion of stone in tonne to be produced from
quarries A, B and C respectively.
 0PERATIONS RESEAROM
Dhective henction: The objective is to minimize the total cost, i.e..
Minimize z = 10Or, + 120r, + I50r
Constrgints : The constraints are on the three types of material of the stone. These are:
20x, + 40x, + 10r 30
60x, + 30x, + 40 s 40
(Material X
(Material n
20x + 30x, + 5Or s 40
20x + 30, + 50r, 30 (Material Z
Also,
(Non-negative restrictiony
212. (Blending Problem). Three grades of coal A, B and C contain ash and phosphorlue.
impurities. In a particular industrial process a fuel obtained by blending the above grades containie
not more than 25% ash and 0.03% phosphorus is required. The naximum demand of
the
tons. Percentage impurities and costs of the various grades of coal are shown below. fuel is l00
there is an unlimited supply of each grade of coal and there is no loss in Assuming thes
blending, formulate the
blending problem to minimise the cost.
Coal grade % ash %phosphorus Cost per ton (in Rs.)
30 0.02 240
B 20 0.04 300
C 35 0.03 280
Mathematical Formulation
Decision variables : Let x =tons of grade A coal,
Iy = tons of grade Bcoal, and X = tons of grade Ccoal.
Objective function : Minimize z= 240x + 300x + 280r3
Constraints : 0.3x + 0.2 x, + 0.35x, S 0.25 (x + x t xa)
or
(ash)
0.02 0.04 0.03 0.03
100 100 100 100
-X t xy S0 (phosphorus)
(demand of fuel)
x 2 0, X) 20 and x > 0. (Non-negative restrictions)
213. (Capital Budgeting Problem). An engineering company is planning to diversify its
operations during the year 2006-07. The company has allocated capital expenditure budget equal to
Rs. 5.15 crore in the year 2006 and Rs. 6.50crore in the year 2007. The company has five investment
projects under consideration. The estimated net returns at present value and expected cash
expenditures of each project in the two years are as follows :
Project
Estimated net returns Cash èxpenditure (in '000Rs.)
(in '000Rs.) Year 2006 Year 2007
A 240 120 320
B 390 S50 594
C 80 118 202
D 150 250 340
E 182 324 474

Assume that the returns from a particular project would be in direct proportion to the investme
in it, so that, for example, if in a project, say A, 20% (of 120 in 2006 and of 320 in 2007) is invese
then the resulting net returns in it would be 20% (of 240). This assumption also implies
LINEAR PROGRAMMING PROBLEM--MATHEMATICAL FORMULATION 51

individualiy of the project should be ignored. Formulate this capital budgeting problem as a Linear
Programining model to muxinie the net returns.
Mathematical Formulation
Decision Irariables : Let x;, Ny, 3, d4 and x, represent the proportion of investment in project A, 3, C,
Dand E respectively.
Objective fncton : Ihe objective is to maximize the net returns, Thus, the objective function is :
Maximize = 24Ox + 3901, + 80x3 + I50x4 + l82xs
Constraints : Capital expenditure budget constraints are :
120x + S50x, + 118r, + 250x4 + 324xs S 515 (for 2006)
320x + 594r, + 202va + 340x4 + 474x, S 650 for 2007)
Also, X 20, 20, X 20, .420 and xs 20. (Non-negative restrictions)
In addition to the above, there is a requirement of 0-1 (i.e., of integrality). So,
N; = 1 or 0 G= 1, 2, 3, 4, 5).
214. (Media Problem). The Marketing Department of Everest Company has collected
information on the problem of advertising for its products. This relates to the advertising media
vailable, the number of families expected to be reached with each alternative, cost per advertisement,
the maximun availability of each medium and the expected exposure of each one (Measured as the
relative value of one advertisement in each of the media).
The information is given as under :
Advertising media
No. of fumilies Cost/ad. Maximum availability Expected exposure
lo cover (Rs.) (No. of times) (Units)
TV (30 sec.) 3,000 8,000 8 80
Radio (15 sec.) 7,000 3,000 30 20

Sunday Edition (1/4 page) 5,000 4,000 4 50

Magazine (lpage) 2,000 3,000 60

Other information and requirements :

(a) The advertising budget is Rs. 70,000. (b) At least 40,000 families should be covered.
(c) At least 2 insertions be given in Sunday Edition of Daily but not more than 4 advertisements
should be given on the TV.
Formulate this as a linear programming problem. The conpany 's objective is to maximize the
expected exposure.
Mathematical Formulation
The key decision to be made is to determine the number of advertisements to be brought in
Television, Radio, Sunday Edition and Magazine.
Decision variables. Let x,, X9, X and x, represent the number of advertisements in TV, Radio.
Sunday Edition and Magazine respectively.
Using the given information, the appropriate linear programming problem is:
Maximize (total expected exposure) z= 80x1 + 20x, + 50x3 + 60x3
subject to the constraints :
3,000x + 7,000, + 5,000x, + 2,000x4 2 40,000 (Families)
8,000x + 3,000x + 4,000x; + 3,000:4 2 70,000 (Budget)
x s8, x S30, x3s4, x4 S 2 (Availability)
X3 2 2 and x s 4 (No. of advt.)
Also, 20, x, 2 0, X3 20 and x4 0. (Non-negative restrictions)