Home | ARTS | Operations Management | Introduction and Definition of Linear Programming – Problem Solving [GRAPHICAL METHOD]

# Introduction and Definition of Linear Programming – Problem Solving [GRAPHICAL METHOD]

Posted On :  22.06.2018 10:01 pm

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 1093 views