ortutor

OPERATIONS RESEARECH

(Tutor)

LINEAR PROGRAMMING 

LINEAR PROGRAMMING PROBLEM (LPP)

      The general linear programming problem calls for optimizing objective function (maximizing / minimizing) the subject to the set of equations and / or inequalities called constraints or restrictions.

SOLVING LPP

There are two methods to solve LPP

• GRAPHICAL METHOD

• SIMPLEX METHOD

GRAPHICAL METHOD

   Graphical Method is used to solve the LPP with at most three variables.

ALGORITHM : GRAPHICAL METHOD

1. Consider each  inequality - constraint as equation.

2. Plot each equation on the graph, as each one will geometrically represent a straight line.

3. Shade the feasible region.  Every point on the line will satisfy the equation of the line. If the inequality constraint corresponding to the line is <= sign, then the region below the line lying in the first quadrant (due to non-negativity of variables) is shaded.  For the inequality constraint with >= sign, the region above the line in the first quadrant is shaded. The points lying in the common region will satisfy all the constraints simultaneously.  The common region thus obtained is called feasible region.

4. choose the convenient value of z (say = 0) and plot the  objective function line.

5. Pull the objective function line until the extreme points of the feasible region.  In the maximization case, this line will stop farthest from the origin and passing through at least one corner of the feasible region.  In the minimization case, this line will stop nearest to the region and pass through at least one corner of the feasible region.

6. Read the coordinates of the extreme point(s) selected in step(e), and find the maximum or minimum (as the case may be) value of z.

 SLACK VARIABLE

   The non negative variable which is added to the left hand side of the constraint to convert into equation is called the slack variable.

SURPLUS VARIABLE

   The non negative variable which is subtracted  to the left hand side of the constraint to convert into equation is called the slack variable.

STANDARD FORM OF A LINEAR PROGRAMMING PROBLEM

• 1. All the constraints should be converted to equations except for the non-negativity restrictions which remain as inequalities (>=0).

  2. The right side element of each constraint should be made non-negative ( if not).

  3. All variables must have non negative values.

  4. The objective function should be of maximization form.

IMPORTANT DEFINITIONS

SOLUTION OF LPP

    Any set X={x1, x2, - - -, xn+m} of variables is called solution to LPP, if it satisfies constraints only.

FEASIBLE SOLUTION OF LPP

    Any set X={x1, x2, - - -, xn+m} of variables is called feasible solution to LPP, if it satisfies constraints and non-negativity restrictions also.