Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    Comparative Study of LP Methods

    Uploaded by

    jonnajon92-1
    This document compares different linear programming methods including graphical, simplex, assignment, and transportation. It outlines key conditions, objectives, steps, optimality tests, solutions, and formulations for each method. Graphical methods are used for problems with two variables, simplex for two or more variables, assignment for one-to-one matching problems, and transportation for matching total availability to requirements. The document provides details on testing optimality, handling infeasibility, dealing with degeneracy, and incorporating additional constraints for each linear programming technique.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Comparative Study of LP Methods

    Uploaded by

    jonnajon92-1
    25 views1 page
    This document compares different linear programming methods including graphical, simplex, assignment, and transportation. It outlines key conditions, objectives, steps, optimality tests, solutions, and formulations for each method. Graphical methods are used for problems with two variables, simplex for two or more variables, assignment for one-to-one matching problems, and transportation for matching total availability to requirements. The document provides details on testing optimality, handling infeasibility, dealing with degeneracy, and incorporating additional constraints for each linear programming technique.

    Original Description:

    f

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document compares different linear programming methods including graphical, simplex, assignment, and transportation. It outlines key conditions, objectives, steps, optimality tests, solutions, and formulations for each method. Graphical methods are used for problems with two variables, simplex for two or more variables, assignment for one-to-one matching problems, and transportation for matching total availability to requirements. The document provides details on testing optimality, handling infeasibility, dealing with degeneracy, and incorporating additional constraints for each linear programming technique.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    25 views1 page

    Comparative Study of LP Methods

    Uploaded by

    jonnajon92-1
    This document compares different linear programming methods including graphical, simplex, assignment, and transportation. It outlines key conditions, objectives, steps, optimality tests, solutions, and formulations for each method. Graphical methods are used for problems with two variables, simplex for two or more variables, assignment for one-to-one matching problems, and transportation for matching total availability to requirements. The document provides details on testing optimality, handling infeasibility, dealing with degeneracy, and incorporating additional constraints for each linear programming technique.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 1

    Comparative Study of LP Methods

    Situations

    Graphical

    Simplex

    Assignment

    Transportation

    1.

    Condition

    Strictly 2 variables

    2 variables

    One to one one row to be


    asigned to one column

    Total availability must match


    with total requirement

    2.

    Objective

    Maximisation / Minimization

    Maximisation / Minimization

    Minimization

    Minimization

    3.

    Steps

    Class Notes

    Class Notes

    Class Notes

    Class Notes

    4.

    Optimality Test

    The point of the boundary of


    common region is put in the
    Objective function to check the
    maximum / minimum value of
    Z.

    NER (or ) should be 0 or


    negative for maximum obj or
    NER should be 0 or positive
    minimum Obj

    No. of lines drawn = Order of


    Matrix

    should be 0 or +ve

    5.

    If optimality test
    not satisfied

    Try another boundary point of


    the common region

    Iteration by making that


    Adjustment with uncovered
    column as KC, where condition element
    is not satisfied and the variable
    of KC would enter into the
    solution

    Reallocation by way of loop


    starting form the cell where is
    most negative

    6.

    No Feasible
    Solution

    When there is an artificial slack


    variable in optimal solution or
    Quantity of basic variables are
    all negative

    Not feasible if total availability


    is not matching with the total
    requirement

    (Not feasible)

    Not feasible if no. of line >


    order of matrix or Boxing not
    being done in each row or
    column

    When no common region exist


    for set of Constraints
    7.

    Opportunity Cost
    on shadow price

    8.

    Multiple or
    alternate solution

    When same results come at


    more than one boundary point
    of the common region

    When NER of non basic


    variable is 0. To get that
    alternate solution select that
    column as KC and reiterate

    9.

    Unbounded
    solution

    When there is no boundary of


    common region. Minimization
    objective can be solved using
    artificial boundary. Maximization objective cannot be solved
    if unbounded

    When replacement ratios for


    all the rows become negative.
    This would make the quantity
    of incoming variable in the
    iteration also negative. Such
    problem cannot be solved
    irrespective of the objective.

    10. Degeneracy
    (solution cannot
    be proceeded
    further)

    (0,y1)
    (x2,0)
    (x1,0)

    When any of main variable is 0


    in the optimum solution

    11. Formulation

    Objective function & constraints

    NER Value

    When any of main / basic variable has quantity = 0


    Indication of quantity of
    basic variable will be 0 can be
    obtained from Replacement
    ratio of previous iteration,
    where there is a tie between 2
    minimum Replacement Ratios
    (Tie to be broken by selecting
    any RR).

    Value

    When Arbitrary boxing is to be When of an unallocated


    done, i.e. no single 0 is available cell is 0. To get the alternate
    in a row / column
    solution allocate quantity to
    that cell by way of a loop

    Objective and constraints along Matrix showing cost / time in


    with slack / Surplus / Artificial row and columns
    slack variable and their coefficients

    M + n 1 > No. of allocations


    (This would not complete the
    (u + v) Matrix.
    Introduce e (e 0) to the least
    cost unallocated independent
    cell

    Matrix showing cost / time and


    requirement and availability of
    each column and row respectively.

    12. Prohibited
    Solution

    Introduce M (M ) in the
    prohibited cell

    Introduce M (M ) in the
    prohibited cell

    13. Conditional
    Allocation

    Remove that row and column


    and apply steps on remaining

    Allocate by way of loop to the


    conditional cell.

    You might also like