GRAPHICAL METHOD
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 on a graph paper to locate the best (optimal) solution. The technique used to identify the optimal solution is called the graphical solution approach.
IMPORTANT DEFINITIONS:
1) Solution:
The set of values of decision variables xj (j = 1, 2, …, n) which satisfy the constraints of an LP problem is said to constitute solution to that LP problem.
2) Feasible solution:
The set of values of decision variables xj (j = 1, 2, …, n) which satisfy all the constraints and non-negativity conditions of an LP problem simultaneously is said to constitute the feasible solution to that LP problem.
3) Infeasible solution:
The set of values of decision variables xj (j = 1, 2, …, n) which do not satisfy all the constraints and non-negativity conditions of an LP problem simultaneously is said to constitute the infeasible solution to that LP problem.
Basic solution for a set of m simultaneous equations in n variables (n – m), a solution obtained by setting (n – m) variables equal to zero and solving for remaining m equations in m variables is called a basic solution.
The (n – m) variables whose value did not appear in this solution are called non-basic variables and the remaining m variables are called basic variables.
4) Basic feasible solution:
A feasible solution to an LP problem which is also the basic solution is called basic feasible solution. That is, all basic variables assume non-negative values.
Basic feasible solutions are of two types:
(i) Degenerate:
A basic feasible solution is called degenerate if value of at least one basic variable is zero.
(ii) Non-degenerate:
A basic feasible solution is called non-degenerate if values all m basic variables are non-zero and positive.
5) Optimum basic feasible solution:
A basic feasible solution which optimizes (maximizes or minimizes) the objective function value of the given LP problem is called an optimum basic feasible solution.
6) Unbounded solution:
A solution which can increase or decrease the value of objective function of the LP problem indefinitely is called an unbounded solution.