Algoritmo Simplex – Método Tabular

El Algoritmo Simplex es una técnica de optimización muy conocida en Programación Lineal . La forma general de un LPP (Problema de Programación Lineal) es  Ejemplo: Consideremos el siguiente problema de maximización. Pasos iniciales de construcción: 

• Construya su array A. A contendrá los coeficientes de las restricciones.
• La array b contendrá la cantidad de recursos.
• Y la array c contendrá los coeficientes de función objetivo o costo.

Para el problema anterior – Array A – En la iteración 0

En la iteración 0

Explicación de la tabla- B : Base y contiene las variables básicas. El algoritmo simplex comienza con aquellas variables que forman una array de identidad. En lo anterior, por ejemplo, x4 y x3 forman una array identidad de 2×2. CB : Son los coeficientes de las variables básicas en la función objetivo. Las funciones objetivo no contienen x4 y x3, por lo que estos son 0. XB: El número de recursos o podemos decir el RHS de las restricciones. yi : La Array A completa.

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 continue 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 continue 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 i.e '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.

Tabla en la iteración 1

Tabla en la iteración 1

Cálculo de beneficios relativos – (Cj – Zj), donde Cj es el coeficiente en Z y Zj es 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) Entonces, las ganancias relativas son: 1, 1, 0, 0 (como se muestra en la tabla) Claramente no todas las ganancias relativas son menores o iguales a 0. Así se realizará la siguiente iteración. Determinación de variable de entrada y variable de salida. Beneficio relativo máximo 1 en el índice 1. Por lo tanto, x1 ingresará a la base. Min de (8, 5) es 5 que está en el índice 2. Entonces x3 dejará la base. Dado que x1 ingresó, realice las operaciones de fila requeridas para hacer una array de identidad. Índice de pivote = [2, 4] Elemento de pivote = 2 Divida la segunda fila por el elemento de pivote, es decir, 2 para convertirlo en 1. Y reste 1*R2 de R1 para convertirlo en 0 Consulte la siguiente tabla. Tabla en la iteración 2

Tabla en la iteración 2

Beneficios relativos = 0, 1/2, -1/2, 0 Índice de pivote = [1, 5] Elemento de pivote = 1/2 Realice las operaciones de fila necesarias. Ver tabla siguiente

Tabla en la iteración 3

Ganancias relativas = 0, 0, 0, -1 Ya que todas las ganancias relativas son menores o iguales a 0. Entonces se alcanza la optimización. Esta será la tabla símplex final y la óptima. Valor de Z en la optimización = 6*1 + 2*1 = 8 Los siguientes casos pueden ocurrir mientras se realiza este algoritmo.

• Caso 1 : solución ilimitada Si la columna correspondiente a la ganancia relativa máxima contiene solo números reales no positivos, entonces no podremos realizar la prueba de la relación mínima. Por lo tanto, se reporta como una solución ilimitada.
• Caso 2 : solución alternativa Si en cualquier iteración cualquiera de las ganancias relativas de la variable no básica resulta ser 0, entonces contiene soluciones alternativas. Existirán muchas soluciones óptimas.

Ejemplo 2 El ejemplo anterior fue un caso de igualdad donde pudimos encontrar la base inicial. Ahora realizaremos simplex en un ejemplo donde no se forma identidad. Convierta el problema anterior a la forma estándar, es decir  , donde x3, x4 y x5 son variables de holgura . Estos formarán la identidad y por lo tanto la base inicial. Tabla en la iteración 0

Tabla en la iteración 0

Ahora continuando como el ejemplo anterior. Tabla en la iteración 1

Tabla en la iteración 1

Beneficios relativos = 2, 5, 0, 0, 0 Índice de pivote = [2, 5] Elemento de pivote = 1 Tabla en la iteración 2

Tabla en la iteración 2

Beneficios relativos = 2, 0, 0, -5, 0 Índice de pivote = [1, 4] Elemento de pivote = 1 Tabla en la iteración 3

Tabla en la iteración 3

Ganancias relativas = 0, 0, 0, -2, -3, 0 Ya que todas las ganancias relativas son menos que iguales a 0. Se alcanza la optimización. Esta es la tabla símplex final y la óptima. Valor de Z en la optimización = 3*2 + 3*5 + 0*0 = 21 Implementación de código del algoritmo Simplex 

import numpy as np
from fractions import Fraction # so that numbers are not displayed in decimal.
 
print("\n                 ****SiMplex Algorithm ****\n\n")
 
# inputs
 
# A will contain the coefficients of the constraints
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 contain coefficients of objective function Z     
c = np.array([1, 1, 0, 0])            
 
# B will contain the basic variables that make 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 the complete simplex table
table = np.hstack((table, A))        
# change the type of table to float
table = np.array(table, dtype ='float')
# inputs end
 
# if min problem, make this var 1
MIN = 0
 
print("Table at itr = 0")
print("B \tCB \tXB \ty1 \ty2 \ty3 \ty4")
for row in table:
    for el in row:
                # limit the denominator under 100
        print(Fraction(str(el)).limit_denominator(100), end ='\t')
    print()
print()
print("Simplex Working....")
 
# when optimality reached it will be made 1
reached = 0    
itr = 1
unbounded = 0
alternate = 0
 
while reached == 0:
 
    print("Iteration: ", end =' ')
    print(itr)
    print("B \tCB \tXB \ty1 \ty2 \ty3 \ty4")
    for row in table:
        for el in row:
            print(Fraction(str(el)).limit_denominator(100), end ='\t')
        print()
 
    # calculate Relative profits-> cj - zj for non-basics
    i = 0
    rel_prof = []
    while i<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]
    # checking for alternate solution
    while i<len(A[0]):
        j = 0
        present = 0
        while j<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 =" ")
        i+= 1
    print()
    flag = 0
    for profit in rel_prof:
        if profit>0:
            flag = 1
            break
        # if all relative profits <= 0
    if flag == 0:
        print("All profits are <= 0, optimality reached")
        reached = 1
        break
 
    # kth var will enter the basis
    k = rel_prof.index(max(rel_prof))
    min = 99999
    i = 0;
    r = -1
    # min ratio test (only positive values)
    while i<len(table):
        if (table[:, 2][i]>0 and table[:, 3 + k][i]>0):
            val = table[:, 2][i]/table[:, 3 + k][i]
            if val<min:
                min = val
                r = i     # leaving variable
        i+= 1
 
        # if no min 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 row operations
    # divide the pivot row with the pivot element
    table[r, 2:len(table[0])] = table[
            r, 2:len(table[0])] / pivot
             
    # do row operation on other rows
    i = 0
    while i<len(table):
        if i != r:
            table[i, 2:len(table[0])] = table[i,
                 2:len(table[0])] - table[i][3 + k] *
                 table[r, 2:len(table[0])]
        i += 1
 
     
    # assign the new basic variable
    table[r][0] = k
    table[r][1] = c[k]
     
    print()
    print()
    itr+= 1
     
 
print()
 
print("***************************************************************")
if unbounded == 1:
    print("UNBOUNDED LPP")
    exit()
if alternate == 1:
    print("ALTERNATE Solution")
 
print("optimal table:")
print("B \tCB \tXB \ty1 \ty2 \ty3 \ty4")
for row in table:
    for el in row:
        print(Fraction(str(el)).limit_denominator(100), end ='\t')
    print()
print()
print("value of Z at optimality: ", end =" ")
 
basis = []
i = 0
sum = 0
while i<len(table):
    sum += c[int(table[i][0])]*table[i][2]
    temp = "x"+str(int(table[i][0])+1)
    basis.append(temp)
    i+= 1
# if MIN problem make z negative
if MIN == 1:
    print(-Fraction(str(sum)).limit_denominator(100))
else:
    print(Fraction(str(sum)).limit_denominator(100))
print("Final Basis: ", end =" ")
print(basis)
 
print("Simplex Finished...")
print()

Para lo anterior, simplemente ingrese los valores requeridos y obtendrá una solución detallada paso a paso de su LPP mediante el algoritmo simplex.