Scribd Logo
Upload

Welcome to Scribd!

  • 47 views

    Notes 2 - 4 - Algebraic Method Minimization

    Uploaded by

    Princess Joy Diocares
    The document discusses using the algebraic method to solve a linear programming problem. It introduces slack variables to convert inequality constraints to equality constraints. The problem is then solved by assuming values for non-basic variables and solving the basic variables. There are 6 possible combinations of basic and non-basic variables. The optimal solution is found when X1 and X2 are chosen as the basic variables.

    Copyright:

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

    Notes 2 - 4 - Algebraic Method Minimization

    Uploaded by

    Princess Joy Diocares
    47 views8 pages
    The document discusses using the algebraic method to solve a linear programming problem. It introduces slack variables to convert inequality constraints to equality constraints. The problem is then solved by assuming values for non-basic variables and solving the basic variables. There are 6 possible combinations of basic and non-basic variables. The optimal solution is found when X1 and X2 are chosen as the basic variables.

    Original Description:

    Numerical Method Notes

    Original Title

    Notes-2_4_Algebraic-Method-Minimization

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses using the algebraic method to solve a linear programming problem. It introduces slack variables to convert inequality constraints to equality constraints. The problem is then solved by assuming values for non-basic variables and solving the basic variables. There are 6 possible combinations of basic and non-basic variables. The optimal solution is found when X1 and X2 are chosen as the basic variables.

    Copyright:

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

    Notes 2 - 4 - Algebraic Method Minimization

    Uploaded by

    Princess Joy Diocares
    The document discusses using the algebraic method to solve a linear programming problem. It introduces slack variables to convert inequality constraints to equality constraints. The problem is then solved by assuming values for non-basic variables and solving the basic variables. There are 6 possible combinations of basic and non-basic variables. The optimal solution is found when X1 and X2 are chosen as the basic variables.

    Copyright:

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

    Operation Research

    Linear Programming
    Algebraic Method
    Minimization
    — Consider the Linear Programming Problem formulated

    — Minimize 7X1 + 5X2


    — Subject to
    — X1 + X2 ≥ 4
    — 5X1 + 2X2 ≥ 10
    — X1, X2 ≥ 0

    — We will convert the inequality constraints to equations.


    Algebraic Method LP
    The in-equality constraints can now be converted to equalities
    by introducing slack variables (x3 and x4)
    — Minimize 7X1 + 5X2
    — Subject to
    X1 + X2 ≥ 4 X1 + X2 – X3 = 4
    5X1 + 2X2 ≥ 10 5X1 + 2X2 – X4 = 10
    X1, X2 ≥ 0 X1, X2, X3, X4 ≥ 0

    — x3 and x4 are variables that will be subtracted on the inequality


    equations to make it equality. (if the sum of x1 and x2 is greater
    than the right hand side of the equation, then the value of x3 or
    x4 will be subtracted to make it equal.)
    — This negative slack variable is called “Surplus Variable”
    Algebraic Method LP
    Slack Variable:

    —When we have a greater than or equal to constraint, we


    have a negative slack variable or a surplus variable
    introduced.

    —When we had a less than or equal to constraint, we


    introduced X3 and X4 as positive slack variables.
    Algebraic Method LP
    — Minimize 7X1 + 5X2
    — Subject to
    — X1 + X2 – X3 = 4
    — 5X1 + 2X2 – X4 = 10
    — X1, X2, X3, X4 ≥ 0

    — We now have 4 variables for only two equations


    — Let us solve 2 variables at a time
    — Assume value for the variables that will not be solved (fixed
    variable)
    — Then solved for the other remaining 2 variables
    Algebraic Method LP
    — Minimize 7X1 + 5X2
    — Subject to
    — X1 + X2 – X3 = 4
    — 5X1 + 2X2 – X4 = 10
    — X1, X2, X3, X4 ≥ 0

    — Variables to be solved = Basic variable


    — Variables fixed to zero = non-basic variable

    — Total number of combinations : 4C2=6


    Algebraic Method LP
    No Basic Non-basic Solution Objective Comments
    Variables Variable function
    value
    1 X3 & X4 X1 & X2 =0 X3=4; x4=- Infeasible
    10
    2 X1 & X3 X2 & X4 =0 X1=2;X3=- Infeasible
    2
    3 X1 & X4 X2 & X4 =0 X1=4, Z=28 Basic Feasible
    X4=10
    4 X2 & X3 X1 & X4 =0 X2=5,X3=1 Z=25 Basic Feasible
    5 X2 & X4 X1& X3 X2=4, X4=- Infeasible
    2
    6 X1 & X2 X3=0; X1=2/3, Z=64/3 Basic
    X4=0 X2=10/3 Feasible-
    Optimum

    You might also like