Scribd Logo
Upload

Welcome to Scribd!

  • 142 views

    The Simplex Minimization Method

    Uploaded by

    Jean Hipolito
    1. Minimization problems commonly involve costs from slack and artificial variables. Slack variables do not contribute to cost, while artificial variables have a very high cost coefficient. 2. To convert inequality constraints to equations in minimization, add a slack variable for "<=" constraints and subtract a slack variable but add an artificial variable for ">=" constraints. 3. For "=" constraints, add an artificial variable to prevent variables from equating to zero when all other variables are zero.

    Copyright:

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

    The Simplex Minimization Method

    Uploaded by

    Jean Hipolito
    142 views13 pages
    1. Minimization problems commonly involve costs from slack and artificial variables. Slack variables do not contribute to cost, while artificial variables have a very high cost coefficient. 2. To convert inequality constraints to equations in minimization, add a slack variable for "<=" constraints and subtract a slack variable but add an artificial variable for ">=" constraints. 3. For "=" constraints, add an artificial variable to prevent variables from equating to zero when all other variables are zero.

    Original Description:

    ManaScie

    Original Title

    SIMPLEX-MINIMIZATION

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. Minimization problems commonly involve costs from slack and artificial variables. Slack variables do not contribute to cost, while artificial variables have a very high cost coefficient. 2. To convert inequality constraints to equations in minimization, add a slack variable for "<=" constraints and subtract a slack variable but add an artificial variable for ">=" constraints. 3. For "=" constraints, add an artificial variable to prevent variables from equating to zero when all other variables are zero.

    Copyright:

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

    The Simplex Minimization Method

    Uploaded by

    Jean Hipolito
    1. Minimization problems commonly involve costs from slack and artificial variables. Slack variables do not contribute to cost, while artificial variables have a very high cost coefficient. 2. To convert inequality constraints to equations in minimization, add a slack variable for "<=" constraints and subtract a slack variable but add an artificial variable for ">=" constraints. 3. For "=" constraints, add an artificial variable to prevent variables from equating to zero when all other variables are zero.

    Copyright:

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

    THE SIMPLEX

    MINIMIZATION
    METHOD
    Simplex Minimization
    Although  and = symbols are occasionally
    used in constraints of maximization problems,
    these are more common among minimization
    problems.
    We are going to discuss how to change these constraints with  and = symbols to equations.

    Subtraction of slack variables is permitted in


    minimization, because if we intend to
    minimize, it is but logical to subtract, if we
    intend to maximize, it is otherwise.
    Simplex Minimization
    Common sense tells us that to change a
    constraint with  sign to equation, simply
    subtract a slack variable from the left member.
    But in this particular case, if other variables are
    zero, the slack variable will have a negative
    value.
    For instance, x + y  10.
    If we converted to equation it becomes
    x + y – S1=10.
    Now, if x = 0 and y = 0, since the objective is to
    minimize, then S1 = –10.
    Simplex Minimization
    But it is a general rule in linear
    programming that all variables must be
    greater than or equal to zero,
    hence there’s a need to use another kind
    of variable that will save the slack variable
    from becoming negative.
    Let this be known as an “artificial” variable
    (An).
    Simplex Minimization
    An artificial variable has a large value
    which is used as a computational device
    that prevents an equality constraint from
    equating to zero, and preventing the slack
    variables from becoming negative.
    Thus, in a  symbol, we convert the
    inequality to equation by subtracting a
    slack variable, but at the same time add
    an artificial variable.
    Simplex Minimization
    In a constraint containing = symbol, add an
    artificial variable to the left member,
    to save the right member from being equated
    to zero, if other solution variables are all
    zero.
    Example: 3x + 2y = 10, if x = 0 and y = 0,
    then we will have 0 = 10, which is false.
    Hence we need an artificial and have
    3x + 2y + An = 10.
    Simplex Minimization
    Minimization problems commonly deal
    with cost.
    Slack variables do not contribute any
    amount to cost, but artificial variables
    contribute the biggest amount to cost in
    minimization problem.
    It contributes to the objective an amount
    greater than any of the coefficients of
    solution variables.
    Simplex Minimization
    For convenience, in representing the
    contribution of the artificial variable to
    the objective,
    we may use a quantity which is a power
    of ten, greater than any of the
    coefficients found in the constraints and
    objective.
    Powers of ten are numerals such as 10,
    100, 1000, etc.
    Simplex Minimization
    Steps in solving a minimization
    problem are similar to
    maximization except for 3
    processes:
    1. The Cj column of the initial table
    begins with the coefficients of the
    artificial variables and of slack variables in
    the objective with positive coefficients in
    the constraints.
    Simplex Minimization
    2. Instead of looking for the most
    positive quantity in Cj–Zj row for the
    optimum column, look for the most
    negative entry.

    3. The optimum table or final table has


    entries in the Cj–Zj row which are
    either zero or positive.
    Simplex Minimization
    SUMMARY OF CONVERTING CONSTRAINTS
    TO EQUATIONS IN A MINIMIZATION
    PROBLEM
    1. Add an artificial variable if the symbol
    is =.
    2. Add a slack variable if the symbol is ≤.
    3. Subtract a slack variable but add an
    artificial variable if the symbol is .
    Simplex Minimization
    Example 1: Consider the following linear
    program:

    Minimize C = 60x + 50y


    Subject to: 3x + 5y ≤ 15
    4x + 4y ≥ 16
    x ≥ 0, y ≥ 0
    MinimizeC = 60x + 50y
    Subject to: 3x + 5y ≤ 15
    4x + 4y ≥ 16
    x ≥ 0, y ≥ 0

    Solution:
    The new program with slack and
    artificial variables:
    Minimize C = 60x+50y +0S1+0S2+100A1
    Subject to: 3x + 5y + S1 = 15
    x + y – S2 + A1 = 4
    x, y ≥ 0, S1, S2 ≥ 0

    You might also like