Método Simplex#
Es un método para resolver problemas de programación lineal de tamaño \(m X n\). Donde m son el numero de restricciones y n el numero de variables.
Conceptos Básicos:#
Variables de Decisión: Representan las incógnitas del problema.
Restricciones: Limitaciones o condiciones que deben cumplirse.
Función Objetivo: La función que se busca maximizar o minimizar.
Soluciones Factibles: Conjunto de todas las posibles soluciones que satisfacen las restricciones.
Variables artificiales
Holgura(\(H_i\) o \(S_i\)): Sobrante, lo que no se utilizó, lo que queda de una producción, material ocioso, recurso no utilizado. Es la cantidad utilizada para volver una restricción de \(\leq\) en \(=\)
Artificiales(A): Artificio que solo me ayuda a resolver el problema.
Superavit(s_i): Cantidad que se genera por encima de un mínimo.
Restricciones
\(\leq\) se agrega una variable de holgura (+S)
\(=\) Se agrega una variable artificial (+A)
\(\geq\) Se agrega una variable de superavit (-s+A)
Variables
Básicas: \(x_1, x_2,x_3,...,x_n\)
No Básicas: S,A, -S
Este método consiste en resolver un problema de programación lineal mediante varias iteraciones o tableros. Mediante entrada y salida de variables desde y hacia una base hasta llegar a un criterio de optimalidad.
En el mundo real, se utiliza para la asignación de recursos, planificación de la producción, logística de transporte, entre otros.
Análisis de las restricciones#
Restricción (\(\leq\))#
Se agrega una variable de holgura (\(+S_i\))con el objetivo de convertir una restricción de \(\leq\) en \(=\)
Restricción (\(=\))#
Es aprox \(\leq \land \geq\). Se agrega una variable artificial \((A_i)\) y se aplica el método de la gran M
Método de la gran M#
Se adiciona A en la restricción
Si PPL es MAX se resta “MA” en la función objetivo
Si PPL es MIN se adiciona “MA” en la función objetiv
Reesticción (\(\geq\))#
Se agrega una variable de superavit (\(-s_i+A_i\)) con el objetivo de convertir una restricción de \(\geq\) en \(=\)
Minimización#
Convertir la función objetivo Min en Max
Procedimiento del método simplex#
Formular el PPL
Estandarizar el problema, es decir establecer la matriz básica o canónica en donde las variables básicas son dependientes y las no basicas independientes.
Aplicar los criterios.
3.1. Criterio de entrada: Min \(C_i\)
3.2. Criterio de salida: Min \(\bigg(\frac{b_i}{a_i}\bigg)\) con \(a_i>0\)
Recuerde que buscamos optimizar \(Z = \pm C_iX_i\)
Sujeto a:
\(a_iX_i \leq = \geq b_i\);
\(x_i\geq 0\)
3.3. Pivote: Intercepto entre columna y fila.
3.4. Hacer el tratamiento para la Variable de entrada: Es decir, dejar en 1 la posición del pivote y en \(0\) las demás posiciones de la columna.
3.5. Hacer el tratamiento para la Variable de salida: Es decir, se divide el valor de cada celda entre el pivote.
3.6. Calcular los valores de las demás celdas: \(D_n = D_a - \frac{p_1 x p_2}{p}\)
Ejemplo:#
Sujeto a: $\(2x_1+2x_2\leq9\)$
Solución#
Primero analicemos las restricciones:
Sujeto a: $\(2x_1+2x_2 + S_1 = 9\)$
Ahora vamos a estandarizar las restricciones. $\(2x_1+2x_2 + S_1 = 9\)\( \)\(2x_1+x_2 + S_2 = 6\)\( **\)\(z-16x_1 -10x_2 = 0\)$**
Ahora vamos a implementar el tablero 1 simplex#
Primero vamos a encontrar el criterio de entrada, en este caso de la fila donde está z vamos a buscar el valor más lejos de cero por la izquierda.
En este caso es la columna donde está el -16 en la última fila.
Ahora debemos encontrar el criterio de salida, para ello vamos a dividir cada elemento de la columna b por su correspondiente en la columna de entrada y el menor valor de estas divisiones será la fila de salida.
Como es la fila S2 en la que está el menor valor de la división,
entonces esta será la fila que sale y podemos definir el pivote como la celda en la que se interceptan la columna de entrada y la fila salida.
Por lo tanto el pivote es 2
Tabla Simplex 2#
Tomamos la fila salida y le cambiamos el nombre por el de la columna entrada que indentificamos anteriormente y los valores de esta nueva fila serán los de la fila anterior dividio entre el pivote.
Ahora vamos a recalcular las demás filas usando la formula.
\(F_{nueva} = F_{vieja} - CPFV*(F_{entrante})\)
Donde \(CPFV\) es el valor de la fila vieja en el indice de la columna pivote.
En la siguiente imagen note que es el del color verde.
entonces para S1 queda
(9,2,2,1,0) - 2*(3,1,0.5,0,0.5) = (3,0,1,1,-1)
por lo tanto la tabla simplex 2 queda:
A esta se le vuelve a calcular la columna de entrada y la fila como al principio y se repite el proceso hasta que x1 y x2 sean identidad.
Por lo tanto el tablero 3 queda:
En este punto los valores de S1 y S2 en la fila Z se denominan precios sombra.
El resultado de este ejercicio es:
Solucion óptima única
Tarea#
Realice el calculo del siguiente problema mediante el método simplex y comparlo con el resultado obtenido mediante el método gráfico.
Sujeto a: $\(2x_1+x_2\geq4\)$
Tarea#
Teniendo en cuenta lo visto en el método, implemente un algoritmo que resuelva problemas de programación lineal usando python para cualquier problema.
Encuentre una función en Python que implemente el método Simplex para resolver problemas de optimización con restricciones.