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 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.


    SIMPLEX METHOD 

    BIG-M METHOD 


    NOTES 



    Comments

    READ ARTICLES:

    VARIOUS METHODS FOR SEDIMENT CONTROL IN ALLUVIAL RIVER

    What is the Importance of Geometric Design of Highway?

    WHAT IS LINEAR PROGRAMMING? | ADVANTAGES AND LIMITATIONS OF LP | APPLICATIONS OF LP

    GROUND WATER HYDROLOGY NUMERICALS | HYDROLOGY AND WATER RESOURCES ENGINEERING