Scribd Logo
Upload

Welcome to Scribd!

  • 55 views

    A: Simplex Method: J I Ij Bi

    Uploaded by

    Kimondo King
    There are several methods to solve linear programming problems, including the simplex method. The simplex method works by solving simultaneous equations to find an optimal solution. It involves writing the problem in standard and canonical form and then iteratively selecting leaving and entering variables until optimality is reached. This is done by calculating ratios to check for feasibility and comparing objective function coefficients to check for optimality. Two examples are provided to demonstrate solving linear programming problems using the simplex method.

    Copyright:

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

    A: Simplex Method: J I Ij Bi

    Uploaded by

    Kimondo King
    55 views4 pages
    There are several methods to solve linear programming problems, including the simplex method. The simplex method works by solving simultaneous equations to find an optimal solution. It involves writing the problem in standard and canonical form and then iteratively selecting leaving and entering variables until optimality is reached. This is done by calculating ratios to check for feasibility and comparing objective function coefficients to check for optimality. Two examples are provided to demonstrate solving linear programming problems using the simplex method.

    Original Title

    STA 225 LECTURE 4

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    There are several methods to solve linear programming problems, including the simplex method. The simplex method works by solving simultaneous equations to find an optimal solution. It involves writing the problem in standard and canonical form and then iteratively selecting leaving and entering variables until optimality is reached. This is done by calculating ratios to check for feasibility and comparing objective function coefficients to check for optimality. Two examples are provided to demonstrate solving linear programming problems using the simplex method.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    55 views4 pages

    A: Simplex Method: J I Ij Bi

    Uploaded by

    Kimondo King
    There are several methods to solve linear programming problems, including the simplex method. The simplex method works by solving simultaneous equations to find an optimal solution. It involves writing the problem in standard and canonical form and then iteratively selecting leaving and entering variables until optimality is reached. This is done by calculating ratios to check for feasibility and comparing objective function coefficients to check for optimality. Two examples are provided to demonstrate solving linear programming problems using the simplex method.

    Copyright:

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

    LINEAR PROGRAMMING METHODS

    There are many algorithmic methods to solve linear programming problems.

    A: SIMPLEX METHOD

    This method is devised based on the concept of solving simultaneous equations. The
    working of the simplex method can be illustrated using the example below

    EXAMPLE ONE

    Max: z=6 x 1 +8 x2

    S/t: 5 x 1+10 x 2 ≤ 60

    4 x1 + 4 x 2 ≤ 40

    x1 , x2 ≥ 0

    Solution:

    The standard form of the l.p is given as

    Max: z=6 x 1 +8 x2 +0 s1 +0 s2

    s/t: 5 x 1+10 x 2+ s 1=¿60 ¿

    4 x1 + 4 x 2+ s 2=40

    x 1 , x 2 , s1∧s 2 ≥ 0

    Where s1∧s2 are the slack variables which are introduced to balance the constraints

    The canonical form is the form in which each constraint has a basic variable.
    Definition of a Basic Variable
    A variable is said to be a basic variable if it has unit coefficient in one of the constraints.
    If all constraints carry≤ then the standard form is the canonical form.

    cj 6 8 0 0 b i /aij
    c Bi Basic variables x1 x2 s1 s2 Solution Ratio
    l1 0 s1 5 10 1 0 60 60/10=6
    l2 0 s2 4 4 0 1 40 40 /4=10
    zj 0 0 0 0 0
    c j−z j 6 8 0 0
    Have, c j is the coefficient of the j th term of the objective function and CB i is the
    coefficient of the i th basic variable. The value of the intersection of the key row and the
    key column is called the key element. The value of z j is computed using the formula
    2
    z j =∑ (CB i )(aij )
    c=1

    Where a ij is the technological coefficient for the j th column of the table. c j−z j Is the
    relative contribution . In this term c j is the objective function coefficient of the j th
    variable. The value of z j against the solution column is the value of the objective
    function in this iteration in this case.

    Optimality condition

    For maximization problem, if all c j−z j are less than or equal to zero, than optimality is
    reached, otherwise select the variable with the most negative value as the entering
    variable. The chosen column is called the key column.

    Feasibility condition

    To maintain the feasibility of the solution in each iteration,

    i. In each row find the ratio between the solution column value and the value in
    the key column
    ii. Select the variable from the present set of basic variables with respect to
    minimum ration, such variable is the leaving variable and corresponding row is
    called the key row. The value of the intersection is called the key/pivot element.

    cj 6 8 0 0
    CB i Basic x1 x2 s1 s2 Solution Ratio
    8 x2
    variable 1/2 1 1/10 0 6 6 /0.5 l3
    0 s2 2 0 −2/5 1 16 l4
    zj 4 8 4 /5 0 48
    c j−z j 0 0 −4/5 0

    l1
    l 3=
    pivot element

    l 4 =l 2−4 l 3
    cj 6 8 0 0 solution
    CB i Basic variable x 1 x2 s1 s2
    8 x1 0 1 1/5 1/4 2
    6 x2 1 0 −1/5 1/2 8
    zj 6 8 2/5 1 64
    c j−z j 0 0 −2/5 1
    All the values for c j−z j are either 0 or negative. Hence the optimality is reached

    x 1=8 units

    x 2=2 units

    z=64
    EXAMPLE TWO

    Solve the following l.p problem using the simplex method

    Maximize: z=10 x 1+15 x 2 +20 x3


    S/t :2 x1 + 4 x 2+ 6 x 3 ≤24
    3 x 1+ 9 x 2 +6 x 3 ≤ 30
    x1 , x2 , x3 ≥ 0
    The standard form of this problem is
    Maximize: z=10 x 1+15 x 2 +20 x3
    S/t: 2 x1 + 4 x 2+ 6 x 3 + s1=24
    3 x 1+ 9 x 2 +6 x 3+ s 2=30
    x 1 , x 2 , x 3 , s1 , s 2 ≥ 0
    When s1 and s2 are slack variables. Here all constraints are of the≤ types and hence the
    canonical form is the standard form.
    Max: Z=10 x1 +15 x 2+ 20 x 3 +0 s 1 +0 s 2
    S/t: 2 x1 + 4 x 2+ 6 x 3 + s1=24
    3 x 1+ 9 x 2 +6 x 3+ s 2=30
    x 1 , x 2 , x 3 , s1 , s 2 ≥ 0

    cj 10 15 20 0 0
    CB i basis Basic x1 x2 x3 s1 s2 Solution Ratio
    variable
    0 s1 2 4 6 1 0 24 4
    0 s2 3 9 6 0 1 30 5
    zj 0 0 0 0 0 0
    c j−z j 10 15 20 0 0
    cj 10 15 20 0 0
    CB i Basic x1 x2 x3 s1 s2 solution ratio
    20 x3
    variable 1/3 2/3 1 1/6 0 4 12
    0 s2 1 5 0 -1 1 6 6
    zj 20/3 40 /3 20 10/3 0 80
    c j−z j 10/3 5/3 0 −10 0
    3

    cj 10 15 20 0 0
    CB i Basic x1 x2 x3 s1 s2 solution
    20 x3
    variable 0 -1 1 1 −1 2
    0 x1 1 5 0 2
    -1 13 6
    zj 10 30 20 0 10 100
    c j−z j 0 -15 0 0 3
    −10
    3
    x 1=6 , x 2=0 , x3 =2∧z ( optimum )=100
    TORA moment

    You might also like