## 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 x(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 x(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.