1.0 INTRODUCTION
In many business situations, resources are limited while demand
for them is unlimited. For example, a
limited number of vehicles may have to be scheduled to make multiple trips to customers or a
staffing plan may have to be developed
to cover expected variable demand with the fewest employees. In this
note we describe a method called linear
programming (LP), which is useful for
allocating scarce resources among competing demands. The resources may
be time, money, or materials, and the
limitation are known as constraints. Linear
programming can help managers find the best allocation solution and
provide information about the value of
additional resources.
2.0 OBJECTIVES
After reading this note you will be able to:
(i) Explain the characteristics and assumption of linear
programming model.
(ii) Formulate models for various problems
(iii) Perform graphic analysis for two-variable problems and find
the algebraic solution for the corner
point found to be optimal.
(iv) Describe the meaning of slack and surplus variables
(v) Discuss the meaning of sensitivity analysis on the objective
function coefficient and right hand side
parameters.
(vi) Interpret the computer output of a linear programming
solution.
3.0 MAIN CONTENT
3.1 Function and Characteristics of LP 3.1.1 Functions
(i) LP is useful in the specification of optimum organisation of
resources in a business organisation
such that net returns of maximization of returns is achieved under given condition of resource
restriction.
(ii) LP makes long range planning possible in business
(iii) LP gives technical co-efficient based largely on the
practices and methods of operation
adopted by the manager.
(iv) By-product obtained from results of the LP planning exercises
are capable of throwing considerable
light on a number of aspects of business
management e.g. the surplus or unexhausted resource(s), the rate of interest the manager can justifiably
pay on borrowed funds, wages that the
manager is willing to pay for labour.
3.1.2 Characteristics
Some assumptions (characteristics) go with the three components of
LP outlined in section 3.2, they
are:
(i) Linearity:- This implies that the input-output co-efficient
are constant and independent of
the scale of operation implying constant resource productivity and return to scale.
(ii) Additivity:- This assumption implies that the total quantity
of resources used in different
activities is equal to the sum of the quantities of different input used in each activity and
that the size of any activity is
independent of the size of other activities.
(iii) Divisibility:- This means that inputs are infinitely
divisible. Thus, an LP solution can specify
inputs and outputs in fractional notes such as 10.7 units of labour etc.
(iv) Finiteness:- This implies that a limit exists on the number
of `activities and resources which
can be programmed. This is a practical assumption in the sense that an unlimited number of
activities and resources would make an
optimum solution impossible to obtain
(v) Single valued expectation:- This characteristics shows that
the prices of inputs and
outputs, the input-output co-efficient and the levels of resources are known with certainty. Hence, a
LP model is deterministic.
(vi) Non -negativity of decision variables:- This is very logical,
there is no way you use any
negative quantity of any resource, the least you use of any input among series of inputs in a
production process is zero i.e. not used
at all.
3.2 Components of LP Model
(i) An objective function:- This must be clearly spelt out in
mathematical language, and this
can take one of several forms e.g.
(a) Maximization of net
revenue or profit from one or a several combination of enterprises
(b) Maximization of production or a transportation cost.
(ii) Competitive enterprises with possible alternative methods
of producing each enterprise. This
implies that enterprises must be competing for the use
of resources and in which case there is a problem of choice among enterprises, (see section
under formulation of LP problem).
(iii) Constraint to the attainment of the objective: A linear
programming (LP) problem exists
only if there are constraints limiting the attainment of an objective
Basically there are 3 types of constraints
(a) Resource constraint:- A manager always have limited levels of
such resources as capital, labour, machines,
building capacity etc. which limits the
scale of his operation.
(b) Institutional constraint: - This is typified by quota system
which is a contractual
arrangement with say a governmental agency specified minimum or maximum production levels.
(c) Subjective constraint: - The manager imposes this on himself.
For example, there may be internal capital
rationing due to (i) debt aversion (ii)
scale restriction due to skill (iii) consumption habit consideration etc.
3.3 Formulating a LP problem
Linear programming application begins with the formulation of a
model of the problem with the general
characteristics just described. We illustrate the modeling process here with the product mix
problem, a one- period type of aggregate
planning problem, the solution of which yields optimal output quantities (or product mix) of a group of
product or services, subject to resource
capacity and market demand constraints. Formulating a model to represent each unique problem, using the
following three-step sequence, is the
most creative and perhaps the most difficult part of linear
programming.
Step 1: Define the decision variable
Define each decision
variable specifically, remembering that the definitions used in the objective function must be
equally useful in the constraints. The
definitions should be as specific as possible e.g. X, = product 1 or X,
= no of notes of product 1 produced and sold at a time.
Step 2: Write out the objective function.
What is to be maximized or minimized? If it is revenue, write out
an objective function that makes the
revenue a linear function of the decision variables. Identify parameters to go with each decision
variable. For example, if each note of
X1 sold yields a revenue of N45, the total revenue realizable from X1
equal 45 X1. The objective function
often is set to equal to Z, and the goal is to
maximize or minimize Z.
What limits the values of the decision variables? Identify the
constraints and the parameters for each
decision variable in them. To be formally correct, also write out the non-negativity constraints.
Example 1 Lopin factory
produces two basic types of plastic pipe. Three resources are taken to be crucial to the output of pipe:
extrusion hours, packaging hours, and a
special additive to the plastic raw material. The data below represent
next production situation.
Product
Resource Type
1 Type 2 Resource availability
Extrusion 4hr
6hr 48hr
Packaging 2hr
2hr 18hr
Additive mix 2kg
l kg 16kg
The contribution of profits and overhead per 100 feet of pipe is
N34 for type 1 and N40 for type 2.
Formulate a linear programming mode to determine how much of each type of pipe should be produced
to maximize contribution to profits and
to overhead.
Solution
Step 1: To define the decision variables that determine product
mix, we let X1 = amount of type 1
pipe to be produced and sold after next production. X2 = amount of type 2 pipe to be produced and sold
after next production.
Step 2: Next define the objective function. The goal is to
maximize the total contribution that the
two products make to profits and overhead. Each note of X1 yields N34 and each note of X2 yields x
N40. For specific values of X1and X2 we
find the total profit by multiplying the number of notes of each product produced by the profit per note and adding them.
Thus our objective function becomes
Maximize N34 X1 + N40 X2 =Z.
Step 3. The final step is to formulate the constraints. Each note
of X1 and X2 produced consumes
some of the critical resources. In the extrusion department, a note of X1 requires 4 hours and a note of
X2 requires 6 hrs. The total must not
exceed the 48hours capacity available, so we use the = sign. Thus the
first constraint is 4 X1 + 6 X2 = 48
(extrusion).
Similarly, we can formulate constraints for packaging and raw
materials.
2 X1+ 2 X2 = 18 (packaging)
2 X1+ X2 = 16 (additive mix)
These three constraints restrict our choice of values for the
decision variables because the values we
choose for X1and X2 must satisfy all of them. Negative values for X1and X2 don't make sense, so we
add non-negativity restrictions to the
model X1 = 0; X2 = 0
We can now state the entire model, made complete with the
definition of variables.
Maximize 1 N34X1 + ; N40X2 = Z
Subject to 4X1 + 6X2 =
48
2X1 + 2X2 = 18
2X1 + X2 = 16
X1, X2 = 0.
3.3.1 Graphic analysis With the model
formulated, we now seek the optimal solution. In practice, most linear programming problems are solved
with the computer. However, insight into
the meaning of the computer output and linear programming concept in general can be gained by analyzing
a two - variable problem with the
graphic method of linear programming, even though it isn't a practical techniques for solving problems having three
or more decision variables.
Five basic steps involved
are
(i) Plot the constraint
(ii) Identity the feasible region
(iii) Plot an objective function line
(iv) Find the visual solution
(v) Find the algebraic solution
Each of these five steps are briefly discussed
(1) Plot the constraints: We begin by plotting
the constraint equations, disregarding the inequality portion of the constraints. Making each
constraint equal converts it to equation
for a straight line. The line can be drawn as soon as we identify two
points on it. To find the X1 axis
intercept, set X2 equal to 0 and solve the equation for X1. For the Lopin factory in example l, the
equation of the line for the extrusion
process is
We now connect points (0, 8 ) and (12, 0) as in Figure 11.1
below.
Figure 11.1: Graph of the Three Constraints 
The solution for packaging process line
2X1 + 2X2 = 18
for X1, :2X1 + 2(0) = 18
X1, = 9
For X2 : 2(0) + 2(X2) = 18
X2 = 9
We now connect points (9,0) and (0,9) on the same graph behind in
fig. 1. The equation for the additive
mix line is 2X1, + X2 = 16. To find X1, intercept, set X2 = 0
2X1, + X2 = 16
X1 = 8
To find X2, set X1 = 0
2(0) + X2 = 16
X2 = 16.
We also connect points (0, 16) and (8, 0) for the additive mix on
the same graph of Figure 11.1.
(2) Identify the feasible region
The feasible region is the area on the graph that contains the
solutions that satisfy all the
constraints simultaneously, including the nonnegative restriction. The feasible region for a maximization
problem as in this case is that area
bounded by all the tree curves and so we would have the curve ICFH as
our feasible region as shown in Figure
11.2. Having obtained the feasible region we
now seek to locate the point that maximizes the objective function this
is achieved by plotting the objective
function on the feasible region. The series of
lines plotted are called Iso-revenue curves if the
objective function is to
maximize revenue or Iso-profit curve if the objective is to maximize
profit. The optimal point is finally
read as the point where the objective function line cuts the tip of the feasible point (farthest point
from the origin).
Figure 11.2: The Feasible region
X1
X1
2 X1 + 2 X2 18 (packaging)
(3) Find the visual solution
From the feasible region lCFH we eliminate corner point OH because
better points lie above and to the
right. The optimal solution is the last point touching the feasible region when series of lines with
slope equal to the slope of the
objective are plotted within the feasible region. Due to some errors in
reading, the value from the graph or
gradation, visual solution isn't exact.
(4) Find the Algebraic Solution
To find an exact solution, we must use algebra. We begin by
identifying the pair of constraints that
define the corner point at their intersection. We then list the constraints as equations and solve them
simultaneously to find the coordinates
(XI, X2) of the corner point.
Simultaneously equation can be solved several ways. For small problems
the easiest way is as follows.
Step 1: Develop an equation with just one unknown. Start by
multiplying both sides of one
equation by a constant so that the co-efficient for one of the two variables is identical in
both equations. Then subtract one
equation from the other and solve the resulting equation for its single
unknown variable.
Step 2: Insert this decision variable value into either one of the
original constraints and solve for the
other decision variable.
Find the optimal solution
algebraically for the Lopin factory. What is the value of Z when the decision variables have optimal
values.'?
Solution
Step 1
4X1 + 6X2 = 48 (Extrusion)
2X1 + 2X2 = 18 (Packaging)
Multiply each term in packaging constraint by 2 to give 4X1 + 4X2
= 36. Next, we subtract the packaging
constraint from the extrusion constraints.
4X1 + 6X2 = 48
(4X1 + 4 X2 = 36)
2X2 = 12
X2 = 6
Step 2 substituting the values of X2 into the extrusion equation,
we get
4 X1 + 6(6) = 48
4X1 = 12
X1 = 3
The optimal point is thus (3, 6) to give an optimal profit of
34(3) + 40 (6) = N4342
3.4 Slack and surplus variables.
For a O constraints, the amount by which the left-hand side falls
short of the right-hand side is called
slack. For a 1:1 constraint, the amount by which the left-hand side exceeds the right-hand side is
called surplus. To find the slack for a
O constraint algebraically, we add a slack variable to the constraint and convert it to an equality. Then we substitute
in the values of the decision variables
and solve for the slack. For example the additive mix constraint in Lopin factory is 2X1 + X2 + S1 = 16.
We then find the slack at the optimal solution (3, 6) 2(3) + 6 + S1 = 16
S1 = 4.
The procedure is much the same to find the surplus for a ,
constraint, except that we subtract a
surplus variable from the left-hand side. Suppose that X1 + X2 , 6 was another constraint in the Lopin
factory problem, representing a lower
bond on the number of notes produced. We would then rewrite the constraint by subtracting a surplus variable
S2 XI + X2 - S2 = 6
The slack at the optimal solution (3,6) would be 3+6 - S2 = 6
S2 = 3
3.5 Sensitivity analysis The parameters in the
objective function and constraints are rarely known with certainty. Sometimes they are just estimates
of actual values. For example, the
available packaging and extrusion hours for the Lopin factory are
estimates that do not reflect the uncertainties
associated with absenteeism or personnel
transfers, and required time per note to package and extrude may be
work standards that essentially are
averages. Likewise, profit contribution used for the objective function coefficients do not
reflect uncertainties in selling prices
and such variable costs as wages, raw materials, and shipping.
In spite of these uncertainties, initial estimates are needed to
solve the problem. Accounting, marketing
and work-standard information systems usually often provide these initial estimates. After
solving the problem using these estimated
values, the analyst can determine how much the optimal value of the
decision variables and the objective
function value Z would be affected if certain
parameters had different values. This type of post solution analysis
for answering "what if' question is
called sensitivity analysis.
3.5.1 Right - hand -
side parameters Now consider how a
change in the right-hand-side parameter for a constraint may affect the feasible region and perhaps
cause a change in the optimal solution.
Let’s return to the Lopin factory problem. Consider adding one more hour to the packaging process, increasing it
from 18 to 19 hours; i.e.
4X1 + 6X1, = 48 (extrusion)
2X1, + 2X2 = 19 (packaging)
The optimal values are X1 = 4.5 and X2 = 5 and the new Z value is
N34 (4.5) + N40 (5) = N353. Because the
value of Z was N342 with 18 hours of packaging
time, the value of one more hour of packaging is N11 (or N353 - N342).
The change in Z per note of change in the value of the right-hand
side parameter of a constraint is called
the shadow price, which is the marginal
improvement in Z caused by relaxing the constraint by one note.
Relaxations mean making the constraint
or decrease it for an O restrictive, which involves increasing the right-hand-side for an O
constraint. The shadow price also is the
marginal loss in Z caused by making the constraint more restrictive by
one note.
3.6 Computer Solution Most real-world
linear programming problems are solved on a computer, so we will focus our understanding on the use of
computer to solving LP problems and the
logic behind its use. The solution procedure in computer codes is some form of the simplex method, an iterative
algebraic procedure for solving linear
programming problems.
3.6.1 Simplex Method The graphic analysis
gives insight into the logic of the simplex method. One corner point of the feasible region will
always be the optimum, even when there
are multiple optimal solutions. Thus, the simplex method starts with an initial corner point and then systematically
evaluates other corner points in such a
way that the objective function improves (or at worst, stays at the same) at each iteration. In the Lopin factory example
we have being using for illustration; an
improvement would be an increase in profits. When no more improvements are possible, the optimal
solution has been found.
3.6.2 Computer Output Computer programmes
diagrammatically reduce the amount of time required to solve linear programming problems. Special -
purpose programmes can be developed for
applications that must be repeated frequently. Such programmes simplify data input and generate the
objective function and constraint for the
problem. Printout 1 shows the
input data for the Lopin factory problem. The last half of printout 1 gives the values an the type of
constraint (O = or O). The user may
choose to enter labels for the objective function, constraint, and right
hand side values. Here the extrusion
constraint is labelled "Ext" and the right-hand -side values are labelled "RHS" Input
data can be stored in file for use during
subsequent sessions.
3.7 Dual The objective of any
LP process is called the primal, the process of reversing or transpose of the primal process is called the
dual. If the primal is to maximize then
the dual is to minimize, whether the primal function is solved or its dual function is used to establish the solution,
the answer remain unchanged
3.7.1 Procedure for a dual process
1. Observe the objective function of the primal problem
2. Write out the co-efficients of the constraints of the primal
problem in form of matrix.
3. Transpose the matrix of co-efficients of the constraints.
4. Total requirement of each of the constraints of the primal
problem now turn coefficients of the
objective function of the dual.
5. Co-efficients of the objective function of the primal problem
become the resource constraints.
6. The inequality sign is reversed for the dual problem.
4.0 CONCLUSION
We have been able to see how the knowledge of LP can be of help
in management decisions to boost the
performance of a business note or
production organisation.
5.0 SUMMARY
We are now able to take some economic and managerial decision on
the use of resources, what resource
would contribute better to our objective has been pointed out from slack activities column and
the Z-C row of the optimal
strategy. The limitations of
graphical method compared to the simplex method was seen in that graphical solution cannot handle
clearly more than two objective function
case, whereas the simplex approach would do us better. The surplus resource(s) or the shadow prices was equality
highlighted in the simplex method but
cannot be depicted on the graphical solution.
0 comments:
Post a Comment