Simplex algorithm — tabular method

NumPy | Python Methods and Functions

Example: Consider the following maximization problem.

Initial construction stages:

  • Build your matrix A. A will contain the coefficients of the constraints.
  • Matrix b will contain the amount of resources.
  • And matrix c will contain the coefficients of the objective function or cost.
  • For the above problem —
    Matrix A — at iteration 0

    iteration 0

    Table explanation
    B: The base and contains the main variables. The simplex algorithm starts with those variables that form the identity matrix. For example, in the above example, x4 and x3 form the 2 × 2 identity matrix.
    CB: are the coefficients of the main variables in the objective function. The target functions do not contain x4 and x3, so they are equal to 0.
    XB: the amount of resources, or we can say RHS from the limits.
    yi: full matrix A.

      Simplex Algorithm  1. Start with the initial basis associated with identity matrix. 2. Calculate the relative profits.  For MAX problem-  If all the relative profits are less than or equal to 0, then the current basis is the optimal one. STOP. Else contniue to 3.  For MIN problem  If all the relative profits are greater than or equal to 0, then the current basis is the optimal one. STOP. Else contniue to 3. 3. Find the column corresponding to max relative profit. Say column k has the max Rel. profit. So xk will enter the basis. 4. Perform a min ratio test to determine which variable will leave the basis.   Index of the min element ie `r` will determine the leaving variable. The basic variable at index r, will leave the basis.  NOTE: Min ratio test is always performed on positive elements.  5. It`s evident that the entered variable will not form an identity matrix, so we will have to perform row operations to make it identity again. Find the pivot element. The element at index (r, k) will be the pivot element and row r will be the pivot row. 6. Divide the rth row by pivot to make it 1. And subtract c * (rth row) from other rows to make them 0, where c is the coefficient required to make that row 0. 

    Table at iteration 1

    Table at iteration 1

    Calculation of relative profit — (Cj — Zj), where Cj — coefficient in Z, and Zj — yi * CB
    C1 — Z1 = 1 — (1 * 0 + 2 * 0)
    C2 — Z2 = 1 — (1 * 0 + 1 * 0)
    C3 — Z3 = 0 — (0 * 0 + 1 * 0)
    C4 — Z4 = 0 — (1 * 0 + 0 * 0)

    So the Relative Profit — 1, 1, 0, 0 (as shown in the table)
    It is clear that not all relative profits are less than or equal to 0. Therefore, we will perform the next iteration.
    Defining an input variable and an output variable.
    Maximum relative profit 1 for index 1. Thus, x1 will be included in the base.

    The minimum value (8, 5) is 5, which corresponds to index 2. So x3 will leave the base .

    Since the x1 entered does the necessary row operations to create the identity matrix.

    Summary index = [2, 4]
    Pivot = 2

    Divide the 2nd row by the pivot element i.e. 2 to make it 1.
    And subtract 1 * R2 from R1 to make it 0
    See the following table.

    Table at iteration 2

    Iteration 2 table

    Relative profit = 0, 1/2, -1/2, 0
    Composite index = [1, 5]
    Pivot element = 1/2
    Perform the necessary operations with the strings.
    See the following table

    Table at iteration 3

    Relative profit = 0, 0, 0, -1
    Since all relative profits are less than or equal to 0. Thus, the optimality is achieved.
    This will be the final simplex table and the optimal one.
    Z value for optimality = 6 * 1 + 2 * 1 = 8

    The following cases may occur when this algorithm is executed.

    • Case 1 — Unlimited Solution
      If the column corresponding to the maximum relative profit contains only non-positive real numbers, we will not be able to perform the minimum ratio test. Therefore, it is reported as an unlimited solution.
    • Case 2 — Alternative solution
      If at any iteration the relative profit of any one minor variable is equal to 0, then it contains alternative solutions. Many optimal solutions will exist.

    Example 2
    The above example was a case of equality where we were able to find an initial basis. Now let`s run a simplex for an example where there is no identity formation.

    Convert the above issue to standard form i.e.

    where x3, x4 and x5 — weak variables . They will form the identity and therefore the original foundation.
    Table at iteration 0

    Table at iteration 0

    Now continue as in the previous example.
    Table at iteration 1

    Table at iteration 1

    Relative profit = 2, 5, 0, 0, 0
    Composite index = [2, 5]
    Pivot element = 1

    Table in iteration 2

    Table at iteration 2

    Relative profit = 2, 0, 0, -5, 0
    Composite index = [1, 4]
    Spread element = 1

    Table at iteration 3

    Table at iteration 3

    Relative profit = 0, 0, 0, -2, -3, 0
    Since all relative profits are less than equal to 0. Optimality is achieved.
    This is the last simplex table and optimal.
    Z value for optimality = 3 * 2 + 3 * 5 + 0 * 0 = 21

    Code implementation of the simplex algorithm

    import numpy as np 

    from fractions import Fraction # to not display numbers in decimal.

      

    print ( " **** SiMplex Algorithm ****" )

     
    # inputs

     
    # A will contain the constraint factors

    A = np.array ([[ 1 , 1 , 0 , 1 ], [ 2 , 1 , 1 , 0 ]])

    # b will contain the amount of resources

    b = np.array ([ 8 , 10 ]) 

    # c will be contain the coefficients of the objective function Z

    c = np.array ([ 1 , 1 , 0 , 0 ]) 

      
    # B will contain the main variables that make up the identity matrix

    cb = np.array (c [ 3 ])

    B = np.array ([[ 3 ], [ 2 ]]) 

    # cb contains their corresponding coefficients in Z

    cb = np.vstack ((cb, c [ 2 ])) 

    xb = np.transpose ([b]) 

    # combine matrices B and CB

    table = np.hstack ((B, cb)) 

    table = np.hstack ((table, xb)) 

    # combine matrices B, cb and xb
    # finally combine matrix A to form a complete simplex table

    table = np.hstack ((table, A)) 

    # change table type to float

    table = np.array (table, dtype = `float`

    # input end

     
    # if the problem is min, make this variable 1

    MIN = 0

     

    print ( "Table at itr = 0" )

    print ( "B CB XB y1 y2 y3 y4" )

    for row in table:

      for el in row:

    # limit the denominator to 100

    print (Fraction ( str (el)). limit_denominator ( 100 ), end = ``

    print ()

    print ()

    print ( "Simplex Working ...." )

     
    # when optimal, this will be done 1

    reached = 0  

    itr = 1

    unbounded = 0

    alternate = 0

     

    while reached = = 0 :

     

    print ( "Iteration : " , end = ` ` )

    print (itr)

      print ( "B CB XB y1 y2 y3 y4" )

    for row in table:

    for el in row:

    print (Fraction ( str (el)). limit_denominator ( 100 ), end = `` )

    print ()

     

    # calculate relative profit- & gt; cj - zj for non-core

    i = 0

    rel_prof = []

    while i & lt; len (A [ 0 ]):

      rel_prof.append (c [i] - np. sum (table [:, 1 ] * table [:, 3 + i]))

    i = i + 1

     

    print ( " rel profit: " , end = " " )

    for profit in rel_prof:

      print (Fraction ( str (profit)). limit_denominator ( 100 ), end = "," )

    print ()

    i = 0

     

    b_var = table [:, 0 ]

      # check alternative solution

    while i & lt; len (A [ 0 ]):

    j = 0

      present = 0

    while j & lt; len (b_var):

    if int (b_var [ j]) = = i:

    present = 1

    break ;

    j + = 1

    if present = = 0 :

    if rel_prof [i] = = 0 :

    alternate = 1

    print ( "Case of Alternate found" )

    # print (i, end = & quot; & quot;)

    i + = 1

      print ( )

    flag = 0

    for profit in rel_prof:

    if profit & gt; 0 :

    flag = 1

    break

      # if all relative profits & lt; = 0

    if flag = = 0 :

      print ( "All profits are & lt; = 0, optimality reached" )

    reached = 1

    break

     

    # kth var will form the basis

    k = rel_prof.index ( max (rel_prof))

    min = 99999

    i = 0 ;

    r = - 1

    # min test ratio (positive values ​​only)

    while i & lt; len (table):

    if (table [:, 2 ] [i] & gt; 0 and table [:, 3 + k] [i] & gt; 0 ): 

      val = table [:, 2 ] [ i] / table [:, 3 + k] [i]

    if val & lt; min :

    min = val

    r = # leaving the variable

    i + = 1

     

      # if no minimum ratio test was performed

      if r = = - 1 :

    unbounded = 1

    print ( "Case of Unbounded" )

    break

     

    print ( "pivot element index:" , end = ` ` )

    print (np.array ([r, 3 + k]))

     

    pivot = table [r] [ 3 + k]

    print ( "pivot element:" , end = "" )

    print (Fraction (pivot). limit_denominator ( 100 ))

     

    # perform string operations

    # split pivot line with pivot

    table [r, 2 : len (table [ 0 ])] = table [

    r, 2 : len (table [ 0 ])] / pivot

      

      # perform line operation on other lines

    i = 0

    while i & lt; len (table):

    if i! = r:

    table [i, 2 : len (table [ 0 ])] = table [i,

    code class = "keyword"> = r:

    table [i, 2 : len (table [ 0 ])] = table [i,

    code class = "keyword"> = r:

    table [i, 2 : len (table [ 0 ])] = table [i,





    Get Solution for free from DataCamp guru