21-06-2012, 02:05 PM
Linear Programming
2-linear-programming-problem.pdf (Size: 2.44 MB / Downloads: 81)
Introduction
One of the most important problems in management decision is to allocate limited and scarce
resource among competing agencies in the best possible manner. Resources may represent man,
money, machine, time, technology on space. The task of the management is to derive the best
possible output (or set of outputs) under given restraints on resources. The output may be
measured in the form of profits, costs, social welfare, effectiveness, etc. In many situations the
output (or the set of outputs) can be expressed as a linear relationship among a number of
variables. The amount of available resources can also be expressed as a linear relationship among
some system variables.
Learning Objectives:
After studying this unit, you should be able to understand the following
1. Formulate the LPP and observe the feasible region.
2. Graphically analyze and solve a L.P.P.
Requirements of L.P.P
i. Decisions variables and their relationship
ii. Well defined objective function
iii. Existence of alternative courses of action
iv. Nonnegative
conditions on decision variables.
Basic assumptions of L.P.P
1. Linearity: Both objective function and constraints must be expressed as linear inequalities.
2. Deterministic: All coefficient of decision variables in the objective and constraints expressions
should be known and finite.
3. Additivity: The value of objective function for the given values of decision variables and the
total sum of resources used, must be equal to sum of the contributions earned from each
decision variable and the sum of resources used by decision variables respectively.
4. Divisibility: The solution of decision variables and resources can be any nonnegative
values
including fractions.
Graphical Methods To Solve The Linear Programming Problems
A LPP with 2 decision variables x1 and x2 can be solved easily by graphical method. We consider
the x1 x2 – plane where we plot the solution space, which is the space enclosed by the
constraints. Usually the solution space is a convex set which is bounded by a polygon; since a
linear function attains extreme (maximum or minimum) values only on boundary of the region, it is
sufficient to consider the vertices of the polygon and find the value of the objective function in these
vertices. By comparing the vertices of the objective function at these vertices, we obtain the optimal
solution of the problem.
The method of solving a LPP on the basis of the above analysis is known as the graphical
method. The working rule for the method is as follows:
Working Rule:
Step I: Write down the equations by replacing the inequality symbols by the equality symbol in the
given constraints.
Step II: Plot the straight lines represented by the equations obtained in step I.
Step III: Identify the convex polygon region relevant to the problem. We must decide on which
side of the line, the halfplane
is located.
Step IV: Determine the vertices of the polygon and find the values of the given objective function
Z at each of these vertices. Identify the greatest and least of these values. These are
respectively the maximum and minimum value of Z.
Step V: Identify the values of (x1, x2) which correspond to the desired extreme value of Z. This is
an optimal solution of the problem.