Linear programming
Introduction
Definition
Linear programming is a mathematical technique that deals with the
optimization of a linear function of variables known as objective
function to a set of linear inequalities known as constraints.
It is a method of determining an optimum programme of inter-dependent
activities in view of available resources.
Basic parts of a linear programming problem
i. The objective function: it describes the primary purpose of the
formulation i.e. to maximize profit or to minimize cost.
ii. The constraint set: It is a system of equalities and / or
inequalities describing the conditions under which optimization is
to be accomplished e.g. machine hours, man-hours, materials etc.
Assumptions of Linear programming
i. Linearity: Costs, revenues or any physical properties, which form the
basis of the problem, vary in direct proportion with the quantities or
numbers of components produced.
ii. Divisibility: Quantities, revenues and costs are infinitely divisible i.e.
any fraction or decimal answer is valid.
iii. Certainty: The technique makes no allowance for uncertainty in the
estimate made.
iv. Positive solutions: Non-negativity constraints are introduced to ensure
only positive values are considered.
v. Interdependence between demand products is ignored, products may
be complementary or a substitute for one another.
[Link] factors are ignored. All production is assumed to be
instantaneous.
vii. Costs and benefits which cannot be quantified easily, such as
liquidity, good will and labour stability are ignored.
Advantages of Linear Programming
i. Helps in attaining the optimum use of productive factors
ii. Improves the quality of decisions
iii. Improves the knowledge and skill of tomorrow’s executives
iv. It highlights the bottlenecks in the production process
v. It gives insight and perspective into problem situations
[Link] one to consider all possible solutions to problems.
[Link] one to come up with better and more successful decisions
viii. It’s a better tool for adjusting to meet changing conditions.
Limitations of Linear Programming
i. It treats all relationships as linear
ii. It is assumed that any activity is infinitely divisible
iii. It takes into account single objective only i.e. profit maximization or
cost minimization
[Link] can be adopted only under the condition of certainty i.e. that the
resources available, per unit contribution, costs etc are known with
certainty. This does not hold in real situations.
Applications of Linear Programming
Linear programming can find use in many areas where decisions need to
be made based on scarcity of recourses. A few areas are mentioned
below:
i. Business and industry e.g. in the petroleum industry
ii. Food processing industry: to determine the optimal mix of feeds
iii. Paper and textile industry: To determine the optimal cutting method to
minimize trim losses
[Link] industry: To determine the best route
[Link] institutions – to determine investment plans.
[Link] media: assigning advertising expenditures to different
media plans
[Link] – to find the number of financial audits
[Link]- amount of fertilizer to apply per acre
x. Hospital scheduling- number of nurses to employ
[Link] – determining the best marketing strategy
xii. Crude oil refining
xiii. Politics – Campaign strategies
Solutions to LP problems
LP problems can be solved by the help of the following methods:
i. Graphical method
ii. Simplex method
In this study we shall concentrate on the graphical method.
Solving Linear Programming Problems Graphically.
In order to solve a LP problem graphically, the following procedure is
adopted:-
i. Formulate the appropriate LP problem
ii. Graph the constraint inequalities as follows: treat each inequality as
though it were an equality and for each equation, arbitrarily select two
sets of points. Plot each of the points and connect them with
appropriate lines.
iii. Identify the solution space or feasible region, which satisfies all the
constraints simultaneously. For ≤ constraints, this region is below the
lines and for ≥ constraints; the region is above the lines.
iv. Locate the solution points on the feasible region. These points always
occur at the corner points of the feasible region.
[Link] the objective function at each of the corner points.
vi. Identify the optimum value of the objective function.
Example
At the start of the current week, there are 30 units of X and 90 units of Y
in stock. Available processing time on machine, A is forecast to be 40
hours and on machine, B is forecast to be 35 hours.
The demand for X in the current week is forecast to be 75 units and for Y
is forecast to be 95 units. Company policy is to maximize the combined
sum of the units of X and the units of Y in stock at the end of the week.
Formulate the problem of deciding how much of each product to make in
the current week as a linear program.
Solve this linear program graphically.
Solution
Let
x be the number of units of X produced in the current week
y be the number of units of Y produced in the current week
Then the constraints are:
50x + 24y <= 40(60) machine A time
30x + 33y <= 35(60) machine B time
x >= 75 - 30
i.e. x >= 45 so production of X >= demand (75) - initial stock (30),
which ensures we
meet demand
y >= 95 - 90
i.e. y >= 5 so production of Y >= demand (95) - initial stock (90),
which ensures we meet demand
The objective is: maximize (x+30-75) + (y+90-95) = (x+y-50)
i.e. to maximize the number of units left in stock at the end of the
week
It is plain from the diagram below that the maximum occurs at
the intersection of x=45 and 50x + 24y = 2400
Revision exercise
1.A firm is engaged in producing two products A and B. each unit of
product A requires 2 kg of raw material and 4 labour hours for
processing, whereas each unit of product B requires 3 kg of raw material
and 3 hours of labour, of the same type. Every week, the firm has an
availability of 60 kg of raw material and 96 labour hours. One unit of
product A sold yields Sh. 40 and one unit of product sold gives Sh. 35 as
profit. Formulate this problem as a linear programming problem to
determine as how many units of each of the products should be
produced per week so that the firm can earn the maximum profit.
Assume that there is no marketing constraint so that all that is produced
can be sold.