Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Bigmmethod 150702095728 Lva1 App6892 PDF

    Uploaded by

    zohaib
    The Big M Method is a technique for solving linear programming problems that introduces artificial variables to convert inequalities into equalities. It assigns a large value M to each artificial variable. The transformed problem is then solved using the simplex method, eliminating artificial variables until an optimal solution is found. Potential drawbacks include difficulty choosing a sufficiently large M and not knowing feasibility until optimality.

    Copyright:

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

    Bigmmethod 150702095728 Lva1 App6892 PDF

    Uploaded by

    zohaib
    61 views15 pages
    The Big M Method is a technique for solving linear programming problems that introduces artificial variables to convert inequalities into equalities. It assigns a large value M to each artificial variable. The transformed problem is then solved using the simplex method, eliminating artificial variables until an optimal solution is found. Potential drawbacks include difficulty choosing a sufficiently large M and not knowing feasibility until optimality.

    Original Title

    bigmmethod-150702095728-lva1-app6892.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The Big M Method is a technique for solving linear programming problems that introduces artificial variables to convert inequalities into equalities. It assigns a large value M to each artificial variable. The transformed problem is then solved using the simplex method, eliminating artificial variables until an optimal solution is found. Potential drawbacks include difficulty choosing a sufficiently large M and not knowing feasibility until optimality.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    61 views15 pages

    Bigmmethod 150702095728 Lva1 App6892 PDF

    Uploaded by

    zohaib
    The Big M Method is a technique for solving linear programming problems that introduces artificial variables to convert inequalities into equalities. It assigns a large value M to each artificial variable. The transformed problem is then solved using the simplex method, eliminating artificial variables until an optimal solution is found. Potential drawbacks include difficulty choosing a sufficiently large M and not knowing feasibility until optimality.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Big M Method

    A Variant of Simplex Method

    Presented By : Luckshay Batra

    [email protected]
    Content
    • Introduction
    • Algorithm
    • Points to Remember
    • Example
    • Analysis of Big M Method
    • Drawbacks
    • Conclusion
    • References
    Introduction
     A method of solving linear programming problems.

     It is one of the oldest LP techniques.

     Big M refers to a large number associated with the


    artificial variables.

     The Big M method introduces surplus and artificial


    variables to convert all inequalities into standard
    form.
    Algorithm
     Add artificial variables in the model to obtain a
    feasible solution.

     Added only to the ‘>’ type or the ‘=‘


    constraints.

     A value M is assigned to each artificial variable.

     The transformed problem is then solved using


    simplex eliminating the artificial variables.
    Points To Remember
    Solve the modified LPP by simplex method, until
    any one of the three cases may arise:-

     If no artificial variable appears in the basis and the


    optimality conditions are satisfied.

     If at least one artificial variable in the basis at zero level


    and the optimality condition is satisfied .

     If at least one artificial variable appears in the basis at


    positive level and the optimality condition is satisfied, then
    the original problem has no feasible solution.
    Example
     Maximize Z = x1 + 5x2

    Subject to 4x1 + 4x2 ≤ 6


    x1 + 3x2 ≥ 2
    x1 , x2 ≥ 0

    Solution : Introducing slack & surplus variables :


    4x1 + 4x2 + S1 = 6
    x1 + 3x2 - S2 = 2
    where
    S1 is a slack variable
    S2 is a surplus variable
    The surplus variable S2 represents the extra units.
     Now if we let x1 & x2 equal to zero in the initial solution , we will
    have S1=6 , S2=-2 , which is not possible because a surplus variable
    cannot be negative . Therefore , we need artificial variables.

    Introducing an artificial variable , say A1.

     Standard Form :
    Maximize Z = x1 + 5x2+ 0s1 + 0s2 – M(A1)

    Subject to 4x1 + 4x2 +S1 = 6


    x1 + 3x2 –S2 +A1 = 2
    x1 , x2 , S1 , S2 , A1≥0
    Analysis of Big M Method
     Problem P : Minimize cx

    Subject to Ax = b
    x≥ 0

     Problem P(M) : Minimize cx + M s

    Subject to Ax + s = b
    x,s≥0
    where,
    “s” is an artificial variable
    Analysis of Big M Method

    Solve P(M) for a


    very large
    positive M

    Optimal is
    Optimal is finite
    unbounded

    s=0. Optimal s≠0. P has no s=0. Optimal s≠0. P is


    solution of P is feasible solution of P is
    infeasible
    found solutions unbounded
    Drawbacks
     How large should M be?

     If M is too large, serious numerical difficulties in a


    computer.

     Big-M method is inferior than 2 phase method.

     Here feasibility is not known until optimality.

     Never used in commercial codes.


    Conclusion
    The application of the M technique requires that M
    approaches infinity but to computerize the solution
    algorithm , M must be finite while being “sufficiently
    large.”

    The pitfall in this case is, however, if M is too large it can


    lead to substantial round-off error yielding an incorrect
    optimal solution . For this reason, most commercial LP
    solvers do not apply the M-method but use, rather, an
    artificial variable method called the two-phase
    method.
    References
     http://cbom.atozmath.com/CBOM/Simplex.aspx

     http://businessmanagementcourses.org/Lesson09TheBigMMethod.
    pdf

     http://www.slideshare.net/NiteshSinghPatel/big-m-32360766

     http://en.wikipedia.org/wiki/Big_M_method

     Linear Programming & Network Flows by Mokhtar S. Bazaraa , Hanif


    D. Sherali , John J. Jarvis

     Operation Research An Introduction by H. A. Taha

    You might also like