| Objeto | Peso (kg) | Volumen (l) | Costo (monedas) | Consumo de Karma |
|---|---|---|---|---|
| Poción de Salud | 3 | 1 | 100 | 10 |
| Elixir de Ataque | 2 | 1 | 150 | 15 |
| Tónico de Velocidad | 1 | 0.5 | 200 | 20 |
| Escudo de Defensa | 10 | 5 | 250 | 25 |
| Hierbas Curativas | 0.5 | 0.2 | 50 | 5 |
| Cristal de Poder | 5 | 2 | 300 | 30 |
| Crema de la Sapiencia | 0.1 | 0.05 | 500 | 50 |
| Polvo de Agilidad | 4 | 3 | 200 | 20 |
| Brevaje de Invisibilidad | 2 | 1 | 350 | 35 |
| Pudin de Regeneración | 0.05 | 0.01 | 100 | 10 |
| Límite mochila de Hodor | 50 | 30 | 1500 | 500 |
Inicialización del simplex
1 Motivaciones
1.1 La partición trivial
En los problemas lineales, para poder inicializar el método simplex necesitamos de una solución básica factible inicial, esto es una base \(\mathcal{B}\) tal que \(x_{\mathcal{B}} \ge0\).
En problemas con todas las restricciones de tipo \(\le\) y con el vector de recursos \(b\ge0\), se garantiza una solución básica inicial factible, ya que al agregar las variables para estandarizar las restricciones, todas las variables son de holgura.
1.1.1 Ejemplo
Modelo sin estandarizar: \[\min z = c_1x_1+c_2x_2 + \ldots + c_nx_n\] S. a:
\[\begin{matrix}a_{11}x_1 & + & a_{12}x_2 & + & \ldots & + & a_{1n}x_n & \le & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \ldots & + & a_{2n}x_n & \le & b_2 \\ \vdots & + & \vdots & + & \ddots & + & \vdots & \le & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \ldots & + & a_{mn}x_n & \le & b_m \end{matrix}\]
\(\implies\)
Modelo estandarizado: \[\min z = c_1x_1+c_2x_2 + \ldots + c_nx_n + 0x_{n+1}^s + 0x_{n+2}^s + \ldots + 0x_{n+m}^s\] S. a:
\[\begin{matrix}a_{11}x_1 & + & a_{12}x_2 & + & \ldots & + & a_{1n}x_n & & + x_{n+1}^s & & & & = & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \ldots & + & a_{2n}x_n & & & + x_{n+2}^s & & & = & b_2 \\ \vdots & + & \vdots & + & \ddots & + & \vdots & & & & + \ddots & & = & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \ldots & + & a_{mn}x_n & & & & & +x_{n+m}^s & = & b_m \end{matrix}\]
La partición \(\mathcal{B} = \{n+1, n+2, \ldots, n+m\}\), \(\mathcal{N} = \{1, 2, \ldots, n\}\), la cual llamaremos partición trivial, da las siguientes matrices:
\[B= \begin{bmatrix}1 & 0 & \ldots & 0 \\ 0 & 1 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{bmatrix}, N = \begin{bmatrix}a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \ldots & a_{mn}\end{bmatrix}\]
Note que \(B = I\). Esta es la principal característica de la partición trivial, da como resultado una matriz básica que es la identidad. Por propiedades de la inversa, \(I^{-1} = I\), es decir que \(B^{-1} = I\) también. Por lo tanto, considerando un \(b\ge0\), la partición trivial garantiza una solución básica factible inicial, ya que: \[x_{\mathcal{B}} = B^{-1}b = b \ge 0\]
Lo cual es una solución básica factible inicial y se puede iniciar el algoritmo del simplex para resolver el problema.
1.1.2 No todo es color de rosa: las particiones triviales son atípicas
Sin embargo, no siempre se puede conseguir una partición trivial. Por ejemplo, si hay restricciones de tipo o de tipo \(\ge\) se añaden variables de exceso, que tendrán coeficientes negativos en la matriz tecnológica. Similar caso ocurre si hay restricciones de tipo \(=\), en las cuales, no se añaden ni variables de holgura ni de exceso.
1.1.3 Ejemplo 2
Observe el ejemplo anterior pero con la segunda restricción siendo de tipo \(\ge\):
Modelo sin estandarizar: \[\min z = c_1x_1+c_2x_2 + \ldots + c_nx_n\] S. a:
\[\begin{matrix}a_{11}x_1 & + & a_{12}x_2 & + & \ldots & + & a_{1n}x_n & \le & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \ldots & + & a_{2n}x_n & \ge & b_2 \\ \vdots & + & \vdots & + & \ddots & + & \vdots & \le & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \ldots & + & a_{mn}x_n & \le & b_m \end{matrix}\]
\(\implies\)
Modelo estandarizado: \[\min z = c_1x_1+c_2x_2 + \ldots + c_nx_n + 0x_{n+1}^s + 0x_{n+2}^s + \ldots + 0x_{n+m}^s\] S. a:
\[\begin{matrix}a_{11}x_1 & + & a_{12}x_2 & + & \ldots & + & a_{1n}x_n & + x_{n+1}^s & & & & = & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \ldots & + & a_{2n}x_n & & -x_{n+2}^s & & & = & b_2 \\ \vdots & + & \vdots & + & \ddots & + & \vdots & & & \ddots & & = & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \ldots & + & a_{mn}x_n & & & & +x_{n+m}^s & = & b_m \end{matrix}\]
La partición \(\mathcal{B} = \{n+1, n+2, \ldots, n+m\}\), \(\mathcal{N} = \{1, 2, \ldots, n\}\), la cual llamaremos partición trivial, da las siguientes matrices:
\[B= \begin{bmatrix}1 & 0 & \ldots & 0 \\ 0 & -1 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{bmatrix}, N = \begin{bmatrix}a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \ldots & a_{mn}\end{bmatrix}\]
Note que ahora \(B\neq I\), y su inversa resulta en: \[B^{-1} = \begin{bmatrix}1 & 0 & \ldots & 0 \\ 0 & -1 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{bmatrix}\]
Para obtener la solución básica, hacemos:
\[x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}1 & 0 & \ldots & 0 \\ 0 & -1 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{bmatrix}\cdot \begin{bmatrix}b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} =\begin{bmatrix} b_1 \\ \textcolor{red}{-b_2} \\ \vdots \\ b_m \end{bmatrix} \] Observe que debido a la componente \(\textcolor{red}{-b_1}\), \(x_{\mathcal{B}} \ngeq 0\). Por lo tanto no podríamos inicializar el método simplex.
1.2 Las soluciones a esta dificultad
Para solucionar la dificultad de encontrar una partición básica factible inicial, se pueden varias vías:
1. Buscar otra partición dentro del problema existente.
2. Adicionar variables ficticias o artificiales para producir una base que desemboque en \(B = I\).
La primera de las soluciones es problemática por que si bien podríamos hacer esa búsqueda de forma heurística. En el peor de los casos, el gasto computacional de hacerlo podría ser prohibitivo. Por ejemplo, en un problema de 40 variables y 15 restricciones, en el peor caso habría que probar \(40C15\) posibles bases. Esto equivale a más de 40mil millones de bases diferentes.
La solución 2 se vuelve más atractiva. Pero estas nuevas variables serán apenas un auxilio en la consecusión de una base factible inicial para el problema original. Por lo tanto ellas deben ser eliminadas una vez conseguido este objetivo.
Para lograrlo hay dos formas bien conocidas y documentadas en la literatura:
2.1. El método de las 2 fases.
2.2. El método de la gran M.
En ambos métodos se adicionan unas variables nuevas llamadas variables artificiales, que se eliminarán posteriormente durante el desarrollo del método.
2 Método de las 2 fases
Este método consiste en crear un problema auxiliar (Fase 1) con las nuevas variables artificiales añadidas. La función objetivo de este problema auxiliar será la minimización (y por tanto, la eliminación) de esas variables artificiales nuevas.
En seguida, se resolverá el problema auxiliar con el método simplex ya visto, y una vez encontremos la solución óptima, si esta existe, la base óptima encontrada servirá como base factible inicial para la siguiente fase.
La Fase 2 del problema consiste en recuperar el problema original y resolverlo usando como base inicial, la base óptima encontrada en la fase 1 (eliminando los índices añadidos por la adición de las variables artificiales).
Con la base inicial se empieza nuevamente el simplex, y se continúan las iteraciones del simplex de forma normal hasta llegar al óptimo original del problema.
Observe que si el problema de la fase 1 fuese ilimitado o infactible, entonces el problema original no puede ser resuelto y por tanto se concluye el proceso de resolución.
2.1 Esquema general del método
Fase 1:
Resolver y guardar la base óptima de: \[\min \sum_{i \in F} x_i^a\] Sujeto a \[Ax + x^a = b\] \[x, x^a \ge 0\]
Siendo \(x_i^a\) las variables artificiales adicionadas, \(F\) el conjunto de índices de las columnas adicionadas y \(x^a\) el vector de variables adicionadas al modelo.
Fase 2:
Con la base óptima resolverhasta la optimalidad: \[\min c^Tx\] Sujeto a \[Ax = b\] \[x \ge 0\]
2.2 Ejemplo de aplicación
Considere el siguiente problema:
Se desea fabricar un alimento a partir de dos materias primas con existencias limitadas. El silo de maíz aporta, por kg usado en la mezcla, 45% de carbohidratos y 15% de proteína. La melaza provee 20% de carbohidratos y 65% de proteína. El alimento debe tener un máximo de 40% de carbohidratos y un mínimo de 26% de proteína. Cada kg de silo cuesta $3 y cada kg de melaza cuesta $5. Al mezclarse y cocerse, el silo de maíz pierde el 270 g por kg usado, la melaza se reduce en 50 gramos por kg. Se debe producir mínimo 50kg del alimento al menor costo posible. Si se excede de los 50kg, el excedente se pierde y cuesta $6 el kg. ¿Cuánto de cada tipo de materia prima debe usarse?
Este problema se puede modelar de la forma mostrada, a continuación. Sea:
\(x_1:=\) Cantidad de kg de silo de maíz usado en la mezcla.
\(x_2:=\) Cantidad de kg de melaza usada en la mezcla.
\(e:=\) Cantidad de mezcla hecha de más por encima de los 50kg.
Minimizar el costo total de la mezcla: \[\min c_{Total} = 3x_1 + 5x_2 + 6e\]
Sujeto a:
Requisito de carbohidratos: \[0.45x_1 + 0.20x_2 \le 0.4*50\] Requisito de proteína: \[0.15x_1 + 0.65x_2 \ge 0.26*50\] La cantidad fabricada debe ser mínimo 50kg. Observe que la variable de exceso que se debe insertar en esta restricción es equivalente al sobrante \(e\) (vea el modelo estandarizado). \[0.77x_1 + 0.95x_2 \ge 50\] Dominio: \[x_1, x_2 \ge 0\]
Luego de estandarizar este problema queda de la siguiente forma: \[\min c_{Total} = 3x_1 + 5x_2 + 0x_3 +0x_4 + 6x_5\]
Sujeto a: \[0.45x_1 + 0.20x_2 + x_3 = 20 \] \[0.15x_1 + 0.65x_2 - x_4 = 13 \] \[0.77x_1 + 0.95x_2 - x_5 = 50\] \[x_1, x_2, x_3, x_4, x_5 \ge 0\] Observe que la variable \(x_5\) es el exceso de mezcla producido, para continuar con la notación y facilitar el entendimiento del lector, se sustituye a \(e\) por esta variable en la FO.
El problema anterior resulta en las siguientes matrices:
\[c = \begin{bmatrix}3 \\ 5 \\ 0 \\ 0 \\6\end{bmatrix}, x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4\\x_5\end{bmatrix}, A = \begin{bmatrix}0.45 & 0.20 & 1 & 0 & 0\\ 0.15 & 0.65 &0 & -1 & 0\\ 0.77 & 0.95 & 0 & 0 &-1\end{bmatrix}, b = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix}\]
Observe que la base trivial compuesta por las variables adicionadas al estandarizar \(\mathcal{B} = \{3,4,5\}, \mathcal{N} = \{1,2\}\), genera las matrices: \[B = \begin{bmatrix}1 & 0 & 0\\0 & -1 & 0\\0 & 0 &-1\end{bmatrix}, N = \begin{bmatrix}0.45 & 0.20\\ 0.15 & 0.65 \\ 0.77 & 0.95\end{bmatrix}\]
Con \(B^1 = B = \begin{bmatrix}1 & 0 & 0\\0 & -1 & 0\\0 & 0 &-1\end{bmatrix}\)
Y se produce la siguiente solución básica:
\[x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}1 & 0 & 0\\0 & -1 & 0\\0 & 0 &-1\end{bmatrix}\begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}20 \\ \textcolor{red}{-13} \\ \textcolor{red}{-50}\end{bmatrix} = \begin{bmatrix}x_3 \\ x_4 \\ x_5\end{bmatrix}\]
Tal y como se puede ver por los valores de \(x_4\) y \(x_5\), esta solución básica inicial (base \(\mathcal{B} = \{3,4,5\}, \mathcal{N} = \{1,2\}\)) no es una solución factible. Por lo tanto no podríamos iniciar el método simplex para encontrar la solución del problema de la mezcla.
Por esta razón , usemos el método simplex de 2 fases para encontrar, en la primera fase, una base factible inicial, y en la segunda fase, encontraremos el óptimo del problema.
2.2.1 Fase 1
Para formar la matriz identidad que necesitamos, necesitamos agregar las columnas \(\begin{bmatrix}0\\1\\0\end{bmatrix}\) y \(\begin{bmatrix}0\\0\\1\end{bmatrix}\).
Por este motivo asociaremos estas columnas a las nuevas variables artificiales \(x_6^a\) y \(x_7^a\), respectivamente.
La función objetivo para el problema auxiliar será: \[\min \textcolor{blue}{z = x_6^a + x_7^a} \equiv 0x_1 + 0x_2 + 0x_3 + 0x_4 + +0x_5 + x_6^a + x_7^a\] Y las restricciones modificadas (ya estandarizadas) quedan de la siguiente forma: \[0.45x_1 + 0.20x_2 + x_3 + 0x_4 + 0x_5 + 0x_6^a + 0x_7^a = 20 \] \[0.15x_1 + 0.65x_2 + 0x_3 - x_4 + 0x_5 + \textcolor{blue}{x_6^a} + 0x_7^a = 13 \] \[0.77x_1 + 0.95x_2 + 0x_3 + 0x_4 - x_5 + 0x_6^a + \textcolor{blue}{x_7^a} = 50\] \[x_1, x_2, x_3, x_4, x_5, \textcolor{blue}{x_6^a, x_7^a}\ge 0\] Entonces obtenemos las matrices del problema auxiliar: \[c = \textcolor{blue}{\begin{bmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1\end{bmatrix}}, x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \textcolor{blue}{x_6^a} \\ \textcolor{blue}{x_7^a}\end{bmatrix}, A = \begin{bmatrix}0.45 & 0.20 & 1 & 0 & 0 & \textcolor{blue}{0} & \textcolor{blue}{0}\\ 0.15 & 0.65 &0 & -1 & 0 & \textcolor{blue}{1} & \textcolor{blue}{0}\\ 0.77 & 0.95 & 0 & 0 &-1 & \textcolor{blue}{0} & \textcolor{blue}{1}\end{bmatrix}, b = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix}\] Observe que la base (base \(\mathcal{B} = \{3,6,7\}, \mathcal{N} = \{1,2,4,5\}\) es una base trivial de este problema auxiliar. Esta base es factible, como se demuestra en seguida:
\[B = \begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 &1\end{bmatrix}, N = \begin{bmatrix}0.45 & 0.20 & 0 & 0\\ 0.15 & 0.65 & -1 & 0 \\ 0.77 & 0.95 & 0 & -1\end{bmatrix}\] Observe que \(B^{-1} = B = I\), y por tanto la solución básica queda:
\[x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 &1\end{bmatrix}\begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}x_3 \\ x_6^a \\ x_7^a\end{bmatrix}\]
Con esto podemos comenzar el simplex (puede auxiliarse en octave para los cálculos):
Desarrollo del simplex de la Fase 1
Iteración 1
\(\mathcal{B} = \{3,6,7\}, \mathcal{N} = \{1,2,4,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}20 & 13 & 50\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & 1 & 1\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}-0.92 & \textcolor{blue}{-1.6} & 1 & 1\end{bmatrix}\)
4. y 5. Debe entrar \(x_2\) a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_2)^T = \begin{bmatrix}0.20 & 0.65 & 0.95 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}100, \textcolor{red}{20}, 52.63\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_6^a\). Actualizamos la base y continuamos.
Iteración 2
\(\mathcal{B} = \{3,\textcolor{blue}{2},7\}, \mathcal{N} = \{1,\textcolor{red}{6},4,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}16 & 20 & 31\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & -1.4615 & 1\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}-0.5508 & 2.4615 & \textcolor{blue}{-1.4615} & 1\end{bmatrix}\)
4. y 5. Debe entrar x_4 a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_4)^T = \begin{bmatrix}0.30 & -1.54 & 1.46 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}52, \infty, \textcolor{red}{21.21}\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_7^a\). Actualizamos la base y continuamos.
Iteración 3
\(\mathcal{B} = \{3,2,\textcolor{blue}{4}\}, \mathcal{N} = \{1,6,\textcolor{red}{7},5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}9.47 & 52.63 & 21.21\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & 0 & 0\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}0 & 1 & 1 & 0\end{bmatrix}\)
4. y 5. No hay costos reducidos negativos, Se debe parar ya que hemos llegado al óptimo.
Así, luego de resolver la Fase 1, la base óptima es \(\mathcal{B} = \{3,2,4\}, \mathcal{N} = \{1,6,7,5\}\). Podemos continuar a la Fase 2.
2.2.2 Fase 2
Para esta fase, recuperamos la formulación original y ya podemos prescindir de las variables artificiales que fueron adicionadas en el problema auxiliar. Es decir, la base inicial es la base óptima anterior pero sin las columnas 6 y 7:
\[\mathcal{B} = \{3,2,4\}, \mathcal{N} = \{1,\cancel{6,7,}5\} \textcolor{teal}{\rightarrow} \mathcal{B} = \{3,2,4\}, \mathcal{N} = \{1,5\}\] Esta base es factible en el problema original, recordemos los datos, y evaluémosla:
\[c = \begin{bmatrix}3 \\ 5 \\ 0 \\ 0 \\6\end{bmatrix}, x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4\\x_5\end{bmatrix}, A = \begin{bmatrix}0.45 & 0.20 & 1 & 0 & 0\\ 0.15 & 0.65 &0 & -1 & 0\\ 0.77 & 0.95 & 0 & 0 &-1\end{bmatrix}, b = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix}\] A partir de la partición \(\mathcal{B}, \mathcal{N}\), tenemos:
\[B = \begin{bmatrix}1 & 0.20 & 0 \\0 & 0.65 & -1\\0 & 0.95 &0\end{bmatrix}, N = \begin{bmatrix}0.45 & 0 \\ 0.15 & 0\\ 0.77 & -1\end{bmatrix}\]
La solución básica queda:
\[x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}1 & 0.20 & 0 \\0 & 0.65 & -1\\0 & 0.95 &0\end{bmatrix}^{-1}\begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}1 & 0 & -0.21 \\0 & 0 & 1.05\\0 & -1 & 0.68\end{bmatrix}\begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}9.47 \\ 52.63 \\ 21.21\end{bmatrix} = \begin{bmatrix}x_3 \\ x_2 \\ x_4\end{bmatrix}\]
Como todos los \(x_{\mathcal{B}}\ge0\) podemos comenzar el método simplex.
Desarrollo del simplex de la Fase 2
Iteración 1
\(\mathcal{B} = \{3,2,4\}, \mathcal{N} = \{1,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}9.47 & 52.63 & 21.21\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & 0 & 5.26\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}\textcolor{blue}{-1.05} & 11.26\end{bmatrix}\)
4. y 5. Debe entrar \(x_1\) a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_1)^T = \begin{bmatrix}0.28 & 0.81 & 0.38 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}\textcolor{red}{32.91}, 64.94, 56.28\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_3\). Actualizamos la base y continuamos.
Iteración 2
\(\mathcal{B} = \{\textcolor{blue}{1},2,4\}, \mathcal{N} = \{\textcolor{red}{3},5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}32.91 & 25.96 & 8.81\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}-3.66 & 0 & 6.03\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}3.66 & 12.03\end{bmatrix}\)
4. y 5. No hay costos reducidos negativos, Se debe parar ya que hemos llegado al óptimo.
De esta forma llegamos al óptimo del problema, siendo la solución óptima:
\[x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix}32.91 \\ 25.96 \\ 0 \\ 8.81 \\ 0 \end{bmatrix}\] Es decir, que se debe usar aproximadamente 32.91 kg de silo de maíz y 25.96 kg de melaza para producir el alimento. La variable \(x_4 = 8.81\) indica que habrá un sobrante de proteína equivalente a 8.81 kg de la mezcla.
3 Método de la gran M
Este método, al igual que el anterior consiste en adicionar variables artificiales al problema. Sin embargo, a diferencia del anterior método, este consiste en mantener el problema original con las variables nuevas en su estructura sin recurrir a un problema auxiliar. Esto con el único objetivo de hacer viable el inicio del simplex.
Las variables artificiales añadidas se irán eliminando de forma paulatina hasta que todas ellas sean no básicas. En ese momento se puede prescindir de ellas (aunque esto es opcional) y continuar resolviendo el problema hasta la optimalidad.
La forma en que durante la optimización, se opte por ir eliminándolas de forma automática y paulatina, es penalizarlas fuertemente en la función objetivo. Esta penalización es simbólica y se simboliza como un valor M. De ahí el nombre del método.
Este valor debe ser lo suficientemente grande como para priorizar la eliminación de estas variables artificiales por encima del objetivo original del problema sin modificar. Sin embargo, se debe tener cuidado si se elige un valor exagerado, puesto que los cálculos del vector multiplicador y costos reducidos se podrían complicar un poco más por los números mayores.
3.1 Esquema general del método
Resolver hasta la optimalidad, el problema modificado: \[\min c^Tx + M\sum_{i \in F} x_i^a\] Sujeto a \[Ax + x^a = b\] \[x, x^a \ge 0\]
Siendo \(x_i^a\) las variables artificiales adicionadas, \(F\) el conjunto de índices de las columnas adicionadas y \(x^a\) el vector de variables adicionadas al modelo.
3.2 Ejemplo de aplicación
Considere el problema anterior de la Sección 2.2. El modelo sin modificaciones se muestra a continuación. Se presenta junto con un recorderis de la notación final utilizada.
Sea:
\(x_1:=\) Cantidad de kg de silo de maíz usado en la mezcla.
\(x_2:=\) Cantidad de kg de melaza usada en la mezcla.
\(x_5:=\) Cantidad de mezcla hecha de más por encima de los 50kg.
Minimizar el costo total de la mezcla: \[\min c_{Total} = 3x_1 + 5x_2 + 6x_5\]
Sujeto a:
\[0.45x_1 + 0.20x_2 \le 50\] \[0.15x_1 + 0.65x_2 \ge 13\] \[0.77x_1 + 0.95x_2 - x_5 = 50\] \[x_1, x_2, x_5 \ge 0\] De la misma forma como se actuó en el método de las dos fases, se necesita agregar 2 variables artificiales \(x_6^a\) y \(x_7^a\), asociadas a las columnas \(\begin{bmatrix}0\\1\\0\end{bmatrix}\) y \(\begin{bmatrix}0\\0\\1\end{bmatrix}\) de la matriz identidad respectivamente.
Estas variables serán adicionadas a la función objetivo actual, con una penalización simbólica \(M\). Para nuestro caso, el \(M\) seleccionado es de 100, que será una penalización más que suficiente para garantizar la priorización de la eliminación de las variables artificiales añadidas de manera paulatina.
El problema modificado (y estandarizado) queda de la siguiente forma: \[\min \textcolor{blue}{\bar{z}} = 3x_1 + 5x_2 + 0x_3 + 0x_4 + 6x_5 + \textcolor{blue}{100x_6^a + 100x_7^a}\]
Sujeto a:
\[0.45x_1 + 0.20x_2 +x_3 + 0x_4 + 0x_5 + 0x_6^a + 0x_7^a = 20\] \[0.15x_1 + 0.65x_2 +0x_3 -x_4 + 0x_5 + \textcolor{blue}{x_6^a} + 0x_7^a= 13\] \[0.77x_1 + 0.95x_2 +0x_3 + 0x_4 - x_5 + 0x_6^a + \textcolor{blue}{x_7^a}= 50\] \[x_1, x_2, x_3, x_4, x_5, \textcolor{blue}{x_6^a, x_7^a} \ge 0\] Entonces obtenemos las matrices del problema auxiliar: \[c = \textcolor{blue}{\begin{bmatrix}3 \\ 5 \\ 0 \\ 0 \\ 6 \\ 100 \\ 100\end{bmatrix}}, x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \textcolor{blue}{x_6^a} \\ \textcolor{blue}{x_7^a}\end{bmatrix}, A = \begin{bmatrix}0.45 & 0.20 & 1 & 0 & 0 & \textcolor{blue}{0} & \textcolor{blue}{0}\\ 0.15 & 0.65 &0 & -1 & 0 & \textcolor{blue}{1} & \textcolor{blue}{0}\\ 0.77 & 0.95 & 0 & 0 &-1 & \textcolor{blue}{0} & \textcolor{blue}{1}\end{bmatrix}, b = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix}\] Observe que la base (base \(\mathcal{B} = \{3,6,7\}, \mathcal{N} = \{1,2,4,5\}\) es una base trivial de este problema auxiliar. Esta base es factible, como se demuestra en seguida:
\[B = \begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 &1\end{bmatrix}, N = \begin{bmatrix}0.45 & 0.20 & 0 & 0\\ 0.15 & 0.65 & -1 & 0 \\ 0.77 & 0.95 & 0 & -1\end{bmatrix}\] Observe que \(B^{-1} = B = I\), y por tanto la solución básica queda:
\[x_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 &1\end{bmatrix}\begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}20 \\ 13 \\ 50\end{bmatrix} = \begin{bmatrix}x_3 \\ x_6^a \\ x_7^a\end{bmatrix}\]
Que es \(\ge0\) y por tanto es factible. Con esto podemos comenzar el simplex (Nuevamente, puede auxiliarse en octave para los cálculos):
Desarrollo del simplex Gran M
Iteración 1
\(\mathcal{B} = \{3,6,7\}, \mathcal{N} = \{1,2,4,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}20 & 13 & 50\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & 100 & 100\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}-0.89 & \textcolor{blue}{-155} & 100 & 106\end{bmatrix}\)
4. y 5. Debe entrar \(x_2\) a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_2)^T = \begin{bmatrix}0.20 & 0.65 & 0.95 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}100, \textcolor{red}{20}, 52.63\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_6^a\). Actualizamos la base y continuamos.
Iteración 2
\(\mathcal{B} = \{3,\textcolor{blue}{2},7\}, \mathcal{N} = \{1,\textcolor{red}{6},4,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}16 & 20 & 31\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & -138.46 & 100\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}-53.23 & 238.46 & \textcolor{blue}{-138.46} & 106\end{bmatrix}\)
4. y 5. Debe entrar \(x_4\) a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_4)^T = \begin{bmatrix}0.31 & -1.54 & 1.46 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}52, \infty, \textcolor{red}{21.21}\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_7^a\). Actualizamos la base y continuamos.
¡! OBS: A partir de aquí podríamos continuar sin las variables artificiales \(x_6^a\) y \(x_7^a\). Sin embargo, para efectos de este ejemplo continuaremos con ellas.
Iteración 3
\(\mathcal{B} = \{3,2,\textcolor{blue}{4}\}, \mathcal{N} = \{1,6,\textcolor{red}{7},5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}9.47 & 52.63 & 21.21\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}0 & 0 & 5.26\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}\textcolor{blue}{-1.05} & 100 & 94.74 & 11.26\end{bmatrix}\)
4. y 5. Debe entrar \(x_1\) a la base, y dado que hay negativos, debemos continuar.
6. Preparación para la MRT: \(y^T = (B^{-1}a_1)^T = \begin{bmatrix}0.28 & 0.81 & 0.38 \end{bmatrix}\)
7. Test de la razón mínima: \(MRT = \begin{Bmatrix}\textcolor{red}{32.91}, 64.94, 56.28\end{Bmatrix}\)
8. y 9. Hay denominadores \(>0\), se debe continuar. La variable saliente de la base es \(x_3\). Actualizamos la base y continuamos.
Iteración 4
\(\mathcal{B} = \{\textcolor{blue}{1},2,4\}, \mathcal{N} = \{\textcolor{red}{3},6,7,5\}\)
1. Solución básica: \(x^T_{\mathcal{B}} = B^{-1}b = \begin{bmatrix}32.91 & 25.96 & 8.81\end{bmatrix}\)
2. Vector multiplicador: \(p^T = c_{\mathcal{B}}^TB^{-1} = \begin{bmatrix}-3.66 & 0 & 6.03\end{bmatrix}\)
3. Costos reducidos: \(s^T = c^T_{\mathcal{N}} - p^Tb = \begin{bmatrix}3.66 & 100 & 93.97 & 12.03\end{bmatrix}\)
4. y 5. No hay costos reducidos negativos, Se debe parar ya que hemos llegado al óptimo.
De esta manera hemos llegado a la solución óptima del problema modificado. Observe que la solución óptima, dado que no eliminamos las variables artificiales es:
\[x = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\x_6^a \\x_7^a \end{bmatrix} = \begin{bmatrix}32.91 \\ 25.96 \\ 0 \\ 8.81 \\ 0 \\ 0 \\0\end{bmatrix}\] Como es de esperarse, llegamos a la misma solución ótima del problema anterior. Es decir, que se debe usar aproximadamente 32.91 kg de silo de maíz y 25.96 kg de melaza para producir el alimento. La variable \(x_4 = 8.81\) indica que habrá un sobrante de proteína equivalente a 8.81 kg de la mezcla.
Como se deseaba, las variables artificiales tienen valor 0 en la solución óptima.
4 Ejercicios y lecturas complementarias.
4.1 Ejercicios
Resuelva por medio del Simplex 2 fases los siguientes ejercicios:
- Considere el siguiente conjunto de restricciones:
\[-2x_1+3x_2=3 \tag{1}\]
\[4x_1+5x_2\ge10 \tag{2}\]
\[x_1+2x_2\le5 \tag{3}\]
\[6x_1+7x_2\le3 \tag{4}\]
\[4x_1+8x_2\ge5 \tag{5}\]
\[x_1,x_2\ge0\] Re suelva los siguientes problemas con el método especificado al final de cada item:
(a) Maximizar \(z = 5x1 + 6x2\) sujeto a (1), (3) y (4). Use simplex gran M.
(b) Maximizar \(z = 2x1 + 7x2\) sujeto a (1), (2) (4) y (5). Use simplex 2 fases.
(c) Minimizar \(z = 3x1 + 6x2\) sujeto a (3), (4) y (5). Use simplex gran M.
(d) Minimizar \(z = 4x1 + 6x2\) sujeto a (1), (2) y (5). Use simplex gran M.
(e) Minimizar \(z = 3x1 + 2x2\) sujeto a (1) y (5). Use simplex 2 fases.
- Minimizar \(z = 6x1 + 2x2\) sujeto a (1), (3) y (5). Use simplex 2 fases.
- Modele y resuelva por el método de su preferencia el siguiente problema de optimización.
Una universidad ha sido premiada con un nuevo centro de cómputo de alto poder destinado a surtir labores de investigación. El centro de cómputo está compuesto de 3 salas que funcionan en paralelo. Los usuarios apartan su horario, alistan sus experimentos en la sala solicitada y se deja trabajar a los equipos. La universidad ha dispuesto que debe haber un auxiliar por sala durante el horario de atención.
Los auxiliares son estudiantes de posgrado a los que se les reconoce un salario por hora que depende de su nivel de experiencia y habilidades informáticas. Este precio fue fijado por la Universidad en el estudio de las hojas de vida de los aspirantes a auxiliar. En la sala 2, hay equipos especiales que solo pueden manipular auxiliares que sean estudiantes de doctorado. En las otras dos salas puede haber tanto estudiantes de maestría como de doctorado.
La tabla a continuación explica las disponibilidades de los diferentes estudiantes de maestría y doctorado así como el costo por hora para la universidad. Se trabaja una jornada continua de 7 horas de lunes a viernes. A cada auxiliar se le garantiza un mínimo de 8 horas semanales asignadas.
| Est | Lunes | Martes | Miércoles | Jueves | Viernes | Estudia | Salario/h |
|---|---|---|---|---|---|---|---|
| Donald | 4 | 4 | 7 | 0 | 6 | Doctorado | 10 |
| Ana | 7 | 4 | 0 | 8 | 4 | Doctorado | 12 |
| Jonas | 5 | 6 | 6 | 4 | 0 | Maestría | 11 |
| Pepito | 6 | 0 | 4 | 5 | 6 | Maestría | 8 |
| Taylor | 0 | 6 | 8 | 4 | 6 | Maestría | 10 |
Ayude a la universidad a tomar la mejor decisión respecto a la asignación de horas a cada estudiante garantizando.
- Modele y resuelva por el método de su preferencia el siguiente problema de optimización.
Hodor vive en el mundo de los espíritus y se prepara para embarcarse en un viaje que le permitirá desarrollar sus poderes al máximo. En el camino le esperan monstruos y retos que le exigirán tener buena salud, puntos de ataque, velocidad y defensa. Hodor puede embarcar ciertas sustancias que le permitirán potenciar algunos de estos aspectos o curarse en caso de heridas. Sin embargo la mochila de Hodor tiene ciertos límites de peso, volumen, valor monetario y karma.
Aquí tienes la tabla de los objetos que Hodor puede llevar en su viaje:
| Objeto | Atributos mejorados | Disponibilidad |
|---|---|---|
| Poción de Salud | Salud (+50),Defensa (-2) | 10 und |
| Elixir de Ataque | Ataque (+20), Velocidad (+5) | 5 und |
| Tónico de Velocidad | Velocidad (+20), Ataque (+10) | 3 und |
| Escudo de Defensa | Defensa (+20), Salud (+10) | 6 und |
| Hierbas Curativas | Salud (+10) | $\infty$ |
| Cristal de Poder | Todos los atributos (+10) | 8 und |
| Crema de la Sapiencia | Salud (+10), Defensa (+25) | $\infty$ |
| Polvo de Agilidad | Defensa (+25), Velocidad (+10) | 3 und |
| Brevaje de Invisibilidad | Velocidad (+45), Salud (-3) | 7 und |
| Pudin de Regeneración | Salud (+40), Ataque (-5) | 2 und |
Eres el mejor amigo de Hodor y deberías ayudarlo a determinar cuáles deben ser las cantidades que necesita de cada item para poder iniciar su viaje con la mejor preparación posible.
Para ayudarle en su viaje, has preguntado a Hodor qué le gustaría priorizar, y este te ha respondido que le gustaría tener equilibrio en los 4 atributos, le ha dado una nota de 8/10 a cada aspecto menos a la salud a la que le ha dado una nota de 10/10. Siendo este, claramente el aspecto más importante.
Sé un buen amigo y ayuda a Hodor a decidir cuánta cantidad de cada objeto llevar en su mochila para maximizar sus atributos, sin exceder los límites de su mochila.
¡Buena suerte en tu viaje, Hodor!
- Otros ejercicios Hacer cuantos más puedan.
Libro. Investigación de Operaciones de Hamdy Taha 9na Edición. Capítulo 3, Sección 3.5 (Página 99 en adelante.)
Ejercicios 2.4 A
Ejercicios 2.4 B
Ejercicios 2.4 C
Ejercicios 2.4 D
Ejercicios 2.4 E
Ejercicios 2.4 F
4.2 Lecturas complementarias
(Leer para el lunes próximo se evaluará el contenido de esta guía y el de las lecturas complementarias.)
Se recomienda leer los casos especiales del simplex y cómo tratarlos:
Soluciones degeneradas o degeneración (Adicional a la lectura, investigar sobre ciclamientos o looping en el simplex y regla de Bland).
Óptimos alternativos: ¿Cuáles son las condiciones necesarias y suficientes para que se den?.
Problemas ilimitados (Solución no acotada).
Solución no factible.
La lectura recomendada se encuentra en el libro Investigación de Operaciones de Hamdy Taha 9na Edición. Capítulo 3, Sección 3.5 (Página 99 en adelante.)