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

## 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 x_{j }(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 }(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 }(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.

## SIMPLEX METHOD

## BIG-M METHOD

## NOTES

## Comments

## Post a Comment