Chapte r

2
Linear Programming:
Applications and Model
Formulation
“Whenever there is a hard job to be done I assign it to a lazy man; he is sure to find an
easy way of doing it.”
– Walter Chrysler

PREVIEW
Linear programming (LP) is a widely used mathematical modelling technique developed to help decision
makers in planning and decision-making regarding optimal use of scarce resources. This chapter is
devoted to illustrate the applications of LP programming in different functional areas of management and
how LP models are formulated.

LEARNING OBJECTIVES

After reading this chapter you should be able to

⌘ identify situations in which linear programming technique can be applied.
⌘ understand fundamental concepts and general mathematical structure of a linear programming model.
⌘ expressobjective function and resource constraints in LP model in terms of decision variables and
parameters.
⌘ appreciate the limitations and assumptions of linear programming technique with a view to interpret the
solution.

CHAPTER OUTLINE
Formulation
2.1 Introduction 2.8 Examples of LP Model Formulation •
2.2 Structure of Linear Programming Model 2.3 Conceptual Questions
Advantages of Using Linear Programming 2.4 • Self Practice Problems
Limitations of Linear Programming 2.5 • Hints and Answers
Application Areas of Linear Programming 2.6 ⑨ Chapter Summary
General Mathematical Model of Linear ⑨ Chapter Concepts Quiz
Programming Problem ⑨ Case Study
2.7 Guidelines on Linear Programming Model
26 Operations Research: Theory and Applications

2.1 INTRODUCTION
The application of specific operations research techniques to determine the choice among several courses of
action, so as to get an optimal value of the measures of effectiveness (objective or goal), requires to
 formulate (or construct) a mathematical model. Such a model helps to represent the essence of a system that
is required for decision-analysis. The term formulation refers to the process of converting the verbal
description and numerical data into mathematical expressions, which represents the relationship among
relevant decision variables (or factors), objective and restrictions (constraints) on the use of scarce
resources (such as labour, material, machine, time, warehouse space, capital, energy, etc.) to several
competing activities (such as products, services, jobs, new equipment, projects, etc.) on the basis of a given
criterion of optimality. The term scarce resources refers to resources that are not available in infinite
quantity during the planning
choosing a particular course of action (or strategy) among the
Linear
Programming is a mathematical
given courses of action (or strategies) in order to achieve the
technique useful for allocation of ‘scarce’ or ‘limited’ desired objective.
resources, to The usefulness of this technique is enhanced by the availability
several competing activities on the basis of a given criterion of
optimality.
of several user-friendly computer software such as STORM,
TORA, QSB+, LINDO, etc. However, there is no computer
software for building an LP model. Model building is an art that
improves with practice. A variety of examples are given in this
chapter to illustrate the formulation of an LP model.

2.2 STRUCTURE OF LINEAR PROGRAMMING

MODEL

2.2.1 General Structure of an LP Model

The general structure of an LP model consists of following three
basic components (or parts).
Decision variables (activities) The evaluation of various
courses of action (alternatives) and select the best to arrive at the
optimal value of objective function, is guided by the nature of
objective function and availability of resources. For this, certain
activities (also called decision variables) usually denoted by x1,
x2, . . ., xn are conducted. The value of these variables (activities)
represents the extent to which each of these is performed. For
example, in a product-mix manufacturing problem, an LP model
Four components of any LP model are: (i) decision
variables, (ii) may be used to determine units of each of the products to be
objective function, (iii) constraints, and (iv) non-negativity manufactured by using limited resources such as personnel,
period. The criterion of optimality is generally either machinery, money, material, etc.
performance, return on investment, profit, cost, utility, time, The value of certain variables may or may not be under the
distance and the like. decision-maker’s control. If values are under the control of the
In 1947, during World War II, George B Dantzing while working decision-maker, then such variables are said to be controllable,
with the US Air Force, developed LP model, primarily for otherwise they are said to be uncontrollable. These decision
solving military logistics problems. But now, it is extensively variables, usually interrelated in terms of consumption of
being used in all functional areas of management, airlines, resources, require simultaneous solutions. In an LP model all
agriculture, military operations, education, energy planning, decision variables are continuous, controllable and non negative.
pollution control, transportation planning and scheduling, That is, x1 ≥ 0, x2 ≥ 0, . . ., xn ≥ 0.
research and development, health care systems, etc. Though
these applications are diverse, all LP models have certain The objective function The objective function of each LP
common properties and assumptions – that are essential for problem is expressed in terms of decision variables to optimize
decision-makers to understand before their use. the criterion of optimality (also called measure-of-performance)
such as profit, cost, revenue, distance etc. In its general form, it
Before discussing the basic concepts and applications of linear
is represented as:
programming, it is important to understand the meaning of the
words – linear and programming. The word linear refers to Optimize (Maximize or Minimize) Z = c1x1 + c2 x2 + . . . + cn xn,
linear relationship among variables in a model. That is, a given where Z is the measure-of-performance variable, which is a
change in one variable causes a proportional change in another function of x , x , . . ., x . Quantities c , c , . . ., c are parameters
1 2 n 1 2 n
variable. For example, doubling the investment on a certain
that represent the contribution of a unit of the respective variable
project will also double the rate of return. The word
programming refers to the mathematical modelling and solving x1, x2, . . ., xn to the
of a problem that involves the use of limited resources, by
 Linear Programming: Applications and Model Formulation 27

measure-of-performance Z. The optimal value of the given objective function is obtained by the graphical
method or simplex method.
The constraints There are always certain limitations (or constraints) on the use of resources, such as:
labour, machine, raw material, space, money, etc., that limit the degree to which an objective can be
achieved. Such constraints must be expressed as linear equalities or inequalities in terms of decision
variables. The solution of an LP model must satisfy these constraints.

2.2.2 Assumptions of an LP Model

In all mathematical models, assumptions are made for reducing the complex real-world problems into a
simplified form that can be more readily analyzed. The
following are the major assumptions of an LP model: Following are certain advantages of using linear programming
technique:
1. Certainty: In LP models, it is assumed that all its parameters
1. Linear programming technique helps decision-makers to use
such as: availability of resources, profit (or cost) contribution per
unit of decision variable and consumption of resources per unit their productive resources effectively. 2. Linear programming
of decision variable must be known and constant. technique improves the quality of decisions. The
decision-making approach of the user of this technique becomes
2. Additivity: The value of the objective function and the total more objective and less subjective.
amount of each resource used (or supplied), must be equal to the 3. Linear programming technique helps to arrive at optimal
sum of the respective individual contribution (profit or cost) of solution of a decision problem by taking into account constraints
the decision variables. For example, the total profit earned from on the use of resources. For example, saying that so many units
the sale of two products A and B must be equal to the sum of the of any product may be produced does not mean that all units can
profits earned separately from A and B. Similarly, the amount of be sold.
a resource consumed for producing A and B must be equal to the
4. Linear programming approach for solving decision problem
total sum of resources used for A and B individually.
highlight bottlenecks in the production processes. For example,
3. Linearity (or proportionality): The amount of each when a bottleneck occurs, machine cannot produce sufficient
resource used (or supplied) and its contribution to the profit (or number of units of a product to meet demand. Also, machines
cost) in objective function must be proportional to the value of may remain idle.
each decision variable. For example, if production of one unit of
a product uses 5 hours of a particular resource, then making 3 2.4 LIMITATIONS OF LINEAR PROGRAMMING
units of that product uses 3×5 = 15 hours of that resource.
In spite of having many advantages and wide areas of
4. Divisibility (or continuity): The solution values of
applications, there are some limitations associated with this
decision variables are allowed to assume continuous values. For
technique. These are as follows:
instance, it is possible to collect 6.254 thousand litres of milk by
a milk dairy and such variables are divisible. But, it is not 1. Linear programming assumes linear relationships among
desirable to produce 2.5 machines and such variables are not decision variables. However, in real-life problems, decision
divisible and therefore must be assigned integer values. Hence, if variables, neither in the objective function nor in the constraints
any of the variable can assume only integer values or are limited are linearly related.
to discrete number of values, LP model is no longer applicable.
Assumptions of an LP model are:
(i) certainty,
2.3 ADVANTAGES OF USING LINEAR (ii) additivity,
(iii) proportionality, & (iv) divisibility
PROGRAMMING
28 Operations Research: Theory and Applications

2. While solving an LP model there is no guarantee that decision variables will get integer value. For
example, how many men/machines would be required to perform a particular job, a non-integer valued
solution will be meaningless. Rounding off the solution to the nearest integer will not yield an optimal
solution.
3. The linear programming model does not take into consideration the effect of time and uncertainty. 4.
Parameters in the model are assumed to be constant but in real-life situations, they are frequently neither
known nor constant.
5. Linear programming deals with only single objective, whereas in real-life situations a decision problem
may have conflicting and multiple objectives.
 2.5 APPLICATION AREAS OF LINEAR PROGRAMMING

Linear programming is the most widely used technique of decision-making in business and industry and in
various other fields. In this section, broad application areas of linear programming are discussed:

Applications in Agriculture
These applications fall into categories of farm economics and farm management. The former deals with
inter regional competition, optimum allocation of crop production, efficient production patterns under
regional land resources and national demand constraints, while the latter is concerned with the problems of
the individual farm such as allocation of limited resources such as acreage, labour, water supply, working
capital, etc., so as to maximize the net revenue.

Applications in Military
Military applications include (i) selection of an air weapon system against the enemy, (ii) ensuring
minimum use of aviation gasoline (iii) updating supply-chain to maximize the total tonnage of bombs
dropped on a set of targets and takes care of the problem of community defence against disaster at the
lowest possible cost.
Production Management
Product Mix To determine the quantity of several different products to be produced, knowing their per
unit profit (cost) contribution and amount of limited production resources used. The objective is to
maximize the total profit subject to all constraints.
• Production Planning This deals with the determination of minimum cost production plan over the
planning period, of an item with a fluctuating demand, while considering the initial number of units in
inventory, production capacity, constraints on production, manpower and all relevant cost factors. The
objective is to minimize total operation costs.
• Assembly-line Balancing This problem is likely to arise when an item can be made by assembling
different components. The process of assembling requires some specified sequence(s). The objective is
to minimize the total elapse time.
• Blending Problems These problems arise when a product can be made from a variety of available raw
materials, each of which has a particular composition and price. The objective here is to determine the
minimum cost blend, subject to availability of the raw materials, and to minimum and maximum
constraints on certain product constituents.
• Trim Loss When an item is made to a standard size (e.g. glass, paper sheet), the problem of determining
which combination of requirements should be produced from standard materials in order to minimize
the trim loss, arises.
Financial Management
• Portfolio Selection This deals with the selection of specific investment activity among several other
activities. The objective here is to find the allocation which maximizes the total expected return or
minimizes risk under certain limitations.
• Profit Planning This deals with the maximization of the profit margin from investment in plant facilities
and equipment, cash in hand and inventory.
Linear Programming: Applications and Model Formulation 29

Marketing Management
• Media Selection The linear programming technique helps in determining the advertising media mix so as
to maximize the effective exposure, subject to limitation of budget, specified exposure rates to
different market segments, specified minimum and maximum number of advertisements in various
media.
• Travelling Salesman Problem The salesman’s problem is to find the shortest route from a given city to
each of the specified cities and then returning to the original point of departure, provided no city would
be visited twice during the tour. Such type of problems can be solved with the help of the modified
assignment technique.
• Physical Distribution Linear programming determines the most economic and efficient manner of locating
 manufacturing plants and distribution centres for physical distribution.
Personnel Management
• Staffing Problem Linear programming is used to allocate optimum manpower to a particular job so as to
minimize the total overtime cost or total manpower.
• Determination of Equitable Salaries Linear programming technique has been used in determining
equitable salaries and sales incentives.
• Job Evaluation and Selection Selection of suitable person for a specified job and evaluation of job in
organizations has been done with the help of the linear programming technique.
Other applications of linear programming lie in the area of administration, education, fleet utilization,
awarding contracts, hospital administration, capital budgeting, etc.

2.6 GENERAL MATHEMATICAL MODEL OF

LINEAR PROGRAMMING PROBLEM
The general linear programming problem (or model) with n decision variables and m constraints can be
stated in the following form:
Optimize (Max. or Min.) Z = c1x1 + c2x2 + . . . + cn xn
subject to the linear constraints,
ax ax ax b 11 1 12 2 1 1 n n + + + ≤=≥ ... ( , , )
ax ax a x b 21 1 22 2 2 2 n n + + + ≤=≥ ... ( , , )
## # #
ax ax ax b m m mn n m 11 2 2 + + + ≤=≥ ... ( , , )
and xx x 1 2 n , ,..., ≥ 0
The above formulation can also be expressed in a compact form as follows.
n
Optimize (Max. or Min.) Z cx
jj= ℜ= 1(Objective function) (1)
j
subject to the linear constraints
n
( , , ) ; , ,..., 1 2 (Constraints) (2)
ℜ ≤=≥ =
j=

ij j i ax bim1
and xj n j ≥ = 0 12 ; , , ..., (Non-negativity conditions) (3) where, the cj s are coefficients representing
the per unit profit (or cost) of decision variable xj to the value of objective function. The aij’s are referred as
technological coefficients (or input-output coefficients). These represent the amount of resource, say i
consumed per unit of variable (activity) xj. These coefficients can be positive, negative or zero. The bi
represents the total availability of the ith resource. The term resource is used in a very general sense to
include any numerical value associated with the right-hand side of a constraint. It is assumed that bi ≥ 0 for
all i. However, if any bi < 0, then both sides of constraint i is multiplied by –1 to make bi > 0 and reverse the
inequality of the constraint.
In the general LP problem, the expression (≤, =, ≥) means that in any specific problem each constraint
may take only one of the three possible forms:
(i) less than or equal to (≤)
(ii) equal to (=)
(iii) greater than or equal to (≥)
30 Operations Research: Theory and Applications

2.7 GUIDELINES ON LINEAR PROGRAMMING MODEL FORMULATION

The effective use and application requires, as a first step, the mathematical formulation of an LP model.
Steps of LP model formulation are summarized as follows:
Step 1: Identify the decision variables
 (at
(a) Express each constraint in words. For this you should first see whether the constraint is of the form ≥
least as large as), of the form
≤ (no larger than) or of the form = (exactly equal to).
LP model expression in terms of decision variables along with profit (cost)
formulation requires: (i) identification of decision variables and input data, contributions associated with them.
(ii) formulation of constraints, and (iii) objective After gaining enough experience in model building, readers may
function skip verbal description. The following are certain examples of
(b) Express verbally the objective function. LP model formulation that may be used to strengthen the ability
(c) Verbally identify the decision variables with the help of Step to translate a real life problem into a mathematical model.
(a) and (b). For this you need to ask yourself the question – What
decisions must be made in order to optimize the objective 2.8 EXAMPLES OF LP MODEL FORMULATION
function? Having followed Step 1(a) to (c) decide the symbolic
notation for the decision variables and specify In this section a number of illustrations have been presented on
their units of measurement. Such specification of units of LP model formulation with the hope that readers may gain
measurement would help in interpreting the final solution of the enough experience in model building.
LP problem.
2.8.1 Examples on production
Step 2: Identify the problem data
Example 2.1 A manufacturing company is engaged in producing
To formulate an LP model, identify the problem data in terms of
three types of products: A, B and C. The production department
constants, and parameters associated with decision variables. It
produces, each day, components sufficient to make 50 units of A,
may be noted that the decision-maker can control values of the
25 units of B and 30 units of C. The management is confronted
variables but cannot control values in the data set.
with the problem of optimizing the daily production of the
Step 3: Formulate the constraints products in the assembly department, where only 100 man-hours
Convert the verbal expression of the constraints in terms of are available daily for assembling the products. The following
resource requirement and availability of each resource. Then additional information is available:
express each of them as linear equality or inequality, in terms of
Type Profit Contribution per Assembly Time
the decision variables defined in Step 1.
of Product Unit of Product (Rs) per Product (hrs)
Values of these decision variables in the optimal LP problem
solution must satisfy these constraints in order to constitute an A 12 0.8
acceptable (feasible) solution. Wrong formulation can either lead B 20 1.7
to a solution that is not feasible or to the exclusion of a solution C 45 2.5
that is actually feasible and possibly optimal.
The company has a daily order commitment for 20 units of
Step 4: Formulate the objective function products A and a total of 15 units of products B and C.
Identify whether the objective function is to be maximized or Formulate this problem as an LP model so as to maximize the
minimized. Then express it in the form of linear mathematical total profit.
Linear Programming: Applications and Model Formulation 31

LP model formulation The data of the problem is summarized as follows:

Resources/Constraints Product Type Total

ABC
Production capacity (units) 50 25 30
Man-hours per unit 0.8 1.7 2.5 100
Order commitment (units) 20 15 (both for B and C)
Profit contribution (Rs/unit) 12 20 45

Decision variables Let x1, x2 and x3 = number of units of products A, B and C to be produced, respectively.
The LP model

Maximize (total profit) Z = 12x1 + 20x2 + 45x3

subject to the constraints
(i) Labour and materials
(a) 0.8x1 + 1.7x2 + 2.5x3 ≤ 100, (b) x 1 ≤ 50, (c) x2 ≤ 25, (d) x3 ≤ 30
(ii) Order commitment
 (a) x1 ≥ 20; (b) x2 + x3 ≥ 15
and x1, x2, x3 ≥ 0.
Example 2.2 A company has two plants, each of which produces and supplies two products: A and B. The
plants can each work up to 16 hours a day. In plant 1, it takes three hours to prepare and pack 1,000 gallons
of A and one hour to prepare and pack one quintal of B. In plant 2, it takes two hours to prepare and pack
1,000 gallons of A and 1.5 hours to prepare and pack a quintal of B. In plant 1, it costs Rs 15,000 to prepare
and pack 1,000 gallons of A and Rs 28,000 to prepare and pack a quintal of B, whereas in plant 2 these
costs are Rs 18,000 and Rs 26,000, respectively. The company is obliged to produce daily at least 10
thousand gallons of A and 8 quintals of B.
Formulate this problem as an LP model to find out as to how the company should organize its
production so that the required amounts of the two products be obtained at the minimum cost.
LP model formulation The data of the problem is summarized as follows:

Resources/Constraints Product Total

A B Availability (hrs)
Preparation time (hrs) Plant 1: 3 hrs/thousand gallons 1 hr/quintal 16
Plant 2: 2 hrs/thousand gallons 1.5 hr/quintal 16
Minimum daily production 10 thousand gallons 8 quintals
Cost of production (Rs) Plant 1: 15,000/thousand gallons 28,000/quintals
Plant 2: 18,000/thousand gallons 26,000/quintals

Decision variables Let

x1, x2 = quantity of product A (in ’000 gallons) to be produced in plant 1 and 2, respectively. x3,
x4 = quantity of product B (in quintals) to be produced in plant 1 and 2, respectively.

The LP model
Minimize (total cost) Z = 15,000x1 + 18,000x2 + 28,000x3 + 26,000x4
subject to the constraints
(i) Preparation time
(a) 3x1 + 2x2 ≤ 16, (b) x3 + 1.5x4 ≤ 16
(ii) Minimum daily production requirement
(a) x1 + x2 ≥ 10, (b) x3 + x4 ≥ 8
and x1, x2, x3, x4 ≥ 0.
32 Operations Research: Theory and Applications

Example 2.3 An electronic company is engaged in the production of two components C1 and C2 that are
used in radio sets. Each unit of C1 costs the company Rs 5 in wages and Rs 5 in material, while each of C2
costs the company Rs 25 in wages and Rs 15 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 C1
is Rs 30 per unit and of C2 it is Rs 70 per unit. Because of the company’s strong monopoly in these
components, it is assumed that the company can sell, at the prevailing prices, as many units as it produces.
The company’s production capacity is, however, limited by two considerations. First, at the beginning of
period 1, the company has an initial balance of Rs 4,000 (cash plus bank credit plus collections from past
credit sales). Second, the company has, in each period, 2,000 hours of machine time and 1,400 hours of
assembly time. The production of each C1 requires 3 hours of machine time and 2 hours of assembly time,
whereas the production of each C2 requires 2 hours of machine time and 3 hours of assembly time.
Formulate this problem as an LP model so as to maximize the total profit to the company.
LP model formulation The data of the problem is summarized as follows:

Components
Resources/Constraints Total Availability
 C1 C 2
Budget (Rs) 10/unit 40/unit Rs 4,000
Machine time 3 hrs/unit 2 hrs/unit 2,000 hours
Assembly time 2 hrs/unit 3 hrs/unit 1,400 hours
Selling price Rs 30 Rs 70
Cost (wages + material) price Rs 10 Rs 40

Decision variables Let x1 and x2 = number of units of components C1 and C2 to be produced, respectively.
The LP model
Maximize (total profit) Z = Selling price – Cost price
30x2
subject to the constraints
= (30 – 10) x1 + (70 – 40) x2 = 20x1 +

(i) The total budget available

10x1 + 40x2 ≤ 4,000
(ii) Production time
(a) 3x1 + 02x2 ≤ 2,000; (b) 2x1 + 03x2 ≤ 1,400
and x1, x2 ≥ 0.
Example 2.4 A company has two grades of inspectors 1 and 2, the members of which are to be assigned for
a quality control inspection. It is required that at least 2,000 pieces be inspected per 8-hour day. Grade 1
inspectors can check pieces at the rate of 40 per hour, with an accuracy of 97 per cent. Grade 2 inspectors
check at the rate of 30 pieces per hour with an accuracy of 95 per cent.
The wage rate of a Grade 1 inspector is Rs 5 per hour while that of a Grade 2 inspector is Rs 4 per
hour. An error made by an inspector costs Rs 3 to the company. There are only nine Grade 1 inspectors and
eleven Grade 2 inspectors available to the company. The company wishes to assign work to the available
inspectors so as to minimize the total cost of the inspection. Formulate this problem as an LP model so as to
minimize the daily inspection cost. [Delhi Univ., MBA, 2004, 2006] LP model formulation The data of
the problem is summarized as follows:
Inspector

Grade 1 Grade 2
Number of inspectors 9 11
Rate of checking 40 pieces/hr 30 pieces/hr
Inaccuracy in checking 1 – 0.97 = 0.03 1 – 0.95 = 0.05 Cost of inaccuracy in checking Rs
3/piece Rs 3/piece
Wage rate/hour Rs 5 Rs 4
Duration of inspection = 8 hrs per day
Total pieces which must be inspected = 2,000
Linear Programming: Applications and Model Formulation 33

Decision variables Let x1 and x2 = number of Grade 1 and 2 inspectors to be assigned for inspection,
respectively.
The LP model
Hourly cost of each inspector of Grade 1 and 2 can be computed as follows:
Inspector Grade 1 : Rs (5 + 3 × 40 × 0.03) = Rs 8.60
Inspector Grade 2 : Rs (4 + 3 × 30 × 0.05) = Rs 8.50
Based on the given data, the LP model can be formulated as follows:
Minimize (daily inspection cost) Z = 8 (8.60x1 + 8.50x2) = 68.80x1 + 68.00x2
subject to the constraints
(i) Total number of pieces that must be inspected in an 8-hour day
8 × 40x1 + 8 × 30x2 ≥ 2000
(ii) Number of inspectors of Grade 1 and 2 available
(a) x1 ≤ 9, (b) x2 ≤ 11
and x1, x2 ≥ 0.
Example 2.5 An electronic company produces three types of parts for automatic washing machines. It
purchases casting of the parts from a local foundry and then finishes the part on drilling, shaping and
polishing machines.
The selling prices of parts A, B and C are Rs 8, Rs 10 and Rs 14 respectively. All parts made can be
sold. Castings for parts A, B and C, respectively cost Rs 5, Rs 6 and Rs 10.
The shop possesses only one of each type of casting machine. Costs per hour to run each of the three
machines are Rs 20 for drilling, Rs 30 for shaping and Rs 30 for polishing. The capacities (parts per hour)
for each part on each machine are shown in the table:
Machine Capacity per Hour
Part A Part B Part C
Drilling 25 40 25
Shaping 25 20 20
Polishing 40 30 40

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 LP model so as to maximize total
profit to the company. [Delhi Univ., MBA, 2001, 2004, 2007]

LP model formulation Let x1, x2 and x3 = numbers of type A, B and C parts to be produced per hour,
respectively.
Since 25 type A parts per hour can be run on the drilling machine at a cost of Rs 20, then Rs 20/25 =
Re 0.80 is the drilling cost per type A part. Similar reasoning for shaping and polishing gives

Profit per type A part = (8 – 5) – 20 30 30

 ++
   = 0.25
25 25 40

Profit per type B part = (10 – 6) – 20 30 30

 ++
 =1
40 20 30

Profit per type C part = (14 – 10) – 20 30 30

 ++
   = 0.95
25 20 40
On the drilling machine, one type A part consumes 1/25th of the available hour, a type B part consumes
1/40th, and a type C part consumes 1/25th of an hour. Thus, the drilling machine constraint is xxx 123
++≤ 1
25 40 25
Similarly, other constraints can be established.
The LP model
Maximize (total profit) Z = 0.25 x1 + 1.00 x2 + 0.95 x3
subject to the constraints
x 1 2 3 1,
++ ≤ x x (ii) Shaping machine: 25 20 20
1,
(i) Drilling machine: 1 2 3 25 40 25 ++ ≤ x x x
34 Operations Research: Theory and Applications

++ ≤ x x x
1,
(iii) Polishing machine: 1 2 3 40 30 40
and xxx 123 , , ≥ 0.
 Example 2.6 A pharmaceutical company produces two pharmaceutical products: A and B. Production of
both these products requires the same process – I and II. The production of B also results in a by-product C
at no extra cost. The product A can be sold at a profit of Rs 3 per unit and B at a profit of Rs 8 per unit.
Some quantity of this by-product can be sold at a unit profit of Rs 2, the remainder has to be destroyed and
the destruction cost is Re 1 per unit. Forecasts show that only up to 5 units of C can be sold. The company
gets 3 units of C for each unit of B produced. The manufacturing times are 3 hours per unit for A on process
I and II, respectively, and 4 hours and 5 hours per unit for B on process I and II, respectively. Because the
product C is a by product of B, no time is used in producing C. The available times are 18 and 21 hours of
process I and II, respectively. Formulate this problem as an LP model to determine the quantity of A and B
which should be produced, keeping C in mind, to make the highest total profit to the company. [Delhi Univ.,
MBA (HCA), 2001, 2008]
LP model formulation The data of the problem is summarized as follows:
Constraints/Resources Time (hrs) Required by Availability

ABC
Process I 3 4 – 18 hrs
Process II 3 5 – 21 hrs
By-product ratio from B – 1 3 5 units (max. units that
Profit per unit (Rs) 3 8 2 can be sold)

Decision variables Let

x1, x2 = units of product A and B to be produced, respectively
x3, x4 = units of product C to be produced and destroyed, respectively.
The LP model
Maximize (total profit) Z = 3x1 + 8x2 + 2x3 – x4
subject to the constraints
(i) Manufacturing constraints for product A and B
(a) 3x1 + 4x2 ≤ 18, (b) 3x1 + 5x2 ≤ 21
(ii) Manufacturing constraints for by-product C
(a) x3 ≤ 5, (b) – 3x2 + x3 + x4 = 0
and x1, x2, x3, x4 ≥ 0.
Example 2.7 A tape recorder company manufactures models A, B and C, which have profit contributions
per unit of Rs 15, Rs 40 and Rs 60, respectively. The weekly minimum production requirements are 25
units for model A, 130 units for model B and 55 units for model C. Each type of recorder requires a certain
amount of time for the manufacturing of the component parts for assembling and for packing. Specifically,
a dozen units of model A require 4 hours for manufacturing, 3 hours for assembling and 1 hour for
packaging. The corresponding figures for a dozen units of model B are 2.5, 4 and 2 and for a dozen units of
model C are 6, 9 and 4. During the forthcoming week, the company has available 130 hours of
manufacturing, 170 hours of assembling and 52 hours of packaging time. Formulate this problem as an LP
model so as to maximize the total profit to the company.
LP model formulation The data of the problem is summarized as follows:

Resources/Constraints Models
Total Availability

ABC (hrs)

Production requirement (units) 25 130 55

Manufacturing time (per dozen) 4 2.5 6 130
Assembling time (per dozen) 3 4 9 170
Packaging time (per dozen) 1 2 4 52
Contribution per unit (Rs) 15 40 60
Linear Programming: Applications and Model Formulation 35

Decision variables Let x1, x2 and x3 = units of model A, B and C to be produced per week,
respectively.
The LP model
Maximize (total profit) = 15x1 + 40x2 + 60x3
subject to the constraints
(i) Minimum production requirement:
(a) x1 ≥ 25, (b) x2 ≥ 130, (c) x3 ≥ 55
123 6
(ii) Manufacturing time : 4 2.5 130
xxx
+ +≤
12 12 12
123 9
(iii) Assembling time : 3 4 170
xxx
+ +≤
12 12 12
123 4
(iv) Packaging time : 2 52
xxx
+ +≤
12 12 12
and x1, x2, x3 ≥ 0.
Example 2.8 Consider the following problem faced by a production planner of a soft drink plant. He has
two bottling machines A and B. A is designed for 8-ounce bottles and B for 16-ounce bottles. However,
each can also be used for both types of bottles with some loss of efficiency. The manufacturing data is as
follows:
Machine 8-ounce Bottles 16-ounce Bottles
A 100/minute 40/minute
B 60/minute 75/minute
The machines can be run for 8 hours per day, 5 days per week. The profit on an 8-ounce bottle is Rs
1.5 and on a 16-ounce bottle is Rs 2.5. Weekly production of the drink cannot exceed 3,00,000 bottles and
the market can absorb 25,000, 8-ounce bottles and 7,000, 16-ounce bottles per week. The planner wishes to
maximize his profit, subject of course, to all the production and marketing restrictions. Formulate this
problem as an LP model to maximize total profit.
LP model formulation The data of the problem is summarized as follows:

Constraints Production Availability

8-ounce Bottles 16-ounce Bottles
Machine A time 100/minute 40/minute 8 × 5 × 60 = 2,400 minutes
Machine B time 60/minute 75/minute 8 × 5 × 60 = 2,400 minutes
Production 1 1 3,00,000 units/week
Marketing 1 – 25,000 units/week
– 1 7,000 units/week
Profit/unit (Rs) 1.5 2.5

Decision variables Let x1 and x2 = units of 8-ounce and 16-ounce bottles to be produced weekly,
respectively
The LP model
Maximize (total profit) Z = 1.5x1 + 2.5x2
subject to the constraints
xx 2,400
+≤ and (b) 1 2 60 75
2,400 3,00,000
(i) Machine time : (a) 1 2
100 40 (ii) Production : x + x ≤ + ≤ x x
1 2
 (iii) Marketing : (a) x1 ≤ 25,000, (b) x2 ≤ 7,000
and x1, x2 ≥ 0.
Example 2.9 A company engaged in producing tinned food has 300 trained employees on its rolls, each of
whom can produce one can of food in a week. Due to the developing taste of public for this kind of food,
the company plans to add to the existing labour force, by employing 150 people, in a phased manner, over
the next five weeks. The newcomers would have to undergo a two-week training programme before being
36 Operations Research: Theory and Applications

put to work. The training is to be given by employees from among the existing ones and it is a known fact
that one employee can train three trainees. Assume that there would be no production from the trainers and
the trainees during training period, as the training is off-the-job. However, the trainees would be
remunerated at the rate of Rs 300 per week, the same rate would apply as for the trainers.
The company has booked the following orders to supply during the next five weeks:
Week : 1 2 3 4 5
No. of cans : 280 298 305 360 400
Assume that the production in any week would not be more than the number of cans ordered for, so that
every delivery of the food would be ‘fresh’.
Formulate this problem as an LP model to develop a training schedule that minimizes the labour cost
over the five-week period. [Delhi Univ., MBA, 2003, 2005]

LP model formulation The data of the problem is summarized as given below:

(i) Cans supplied Week : 12345
Number : 280 298 305 360 400
(ii) Each trainee has to undergo a two-week training.
(iii) One employee is required to train three trainees.
(iv) Every trained worker produces one can/week but there would be no production from trainers and
trainees during training.
(v) Number of employees to be employed = 150
(vi) The production in any week is not to exceed the cans required.
(vii) Number of weeks for which newcomers would be employed: 5, 4, 3, 2, 1.
Observations based on given data are as follows:
(a) Workers employed at the beginning of the first week would get salary for all the five weeks; those
employed at the beginning of the second week would get salary for four weeks and so on.
(b) The value of the objective function would be obtained by multiplying it by 300 because each person
would get a salary of Rs 300 per week.
(c) Inequalities have been used in the constraints because some workers might remain idle in some
week(s).
Decision variables Let x1, x2, x3, x4 and x5 = number of trainees appointed in the beginning of week 1, 2,
3, 4 and 5, respectively.
The LP model
Minimize (total labour force) Z = 5x1 + 4x2 + 3x3 + 2x4 + x5
subject to the constraints
(i) Capacity
x 300 12
, (b) 3 3298 −−≥
300 1 xx
(a) 3280 − ≥

300 23 xx 300 34 300

(c) 3 3305 1 +− − ≥ x , (d) 3 3360 1 2 ++− − ≥ x xx x (e) 3 3400
45
123 +++− − ≥ xxxx x
(ii) New recruitment
x1 + x2 + x3 + x4 + x5 = 150
 and x1, x2, x3, x4, x5 ≥ 0.
Example 2.10 XYZ company assembles and markets two types of mobiles – A and B. Presently 200
mobiles of each type are manufactured per week. You are advised to formulate the production schedule
which will maximize the profits in the light of the following information:

Type Total Component Cost Man-Hours of Average Man-Minutes of Selling Price Per Per Mobile (Rs)
Assembly Time Per Inspection and Correction Mobile (Rs) Mobile
A 2000 12 10 6000 B 1600 6 35 4800
Linear Programming: Applications and Model Formulation 37

The company employs 100 assemblers who are paid Rs 50 per hour actually worked and who will
work up to a maximum of 48 hours per week. The inspectors, who are presently four, have agreed to a plan,
whereby they average 40 hours of work per week each. However, the four inspectors have certain other
administrative duties which have been found to take up an average of 8 hours per week between them. The
inspectors are each paid a fixed wage of Rs 12000 per week.
Each mobile of either type requires one camera of same type. However, the company can obtain a
maximum supply of 600 cameras per week. Their cost has been included in the component's cost, given for
each mobile in the table above. The other cost incurred by the company are fixed overheads of Rs 20,000
per week.
LP model formulation Computation of contribution from radio types A and B is as follows: A B
Component cost : 2000 1600
Labour cost in assembly (Rs 50 per hour) : 600 300
Labour cost for inspection
1200 1

⋅ = Re 0.50 per minute 5.00 17.5

40 60
Total variable cost 2605.00 1917.50
Selling price 6000 4800
Contribution (selling price – cost price) 3395 2882.50
Decision variables Let x1 and x2 = number of units of radio types A and B to be produced, respectively. The
LP model
Maximize (total contribution) Z = 3395x1 + 2882.5x2 – 20,000
subject to the constraints
25 40
(i) 12x1 + 6x2 ≤ 48 × 100, (ii) 10x1 + 35x2 ≤ 4 × 3
 −
   × 60 = 7,600
(iii) x1 + x2 ≤ 600
and x1, x2 ≥ 0.
Example 2.11 A plastic products manufacturer has 1,200 boxes of transparent wrap in stock at one factory
and another 1,200 boxes at its second factory. The manufacturer has orders for this product from three
different retailers, in quantities of 1,000, 700 and 500 boxes, respectively. The unit shipping costs (in rupees
per box) from the factories to the retailers are as follows:

Retailer I Retailer II Retailer III

Factory A 14 11 13
Factory B 13 13 12

Determine a minimum cost shipping schedule for satisfying all demands from current inventory.
Formulate this problem as an LP model.
LP model formulation Given that the total number of boxes available at factory A and B = total number
of boxes required by retailers 1, 2 and 3.
Decision variables Let x1, x2 and x3 = number of boxes to be sent from factory A to retailer 1; factory B to
retailer 2 and factory C to retailer 3, respectively.
 Number of Boxes to be Sent
Retailer 1 Retailer 2 Retailer 3

Factory A x1 x2 1,200 – (x1 + x2)

Factory B 1,000 – x1 700 – x2 500 – [(1,000 – x1) + (700 – x2)]

The LP model

Minimize (total distance) Z = 14x1 + 13x2 + 11 (1,200 – x1 – x2) + 13 (1,000 – x1) +

13 (700 – x2) + 12 (x1 – x2 – 700) = 2x1 + x2 + 26,900
38 Operations Research: Theory and Applications

subject to the constraints

(i) x1 + x2 ≤ 1,200, (ii) x1 ≤ 1,000, (iii) x2 ≤ 700;
and x1, x2 ≥ 0.
Example 2.12 A company produces two types of sauces: A and B. Both these sauces are made by blending
two ingredients – X and Y. A certain level of flexibility is permitted in the formulae of these products.
Indeed, the restrictions are that (i) B must contain no more than 75 per cent of X, and (ii) A must contain no
less than 25 per cent of X, and no less than 50 per cent of Y. Up to 400 kg of X and 300 kg of Y could be
purchased. The company can sell as much of these sauces as it produces at a price of Rs 18 for A and Rs 17
for B. The X and Y cost Rs 1.60 and 2.05 per kg, respectively.
The company wishes to maximize its net revenue from the sale of these sauces. Formulate this problem
as an LP model.

LP model formulation Let x1, x2 = kg of sauces A and B to be produced, respectively.

y1, y2 = kg of ingredient X used to make sauces A and B, respectively.
B, respectively.
The LP model
y3, y4 = kg of ingredient Y used to make sauces A and

Maximize Z = 18x1 + 17x2 – 1.60 (y1 + y2) – 2.05 (y3 + y4)

subject to the constraints

(i) y1 + y3 – x1 = 0, (ii) y2 + y4 – x2 = 0 


≥0 (Purchase)
(iii) y1 + y2 ≤ 400 (iv) y1 – 0.25 x1 (Sauce A) y3 + y4 ≤ 300 y2 – 0.50

x2 ≥ 0
(v) y2 – 0.75x2 ≥ 0 (Sauce B)
and x1, x2, y1, y2, y3, y4 ≥ 0.
Example 2.13 A complete unit of a certain product consists of four units of component A and three units of
component B. The two components (A and B) are manufactured from two different raw materials of which
100 units and 200 units, respectively, are available. Three departments are engaged in the production
process with each department using a different method for manufacturing the components per production
run and the resulting units of each component are given below:

Department Input of Raw Materials Output of Components

per Run (units) per Run (units)
I IIAB
17564
24858
32773

Formulate this problem as an LP model to determine the number of production runs for each
 department which will maximize the total number of complete units of the final product.
LP model formulation Let x1, x2 and x3 = number of production runs for departments 1, 2 and 3,
respectively.
Since each unit of the final product requires 4 units of component A and 3 units of component B, therefore

RS UV
maximum number of units of the final product cannot exceed the smaller value of
T W
Total number of units of A produced
4 3;
Total number of units of B produced

S UV
12 3 2 3 R xx x xx x ++ ++ T W
or 657 4 833
and4 1
Also if y is the number of component units of final product, then we obviously have 657
xx x xxx
12 3 12 3 y y
++
≥+ +
483
and ≥
4
3
The LP model 657
Maximize Z = Min 4
R
12 3 12 3
xx x xx x ++ ++
483 3

S UV ;
T W
Linear Programming: Applications and Model Formulation 39

subject to the constraints

i(i) Raw material
(a) 7x1 + 4x2 + 2x3 ≤ 100 (Material I), (b) 5x1 + 8x2 + 7x3 ≤ 200 (Material II)
(ii) Number of component units of final product
(a) 6x1 + 5x2 + 7x3 – 4y ≥ 0, (b) 4x1 + 8x2 + 3x3 – 4y ≥ 0
and x1, x2, x3 ≥ 0.
Example 2.14 ABC company manufactures three grades of paint: Venus, Diana and Aurora. The plant
operates on a three-shift basis and the following data is available from the production records:
Grade
Requirement Availability
of Resource Venus Diana Aurora (capacity/month)
Special additive (kg/litre) 0.30 0.15 0.75 600 tonnes
Milling (kilolitres per machine shift) 2.00 3.00 5.00 100 machine shifts
Packing (kilolitres per shift) 12.00 12.00 12.00 80 shifts

There are no limitations on the other resources. The particulars of sales forecasts and the estimated
contribution to overheads and profits are given below:
Venus Diana Aurora
Maximum possible sales
per month (kilolitres) 100 400 600
Contribution (Rs/kilolitre) 4,000 3,500 2,000
Due to the commitments already made, a minimum of 200 kilolitres per month, of Aurora, must be
supplied the next year.
Just when the company was able to finalize the monthly production programme for the next 12 months,
it received an offer from a nearby competitor for hiring 40 machine shifts per month of milling capacity for
grinding Diana paint that could be spared for at least a year. However, due to additional handling at the
competitor’s facility, the contribution from Diana would be reduced by Re 1 per litre.
Formulate this problem as an LP model for determining the monthly production programme to
maximize contribution. [Delhi Univ., MBA, 2006]
LP model formulation Let
x1 = quantity of Venus (kilolitres) produced in the company
x2 = quantity of Diana (kilolitres) produced in the company
x3 = quantity of Diana (kilolitres) produced by hired facilities
x4 = quantity of Aurora (kilolitres) produced in the company
The LP model
Maximize (total profit) Z = 4,000x1 + 3,500x2 + (3,500 – 1,000)x3 + 2,000x4
subject to the constraints
(i) Special additive : 0.30x1 + 0.15x2 + 0.15x3 + 0.75x4 ≤ 600
xx x
(ii) Own milling facility : 124
++≤ 100
235
x
(iii) Hired milling facility : 33≤ 40
+
+ 80 + ≤
(iv) Packing :xxx x 1 23 4
(v) Marketing: 12 12 12

(i) x1 ≤ 100 (Venus); (ii) x2 + x3 ≤ 400 (Diana); (iii) 200 ≤ x4 ≤ 600 (Aurora) and
x1, x2, x3, x4 ≥ 0.
Example 2.15 Four products have to be processed through a particular plant, the quantities required for the
next production period are:
Product 1 : 2,000 units Product 2 : 3,000 units
Product 3 : 3,000 units Product 4 : 6,000 units
There are three production lines on which the products could be processed. The rates of production in
units per day and the total available capacity in days are given in the following table. The corresponding
cost of using the lines is Rs 600, Rs 500 and Rs 400 per day, respectively.
40 Operations Research: Theory and Applications

Production Line Product Maximum

(days)
1234 Line
1 150 100 500 400 20
2 200 100 760 400 20
3 160 80 890 600 18
Total 2,000 3,000 3,000 6,000
Formulate this problem as an LP model to minimize the cost of operation.

LP model formulation Let xij = number of units of product i (i = 1, 2, 3, 4) produced on production line j
( j = 1, 2, 3)
The LP model 4
4 4
i i
i i i i xx x == = + +
3 ΣΣ Σ
Minimize (total cost) Z = 600 500 400
1 subject to the constraints
 1 2
1 1

i
(i) Production: (a)31 12,000, =Σ = ix (b) Σi i x = = 132 3 000 , (c)33
i
13,000, =Σ = ix (d) Σi i x = = 134 6 000 ,
(ii) Line capacity
xxxx
(a) 11 12 13 14
xxxx
+++≤ 20, (b) 21 22 23 24
150 100 500 400 160 80 890 600
xxxx and xij ≥ 0 for all i and j.
(c) 31 32 33 34
+++≤ 18 +++≤ 20 200 100 760 400

Example 2.16 XYZ company produces a specific automobile spare part. A contract that the company has
signed with a large truck manufacturer calls for the following 4-month shipping schedule.

Month Number of Parts

to be Shipped
January 3,000
February 4,000
March 5,000
April 5,000

The company can manufacture 3,000 parts per month on a regular time basis and 2,000 parts per month
on an overtime basis. Its production cost is Rs 15,000 for a part produced during regular time and 25,000
for a part produced during overtime. Its monthly inventory holding cost is Rs 500. Formulate this problem
as an LP model to minimize the overall cost.

LP model formulation Let xijk = number of units of automobile spare part manufactured in month i (i =
1, 2, 3, 4) using shift j ( j = 1, 2) and shipped in month
k (k = 1, 2, 3, 4)
The LP model
Minimize (total cost) Z = Regular time production cost + Overtime production cost +
One-month inventory cost + Two-month inventory cost
+ Three-month inventory cost
= 15,000(x111 + x112 + x113 + x114 + x212 + x213 + x214 + x313 + x314 + x414)
+ 25,000(x121 + x122 + x123 + x124 + x222 + x223 + x224 + x323 + x324 + x424)
+ 500(x112 + x122 + x213 + x223 + x314 + x324) + 1,000(x113 + x123 + x214
+ x224) + 1,500(x114 + x124)
Linear Programming: Applications and Model Formulation 41

subject to the constraints

(i) Monthly regular time production
(a) x111 + x112 + x113 + x114 ≤ 3,000, (b) x212 + x213 + x214 ≤ 3,000
(c) x313 + x314 ≤ 3,000, (d) x414 ≤ 3,000
(ii) Monthly overtime production constraints
(a) x121 + x122 + x123 + x124 ≤ 2,000, (b) x222 + x223 + x224 ≤ 2,000
(c) x323 + x324 ≤ 2,000, (d) x424 ≤ 2,000
 (iii) Monthly demand constraints
(a) x111 + x121 = 3,000, (b) x112 + x122 + x212 + x222 = 4,000
(c) x113 + x123 + x213 + x223 + x313 + x323 = 5,000
(d) x114 + x124 + x214 + x224 + x314 + x324 + x414 + x424 = 5,000
and xijk ≥ 0 for all i, j and k.

2.8.2 Examples on Marketing

Example 2.17 An advertising company wishes to plan an advertising campaign for three different media:
television, radio and a magazine. The purpose of the advertising is to reach as many potential customers as
possible. The following are the results of a market study:

Television
Prime Day Prime Time Radio Magazine
(Rs) (Rs) (Rs) (Rs)
Cost of an advertising unit 40,000 75,000 30,000 15,000 Number of potential customers reached per unit
4,00,000 9,00,000 5,00,000 2,00,000 Number of women customers reached per unit 3,00,000 4,00,000 2,00,000
1,00,000

The company does not want to spend more than Rs 8,00,000 on advertising. It is further required that
(i) at least 2 million exposures take place amongst women,
(ii) the cost of advertising on television be limited to Rs 5,00,000,
(iii) at least 3 advertising units be bought on prime day and two units during prime time; and (iv) the
number of advertising units on the radio and the magazine should each be between 5 and 10. Formulate this
problem as an LP model to maximize potential customer reach.
LP model formulation Let x1, x2, x3 and x4 = number of advertising units bought in prime day and time
on television, radio and magazine, respectively.
The LP model
Maximize (total potential customer reach) Z = 4,00,000x1 + 9,00,000x2 + 5,00,000x3 + 2,00,000x4
subject to the constraints
(i) Advertising budget: 40,000x1 + 75,000x2 + 30,000x3 + 15,000x4 ≤ 8,00,000
(ii) Number of women customers reached by the advertising campaign
3,00,000x1 + 4,00,000x2 + 2,00,000x3 + 1,00,000x4 ≥ 20,00,000
(iii) Television advertising : (a) 40,000x1 + 75,000x2 ≤ 5,00,000; (b) x1 ≥ 3; (c) x2 ≥ 2
(iv) Radio and magazine advertising : (a) 5 ≤ x3 ≤ 10; (b) 5 ≤ x4 ≤ 10
and x1, x2, x3, x4 ≥ 0.
Example 2.18 A businessman is opening a new restaurant and has budgeted Rs 8,00,000 for advertisement,
for the coming month. He is considering four types of advertising:
(i) 30 second television commercials
(ii) 30 second radio commercials
(iii) Half-page advertisement in a newspaper
(iv) Full-page advertisement in a weekly magazine which will appear four times during the coming
month. The owner wishes to reach families (a) with income over Rs 50,000 and (b) with income under Rs
50,000. The amount of exposure of each media to families of type (a) and (b) and the cost of each media is
shown below:
42 Operations Research: Theory and Applications

Media Cost of Advertisement Exposure to Families with Exposure to Families with

(Rs) Annual Income Over Annual Income Under
Rs 50,000 (a) Rs 50,000 (b)
Television 40,000 2,00,000 3,00,000
Radio 20,000 5,00,000 7,00,000
Newspaper 15,000 3,00,000 1,50,000
Magazine 5,000 1,00,000 1,00.000
 To have a balanced campaign, the owner has determined the following four restrictions:
(i) there should be no more than four television advertisements
(ii) there should be no more than four advertisements in the magazine
(iii) there should not be more than 60 per cent of all advertisements in newspaper and magazine put
together (iv) there must be at least 45,00,000 exposures to families with annual income of over Rs 50,000.
Formulate this problem as an LP model to determine the number of each type of advertisement to be given
so as to maximize the total number of exposures.
LP model formulation Let x1, x2, x3 and x4 = number of television, radio, newspaper, magazine
advertisements to be pursued, respectively.
The LP model
Maximize (total number of exposures of both groups) Z
= (2,00,000 + 3,00,000) x1 + (5,00,000 + 7,00,000) x2 + (3,00,000 + 1,50,000) x3
+ (1,00,000 + 1,00,000) x4
= 5,00,000 x1 + 12,00,000 x2 + 4,50,000 x3 + 2,00,000 x4
subject to the constraints
(i) Available budget : 40,000x1 + 20,000x2 + l5,000x3 + 5,000x4 ≤ 8,00,000
(ii) Maximum television advertisement : x1 ≤ 4
(iii) Maximum magazine advertisement
x4 ≤ 4 (because magazine will appear only four times in the next month)
(iv) Maximum newspaper and magazine advertisement
+
xx
34

+++≤ . or – 0.6x1 – 0.6x2 + 0.4x3 + 0.4x4 ≤ 0

xxxx 1234 0 60

(v) Exposure to families with income over Rs 50,000

2,00,000x1 + 5,00,000x2 + 3,00,000x3 + 1,00,000x4 ≥ 45,00,000
and x1, x2, x3, x4 ≥ 0.
Example 2.19 An advertising agency is preparing an advertising campaign for a group of agencies. These
agencies have decided that different characteristics of their target customers should be given different
importance (weightage). The following table gives the characteristics with their corresponding importance
(weightage).

Characteristics Weightage (%)

Age 25–40 years 20

Annual income Above Rs 60,000 30
Female Married 50

The agency has carefully analyzed three media and has compiled the following data:
Data Item Media
Women’s Magazine (%) Radio (%) Television (%)
Reader characteristics
(i) Age: 25–40 years 80 70 60 (ii) Annual income: Above Rs 60,000 60 50 45 (iii) Females/Married 40 35 25
Cost per advertisement (Rs) 9,500 25,000 1,00,000 Minimum number of advertisement allowed 10 5 5
Maximum number of advertisement allowed 20 10 10 Audience size (1000s) 750 1,000 1,500
Linear Programming: Applications and Model Formulation 43

The budget for launching the advertising campaign is Rs 5,00,000. Formulate this problem as an LP
model for the agency to maximize the total expected effective exposure.

LP model formulation Let x1, x2 and x3 = number of advertisements made using advertising media:
 women’s magazines, radio and television, respectively.
The effectiveness coefficient corresponding to each of the advertising media is calculated as follows:

Media Effectiveness Coefficient

Women’s magazine 0.80 (0.20) + 0.60 (0.30) + 0.40 (0.50) = 0.54

Radio 0.70 (0.20) + 0.50 (0.30) + 0.35 (0.50) = 0.46
Television 0.60 (0.20) + 0.45 (0.30) + 0.25 (0.50) = 0.38

The coefficient of the objective function, i.e. effective exposure for all the three media employed, can
be computed as follows:
Effective exposure = Effectiveness coefficient × Audience size
where effectiveness coefficient is a weighted average of audience characteristics. Thus, the effective
exposure of each media is as follows:
Women’s magazine = 0.54 × 7,50,000 = 4,05,000
Radio = 0.46 × 10,00,000 = 4,60,000
Television = 0.38 × 15,00,000 = 5,70,000
The LP model
Maximize (effective exposure) Z = 4,05,000x1 + 4,60,000x2 + 5,70,000x3
subject to the constraints
(i) Budget: 9,500x1 + 25,000x2 + 1,00,000x3 ≤ 5,00,000
(ii) Minimum number of advertisements allowed
(a) x1 ≥ 10; (b) x2 ≥ 5; and (c) x3 ≥ 5
(iii) Maximum number of advertisements allowed constraints
(a) x1 ≤ 20; (b) x2 ≤ 10; and (c) x3 ≤ 10
and x1, x2, x3 ≥ 0.

2.8.3 Examples on Finance

Example 2.20 An engineering company planned to diversify its operations during the year 2005-06. The
company allocated capital expenditure budget equal to Rs 5.15 crore in the year 2005 and Rs 6.50 crore in
the year 2006. The company had to take five investment projects under consideration. The estimated net
returns at that present value and the expected cash expenditures on each project in those two years are as
follows.
Assume that the return from a particular project would be in direct proportion to the investment in it, so
that, for example, if in a project, say A, 20% (of 120 in 2005 and of 320 in 2006) was invested, then the
resulting net return in it would be 20% (of 240). This assumption also implies that individuality of the
project should be ignored. Formulate this capital budgeting problem as an LP model to maximize the net
return.

Project Estimated Net Returns Cash Expenditure

(in ’000 Rs) (in ’000 Rs)
Year 2005 Year 2006
A 240 120 320
B 390 550 594
C 80 118 202
D 150 250 340
E 182 324 474

LP model formulation Let x1, x2, x3, x4 and x5 = proportion of investment in projects A, B, C, D and E,
respectively.
The LP model
Maximize (net return) = 240x1 + 390x2 + 80x3 + 150x4 + 182x5
44 Operations Research: Theory and Applications

subject to the constraints

 (i) Capital expenditure budget
(a) 120x1 + 550x2 + 118x3 + 250x4 + 324x5 ≤ 515 [For year 2005]
(b) 320x1 + 594x2 + 202x3 + 340x4 + 474x5 ≤ 650 [For year 2006]
(ii) 0-1 integer requirement constraints
(a) x1 ≤ 1, (b) x2 ≤ 1, (c) x3 ≤ 1, (d) x4 ≤ 1, (e) x5 ≤ 1
and x1, x2, x3, x4, x5 ≥ 0
Example 2.21 XYZ is an investment company. To aid in its investment decision, the company has
developed the investment alternatives for a 10-year period, as given in the following table. The return on
investment is expressed as an annual rate of return on the invested capital. The risk coefficient and growth
potential are subjective estimates made by the portfolio manager of the company. The terms of investment
is the average length of time period required to realize the return on investment as indicated.

Investment Length of Annual Rate of Risk Coefficient Growth Potential

Alternative Investment Return (Year) Return (%)
A 43 1 0
B 7 12 5 18
C 8 9 4 10
D 6 20 8 32
E 10 15 6 20
F 36 3 7
Cash 0 0 0 0

The objective of the company is to maximize the return on its investments. The guidelines for selecting
the portfolio are:
(i) The average length of the investment for the portfolio should not exceed 7 years.
(ii) The average risk for the portfolio should not exceed 5.
(iii) The average growth potential for the portfolio should be at least 10%.
(iv) At least 10% of all available funds must be retained in the form of cash, at all times.
Formulate this problem as an LP model to maximize total return.
LP model formulation Let xj = proportion of funds to be invested in the jth investment alternative ( j =
1, 2, . . ., 7)
The LP model
Maximize (total return) Z = 0.03x1 + 0.12x2 + 0.09x3 + 0.20x4 + 0.15x5 + 0.06x6 + 0.00x7
subject to the constraints
(i) Length of investment : 4x1 + 7x2 + 8x3 + 6x4 + 10x5 + 3x6 + 0x7 ≤ 7
(ii) Risk level : x1 + 5x2 + 4x3 + 8x4 + 6x5 + 3x6 + 0x7 ≤ 5
(iii) Growth potential : 0x1 + 0.18x2 + 0.10x3 + 0.32x4 + 0.20x5 + 0.07x6 + 0x7 ≥ 0.10
(iv) Cash requirement : x7 ≥ 0.10
(v) Proportion of funds : x1 + x2 + x3 + x4 + x5 + x6 + x7 = 1
and x1, x2, x3, x4, x5, x6, x7 ≥ 0.
Example 2.22 An investor has three investment opportunities available to him at the beginning of each
years, for the next 5 years. He has a total of Rs 5,00,000 available for investment at the beginning of the
first year. A summary of the financial characteristics of the three investment alternatives is presented in the
following table:

Investment Allowable Size of Return (%) Timing of Return Immediate

Alternative Initial Investment Reinvestment Possible?
(Rs)
1 1,00,000 19 1 year later yes
2 unlimited 16 2 years later yes
3 50,000 20 3 years later yes
Linear Programming: Applications and Model Formulation 45
 The investor wishes to determine the investment plan that will maximize the amount of money which
can be accumulated by the beginning of the 6th year in the future. Formulate this problem as an LP model
to maximize total return. [Delhi Univ., MBA, 2002, 2008]
LP model formulation Let

xij = amount to be invested in investment alternative, i (i = 1, 2, 3) at the beginning of the year j ( j =1,
2, . . ., 5)
yj = amount not invested in any of the investment alternatives in period j
The LP model
Minimize (total return) Z = 1.19x15 + 1.16x24 + 1.20x33 + y5
subject to the constraints
i(i) Yearly cash flow
(a) xxxy 11 21 31 1 + + += 5 00 000 , , (year 1)
(b) −− + + + + = y xxxx y 1 11 12 22 32 2 119 . 0 (year 2)
(c) – y2 – 1.16x21 – 1.19x12 + x23 + x23 + x33 + y3 = 0
(d) – y3 – 1.20x31 – 1.16x22 – 1.19x13 + x14 + x24 + x34 + y4 = 0 (year 4)
(e) – y4 – 1.20x32 – 1.16x23 – 1.19x14 + x15 + x25 + x35 + y5 = 0 (year 5)
(ii) Size of investment
x11 ≤ 1 00 000 , , , x12 ≤ 1 00 000 , , , x13 ≤ 1 00 000 , , , x14 ≤ 1 00 000 , , , x15 ≤ 1 00 000 , ,
x31 ≤ 50 000 , , x32 ≤ 50 000 , , x33 ≤ 50 000 , , x34 ≤ 50 000 , , x35 ≤ 50 000 ,
and x y ij j , ≥ 0 for all i and j.
Remark To formulate the first set of constraints of yearly cash flow, the following situation is adopted:
Investment alternatives Investment alternatives
=
1.19 xxxy y x +++ +
12 22 32 2 1 11

or – y1 – 1.19x11 + x12 + x22 + x32 + y2 = 0.

Example 2.23 A leading CA is attempting to determine the ‘best’ investment portfolio and is considering
six alternative investment proposals. The following table indicates point estimates for the price per share,
the annual growth rate in the price per share, the annual dividend per share and a measure of the risk
associated with each investment.
Portfolio Data
Shares Under Consideration A B C D E F
Current price per share (Rs) 80.00 100.00 160.00 120.00 150.00 200.00 Projected annual growth rate 0.08 0.07
0.10 0.12 0.09 0.15 Projected annual dividend per share (Rs) 4.00 4.50 7.50 5.50 5.75 0.00 Projected risk return
0.05 0.03 0.10 0.20 0.06 0.08

The total amount available for investment is Rs 25 lakh and the following conditions are required to be
satisfied:
(i) The maximum rupee amount to be invested in alternative F is Rs 2,50,000.
(ii) No more than Rs 5,00,000 should be invested in alternatives A and B combined.
(iii) Total weighted risk should not be greater than 0.10, where
( )) Amount invested in alternative (Risk of alternative
Total weighted risk =
jj
Total amount invested in all the alternatives
(iv) For the sake of diversity, at least 100 shares of each stock should be purchased.
(v) At least 10 per cent of the total investment should be in alternatives A and B combined. (vi)
Dividends for the year should be at least 10,000.
Rupee return per share of stock is defined as the price per share one year hence, less current price per
share plus dividend per share. If the objective is to maximize total rupee return, formulate this problem as
an LP model for determining the optimal number of shares to be purchased in each of the shares under
consideration. You may assume that the time horizon for the investment is one year.
46 Operations Research: Theory and Applications

LP model formulation Let x1, x2, x3, x4, x5 and x6 = number of shares to be purchased in each of the six
investment proposals A, B, C, D, E and
F, respectively.
Rupee return per share = Price per share one year hence – Current price per share + Dividend per
share
= Current price per share × Projected annual growth rate (i.e. Projected
growth each year + Dividend per share).
Thus, we compute the following data:

Investment Alternatives : ABCDEF

No. of shares purchased : x1 x2 x3 x4 x5 x6 Projected growth for each share (Rs) : 6.40 7.00 16.00 14.40 13.50
30.00 Projected annual dividend per share (Rs) : 4.00 4.50 7.50 5.50 5.75 0.00 Return per share (Rs) : 10.40
11.50 23.50 19.90 19.25 30.00

The LP model

Maximize (total return) R = 10.40x1 + 11.50x2 + 23.50x3 + 19.90x4 + 19.25x5 + 30.00x6

subject to the constraints
(i) 80x1 + l00x2 + 160x3 + 120x4 + 150x5 + 200x6 ≤ 25,00,000 (total fund available)
(ii) 200x6 ≤ 2,50,000 [from condition (i)]
(iii) 80x1 + l00x2 ≤ 5,00,000 [from condition (ii)]
80 0 05 100 0 03 160 0 10 120 0 02 150 0 06 200 0 08
xxxx x x
(. ) (. ) (. ) (. ) (. ) (. ) +++ ++
1234 5 6
80 100 160 120 150 2001
+++++≤
(iv)
xxxxxx
123456

4x1 + 3x2 + 16x3 + 24x4 + 9x5 + 16x6 ≤ 8x1 + l0x2 + 16x3 + 12x4 + 15x5 + 20x6 – 4x1
– 7x1 + 0x3 + 12x4 – 6x5 – 4x6 ≤ 0
(v) x1 ≥ 100, x2 ≥ 100, x3 ≥ 100, x4 ≥ 100, x5 ≥ 100, x6 ≥ 100 [from condition (iv)] (vi) 80x1 + l00x2
≥ 0.10 (80x1 + l00x2 + 160x3 + 120x4 + 150x5 + 200x6) [from condition (v)] 80x1 + l00x2 ≥ 8x1 +
l0x2 + 16x3 + 12x4 + 15x5 + 20x6
72x1 + 90x2 – 16x3 – 12x4 – 15x5 – 20x6 ≥ 0
(vii) 4x1 + 4.5x2 + 7.5x3 + 5.5x4 + 5.75x5 ≥ 10,000 [from condition (vi)] and xj ≥ 0; j = 1, 2, 3, 4, 5
and 6.
Example 2.24 A company must produce two products over a period of three months. The company can pay
for materials and labour from two sources: company funds and borrowed funds. The firm has to take three
decisions:
(a) How many units of product 1 should it produce?
(b) How many units of product 2 should it produce?
(c) How much money should it borrow to support the production of the products? The firm must take these
decisions in order to maximize the profit contribution, subject to the conditions stated below:
(i) Since the company’s products enjoy a seller’s market, the company can sell as many units as it can
produce. The company would therefore like to produce as many units as possible, subject to its
production capacity and financial constraints. The capacity constraints, together with cost and
price data, are shown in the following table:
Capacity, Price and Cost Data
Product Selling Price Cost of Production Required Hours per Unit in (Rs per Unit) (Rs per Unit)
Department
 ABC
1 14 10 0.5 0.3 0.2 2 11 8 0.3 0.4 0.1 Available hours per production period of three months : 500.00
400.00 200.00 (ii) The available company funds during the production period will be Rs 3 lakh.
Linear Programming: Applications and Model Formulation 47

(iii) A bank will give loans up to Rs 2 lakh per production period at an interest rate of 20 per cent per
annum provided that company’s acid (quick) test ratio is at 1 to 1 while the loan is outstanding.
Take a simplified acid-test ratio given by
Surplus cash on hand after production + Accounts receivable
Bank borrowings + Interest occurred thereon
(iv) Also make sure that the needed funds are made available for meeting production costs. Formulate
this problem as an LP model.
LP model formulation Let x1, x2 = number of units of products 1 and 2 produced, respectively.
x3 = amount of money borrowed.
The LP model

Profit contribution per unit of each product = (Selling price – Variable cost of production)
Maximize Z = Total profit by producing two products – Cost of borrowed money = (14 –
10)x1 + (11 – 8)x2 – 0.05x3 = 4x1 + 3x2 – 0.05x3
(since the interest rate is 20 per cent per annum, it will be 5 per cent for a period of
three months)
subject to the constraints
(i) The production capacity constraints for each department
(a) 0.5x1 + 0.3x2 ≤ 500, (b) 0.3x1 + 0.4x2 ≤ 400, (c) 0.2x1 + 0.lx2 ≤ 200
(ii) The funds available for production are the sum of Rs 3,00,000 in cash that the firm has and
borrowed funds maximum up to Rs 2,00,000. Consequently, production is limited to the extent
that the funds are available to pay for production costs. Thus, we write the constraint as: Funds
required for production ≤ Funds available
10x1 + 8x2 ≤ 3,00,000 + x3
10x1 + 8x2 – x3 ≤ 3,00,000
(iii) Borrowed funds constraint [from condition (iii) of the problem]
x1 ≤ 2,00,000
(iv) Acid-test condition
constraint

Surplus cash on hand after production + Accounts receivable

1

Bank borrowings + Interest accrued thereon≥

(3,00,000 10 8 ) 14 11
1
+− − + +
≥
x xx x x
3 12 1 2
+
xx
0.2
33

3 1 23 3 3,00,000 4 3 0.2 ++ + ≥+ x x xx x
or −− + ≤ 4 3 0 2 3 00 000 12 3 xx x . ,,
and x1, x2, x3 ≥ 0.
Example 2.25 The most recent audited summarized balance sheet of Shop Financial Service is given
below: The company intends to enhance its investment in the lease portfolio by another Rs 1,000 lakh. For
this purpose, it would like to raise a mix of debt and equity in such a way that the overall cost of raising
additional funds is minimized. The following constraints apply to the way the funds can be mobilized: (i)
Total debt divided by net owned funds, cannot exceed 10.
(ii) Amount borrowed from financial institutions cannot exceed 25 per cent of the net worth. (iii)
Maximum amount of bank borrowings cannot exceed three times the net owned funds. Balance
Sheet as on 31 March 2008
Liabilities (Rs lakh) Assets (Rs lakh)
Equity Share Capital 65 Fixed Assets:
Reserves & Surplus 110 Assets on Lease
(Original Cost: Rs 550 lakhs) 375
Term Loan from IFCI 80 Other Fixed Assets 50 Public Deposits 150 Investments (on wholly owned
subsidiaries) 20 Bank Borrowings 147 Current Assets:
Other Current Liabilities 50 Stock on Hire 80 602 Receivables 30
Other Current Assets 35
Miscellaneous Expenditure (not written off) 12
602
48 Operations Research: Theory and Applications

(iv) The company would like to keep the total public deposit limited to 40 per cent of the total debt.
The post-tax costs of the different sources of finance are as follows:
Equity Term Loans Public Deposits Bank Borrowings
2.5% 8.5% 7% 10%
Formulate this problem as an LP model to minimize cost of funds raised.
Note: (a) Total Debt = Term loans from Financial Institutions + Public deposits + Bank borrowings (b)
Net worth = Equity share capital + Reserves and surplus
(c) Net owned funds = Net worth – Miscellaneous expenditures

LP model formulation Let x1, x2, x3 and x4 = quantity of additional funds (in lakh) raised on account of
additional equity, term loans, public deposits, bank
borrowings, respectively.
The LP model
Minimize (cost of additional funds raised) Z = 0.025x1 + 0.085x2 + 0.07x3 + 0.1x4
subject to the constraints
Total Debt
(i)
≤ 10 Existing debt+Additional total debt
Net owned funds or
≤ 10
(Equity share capital+ Reserve & surplus
+ Additional equity Misc. exp.) −
80 150 147
+ + +++
xxx 234 xxx +++ 377

234
+ +−≤ 10 or
(65 110 ) 12 x
x +≤ 10 163
1 1
x2 + x3 + x4 + 377 ≤ 10 x1 + 1,630 or –10x1 + x2 + x3 + x4 ≤ 1,253. (ii) Amount borrowed (from
financial institutions) ≤ 25% of net worth
or (Existing long-term loan from financial institutions + Additional loan)
≤ 25% (Existing equity capital + Reserve & surplus + Addl. equity capital)
80 + x2 ≤ 0.25 (175 + x1)
320 + 4x1 ≤ 175 + x1
– x1 + 4x2 ≤ –145 or x1 – 4x2 ≥ 145.
(iii) Maximum bank borrowings ≤ 3 (Net owned funds)
or (Existing bank borrowings + Addl. bank borrowings ≤ 3 (Existing equity capital + Reserves &
 surplus + Addl. equity capital – Misc. exp.)
(147 + x4) ≤ 3 (65 + 110 + x1 – 12)
x4 – 3x1 ≤ 525 – 36 – 147
–3x1 + x4 ≤ 342.
(iv) Total public deposit ≤ 40% of total debt.
or (Existing public deposits + Addl. public deposits) ≤ 0.40 (Existing total debt + Addl. total debt)
or 150 + x3 ≤ 0.40 (80 + 150 + 147 + x2 + x3 + x4) or 150 + x3 ≤ 0.40 (x2 + x3 + x4 + 377) 1,500 +
l0x3 ≤ 4x2 + 4x3 + 4x4 + 1,508 or – 4x2 + 6x3 – 4x4 ≤ 8.
(v) Addl. equity capital + Addl. term loan + Addl. public deposits + Addl. bank borrowings = 1,000
(since the company wants to enhance the investment by Rs 1,000 lakh)
or x1 + x2 + x3 + x4 = 1,000
and x1, x2, x3, x4 ≥ 0.
Example 2.26 Renco-Foundries is in the process of drawing up a Capital Budget for the next three years. It
has funds to the tune of Rs 1,00,000 that can be allocated among projects A, B, C, D and E. The net cash
flows associated with an investment of Re 1 in each project are provided in the following table. Cash Flow at
Time

Investment in 0 1 2 3
A – Re 1 + Re 0.5 + Re 1 Re 0
B Re 0 – Re 1 + Re 0.5 + Re 1
C – Re 1 + Rs 1.2 Re 0 Re 0
D – Re 1 Re 0 Re 0 Rs 1.9
E Re 0 Re 0 – Re 1 Rs 1.5

Note: Time 0 = present, Time 1 = 1 year from now. Time 2 = 2 years from now. Time 3 = 3 years from now.
Linear Programming: Applications and Model Formulation 49

For example, Re 1 invested in investment B requires a Re 1 cash outflow at time 1 and returns Re 0.50
at time 2 and Re 1 at time 3.
To ensure that the firm remains reasonably diversified, the firm will not commit an investment
exceeding Rs 75,000 for any project. The firm cannot borrow funds and therefore, the cash available for
investment at any time is limited to the cash in hand. The firm will earn interest at 8 per cent per annum by
parking the un-invested funds in money market investments. Assume that the returns from investments can
be immediately re-invested. For example, the positive cash flow received from project C at time 1 can
immediately be re-invested in project B. Formulate this problem as an LP model so as to maximize cash on
hand at time 3. [CA, 2000; Delhi Univ., MBA, 2007]
LP model formulation Let x1, x2, x3, x4 and x5 = Amount of rupees invested in investments A, B, C, D
and E, respectively.
si = Money invested in money market instruments at
time i (for i = 0, 1, 2).
Firm earns interest at 8 per cent per annum by parking the un-invested funds in money market
instruments, hence Rs s0, Rs s1 and Rs s2 which are invested in these instruments at times 0, 1 and 2 will
become 1.08s0, 1.08s1 and 1.08s2 at times 1, 2 and 3, respectively.
Note: Cash available for investment in time t = cash on hand at time t.
From the given data, it can be computed that at time 3:
Cash on hand = x1 × 0 + x2 × 1 + x3 × 0 + 1.9x4 + 1.5x5 + 1.08s2
1.08s2)
The LP model
= Rs (x2 + 1.9x4 + 1.5x5 +

Maximize (Cash on hand at time 3) Z = x2 + 1.9x4 + 1.5x5 + 1.08s2

subject to the constraints
At time 0: Total fund of Rs 1,00,000 is available for investing on projects A, C and D. That is x1 +
x2 + x3 + s0 = 1,00,000
At time 1: Rs 0.5x1, Rs 1.2x3, and Rs 1.08s0 will be available as a result of investment made at time 0. Since
Rs x2 and s1 are invested in project B and money market instruments, respectively at time 1,
therefore we write
0.5x1 + 1.2x3 + 1.08s0 = x2 + s1
At time 2: Rs x1; Rs 0.5x2 and Rs 1.08 s1 will be available for investment. As Rs x5 and Rs s2 are invested at
time 2. Thus
x1 + 0.5x2 + 1.08s1 = x5 + s2
Also, since the company will not commit an investment exceeding Rs 75,000 in any project,
therefore the constraint becomes: xi ≤ 75,000 for i = 1, 2, 3, 4, 5.
and x1, x2, x3, x4, x5, s0, s1, s2 ≥ 0.
2.8.4 Examples on Agriculture
Example 2.27 A cooperative farm owns 100 acres of land and has Rs 25,000 in funds available for
investment. The farm members can produce a total of 3,500 man-hours worth of labour during September –
May and 4,000 man-hours during June – August. If any of these man-hours are not needed, some members
of the firm would use them to work on a neighbouring farm for Rs 2 per hour during September – May and
Rs 3 per hour during June – August. Cash income can be obtained from the three main crops and two types
of livestock: dairy cows and laying hens. No investment funds are needed for the crops. However, each cow
will require an investment outlay of Rs 3,200 and each hen will require Rs 15.
In additon each cow will also require 15 acres of land, 100 man-hours during the summer. Each cow
will produce a net annual cash income of Rs 3,500 for the farm. The corresponding figures for each hen
are: no acreage, 0.6 man-hours during September – May; 0.4 man-hours during June – August, and an
annual net cash income of Rs 200. The chicken house can accommodate a maximum of 4,000 hens and the
size of the cattle-shed limits the members to a maximum of 32 cows.
Estimated man-hours and income per acre planted in each of the three crops are:
Paddy Bajra Jowar
Man-hours
September-May 40 20 25
June-August 50 35 40
Net annual cash income (Rs) 1,200 800 850
50 Operations Research: Theory and Applications

The cooperative farm wishes to determine how much acreage should be planted in each of the crops
and how many cows and hens should be kept in order to maximize its net cash income. Formulate this
problem as an LP model to maximize net annual cash income.
LP model formulation The data of the problem is summarized as follows:

Constraints Cows Hens Crop Extra Hours Total Paddy Bajra Jowar Sept–May June–Aug Availability

Man-hours
Sept–May 100 0.6 40 20 25 1 – 3,500 June–Aug 50 0.4 50 35 40 – 1 4,000 Land 1.5 – 1 1 1 – – 100 Cow 1 – –
– – – – 32 Hens – 1 – – – – – 4,000 Net annual cash
income (Rs) 3,500 200 1,200 800 850 2 3

Decision variables Let

x1 and x2 = number of dairy cows and laying hens, respectively.
x3, x4 and x5 = average of paddy crop, bajra crop and jowar crop, respectively.
x6 = extra man-hours utilized in Sept–May.
in June–Aug.
The LP model
x7 = extra man-hours utilized

Maximize (net cash income) Z = 3,500x1 + 200x2 + 1,200x3 + 800x4 + 850x5 + 2x6 + 3x7
subject to the constraints
 (i) Man-hours: 100x1 + 0.6x2 + 40x3 + 20x4 + 25x5 + x6 = 3,500 (Sept-May duration) 50x1 +
0.4x2 + 50x3 + 35x4 + 40x5 + x7 = 4,000 (June-Aug duration)
(ii) Land availability: 1.5x1 + x3 + x4 + x5 ≤ 100
(iii) Livestock: (a) x1 ≤ 32 (dairy cows), (b) x2 ≤ 4,000 (laying hens)
and x1, x2, x3, x4, x5, x6, x7 ≥ 0.
Example 2.28 A certain farming organization operates three farms of comparable productivity. The output
of each farm is limited both by the usable acreage and by the amount of water available for irrigation. The
data for the upcoming season is as shown below:

Farm Usable Acreage Water Available

(in cubic feet)
1 400 1,500
2 600 2,000
3 300 900

The organization is considering planting crops which differ primarily in their expected profit per acre
and in their consumption of water. Furthermore, the total acreage that can be devoted to each of the crops is
limited by the amount of appropriate harvesting equipment available.

Crop Maximum Water Consumption Expected Profit

Acreage (in cubic feet) per Acre (Rs)
A 700 5 4,000
B 800 4 3,000
C 300 3 1,000

In order to maintain a uniform workload among the three farms, it is the policy of the organization that
the percentage of the usable acreage planted be the same for each farm. However, any combination of the
crops may be grown at any of the farms. The organization wishes to know how much of each crop should
be planted at the respective farms in order to maximize expected profit.
Formulate this problem as an LP model in order to maximize the total expected profit.
Linear Programming: Applications and Model Formulation 51

LP model formulation The data of the problem is summarized below:

Crop Farm Crop Expected

Requirement Profit per Acre
1 23
(in acres) (Rs)

A x11 x12 x13 700 4,000

B x21 x22 x23 800 3,000
C x31 x32 x33 300 1,000
Usable acreage 400 600 300
Water available per acre 1,500 2,000 900

Decision variables Let xij = number of acres to be allocated to crop i (i = 1, 2, 3) to farm j ( j = 1, 2) The
LP model
Maximize (net profit) Z = 4,000(x11 + x12 + x13) + 3,000(x21 + x22 + x23) + l,000(x31 + x32 + x33)
subject to the constraints
(i) Crop requirement
(a) x11 + x12 + x13 ≤ 700, (b) x21 + x22 + x23 ≤ 800, (c) x31 + x32 + x33 ≤ 300
(ii) Available acreage
(a) x11 + x21 + x31 ≤ 400, (b) x12 + x22 + x32 ≤ 600, (c) x13 + x23 + x33 ≤ 300
(iii) Water available (in acre feet)
 (a) 5x11 + 4x21 + 3x31 ≤ 1,500, (b) 5x12 + 4x22 + 3x32 ≤ 2,000, (c) 5x13 + 4x23 + 3x33 ≤ 900 (iv)
Social equality
xxx xxx
(a) 11 21 31 12 22 32
++ ++ xxx xxx
= , (b) 12 22 32 13 23 33
400 600 and xij ≥ 0 for all i and j.
xxx xxx
(c) 13 23 33 11 21 31
2.8.5 Examples on Transportation
++
= + + ++ ++
= , 600 300
300 400

Example 2.29 ABC manufacturing company wishes to develop its monthly production schedule for the
next three months. Depending upon the sales commitments, the company can either keep the production
constant, allowing fluctuation in inventory; or its inventories can be maintained at a constant level, with
fluctuating production. Fluctuating production makes overtime work necessary, the cost of which is
estimated
to be double the normal production cost of Rs 12 per
unit. Fluctuating inventories result in an inventory Month Production Capacity (units) Sales Regular
carrying cost of Rs 2 per unit/month. If the company
fails to fulfil its sales commitment, it incurs a Overtime (units)
shortage cost of Rs 4 per unit/month. The production 1 50 30 60 2 50 0 120 3 60 50 40
capacities for the next three months are in the table:

Formulate this problem as an LP model to minimize the total production cost.

[Delhi Univ., MBA, 2008]
LP model formulation The data of the problem is summarized as follows:

Month Production Capacity Sales

Regular Overtime
1 50 30 60
2 50 0 120
360 50 40
52 Operations Research: Theory and Applications

Normal production cost : Rs 12 per unit Overtime cost : Rs 24 per unit

Carrying cost : Rs 12 per unit per month Shortage cost : Rs 14 per unit per month Assume five sources
of supply: three regular and two overtime (because the second months overtime production is zero)
production capacities. The demand for the three months will be the sales during these months. All supplies
against the order have to be made and can be made in the subsequent month if it is not possible to make
them during the month of order, with additional cost equivalent to shortage cost, i.e. in month 2. The
cumulative production of months 1 and 2 in regular and overtime is 130 units while the orders are for 180
units. This balance can be supplied during month 3 at an additional production cost of Rs 4.
The given information can now be presented in matrix form as follows:
M1 M2 M3 Production (supply)
M1 12 14 16 50
M2 16 12 14 50
M3 20 16 12 60
M1(OT) 24 26 28 30
 M2(OT) 32 28 24 50
Sales (demand) 60 120 40
Decision variables Let xij = amount of commodity sent from source of supply i (i = 1, 2, . . ., 5) to
destination j ( j = 1, 2, 3)
The LP model
Minimize (total cost) Z = 12x11 + l4x12 + 16x13 + 16x21 + l2x22 + 14x23 + 20x31 + 16x32 + 12x33 + 24x41
24x53
subject to the constraints
+ 26x42 + 28x43 + 32x51 + 28x52 +

(i) Production (supply) constraints

(a) x11 + x12 + x13 = 50, (b) x21 + x22 + x23 = 50, (c) x31 + x32 + x33 = 60,
(d) x41 + x42 + x43 = 30, (e) x51 + x52 + x53 = 30
(ii) Sales (demand) constraints
(a) x11 + x21 + x31 + x41 + x51 = 160, (b) x12 + x22 + x32 + x42 + x52 = 120, (c) x13 +
x23 + x33 + x43 + x53 = 140
and xij ≥ 0 for all i and j.
Example 2.30 A trucking firm has received an order to move 3,000 tonnes of industrial material to a
destination 1,000 km away. The firm has available, at the moment, a fleet of 150 class-A 15-tonne trailer
trucks and another fleet of 100 class-B 10-tonne trailer trucks. The operating costs of these trucks are Rs 3
and Rs 4 per tonne per km, respectively. Based on past experience, the firm has a policy of retaining at least
one class-A truck with every two class-B trucks in reserve. It is desired to know how many of these two
classes of vehicles should be despatched to move the material at minimal operating costs. Formulate this
problem as an LP model.
LP model formulation Let x1 and x2 = number of class A and B trucks to be despatched, respectively.
The LP model
Minimize (total operating cost) Z = 3x1 + 4x2
subject to the constraints
15x1 + 10x2 ≤ 3,000
x 1 least one class
x 2149 ≤
≤
98
UV A truck with every two class-B
W truck in reserve)

(due to the policy of retaining at

and x x 1 2 , . ≥ 0
Example 2.31 A ship has three cargo loads – forward, after and centre. Their capacity limits are:

Weight (kg) Volume (cu cm)

Forward 2,000 1,00,000
Centre 3,000 1,35,000
After 1,500 30,000
Linear Programming: Applications and Model Formulation 53

The following cargos are offered to be carried in the ship. The ship owner may accept all or any part of
each commodity:

Commodity Weight (kg) Volume (cu cm) Profit (in Rs) per kg
A 6,000 60 60
B 4,000 50 80
C 2,000 25 50

In order to preserve the trim of the ship, the weight in each cargo must be proportional to the capacity
in kg. The cargo is to be distributed in a way so as to maximize profit. Formulate this problem as an LP
model.
LP model formulation xiA, xiB and xiC = weight (in kg) of commodities A, B and C to be accommodated
in the direction i(i = 1, 2, 3 – forward, centre
and after), respectively.
The LP model
Maximize (total profit) 123 123 123 = ++ + ++ + ++ 60 ( ) 80 ( ) 50 ( ) Z xx x xx x xx x AAA BBB CCC
subject to the constraints
x1B + x2B + x3B ≤ 4,000; x1B + x2B + x3B ≤ 4,000;
x1B + x2B + x3B ≤ 4,000; x1A + x1B + x1C ≤ 2,000
x1A + x2B + x3C ≤ 4,000; x3A + x3B + x3C ≤ 1,500
60x1A + 50x1B + 25x1C ≤ 1,00,000
60x2A + 50x2B + 25x2C ≤ 1,35,000
60x3A + 50x3B + 25x3C ≤ 1,30,000
and xxx iA iB iC ,, 0 ≥ , for all i.
2.8.6 Examples on Personnel
Example 2.32 Evening shift resident doctors in a government hospital work five consecutive days and have
two consecutive days off. Their five days of work can start on any day of the week and their schedule
rotates indefinitely. The hospital requires the following minimum number of doctors to work on the given
days:
Sun Mon Tues Wed Thus Fri Sat
35 55 60 50 60 50 45
No more than 40 doctors can start their five working days on the same day. Formulate this problem as
an LP model to minimize the number of doctors employed by the hospital.
[Delhi Univ., MBA (HCA), 2006]
LP model formulation Let xj = number of doctors who start their duty on day j ( j = 1, 2, . . ., 7) of the
week.
The LP model
Minimize (total number of doctors) Z = x1 + x2 + x3 + x4 + x5 + x6 + x7
subject to the constraints
(i) x1 + x4 + x5 + x6 + x7 ≥ 35, (ii) x2 + x5 + x6 + x7 + x1 ≥ 55
(iii) x3 + x6 + x7 + x1 + x2 ≥ 60, (iv) x4 + x7 + x1 + x2 + x3 ≥ 50
(v) x5 + x1 + x2 + x3 + x4 ≥ 60, (vi) x6 + x2 + x3 + x4 + x5 ≥ 50
(vii) x7 + x3 + x4 + x5 + x6 ≥ 45, (viii) xj ≤ 40
and x j ≥ 0 for all j.
Example 2.33 A machine tool company conducts on-the-job training programme for machinists. Trained
machinists are used as teachers for the programme, in the ratio of one for every ten trainees. The training
programme lasts for one month. From past experience it has been found that out of the ten trainees hired,
only seven complete the programme successfully and the rest are released.
Trained machinists are also needed for machining. The company’s requirement for machining for the
next three months is as follows: January 100, February 150 and March 200. In addition, the company
requires 250 machinists by April. There are 130 trained machinists available at the beginning of the year.
Pays per month are:
54 Operations Research: Theory and Applications

Each trainee : Rs 4,400

Each trained machinist
(machining and teaching) : Rs 4,900
Each trained machinist idle : Rs 4,700
Formulate this problem as an LP model to minimize the cost of hiring and training schedule and the
company’s requirements.
LP model formulation Let
 x1, x2 = trained machinist teaching and idle in January, respectively
x3, x4 = trained machinist teaching and idle in February, respectively
x5, x6 = trained machinist teaching and idle in March, respectively
The LP model
Minimize (total cost) Z = Cost of training programme (teachers and trainees) + Cost of idle machinists
+ Cost of machinists doing machine work (constant)
4,700 (x2 + x4 + x6)
subject to the constraints
= 4,400 (10x1 + 10x3+ 10x5) + 4,900 (x1 + x3 + x5) +

(i) Total trained machinists available at the beginning of January

= Number of machinists doing machining + Teaching + Idle
130 = 100 + x1 + x2 or x1 + x2 = 30
(ii) Total trained machinists available at the beginning of February
= Number of machinists in January + Joining after training programme
130 + 7x1 = 150 + x3 + x4 or 7x1 – x3 – x4 = 20
In January there are 10x1 trainees in the programme and out of those only 7x1 will become trained
machinists.
(iii) Total trained machinists available at the beginning of March
= Number of machinists in January + Joining after training
= programme in January and February
130 + 7x1 + 7x3 = 200 + x5 + x6
7x1 + 7x3 – x5 – x6 = 70
(iv) Company requires 250 trained machinists by April
130 + 7x1 + 7x3 + 7x5 = 250
7x1 + 7x3 + 7x5 = 120
and x1, x2, x3, x4, x5, x6 ≥ 0.
Example 2.34 The super bazzar in a city daily needs anything between 22 to 30 workers in the bazzar
depending on the time of day. The rush hours are between noon and 2 pm. The table indicates the number
of workers needed at various hours when the bazzar is open.
The super bazzar now employs 24 full-time workers, but also needs a few part-time workers. A part
time worker must put in exactly 4 hours per day, but can start any time between 9 am and 1 pm. Full- time
workers work from 9 am to 5 pm but are allowed an hour for lunch (half of the full-timers eat at 12 noon,
the other half at 1 am). Full-timers thus provide 35 hours per week of productive labour time.
The management of the super bazzar limits part-time total daily manpower cost.
hours to a maximum of 50 per cent of the day’s total
LP model formulation Let
requirement.
Part-timers earn Rs 28 per day on the average, while y = full-time workers
full-timers earn Rs 90 per day in salary and benefits
Time Period Number of Workers Needed
on the average. The management wants to set a
schedule that would minimize total manpower costs. 9 AM – 11 A M 22 11 AM – 1 P M 30 1 PM – 3 P M 25 3
Formulate this problem as an LP model to minimize PM – 5 P M 23

xj = part-time workers starting at 9 am, 11 am and 1 pm, respectively ( j = 1, 2, 3)

Linear Programming: Applications and Model Formulation 55

The LP model
Minimize (total daily manpower cost) Z = 90y + 28(x1 + x2 + x3)
subject to the constraints
1 yx x ++ ≥
(i) y x + ≥ 1 22 [9 am – 11 am], (ii) 230 1 2 [11 am – 1 pm],
 1 yx x ++≥
(iii) 225 2 3 [1 pm – 3 pm], (iv) y x + ≥ 3 23 [3 pm – 5 pm],
(v) y ≤ 24 [Full-timers available], (iv) 4 ( ) .( ) xxx 123 ++ ≤ +++ 050 22 30 25 23
[Part-timers’ hours cannot exceed 50% of total hours required each day which is the sum of the
workers needed each hour]
and y, xj ≥ 0 for all j.
Example 2.35 The security and traffic force, on the determine the minimum number of officers required
eve of Republic Day, must satisfy the staffing on duty at beginning of each time period.
requirements as shown in the table. Officers work
Time Number of Officers Required
8-hour shifts starting at each of the 4-hour intervals
as shown below. How many officers should report for 0:01 – 4:00 5
duty at the beginning of each time period in order to 4:01 – 8:00 7
minimize the total number of officers needed to 8:01 – 12:00 15
satisfy the requirements? 12:01 – 16:00 7 16:01 – 20:00 12 20:01 – 24:00 9
Formulate this problem as an LP model so as to

LP model formulation xi = number of officers who start in shift i (i = 1, 2, 3, . . ., 6) The

LP model
Minimize (number of officers required on duty) Z = xxxxxx 123456 +++++ subject
to the constraints
(i) 1 2 x x + ≥ 7 , (ii) 2 3 x x + ≥ 15 , (iii) 3 4 x x + ≥ 7 , (iv) 4 5 x x + ≥ 12 , (v) 5 6
x x + ≥ 9 , (vi) 6 1 x x + ≥ 5 and ≥ 0, j x for all j.

CONCEPTUAL QUESTIONS
(b) Discuss and describe the role of linear programming in
managerial decision-making, bringing out limitations, if any.
1. (a) What is linear programming? What are its major assumptions
[Delhi Univ., MBA, 2003]
and limitations? [Delhi Univ., MBA, Nov. 2005] 1. (b) Two of the major
limitations of linear programming are: assumption of ‘additivity’ and 7. Regardless of the way one defines linear programming, certain
‘single objective’. Elaborate by giving appropriate examples. [Delhi basic requirements are necessary before this technique can be
Univ., MBA, Nov. 2009 ] 2. Linear programming has no real-life employed to business problems. What are these basic
applications’. Do you agree with this statement? Discuss. [Delhi requirements in formulation? Explain briefly.
Univ., MBA, 2004 ] 8. Discuss in brief linear programming as a technique for resource
utilization. [Delhi Univ., MBA (HCA), 2004] 9. What are the four major
3. In relation to the LP problem, explain the implications of the
types of allocation problems that can be solved using the linear
following assumptions of the model:
programming technique? Briefly explain each with an example.
(i) Linearity of the objective function and constraints, (ii)
Continuous variables, 10. Give the mathematical and economic structure of linear
(iii) Certainty. programming problems. What requirements should be met in
order to apply linear programming?
4. What is meant by a feasible solution of an LP problem? 5. ‘Linear
programming is one of the most frequently and successfully applied 11. Discuss and describe the role of linear programming in managerial
operations research technique to managerial decisions.’ Elucidate decision-making bringing out limitations, if any.
this statement with some examples. [Delhi Univ., MBA, 2008] [Delhi Univ., MBA, 2004, 2009]
6. (a) What are the advantages and limitations of LP models?
56 Operations Research: Theory and Applications

SELF PRACTICE PROBLEMS

Problems on Production (units)

Process Input (units) Output Crude A Crude B Gasoline
1. A company sells two different products A and B, making a profit of X Gasoline Y
Rs 40 and Rs 30 per unit, respectively. They are both produced
153 5 8
with the help of a common production process and are sold in two
245 4 4
different markets. The production process has a total capacity of
30,000 man-hours. It takes three hours to produce a unit of A and The maximum available amount of crude A and B are
one hour to produce a unit of B. The market has been surveyed 200 units and 150 units, respectively. Market requirements show
and company officials feel that the maximum number of units of A that at least 100 units of gasoline X and 80 units of gasoline Y
that can be sold is 8,000 units and that of B is 12,000 units. must be produced. The profit per production run from process 1
Subject to these limitations, products can be sold in any and process 2 are Rs 300 and Rs 400, respectively. Formulate
combination. Formulate this problem as an LP model to maximize this problem as an LP model to maximize profit.
profit. 3. A firm places an order for a particular product at the beginning of
2. The manager of an oil refinery must decide on the optimal mix of each month and that product is received at the end of the month.
two possible blending processes of which the input and output per The firm sells during the month from the stocks and it can sell any
production run are given as follows: quantity.
 The prices at which the firm buys and sells vary every month.
The following table shows the projected buying and selling prices Nutritional Units of Nutritional Elements Basic Foods
for the next four months: Elements (Per 100 gm Serving of Hi-Pro Basic Foods)
Specifications
Month Selling Price (Rs) Purchase Price (Rs) (During the
12 3
Month) (Beginning of the Month)
Calories 350 250 200 300 Proteins 250 300 150 200
April – 75 Vitamin A 100 150 75 100 Vitamin C 75 125 150 100 Cost
May 90 75 per
June 60 60 serving (Rs) 1.50 2.00 1.20
July 75 –
What quantities of foods 1, 2, and 3 should be used? Formulate
As on April 1 the firm has no stocks on hand, and does not wish this problem as an LP model to minimize cost of serving. [Delhi
to have any stocks at the end of July. The firm has a warehouse Univ., MBA (HCA), 2009]
of limited size, which can hold a maximum of 150 units of the 9. Omega leather goods company manufactures two types of leather
product. soccer balls X and Y. Each type of ball requires work by two types
Formulate this problem as an LP model to determine the of employees – semi-skilled and skilled. Basically, the semi-skilled
number of units to buy and sell each month so as to maximize the employees use machines, while the skilled employees stitch the
profits from its operations. [Delhi Univ., MBA, 2007] balls. The available time (per week) for manufacturing each type
4. A manufacturer produces three models (I, II and III) of a certain of employee and the time requirement for each type of ball are
product. He uses two types of raw materials (A and B) of which given below:
4,000 and 6,000 units, respectively, are available. The raw
material requirements per unit of the three models are as follows:
The labour time of each unit of model I is twice that of model II
and three times that of model III. The entire labour force of the Type of Employee Manufacturing Time Time Available
factory can produce equivalent of 2,500 units of model I. A market Requirement (hr) (hr/week)
survey indicates that the minimum demand of the three models is:
500, 500 and 375 units, respectively. However, the ratios of the Ball X Ball Y
number of units produced must be equal to 3 : 2 : 5. Assume that
Semi-skilled 2 3 8 0 Skilled 4 6 150
the profit per unit of models I, II and III are Rs 60, 40 and 100,
respectively. Formulate this problem as an LP model to determine The cost of an hour of semi-skilled labour is Rs 5.50 and that of
the number of units of each product which will maximize profit. an hour of skilled labour is Rs 8.50. To meet the weekly demand
5. Consider a small plant which makes two types of automobile parts, requirements, at least 15 balls of type X and at least 10 balls of
say A and B. It buys castings that are machined, bored and type Y must be manufactured. Formulate this problem as an LP
polished. The capacity of machining is 25 per hour for A and 24 model so as to minimize cost of production.
per hour for B, capacity of boring is 28 per hour for A and 35 per 10. A pharmaceutical company has developed a new pill to be taken
hour for B, and the capacity of polishing is 35 per hour for A and by smokers that will nauseate them if they smoke. This new pill is
25 per hour for B. Castings for part A cost Rs 2 and sell for Rs 5 a combination of four ingredients that are costly and in limited
each and those for part B cost Rs 3 and sell for Rs 6 each. The supply. The available supply and costs are as follows:
three machines have running costs of Rs 20, Rs 14 and Rs 17.50
per hour. Assuming that any combination of parts A and B can be Ingredient Supply Cost
sold, formulate this problem as an LP model to determine the Availability (kg) (Rs/kg)
product mix which would maximizes profit.
1 22 28
6. On October 1, a company received a contract to supply 6,000 units 2 18 25
of a specialized product. The terms of contract require that 1,000 3 20 52
units of the product be shipped in October; 3,000 units in 4 24 26
November and 2,000 units in December. The company can
manufacture 1,500 units per month on regular time and 750 units
per month in overtime. The manufacturing cost per item produced Blending requirements for this new pill are as follows: (i) Ingredient
during regular time is Rs 3 and the cost per item produced during 1 must be at least 45 per cent of the total quantity, but cannot
overtime is Rs 5. The monthly storage cost is Re 1. Formulate this exceed 60 per cent of the total. (ii) Ingredients 2 and 3 must each
problem as an LP model so as to minimize total costs. [Delhi comprise at least 10 per cent of the mixture, but their combined
Univ., MBA, 1999] percentage cannot exceed 25 per cent of the total quantity.
(iii) Ingredient 4 must not be more than 50 per cent of the total
7. A wine maker has a stock of three different wines with the following quantity. Additionally, at least 25 kg of the pill must be
characteristics: produced.
Wine Proofs Acids% Specific Gravity Stock (gallons) A 27 0.32 Formulate this problem as an LP model to determine
1.70 20 B 33 0.20 1.08 34 C 32 0.30 1.04 22 optimum blending of ingredients.
[Delhi Univ., MBA (HCA), 2008]
A good dry table wine should be between 30 and 31 degree proof, 11. A paint manufacturing company manufactures paints at two of its
it should contain at least 0.25% acid and should have a specific plants. Firm orders have been received from three large
gravity of at least 1.06. The wine maker wishes to blend the three contractors. The firm has determined that the following shipping
types of wine to produce as large a quantity as possible of a cost data is appropriate for these contractors with respect to its
satisfactory dry table wine. However, his stock of wine A must be two plants:
completely used in the blend because further storage would
cause it to deteriorate. What quantities of wines B and C should (gallon)
be used in the blend. Formulate this problem as an LP model. Contractor Order Size Shipping Cost/Gallon (Rs) From
Plant 1 From Plant 2
8. ABC foods company is developing a low-calorie high-protein diet
supplement called Hi-Pro. The specifications of Hi-Pro have been A 1,750 1.80 2.00 B 1,500 2.60 2.20 C 1,500 2.10
established by a panel of medical experts. These specifications 2.25
along with the calorie, protein and vitamin content of three basic
Each gallon of paint must be blended and tinted. The
foods, are given in the following table:
company’s costs with respect to these two operations at both of
 the plants are as follows: maximize sales.
15. A manufacturer of metal office equipments makes desks, chairs,
Plant/Operation Hours Cost/hour Hours Required (Rs) cabinets and book cases. The work is carried out in the three
Available major manufacturing departments: Metal stamping, Assembly and
per Gallon Finishing. Exhibits, A, B the and C give the requisite data of the
problem.
Blending
Plant 10.10 3.80 300 58 Operations Research: Theory and Applications
Blending
Tinting 0.25 3.20 360 Plant 20.15 4.00 600 Exhibit A
Tinting 0.20 3.10 720
Formulate this problem as an LP model. Department Time Required per Unit Available of Product (hrs)
Products Time per
12. Vitamins A and B are found in foods F1 and F2. One unit of food F1
contains three units of Vitamin A and four units of Vitamin Desk Chair Cabinet Bookcase Week (hrs)
Linear Programming: Applications and Model Formulation 57 Stamping 4 2 3 3 1,800 Assembly 10 6 8 7 1,200 Finishing
10 8 8 8 1,800
B. One unit of food F2 contains six units of Vitamin A and three Exhibit B
units of Vitamin B, One unit of food F1 and F2 cost Rs 4 and 5,
respectively. The minimum daily requirement (for a person) of Department Cost (Rs) of Operation per Unit of Product Desk
Vitamins A and B is 80 and 100 units, respectively. Assuming that Chair Cabinet Bookcase
anything in excess of the daily minimum requirement of A and B is
not harmful. Formulate this problem as an LP model to find out Stamping 15 8 12 12 Assembly 30 18 24 21 Finishing 35 28
the optimum mixture of food F1 and F2 at the minimum cost which 25 21
meets the daily minimum requirement of Vitamins A and B. [Delhi Exhibit C: Selling price (Rs) per unit of product
Univ., MBA (HCA), 2009] Desk : 175 Chair : 95 Cabinet : 145 Bookcase : 130 In order
13. The Omega Data Processing Company performs three types of to maximize weekly profits, what should be all production
activities: payrolls, account receivables, and inventories. The programme? Assuming that the items produced can be sold,
profit and time requirements for keypunch, computation and office which department needs to be expanded for increasing profits?
printing for a ‘standard job’ are shown in the following table: Formulate this problem as an LP model.
16. The PQR stone company sells stone procured from any of three
Job (Rs)
Job Profit/Standard Time Requirement (Min.) adjacent quarries. The stone sold by the company conforms to
Keypunch Computation Print the following specification:
Material X equal to 30%
Payroll 275 1,200 20 100 A/c Receivable 125 1,400 15 60 Material Y equal to or less than 40%
Inventory 225 800 35 80 Material Z between 30% and 40%
Stone from quarry A costs Rs 10 per tonne and has the following
Omega guarantees overnight completion of all standard jobs. Any properties:
job scheduled during the day can be completed during the day or Material X : 20%, Material Y : 60%, Material Z : 20%
night. Any job scheduled during the night, however, must be Stone from quarry B costs Rs 12 per tonne and has the following
completed during the night. The capacity for both day and night properties:
are shown in the following table: Material X : 40%, Material Y : 30%, Material Z : 30%
Stone from quarry C costs Rs 15 per tonne and has the following
Capacity (Min.) Keypunch Computation Print properties:
Day 4,200 150 400 Night 9,200 250 650 Material X : 10%, Material Y : 40%, Material Z : 50%
From what quarries should the PQR stone company procure
Formulate this problem as an LP model to determine the ‘mix’ of rocks in order to minimize cost per tonne of rock? Formulate this
standard jobs that should be accepted during the day and night. problem as an LP model. [Delhi Univ., MBA, 2006]
[Delhi Univ., MBA, 2008]
17. A manufacturer produces three models (I, II and III) of a certain
14. PQR coffee company mixes South Indian, Assamese and imported product. He uses two types of raw material: A and B of which
coffee for making two brands of coffee: plains X and plains XX. 4,000 and 6,000 units are available, respectively. The raw
The characteristics used in blending the coffee include strength, material requirements per unit of the three models are given
acidity and caffeine. The test results of the available supplies of below:
South Indian, Assamese and imported coffee are shown in the
following table: Raw Material Requirements per Unit of Given Model I II III

Price per kg Strength Acidity Per cent Supply (Rs) Index A 235
Index Caffeine Available B 427
(kg) 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
South Indian, 30 6 4.0 2.0 40,000 Assamese, 40 8 3.0 2.5
factory can produce the equivalent of 2,500 units of model I. A
20,000 Imported, 35 5 3.5 1.5 15,000
market survey indicates that the minimum demand for the three
The requirements for plains X and plains XX coffees are given in models is 500, 500 and 375 units, respectively. However, the
the following table: 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 is Rs 60, Rs
Plains Price Minimum Maximum Maximum Quantity Coffee per 40 and Rs 100, respectively. Formulate this problem as an LP
kg Strength Acidity Per Demanded (Rs) Caffeine (kg) Cent model to determine the number of units of each product that will
the maximize amount of profit.
X 45 6.5 3.8 2.2 35,000 XX 55 6.0 3.5 2.0 25,000
18. A company manufactures two models of garden rollers: X and Y.
Assume that 35,000 kg of plains X and 25,000 kg of plains XX, When preparing the 2008 budget, it was found that the limitations
are to be sold. Formulate this problem as an LP model to on capacity were represented by the following weekly production
 maxima:
Data Item Magazines
123
Model Foundry Machine-shop Contribution per Model (Rs) Reader characteristics
X 100 200 120 Y 240 150 90 (a) Age: 25–35 yrs 70% 80% 40% (b) Education level: Graduation
and above 80% 60% 50% (c) Income: Rs 5,000 and above 60% 70%
In addition, the material required for model X was in short supply 40% Minimum number of advertisements 20 10 5 Maximum number
and sufficient only for 140 units per week, guaranteed for the of advertisements 50 40 30 Cost per advertisement (Rs) 1,000 700
year. Formulate this problem as an LP model to determine the 500 Readership 3,20,000 5,00,000 2,00,000
optimal combination of output.
19. A company manufacturing television and radio sets has four major Additionally, the company has specified that the relative
departments: chassis, cabinet, assembly and final testing. The importance of the reader characteristics should be weighted as
monthly capacities of these are as follows: follows:

Television Radio Reader Characteristics Weightage

Chassis 1,500 or 4,500 Cabinet 1,000 or 8,000 Assembly Age: 25–35 yrs 0.4
2,000 or 4,000 Testing 3,000 or 9,000 Graduate and above 0.4
Income ≥ Rs 5,000 0.2
The contribution of a television set is Rs 500 and that of a radio
set Rs 250. Assume that the company can sell any quantity of At this point in time the company has Rs 5,00,000 to spend.
either product. Formulate this problem as an LP model to Formulate this problem as an LP model to maximize the effective
determine the optimal combination of television and radio sets. exposure level.
20. A company wants to plan production for the ensuing year so as to 23. The owner of Metro Sports wishes to determine the number of
minimize the combined cost of production and inventory storage. advertisements to be placed in the selected three monthly
In each quarter of the year, demand is anticipated to be 65, 80, magazines A, B and C. His objective is to advertise in such a way
135 and 75 respectively. The product can be manufactured during that total exposure to principal buyers of expensive sports goods
regular time at a cost of Rs 16 per unit produced, or during is maximized. The percentage of readers for each magazine is
overtime at a cost of Rs 20 per unit. The table given below gives known. Exposure to any particular magazine is the number of
data pertinent to production capacities. The cost of carrying one advertisements placed multiplied by the number of principal
unit in inventory per quarter is Rs 2. The inventory level at the buyers. The following data may be used:
beginning of the first quarter is zero.
Magazines
A BC
Quarter Capacities (units) Quarterly Regular Time Overtime
Demand Readers 1 lakh 0.6 lakh 0.4 lakh Principal buyers 10 % 15 % 7
% Cost per advertisement (Rs) 5,000 4,500 4,250
1 80 10 65
2 90 10 80 The budget amount is at the most Rs 2,00,000 for the
3 95 20 135 advertisements. The owner has already decided that magazine A
4 70 10 75 should have no more than six advertisements and that B and C
each should have at least two advertisements. Formulate this
Formulate this problem as an LP model so as to minimize the
problem as an LP model to determine the number of
production plus storage costs for the entire year. [Delhi Univ.,
advertisements that should be placed in each magazine.
MBA, 2005]
24. The XYZ company is preparing a proposal for an advertising
Problems on Marketing
campaign for a client who is a publisher of law books. An optimal
21. Suppose a media specialist has to decide how to allocate allocation of advertising funds to maximize the total number of
advertising in three media vehicles. Let xi be the number of exposures has to be made for the client. The relevant
messages carried in the media, i = 1, 2, 3. The unit costs of a characteristics of the three alternative publications are shown in
message in the three media are Rs 1,000, Rs 750 and Rs 500. the following table:
The total budget available for the campaign is Rs 2,00,000 period
of a year. The first media is a monthly magazine and it is desired Home Home and Care
to advertise not more than one insertion in one issue. At least six Beautiful Garden (Rs)
messages should appear in the second media. The number of (Rs) (Rs)
messages in the third media should strictly lie between 4 and 8. Cost/advertisement 600 800 450 Max. number of ads 12 24 12
The expected effective audience for unit message in the media Min. number of ads 3 6 2 Characteristics
vehicles is shown below: Homeowner 80% 70% 20% Income: Rs 10,000 or more 70%
80% 60% Occupation: gardener 15% 20% 40% Audience size
Vehicle Expected Effective Audience
6,00,000 8,00,000 3,00,000
1 80,000 Linear Programming: Applications and Model Formulation 59
2 60,000
3 45,000
The relative importance of the three characteristics is:
Formulate this problem as an LP model to determine the optimum Homeowner, 0.4; Income, 0.2; Gardener, 0.4. The advertising
allocation that would maximize total effective audience. 22. An budget is Rs 2,00,000. Formulate this problem as an LP model to
advertising company is planning an advertisement campaign for a new find the most effective number of exposures in each magazine.
product recently introduced in the market. It is decided to insert
advertisements in three leading magazines. The Problems on Finance
25. A gambler plays a game that requires dividing bet money among
four different choices. The game has three outcomes. The
company has made a careful analysis of three available media, following table gives the corresponding gain (or loss) per rupee
and has compiled the following set of relevant data: deposited in each of the four choices for the three outcomes:
 total investment to be allocated.
Outcome Gain (or loss) Deposited in per Rupee Given 29. The Agro Promotion Bank is trying to select an investment portfolio
Choice for a cotton farmer. The bank has chosen a set of five investment
1234 alternatives, with subjective estimates of rates of return and risk
as follows:
1 – 3 4 – 7 15 2 5 – 3 9 4 33– 9 10 – 8
Investment Annual Rate of Return Risk
Assume that the gambler has a total of Rs 500 with which he may
play only once. The exact outcome of the game is not known in Tax-free municipal bonds 6.0 1.3 Corporate bonds 8.0 1.5
advance and in the face of this uncertainty the gambler decides to High grade common stock 5.0 1.9 Mutual fund 7.0 1.7 Real
make the allocation that would maximize the minimum return. estate 15.0 2.7
Formulate this problem as an LP model.
The bank officer incharge of the portfolio would like to maximize
26. An investor has money-making activities A1, A2, A3 and A4. He has the average annual rate of return on the portfolio. However, the
only one lakh rupees to invest. In order to avoid excessive wealthy investor has specified that the average risk of the
investment, no more than 50 per cent of the total investment can portfolio should not exceed 2.0. The investor and does not want
be placed in activity A2 and/or activity A3. Activity A1 is very more than 20% of the investment to be put into real estate.
Formulate this problem as an LP model.
conservative, while activity A4 is speculative. To avoid excessive
30. Raj, a retired government officer, has recently received his
speculation, at least Re 1 must be invested in activity A1 for every
retirement benefits, viz., provident fund, gratuity, etc. He is
Rs 3 invested in activity A4. The data on the return on investment contemplating how much money he should invest in various
is as follows: alternatives open to him so as to maximize return on his
investment. The investment alternatives are: government
Activity Anticipated Return on Investment (%)
securities, fixed deposits of a public limited company, equity
A1 10 shares, time deposits in a bank, and house construction. He has
A2 12 made a subjective estimate of the risk involved on a five point
scale. The data on the return on investment, the number of years
A3 14
for which the funds will be blocked to earn this return on
A4 16 investment and the subjective risk involved are as follows:
The investor wishes to know how much to invest in each in order
activity to maximize the total return on the investment. Formulate Return (%) Number Risk
this problem as an LP model. of Years
27. The board of directors of a company has given approval for the Government securities 16 15 1 Company deposits 13 13 3
construction of a new plant. The plant will require an investment Time deposits 10 15 2 Equity share 20 16 5 House
of Rs 50 lakh. The required funds will come from the sale of a construction 25 10 1
proposed bond issue and by taking loans from two financial
He is wondering as to what percentage of funds he should invest
corporations. For the company, it will not be possible to sell more
in each alternative so as to maximize the return on investment.
than Rs 20 lakh worth of bonds at the proposed rate of 12%.
He has decided that the risk should not be more than 4, and
Financial corporation A will give loan up to Rs 30 lakh at an
funds should not be locked up for more than 15 years. He would
interest rate of 16% but insists that the amount of bond debt plus
necessarily invest at least 25% in house construction. Formulate
the amount owned to financial corporation B be no more than
this problem as an LP model.
twice the amount owed to financial corporation A. Financial
corporation B will loan the same amount as that loaned by 31. A dealer of used scooters wishes to stock up his lot to maximize
financial corporation A but it would do so at an interest rate of his profit. He can select scooters A, B and C which are valued on
18%. Formulate this problem as an LP model to determine the wholesale at Rs 5,000, Rs 7,000 and Rs 8,500 respectively.
amount of funds to be obtained from each source in a manner These can be sold at Rs 6,000, Rs 8,500 and Rs 10,500,
that minimizes the total annual interest charges. respectively. For each type of scooter, the probabilities of sale
are:
28. An investor wishes to diversify his portfolio and make due
allowance for long-term potentialities, but at the same time wishes Type of scooter : A B C Prob. of sale in 90 days : 0.7 0.8 0.6
to maximize his current dividend income. He has considered For every two scooters of B-type he should buy one scooter of
various securities in which he might invest, and has classified type A or type C. If he has Rs 1,00,000 to invest, what should he
them into four types: buy in order to maximize his expected gain. Formulate this
Type A : Relatively high element of risk, with commensurately problem as an LP model.
high dividend and considerable growth potential.
Type B : Speculative stock with considerable risk, high dividends,
but less growth potential than type A. 32. A transport company is considering the purchase of new vehicles
60 Operations Research: Theory and Applications for transportation between Delhi airport and hotels in the city.
There are three vehicles under consideration – station wagons,
Type C : Stock with little risk, considerable growth potential, but mini buses and large buses. The purchase price would be Rs
relatively low dividend income at present. 2,45,000 for each station wagon, Rs 3,50,000 for a mini bus and
Type D : Stock with little risk, not much growth potential, and fairly Rs 5,00,000 for a large bus. The board of directors has
high dividends. authorized a maximum amount of Rs 50,00,000 for these
Because of the element of risk, the investor wishes to restrict purchases. Because of the heavy air travel involved, the new
purchases of types A and B to not more than 30% of his vehicles would be utilized at maximum capacity, regardless of the
investment. type of vehicles purchased. The expected net annual profit would
be Rs 15,000 for the station wagon, Rs 35,000 for the mini bus,
To enhance prospects for long-term growth of his invest ments,
and Rs 45,000 for the large bus. The company has hired 30 new
he wishes to have at least 40% of his total outlay in types A and
drivers for the new vehicles. They are qualified drivers for all the
C. Within these restrictions, he wishes to maximize his current
three types of vehicles. The maintenance department has the
dividend income. Total investment is Rs 1,00,000. Dividend
capacity to handle an additional 80 station wagons. A mini bus is
returns on the four types of investments are A: 6%, B: 7%, C: 3%,
equivalent to 5/3 station wagons and each large bus is equivalent
D: 5%. Formulate this problem as an LP model to suggest the
to two station wagons in terms of their use of the maintenance
 department. Formulate this problem as an LP model to determine suppliers in unlimited quantities with the following percentage (in
optimal number of each type of vehicle to be purchased in order terms of weight) of high quality copper and unfit scrap:
to maximize profit.
[Delhi Univ., MBA, Oct. 2000] Supplier A Supplier B
33. The managers of several cattle feed lots are interested in Copper 25% 75% Unfit scrap 5 % 10%
determining how many of each of several types of livestock feeds
should be purchased in order to satisfy the nutritional The cost per kg of metal purchased from supplier A and supplier
requirements for their livestock. They wish to purchase such food B is Re 1 and Rs 4, respectively. Formulate this problem as an LP
in a manner that minimizes the cost of feeding their livestock. model so as to determine the optimal quantities of metal that the
Relevant costs and nutritional data are as below: dealer should purchase from each of the two suppliers in order to
minimize total the purchase cost.
Nutrient [Delhi Univ., MBA, 2008]
Required Units of Nutritional Element Minimum Alfa Corn37. A company needs 50 new machines. The machines have an
economic life of two years and can be purchased for Rs 4,500 or
Soyabean SorghumNutrient Requirements be leased for Rs 2,800 per year. The purchased machines, at the
A 40 50 30 60 500 end of two years, have no salvage value. Company has Rs
B 30 60 35 40 750 1,00,000 in uncommitted funds that can be used for the purchase
C 25 30 25 50 600 or the lease of machines at the beginning of year 1. The company
Cost per can obtain a loan of upto Rs 2,00,000 at 18 per cent interest per
unit (Rs) 1.00 1.25 0.95 1.35 year. According to the terms of loans, the company has to repay
the amount borrowed plus the interest at the end of each year.
Formulate this problem as an LP model. Each machine can earn Rs 3,000 per year. The earnings from the
34. Old hens can be bought at Rs 100 each and young ones at Rs 250 first year can be used to lease costs and the repayment of debt at
each. The old hens lay 3 eggs per week and the young ones 5 the start of the second
eggs per week, each egg being worth 50 paise. A hen costs Rs Linear Programming: Applications and Model Formulation 61
20 per week to be fed. There are only Rs 8,000 available to be
spent on purchasing the hens and at the most 20 hens can be year. The company wants to minimize the total cost of using 50
accommodated in the space. Formulate this problem as an LP machines over a two-year period. The objective is to minimize the
model to determine each kind of hen that should be bought in costs of purchasing machines or leasing machines during the
order to yield the maximum profit per week. years 1 and 2, and to minimize the interest payments on funds
35. A pension fund manager is considering investing in two shares A borrowed to obtain the machines. Formulate this problem as a
and B. It is estimated that: linear programming problem.
(i) Share A will earn a dividend of 12 per cent per annum and [Delhi Univ., MBA, 2009]
share B, 4 per cent per annum. 38. A trucking company with Rs 40,00,000 to spend on new equipment
(ii) Growth in the market value in one year of share A will be 10 is contemplating three types of vehicles. Vehicle A has a 10 tonne
paise per Re l invested and in B, 40 paise per Re 1 payload and is expected to average 35 km per hour. It costs Rs
invested. 80,000. Vehicle B has a 20-tonne payload and is expected to
He requires to invest the maximum total sum which will give: (i) average 30 km per hour. It costs Rs 1,30,000. Vehicle C is a
dividend income of at least Rs 600 per annum; and (ii) growth modified form of vehicle B; it carries sleeping quarters for one
in one year of at least Rs 1,000 on the initial investment. driver and then reduces its capacity to 18 tonnes and raises the
Formulate this problem as an LP model to compute the minimum cost to Rs 1,50,000. Vehicle A requires a crew of one average
sum in order to be invested to meet the manager’s objective. 36. A man, and if driven on three shifts per day, could be run for an
scrap metal dealer has received an order from a customer for at least average of 18 hours per day. Vehicles B and C require a crew of
2,000 kg of scrap metal. The customer requires that at least 1,000 kg two men each, while B would be driven 18 hours per day with
of the shipment of the metal be high quality copper that can be melted three shifts, C however would average 21 hours per day. The
down and further used to produce copper tubings. Furthermore, the company has 150 drivers available each day and would find it
customer will not accept delivery of the order if it contains more than very difficult to obtain further crews. Maintenance facilities are
175 kg of metal that he deems unfit for commercial use, i.e. metal that such that the total number of vehicles must not exceed 30. How
contains an excessive amount of impurity and cannot be melted down many vehicles of each type should be purchased if the company
and defined profitably. wishes to maximize its capacity in tonne-kms per day? Formulate
this problem as an LP model. [Delhi Univ., MBA, 2009]

The dealer can purchase scrap metal from two different

HINTS AND ANSWERS

UV
1. Let x1, x2 = number of units of products A and B to be
W ,,
produced,
respectively. 123
4 2 7 6 000
Max Z = 40x1 + 30x2 xx x
subject to 3x1 + x2 ≤ 3,000 (Man-hours) ++≤
subject to 2 3 5 4 000 123
xxx (Raw material requirement)
++≤
1
1
 x1 ≤ 8,000 ; x2 ≤ 1,200 (Marketing)
+ +≤ 2 500 , (Production limitation) xxx 123

2
3
and x1, x2 ≥ 0.
2. Let x1, x2 = number of productive runs of process 1 and 2,
xxx 123 ≥≥≥ 500 500 375 ; ; (Market demand)
respectively. 1 1 1 1
12 23
5 xx xx = = ; (Ratios of production) 3

2
2
Max Z = 300x1 + 400x2

UV UV 5. Let x1 and x2 = parts of A and B per hour

W W manufactured, respectively.

xx 5 4 100
+≤ xx 20 14 17.50 (5 6 ) 2.00 +−
subject to 5 4 200 +≥ 25 28 35 xx x
12 12 ++ +  
xx 8 4 80 
+≤ xx 20 14 17.50
Max Z = 1 2 1 3.00
3 5 150 +≥
12 (Max amount of crude A and B)

(Market requirement of gasoline X and Y)

12
xxx yy y 123 123 ++=++
and x1, x2 ≥ 0.
3. Let xi = number of units purchased per month and x y i i , ≥ 0 for all i.
 − ++ +   4. Let x1, x2 and x3 = number of units of models I, II and III,
24 35 25 x 
(i) 1; (ii) 1; (iii) 1
2 subject to 12 12 12 25 24 28 35 35 25
= 1.20x1 + 1.40x2 (Manufacturing capacity)
and x x 1 2 , . ≥ 0
+≤ +≤ +≤ xx xx xx
(i = 1, 2, 3 – April, May, June) 6. Let xijk = number of units manufactured in month i (1,
2, 3 – Oct., Nov., Dec.) during shift
yi = number of units sold per month
(i = 1, 2, 3 – May, June, July) j ( j = 1, 2 – regular, overtime) and shipped in month k (k
= 1, 2, 3 – Oct., Nov., Dec.)
Max Z = (90y1 + 60y2 + 75y3) – (75x1 + 75x2 + 60x3) subject
to y1 ≤ x1 ≤ 150 Min Z = 3x111 + 5x121 + 4x112 + 6x122 + 5x113 + 7x123 + 3x212
y2 ≤ x1 + x2 – y1 ≤ 150 + 5x222 + 4x213 + 6x223 + 3x313 + 5x323
y3 ≤ x1 + x2 + x3 – y1 – y2 ≤ 150
respectively to be 212 213 1 500
manufactured subject to
xxx ++ ≤ , U |
Max Z = 60x1 + 40x2 + 111 112 113
1 500
,
V W|
(Regular time)
100x3 +≤ ≤
xx 1 500
313 ,
x
62 Operations Research: Theory and Applications
222 223 manufactured at plant i (i = 1,
750 750 x1 + x2 + x3 + x4 ≥ 25 (Total 2) and
++ ≤ xxx requirement)
U | (Overtime) and x1, x2, x3, x4 ≥ 0.
V W|
121 122 123
+≤xx 11. Let xij = gallons of paint
x ≤ = 1, 2, 3) Min
323 shipped to contractor j ( j
750 (production
x111 + x121 = 1,000 x121 + x122 + x212 + x222 = 3,000
 x113 + x123 + x213 + x223 + x313 + x323 = 2,000 Z = (x11 + x12 + x13) {(0.10) (3.80) + (0.25) (3.20)} + (x21 +
and xijk ≥ 0 for all i, j, k. x22 + x23) {(0.15) (4.00) + (0.20) (3.10)} + 1.80x11 +
2.00x21 + 2.60x12 + 2.20x22 + 2.10x13 + 2.25x23
7. Let x1, x2 = number of gallons of wine B and C in the blend,
respectively. = 2.98x11 + 3.78x12 + 3.28x13 + 3.22x21 + 3.42x22
cost + shipping cost)
12 22
Max Z = 20 + x1 + x2 ( .) . . +=
. 20 0 32 0 2 0 3
subject to 3020 27 33 32 ⋅+ + xx
13 23

≤⋅+ + + +≥ x x U | ,
V W| , (Order size)
+ 3.47x23
+ +≤ ( ) x x
subject to x x + =
12 750
2031 11 21
xx 1 500
+=
12
xx 1 500
(Resultant degrees proof of blend)
xxx
12
200 25 ++ ≤
( )( . ) 0 10 300 1
(Acidity) 11 12 13 Plant 
xx 
( )( . ) xxx
Plant (Blending)
++ ≤
12 21 22 23 0 15 600 2
++ ≤
0 25 360 1
( .) . . ( )( . ) xxx Plant
. 20 1 07 1 08 1 04 + +≥ x x 
⋅+ + 11 12 13 
12
201 06 ++ ≤ Plant (Tinting)
x x (Specific gravity)
12 xxx
21 22 23
x1 ≤ 34 (Quality)
0 20 720 2 and x ij ≥ 0 for all i and j.
( )( . )
++≥
and x x 1 2 ≥ 0, . 123
75 125 150 100
8. Let x1, x2 and x3 = quantity of foods 1, 2 and 3 to be used,
xx x
respectively.
++≥
123
Min Z = 1.50x1 + 2.00x1 + 1.20x3
and , , 0.
subject to 12,
xy 12. Let x1 and x2 = number of vitamin units purchased of food F1 and
+≤ F2, respectively.
11
350 250 200 300 Min Z = 4x1 + 5x2
xx x subject to (i) 3x1 + 6x2 ≥ 80; (ii) 4x1 + 3x2 ≥ 100 and x1,
++≥ x2 ≥ 0.
123
250 300 150 200 13. Let xij = number of jobs accepted during day and night Max Z =
xxx 275 (x11 + x12) + 125 (x21 + x22) + 225 (x31 + x32) subject to 1,200
+ +≥ (x11 + x12) + 1,400 (x21 + x22) + 800 (x31 + x32) ≤ 13,400
123
100 150 75 100 100 (x11 + x12) + 60 (x21 + x22)
xx x
xx x 123
+ 80 (x31 + x32) ≤ 1,050
≥
9. Let x1 and x2 = number of soccer balls of types X and Y, hrs) (Rs 5.50/hr) x2
respectively. + (6 hrs) (Rs 8.50/hr) x2 = 45x1 + 67.50x2 subject to 2x1 +
Min Z = (2 hrs) (Rs 5.50/hr) x1 + (4 hrs) (Rs 8.50/hr) x1 + (3 3x2 ≤ 180 (Semi-skilled hours) 4x1 + 6x2 ≤ 150 (Skilled
 hours) 100x12 + 60x22 + 80x32 ≤ 650
x1 ≤ 115 (Ball X) and xij ≥ 0 for all i and j.
x2 ≤ 110 (Ball Y) 14. For plain coffee X
and x1, x2 ≥ 110.
x11, x12 and x13 = quantity (in kg) of the three coffees,
10. Let xj = number of kg of ingredient j ( j = 1, 2, 3, 4) used in the respectively.
mixture
For plain coffee XX
Min Z = 28x1 + 25x2 + 52x3 + 26x4
x21, x22 and x23 = quantity (in kg) of the three coffees,
UV respectively.
W Max Z = 45 (30x11 + 40x12 + 35x13)
subject to x x + 55 (30x21 + 40x22 + 35x23)
22 18
subject 11 12 13
;
≤≤ 6 8 5 6.5
12 xx x
 ++ ≤  ++ ≤
++ ≥ 
; (Supplies)
20 24 4 3 3.5 3.8
xx xx x
11 12 13
≤≤
34 (Plain coffee X)
2 2.5 1.5 2.2
U xx x
11 12 13
0 55 0 45 0 45 0 45 0

1,200x12 + 1,400x22 + 800x32 ≤ 9,200

.. .. xxxx −−−≥

|| 
| ++ = 
1234 xxx 11 12 13 xx x
0 40 0 60 0 60 0 60 0 ....
35,000
xx xx V
−−−≥
1234
U
++≥ .
−+ + − ≥ 0 10 0 90 0 90 0 10 0 .. .. −− − + ≤ 1234
xxxx
| |
|| 6 8 5 60
V| W|
| xxx
12 34 ++≤
21 22 23
−+ + − ≤ 0 25 0 75 0 75 0 25 0 .... xx x
xx xx ++≤
1234 ...
.. 2 25 15 20
21 22 23
4 3 35 35 21 22 23
xxx
W
0 50 0 50 0 50 0 50 0 .... (Plain coffee XX)
xxxx
++= 21 22 23 25 000
(Mixing requirements) ,
15. Let x1, x2, x3 and x4 = quantities of four products to be
manufactured, respectively.
x11 + x21 ≤ 40,000; x12 + x22 ≤ 20,000 ;
Max Z = [175 – (15 + 30 + 35)] x1 + [95 – (8 + 18 + 28)] x2 +
x13 + x23 ≤ 15,000 [145 – (12 + 24 + 25)] x3 + [130 – (12 + 21 + 21)] x4 Max Z =
and xij ≥ 0 for all i and j. 95x1 + 41x2 + 84x3 + 76x4
 subject to 1234 4 2 3 3 800, xxxx +++≤ xxx
++≤
10 6 8 7 1 200 1234 xxxx +++ ≤ , 123

1234 10 8 8 8 800 xx xx +++≤

xx x
≤ ≥ ≤≤
and xxxx 1234 ,,, ≥ 0
12 6 4 8
16. The data of the problem can be summarized as given below:
;, ,
12 3
Quarry A Quarry B Quarry C Specifications
Material X 20% 40% 10% = 30% Material Y 60% 30% 40% ≤ 40% and x x 1 2 , . ≥ 0
Material Z 20% 30% 50% between 30% and 40% 22. Let x1, x2 and x3 = number of advertisements in magazine 1, 2 and
Cost/tonne (Rs) 10% 12% 15% 3, repectively.

Let x1, x2, and x3 = number of tonnes procured from Max Z = 3,20,000 (0.7 × 0.4 + 0.8 × 0.4 + 0.6 × 0.2) x1 +
quarry A, B and C, respectively. 5,00,000 (0.8 × 0.4 + 0.6 × 0.4 + 0.7 × 0.2) x2
Min (total cost) Z = 10x1 + 12x2 + 15x3 + 2,00,000 (0.4 × 0.4 + 0.5 × 0.4 + 0.4 × 0.2) x3
= 2,30,400x1 + 35,000x2 + 88,000x3
subject to 2x1 + 4x2 + 4x3 = 3 (Material X) 6x1 + 3x2 + 4x3 ≤
4 (Material Y) 1,000 700 500 5,00,000
xxx
2x1 + 3x2 + 5x3 ≤ 4 ++≤
2x1 + 3x2 + 5x3 ≥ 3 (Material Z) subject to 123
17. Let x1, x2 and x3 = number of units of types I, II and III model, 20 50; 10 40; 5 30
respectively. ≤≤ ≤≤ ≤≤
xxx
113
Max (total profit) Z = 60x1 + 40x2 + 1,000x3
and x j ≥ 0 for all j.
subject to 2x1 + 3x2 + 5x3 ≤ 4,000 (Raw material A) 4x1 +
23. Let x1, x2 and x3 = number of insertions in magazines A, B and C,
2x2 + 7x3 ≤ 6,000 (Raw material B)
respectively.
xxx Max (total exposure) Z = (10% of 1,00,000)x1
23
+ (15% of 60,000)x2 + (7% of 40,000)x3
Linear Programming: Applications and Model Formulation 63
subject to 5 000 4 500 4 250 1 00 000 123 , , , ,, xx x
++≤ xx x 12 3 ≤≥≥ 622 ; ;
subject to (1/1,500) x1 + (1/4,500) x2 ≤ 1,
(1/1,000) x1 + (1/8,000) x2 ≤ 1, and xx x 123 ,, . ≥ 0
(1/2,000) x1 + (1/4,000) x2 ≤ 1, 24. Let xj = number of advertisements in media j ( j = 1, 2, 3). Media
Effectiveness coefficient
(1/3,000) x1 + (1/9,000) x2 ≤ 1,
1 0.80 (0.4) + 0.70 (0.2) + 0.15 (0.4) = 0.52 2 0.70 (0.4)
and x1, x2 ≥ 0.
+ 0.80 (0.2) + 0.20 (0.4) = 0.52 3 0.20 (0.4) + 0.60 (0.2)
21. Let x1, x2 and x3 = number of messages carried in media 1, 2 and
+ 0.40 (0.4) = 0.36
3, respectively.
Max Z = 80,000x1 + 60,000x2 + 45,000x3 Max Z = 0.52 (6,00,000)x1 + 0.52 (8,00,000)x2
subject to 1 000 750 500 2 00 000 + 0.36 (3,00,000)x3
,,,
+ + ≤ 2,500 (Labour force) 1
subject to 600 800 450 2 00 000 123 xx x ++≤ , ,
23
x x 12 + ≤ 1 ; x x 12
3 2 = ; x x 23 x1 ≤ 12; x2 ≤ 24; x3 ≤ 12
= x1 ≥ 13; x2 ≥ 16; x3 ≥ 12
25 (Number of units produced)
and x1, x2, x3 ≥ 0.
x1 ≥ 500; x2 ≥ 500; x3 ≥ 375 (Market demand) 25. y = minimum expected gain per rupee deposited in the given
and x1, x2, x3 ≥ 0. choice j ( j = 1, 2, 3, 4) by the gambler
18. Let x1, and x2 = number of units of models X and Y, respectively. xj = amount of bet money used among four different choices,
Max Z = 120x1 + 90x2 respectively ( j = 1, 2, 3, 4)
Max Z = y
subject to x x 1 2
100 240
+ ≤ 1 ; x1 ≤ 140 200 150 ≥
subject to y
and x1, x2 ≥ 0. −+ − + 3 4 7 15
xx x x
 12 3 4 xx x x y
≥ −+ + 3 9 10 8
y 12 3 4
xx x x
53 9 4 ≥
19. Let x1 and x2 = number of manufactured, respectively. 12 3 4 xx xx ≤
television and radio sets to be −+ − ++ + 500
12 34

Max Z = 500x1 + 250x2

and xj may be negative, zero or positive.
subject to 5,000x1 + 2 × 7,000x2 ≤ 1,00,000 2
64 Operations Research: Theory and Applications
× 7,000x2 + 8,500x3 ≤
1,00,000
26. Let x1, x2, x3 and x4 = percentage of the total fund that
should be invested in activities and x1, x2, x3 ≥ 0.
A1, A2, A3 and 33. Let x1, x2, x3 = number of station wagons, minibuses
and larges buses, respectively to be purchased.
A4, respectively.
Max Z = 0.10x1 + 0.12x2 + 0.14x3 + 0.16x4 Max Z (total profit) = 15,000x1 + 35,000x2 + 45,000x3
subject to xxxx 1234 +++≤ 1 00 000 , , subject to x1 + x2 + x3 ≤ 30 (Availability of drivers) 2
(total money invested) ,, ,, ,, ,, xxx
45 000 3 50 000 5 00 000 50 00 000 123
x x xx xx 23 1234 +≤ +++ 0 50 .( )
++≤
1 (Budget)
x x 14
≥ 3
and x j ≥ 0 for all j.
3
1
27. Let x1 = bond debt to be obtained.
++≤ 80 (Maintenance capacity) xx x 12 3

5 2
12 3 4 5
x2 and x3 = loan to be obtained from financial corporations A
and B, respectively. and x1, x2, x3 ≥ 0.
Min Z = 0.12x1 + 0.16x2 + 0.18x3 Note: 1 S.W. = (3/5) M.B., because (5/3) S.W. = 1 M.B.; and 1
subject to xx x 123 ++= 50 S.W. = (3/5) M.B., because (5/3) S.W. = 1 M.B.
x x 1 2 ≤ ≤ 20; 30 34. Let xj = number of units of food type j ( j = 1, 2, 3, 4) used. Min
xx x xx 13 2 12 +≤ ≤ 2 ; (total cost) Z = 1.00x1 + 1.25x2 + 0.95x3 + 1.35x4 subject to 40x1 +
and x x 1 2 , . ≥ 0 50x2 + 30x3 + 60x4 ≥ 500 30x1 + 60x2 + 35x3 + 40x4 ≥ 750
28. Let x1, x2, x3 and x4 = amount of money to be invested in A, B, C 25x1 + 30x2 + 25x3 + 50x4 ≥ 600
and D securities, respectively. and x1, x2, x3, x4 ≥ 0.
Max (current dividend return) 35. Let x1 and x2 = number of old hens and young hens bought,
Z = 0 06 0 07 0 03 0 05 1234 .. .. xxxx +++ respectively.

subject to 1234 xx xx +++≤1,00,000 Max Z = 0.5 (3x1 + 5x2) – (x1 + x2) = 0.5x2 – 1.5x1 subject

12x x + ≤ 30,000 ; 1 3 x x + ≥ 40,000 to 100x1 + 250x1 ≥ 8,000; x1 + x2 ≤ 20 and x1, x2 ≥ 0.

36. Let x1 and x2 = number of units of share A and B respectively. to
and xxxx 1234 ,,, . ≥ 0 Min (total investment) Z = x1 + x2
31. Let x1, x2, x3, x4 and x5 = percentage of the total fund that should subject to 0.12x1 + 0.04x2 ≥ 600 (Dividend constraint) 0.10x1 +
be invested in all given five
0.40x2 ≥ 1,000 (Investment constraint)
schemes, respectively.
and x1, x2 ≥ 0.
Max Zx x x x x =+ + + + 6 13 10 20 25 123 4 5
37. Let x1 and x2 = volume of purchase from supplier A and B,
subject to 15 3 5 6 10 15 1234 5 xxxx x ++++ ≤ xx x x respectively.
x
325 4 Min Z = x1 + 4x2
++++ ≤
x 5 ≥ 0.25
x1 + x2 + x3 + x4 + x5 = 1 32. Let x1, x2, x3 = number of scooters of types A, B and C,
and x j ≥ 0 for all j. respectively.
 1 1
Max Z = 0.7 (6,000 – 5,000)x1 + 0.8 (8,500 – 7,000)x2 + (iii) 20 10175 1 2 x x + ≥
0.6 (10,500 – 8,500)x3 and x1, x2 ≥ 0.
1 3
subject to (i) x1 + x2 ≥ 2,000; (ii) 4 41 000 1 2 x x + ≥ ,

CHAPTER SUMMARY

This chapter presents basic assumptions, limitations, components of any linear programming model and broad application areas
of linear programming. The guidelines of mathematical modelling of any decision problem were explained followed by a large
number of model building solved exercises in all functional areas of management and allied areas. These exercises are illustrative
for students to deal with more complex and real-life problems.
Linear Programming: Applications and Model Formulation 65

CHAPTER CONCEPTS QUIZ

True or False
into mathematical expression
1. In a Linear Programming model, all parameter are assumed to be
(b) decision-makers prefer to work with formal models (c) it
known as constant.
captures the relevant relationship among decision factors (d) it
2. In LP model, any variable can assume to take only integer values enables the use of algebraic technique
or restricted to take discrete number of values. 3. Total contribution is
22. Linear programming is a
used in place of profit in the objective function of maximization.
(a) constrained optimization technique
problem because whole profit is not linearly related to sales volume.
(b) technique for economic allocation of limited resources (c)
4. An equation is more restrictive than an inequality. 5. All the mathematical technique
variables in the solution of a linear programming problem are either (d) all of the above
positive or negative because of the existence of structural constraints.
23. A constraint in an LP model restricts
6. Linear programming is a technique for finding the best uses of an (a) value of objective function
organizations manpower, money and machinery. 7. Production (b) value of a decision variable
planning is one of the application areas of the linear programming. (c) use of the available resource
8. The effect of time and uncertainty are taken into consideration by (d) all of the above
linear programming model. 24. The distinguishing feature of an LP model is
9. Linear Programming determines the economic and efficient way of (a) relationship among all variables is linear
locating manufacturing plants for physical distribution. 10. All variables (b) it has single objective function and constraints (c)
in the linear programming problem must take one negative values. value of decision variables is non-negative
(d) all of the above
Fill in the Blanks 25. Constraints in an LP model represents
11. Linear programming is a technique which attempts to determine (a) limitations
how best to allocate __________ in order achieve some __________. (b) requirements
12. A linear programming technique improves the quality of (c) balancing limitations and requirements
__________. 13. In a linear programming, all relationships among (d) all of the above
decision variables are __________. 26. Non-negativity condition is an important component of LP model
14. If two variables always take on values which are in the same because
proportion, the variables are __________ related. (a) variables value should remain under the control of the
decision-maker
15. __________ appearing in the models are assumed to be constant
(b) value of variables make sense and correspond to real world
but __________ in real life situations.
problems
16. Every linear programming problem includes __________ which (c) variables are interrelated in terms of limited resources (d)
relates variable in the problem to the goal of the firm and none of the above
__________ which represent the limit on resource available to the
firm. 27. Before formulating a formal LP model, it is better to (a)
express each constraint in words
17. Most of the constraints in the linear programming problem are (b) express the objective function in words
expressed as __________. (c) verbally identify decision variables
18. Linear programming is used to allocate __________ to activities so (d) all of the above
as to optimize the value of objective function. 28. Each constraint in an LP model is expressed as an (a)
19. If the value of the variables are under the control of decision inequality with ³ sign
makers then variables are said to be __________ otherwise (b) inequality with £ sign
__________. (c) equation with = sign
20. __________ of the decision variables is one of the assumption of (d) none of the above
the linear programming model. 29. Maximization of objective function in an LP model means (a)
value occurs at allowable set of decisions
Multiple Choice (b) highest value is chosen among allowable decisions (c)
neither of above
21. The mathematical model of an LP problem is important because
(d) both (a) and (b)
(a) it helps in converting the verbal description and numerical data
30. Which of the following is not a characteristic of the LP model (a)
 alternative courses of action 33. Non-negativity condition in an LP model implies (a) a positive
(b) an objective function of maximization type coefficient of variables in objective function (b) a positive
(c) limited amount of resources coefficient of variables in any constraint (c) non-negative
(d) non-negativity condition on the value of decision variables 31. value of resources
The best use of linear programming technique is to find an optimal use (d) none of the above
of 34. Which of the following is an assumption of an LP model (a)
(a) money (b) manpower divisibility (b) proportionality
(c) machine (d) all of the above (c) additivity (d) all of the above
32. Which of the following is not the characteristic of linear 35. Which of the following is a limitation associated with an LP Model
programming (a) the relationship among decision variables in linear (b) no guarantee
(a) resources must be limited to get integer valued solutions
(b) only one objective function (c) no consideration of effect of time and uncertainty on LP model
(c) parameters value remains constant during the planning period (d) all of the above
(d) the problem must be of minimization type
66 Operations Research: Theory and Applications

Answers to Quiz
1. T 2. F 3. T 4. T 5. F 6. T 7. T 8. F 9. T 10. T 11. resources, objective 12. decisions 13. linear 14. linearly 15. parameters, unknown 16.
objective function, constraints 17. inequalities 18. scarce resources 19. controllable and uncontrollable 20. certainty 21. (a) 22. (d) 23. (d) 24. (a)
25. (d) 26. (b) 27. (d) 28. (d) 29. (a) 30. (b) 31. (d) 32. (d) 33. (d) 34. (d) 35. (d)

CASE STUDY

Case 2.1: Welltype Manufacturing

Welltype manufacturing company produces three types of typewriters. All the three models are required to be
machined first and then assembled. The time required for the various models are as follows:
Types Manual Electronic Deluxe
Typewriters Typewriters Electronic
Typewriters
Machine time (in hours) 15 12 14
Assembly time (in hours) 4 3 5

The total available machine time and assembly time are 3,000 hours and 1,200 hours, respectively. The data
regarding the selling price and variable costs for the three types are:

Types Manual Electronic Deluxe

Typewriters Typewriters Electronic
Typewriters
Selling price (Rs) 4,100 7,500 14,600
Labour, material and
other variable costs
(Rs) 2,500 4,500 9,000
The company sells all the three types on credit, but can only collect the amounts on the first of the following month.
The labour, material and other variable expenses will have to be paid in cash. This company has taken a loan of Rs
40,000 from a co-operative bank and will have to repay it to the bank on 1 April 2008. The TNC Bank from whom this
company has borrowed Rs 60,000 has expressed its approval to renew the loan.
Balance Sheet of the Company as on 31 March 2008

Liabilities Rs Assets Rs
Equity Share Capital 1,50,000 Land 90,000
Capital Reserve 15,000 Building 70,000
General Reserve 1,10,000 Plant &
Profit & Loss A/c 25,000 Machinery 1,00,000
Long-term Loan 1,00,000 Furniture &
Loan from TNC Fixtures 15,000
 Bank 60,000 Vehicles 30,000
Loan from Inventory 5,000
Co-operative Bank 40,000 Receivables 50,000
Cash 1,40,000

Total 5,00,000 Total 5,00,000

The company will have to pay a sum of Rs 10,000 towards salary of top management executives and other fixed
overheads for the month. Interest on long-term loans is to be paid every month at 24% per annum. Interest on loans
from TNC and cooperative banks may be taken to be 1,200 for the month. Also this company has promised to deliver 2
manual typewriters and 8 deluxe electronic typewriters to one of its valued customers next month. Keep
Linear Programming: Applications and Model Formulation 67

in mind the fact that the level of operations in this company is subject to the availability of cash next month. This
company will also be able to sell all types of typewriters in the market. The senior manager of this company desires to
know as to how many units of each typewriter must be manufactured in the factory next month so as maximize the
profits of the company. Advise the management of the company for manufacturing strategy with an aim to maximize
profit.

Case 2.2: Shreya Advertizers

Shreya Advertizers – a marketing company dealing with laminated sheets ‘Gloss’ in the western zone covering
Maharashtra, Gujarat and Madhya Pradesh, is considering to launch an advertisement campaign within a budget of Rs
2.5 lakh. On the basis of advertisement testing of the previous year, the company’s research department has found that
magazines and films are the ideal media for advertising laminated sheets. The company is not in a position to use the
audiovisual medium due to limitation of funds. The magazines enjoying good recall in last year’s campaign are
Stardust, Filmfare, Reader’s Digest and Madhuri. This is attributed to the effective visual impact made by the good
reproduction of the advertisements both in colour, and black and white.
The characteristics of target audience for ‘Gloss’ and weightage for each characteristic are as follows:

Characteristics Weightage (%)

Age 15–34 yrs 20
Monthly income Over Rs 5,000 70
Education Above S.S.C. 10

The audience characteristics for the four magazines selected are given below:

Characteristics Stardust Filmfare Reader’s Madhuri

(%) (%) Digest (%) (%)
Age: 15–34yrs 75 45 56 80
Monthly income: Over Rs 5,000 52 43 47 25
Education: Above S.S.C. 83 53 72 34

The efficacy index for a black and white advertisement may be taken as 0.15 and that for a colour advertisement as
0.20. The cost per insertion of a black and white, and a colour advertisement and the readership for the four magazines
are as follows:

Magazines Cost (Rs) per Insertion Readership

Black and White Colour (in ’000 Rs)

Stardust (Monthly) 4,500 8,400 189
Filmfare (Fortnightly) 4,200 8,400 256
Reader’s Digest (Monthly) 6,400 9,600 136
Madhuri (Fortnightly) 3,300 6,600 205

It has also been found that for creating an impact at least 03 insertions are necessary in Stardust and Reader’s Digest,
while a minimum of 04 insertions will be required in the case of Filmfare.
Suggest an advertising strategy for the company to maximize the expected effective exposure.