LINEAR PROGRAMMING – GRAPHICAL METHOD, SIMPLEX METHOD AND BIG-M METHOD

Feb 6, 2022

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.