Scribd Logo
Upload

Welcome to Scribd!

  • 227 views

    Linear Programming Maximization Method

    Uploaded by

    catubig michael angelo
    The document describes the simplex method for solving linear programming problems. It provides an example problem of a tailor maximizing profits by determining the optimal number of gowns and suits to make given material constraints. The problem is modeled using variables, constraints, and an objective function which are then represented in a tableau. The simplex method iterates, choosing pivot elements and replacing rows until an optimal solution is reached - in this case making 4 gowns.

    Copyright:

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

    Linear Programming Maximization Method

    Uploaded by

    catubig michael angelo
    227 views29 pages
    The document describes the simplex method for solving linear programming problems. It provides an example problem of a tailor maximizing profits by determining the optimal number of gowns and suits to make given material constraints. The problem is modeled using variables, constraints, and an objective function which are then represented in a tableau. The simplex method iterates, choosing pivot elements and replacing rows until an optimal solution is reached - in this case making 4 gowns.

    Original Description:

    :)

    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 describes the simplex method for solving linear programming problems. It provides an example problem of a tailor maximizing profits by determining the optimal number of gowns and suits to make given material constraints. The problem is modeled using variables, constraints, and an objective function which are then represented in a tableau. The simplex method iterates, choosing pivot elements and replacing rows until an optimal solution is reached - in this case making 4 gowns.

    Copyright:

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

    Linear Programming Maximization Method

    Uploaded by

    catubig michael angelo
    The document describes the simplex method for solving linear programming problems. It provides an example problem of a tailor maximizing profits by determining the optimal number of gowns and suits to make given material constraints. The problem is modeled using variables, constraints, and an objective function which are then represented in a tableau. The simplex method iterates, choosing pivot elements and replacing rows until an optimal solution is reached - in this case making 4 gowns.

    Copyright:

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

    LINEAR PROGRAMMING Maximization

    SIMPLEX METHOD Method


    Definition of Terms
    An iterative technique that begins with a feasible
    solution that is not optimal, but serves as a starting point.

    Definition of Terms

    Sequence of steps (row operations) performed in


    moving one basic feasible solution to another.
    SAMPLE PROBLEM
    A tailor has the following materials available: 18
    square meter cotton, 20 square meter silk, 5 square
    meter wool. A gown requires the following: 3 square
    meters cotton, 2 square meter silk, and 1 square meter
    wool. A suit requires the following: 2 square meter
    cotton, 4 square meter silk. If a gown sells for Php1,200
    and a suit for Php1,600, how many of each garment
    should the tailor make to obtain the maximum amount of
    money?
    REPRESENT THE UNKNOWN IN THE
    PROBLEM

    Let: x be the number of gowns


    y be the number of suits
    TABULATE THE DATA ABOUT THE FACTS

    Materials Gown (x) Suit (y) Available


    Cotton 3 2 18
    Silk 2 4 20
    Wool 1 0 5
    Profit Php1,200 Php1,600
    FORMULATE THE OBJECTIVE FUNCTION AND
    CONSTRAINTS
    The objective function is:
    Maximize: Zj = 1200 x + 1600 y

    The structural constraints are:


    3x + 2y ≤ 18 Cotton
    2x + 4y ≤ 20 Silk
    x ≤5 Wool

    Non-negativity constraints:
    x, y ≥ 0
    CONVERT THE INEQUALITY TO EQUATION
    (STRUCTURAL CONSTRAINTS)

    Constraints Adjustments Maximization


    x≤c Add a slack variable x+s=c
    x≥c Multiply both sides by (-1) -x + s = -c
    and add a slack variable
    x=c Add a slack variable x+s=c
    CONVERT THE INEQUALITY TO EQUATION
    (STRUCTURAL CONSTRAINTS)
    The objective function is: The objective function is:

    Maximize: Zj = 1200x + 1600y Maximize: Zj = 1200x + 1600y + 0S1 + 0S2 + 0S3

    The structural constraints are: Subject to:


    3x + 2y ≤ 18 Cotton 3x + 2y + S1 =18
    2x + 4y ≤ 20 Silk 2x + 4y + S2 = 20
    x ≤ 5 Wool x + S3 = 5

    Non-negativity constraints: x, y, S1, S2 ,S3 ≥ 0


    x, y ≥ 0
    ENTER THE CONSTRAINTS COEFFICIENTS
    IN THE INITIAL TABLEAU AND CALCULATE
    Z J AND C J - Z J
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    0 S2 20 2 4 0 1 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0
    C j - Zj 1,200 1,600 0 0 0
    COMPLETED TABLEAU 1
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    0 S2 20 2 4 0 1 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0
    DETERMINE THE OPTIMUM COLUMN
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    0 S2 20 2 4 0 1 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0
    Pivot Row (PR) = RHS ÷ Intersectional Elements (IE)
    IDENTIFY THE PIVOT ROW
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    0 S2 20 2 4 0 1 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0
    Replacing Row (RR)= Pivot Row (PR) ÷ Pivot (P)
    SECOND ROW WILL BE THE REPLACING ROW
    Cj Basic Right Hand 1200 1600 0 0 0
    Variable Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    1,600 y 20 2 4 0 1 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0

    RR = (20, 2, 4, 0, 1, 0) ÷ 4
    SECOND ROW WAS REPLACED
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0
    COMPUTE THE NEW VALUES FOR THE
    REMAINING ROWS
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand Side

    x y S1 S2 S3
    0 S1 18 3 2 1 0 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 0 0 0 0 0 0
    C j - Zj 1200 1600 0 0 0

    RRow = Old Row – [ Intersectional Element (IE) x Replacing Row) ]


    First Row = (18) – (2) (5) = 8 Third Row = (5) – (0) (5) = 5
    PARTIAL TABLEAU 2
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    0 S1 8 2 0 1 -1/2 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj
    C j - Zj
    CALCULATE THE Z J AND C J – Z J VALUES
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    0 S1 8 2 0 1 -1/2 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj
    C j - Zj
    COMPLETED TABLEAU 2
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    0 S1 8 2 0 1 -1/2 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 8,000 800 1,600 0 400 0
    C j - Zj 400 0 0 -400 0

    Return to Step 7 since the Cj – Zj row still contains a


    positive entry.
    IDENTIFY THE PIVOT ROW
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    0 S1 8 2 0 1 -1/2 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 8,000 800 1,600 0 400 0
    C j - Zj 400 0 0 -400 0
    FIRST ROW IS THE REPLACING ROW
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    1,200 x 8 2 0 1 -1/2 0
    1,600 y 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 8,000 800 1,600 0 400 0
    C j - Zj 400 0 0 -400 0
    REPLACING THE REMAINING ROWS
    Cj Basic Right 1200 1600 0 0 0
    Variable Hand
    Side
    x y S1 S2 S3
    1,200 y 4 1 0 ½ -¼ 0
    1,600 S2 5 1/2 1 0 1/4 0
    0 S3 5 1 0 0 0 1
    Zj 8,000 800 1,600 0 400 0
    C j - Zj 400 0 0 -400 0
    PARTIAL TABLEAU 3

    Cj Basic Right Hand 1200 1600 0 0 0


    Variables Side

    x y S1 S2 S3
    1200 X1 4 1 0 ½ -¼ 0
    1600 X2 3 0 1 -¼ 3/8 0
    0 S3 1 0 0 -½ ¼ 1
    Zj
    Cj - Zj
    COMPLETED TABLEAU 3
    Cj Basic Right-hand 1200 1600 0 0 0
    Variables side

    x y S1 S2 S3

    1200 X1 4 1 0 ½ -¼ 0

    1600 X2 3 0 1 -¼ 3/8 0

    0 S3 1 0 0 -½ ¼ 1

    Zj 9600 1200 1600 200 300 0

    C j - Zj 0 0 -200 -300 0
    If the last Cj – Zj row do no contain a positive
    entry the tableau is optimum. Our decision will
    be to make:
    Decision:
    x = 4 gowns S1 = 0
    y = 3 suits S2 = 0
    Zj = Php9,600 profit S3 = 1
    LINEAR PROGRAMMING Maximization
    Method
    SIMPLEX METHOD Special Cases
    ALTERNATIVE OPTIMAL SOLUTION

    Objective function line coincides with one


    of the binding constraints
    More than one solution
    INFEASIBILITY

    No points satisfy all constraint equation


    No solution
    UNBOUNDED

    Value of the solution may be made infinitely


    without violating any of constraint
    Infinite Solution

    You might also like