Solution values of decision variables X1, X2, X3… (i=1, 2…n) which satisfies the constraints of a general LP model, is called the solution to that LP model.
Linear
Programming – Problem Solving [GRAPHICAL METHOD]
Introduction
An optimal as well as feasible solution to an LP
problem is obtained by choosing among several values of decision variables
X1,X2,…….Xn, the one set of values that satisfy the given set
of constraints simultaneously and also provide the optimal (maximum or minimum)
value to the given objective function. For LP problems that have only two variables it is
possible that the entire set of feasible solutions can be displayed graphically
by plotting linear constraints to locate a best (optimal) solution. The
technique used to identify the optimal solution is called the Graphical
Solution Technique for an LP problem with two variables. The two graphical solution
techniques are 1.
Extreme
point enumeration approach, and 2.
Iso-profit
(cost) function approach. We will
list out various definitions that are associated with the graphical solution
method. DEFINITIONS
Solution
Solution values of decision variables X1, X2, X3…
(i=1, 2…n) which satisfies the constraints of a general LP model, is called the
solution to that LP model. Feasible Solution
Solution values of decision variables X1, X2, X3…
(i=1, 2…n), which satisfies the constraints of the given problem as well as the
non-negativity conditions of a LP model, are called as the feasible solution to
that LP model. Basic Solution
We know that to solve 2 variables, we need a
minimum of 2 simultaneous equations; to solve 3 variables, a minimum of 3
simultaneous equations and so on. For a set of m equations in n variables (n>m), a
solution is obtained by setting (n-m) variables values equal to zero and
solving for remaining m equations in m variables is called a Basic solution to
the problem. The (n-m) values, whose value did not appear in
this solution, are called non-basic variables and the remaining m variables are
called basic variables. Basic
Feasible Solution
A feasible solution to an LP problem that is also
the basic solution is called the basic feasible solution to the LPP. That is,
all basic variables assume non-negative values. Basic feasible solutions, in
general, can be classified into two types: a. Degenerate:
A basic feasible solution is called degenerate if at least one basic variable
possesses zero value. b. Non-degenerate:
A basic feasible solution is called non-degenerate if all m basic variables are
non-zero and positive. Optimum
Basic Feasible Solution
A basic feasible solution which optimizes
(maximizes or minimizes) the objective function of the given LP model is called
an optimum feasible solution to the given LPP. Unbounded
Solution
Some occasions, a solution which can be increased
or decreased the value of objective function of LP problem indefinitely, is
known as an unbounded solution to the given problem.
Tags : Operations Management - Introduction to Operations Research
Last 30 days 1013 views