Cálculo del Precio Sombra con el Método Simplex

Una de las ventajas de la utilización del Método Simplex es que además de permitir encontrar la solución óptima y valor óptimo de un modelo de Programación Lineal (cuando existe) es que proporciona información valiosa para el Análisis de Sensibilidad o Postoptimal. En este artículo en particular nos enfocaremos en cómo utilizar los resultados de la tabla final del Método Simplex para el análisis del Precio Sombra de una restricción. Para ello consideremos el siguiente problema el cual se puede representar a través de un modelo con dos variables de decisión.

Ejemplo del Cálculo del Precio Sombra con el Método Simplex

Una empresa administradora de fondos dispone de 21 millones de pesos para invertir en bolsa. El departamento de estudios de inversiones recomienda dos tipos de instrumentos financieros, que llamaremos tipo A y tipo B. Los del tipo A tienen una rentabilidad del 10% anual y los del tipo B del 8% anual. Por razones de políticas de gestión del directorio se decide invertir un máximo de 13 millones de pesos en las del tipo A y como mínimo 6 millones de pesos en las del tipo B. Además la inversión en los instrumentos del tipo A debe ser menor o igual que el doble de la inversión destinada a los instrumentos tipo B.

Sea x e y los millones invertidos en los instrumentos A y B, respectivamente, el modelo de Programación Lineal que permite maximizar la rentabilidad de la administradora sujeta a las condiciones impuestas es el siguiente:

ejemplo modelo precio sombra

En particular el problema anterior puede ser resuelto a través del Método Simplex de Dos Fases. Para ello se agregan variables de holgura para la primera, segunda y cuarta restricción. En el caso de la tercera restricción se agrega una variable de exceso y una variable auxiliar. Otra alternativa sería imponer un cambio de variables, definiendo por ejemplo [latex]z=y-6\geq 0[/latex] de modo que [latex]z+6=y\geq 0[/latex] que evita la aplicación del Método Simplex de Dos Fases y requiere reemplazar en el modelo anterior la variable [latex]y[/latex] por [latex]z+6[/latex].

Adicionalmente existen una serie de herramientas computacionales que permite resolver online un problema de Programación Lineal a través del Método Simplex. Una de ellas se encuentra en: Método Simplex Online Programación Lineal, donde a continuación se muestra una imagen con la implementación del ejemplo propuesto y los resultados alcanzados:

solución método simplex online

La solución óptima es [latex]x=13[/latex] e [latex]y=8[/latex] con valor óptimo de [latex]V(P)=1.94[/latex] (millones). Notar que la variable [latex]s_{1}[/latex] corresponde a la variable de holgura de la primera restricción que corresponde al limite presupuestario. Adicionalmente su costo reducido es 0.08 que corresponde al Precio Sombra de la respectiva restricción.

Para determinar el intervalo en el cual puede variar el lado derecho de la restricción 1 (actualmente [latex]b_{1}=21[/latex]) de modo de conservar la actual base óptima, podemos hacer uso del siguiente resultado:

formula intervalo variacion coeficiente funcion objetivo

Donde [latex]y_{ij}[/latex] corresponde a los valores en las respectivas filas asociada a la variable de holgura de la primera restricción, en este caso [latex]s_{1}[/latex]. De esta forma se obtiene:

[latex]Max\begin{Bmatrix}\frac{-3}{2};\frac{-2}{1};\frac{-8}{1}\end{Bmatrix}\leq D\leq\infty[/latex]

[latex]\frac{-3}{2}\leq D\leq\infty[/latex]

El aumento permisible para [latex]b_{1}[/latex] es infinito (notar que no existen [latex]y_{ij}<0[/latex] en la columna de [latex]s_{1}[/latex]). Análogamente la disminución permisible es -3/2. De esta forma se concluye que si [latex]b_{1}\epsilon [19.5,\infty [[/latex] se conserva la base óptima (restricciones activas en la solución óptima original).

Una forma de facilitar la comprensión del concepto anterior, en especial aquel que se refiere al aumento permisible, se puede lograr a través de una representación gráfica del problema. Se puede evidenciar que en la medida que el lado derecho de la restricción 1 aumente (incluso de forma indefinida( la solución óptima se seguirá encontrando con la restricción 1 y restricción 2 activa (al igual como sucede en el vértice E que es la coordenada de la solución óptima original).

precio sombra grafico

Dado el análisis anterior estamos en condiciones de responder una pregunta como la siguiente que requiere la aplicación del concepto del Precio Sombra:

Si la administradora de fondos pudiese disponer de 500 mil pesos adicionales para invertir, ¿cómo variaría su ingreso?. Justifique su respuesta mediante los argumentos propios del análisis de sensibilidad.

El Análisis de Sensibilidad que aplica es el que se hace para el lado derecho de la primera restricción, cuyo precio sombra es de 0.08 con un aumento permisible para su respectivo para su lado derecho de infinito. Por tanto un incremento en 500 mil pesos (0.5 millones) en el presupuesto determina que el nuevo valor óptimo sería [latex]V(P)=1.94+0.5*0.08=1.98[/latex] (millones).

Ejemplo del Método Simplex

El Método Simplex es sin lugar a dudas el algoritmo por excelencia cuando se trata de resolver un modelo de Programación Lineal. Dado lo anterior suele tener un lugar privilegiado en los programas de estudios de cursos de pregrado relacionados a la Investigación de Operaciones. En el siguiente artículo presentamos una problemática la cual se aborda mediante el modelamiento de un problema lineal y su posterior resolución a través del Método Simplex. Adicionalmente y como forma de complementar el análisis se ofrece una interpretación gráfica de los resultados que da origen el algoritmo de modo de facilitar la comprensión conceptual del mismo.

Ejemplo del Método Simplex

A un grupo de artesanos se le presenta la oportunidad exportar cinturones de piel de salmón al mercado europeo. Clasifican los cinturones en dos tipos A y B: A por alta calidad y B por baja calidad. De acuerdo a sus estimaciones tendrían una utilidad de 4 euros por cinturón tipo A y 3 euros por el tipo B. La confección de un cinturón tipo A les requiere el doble de tiempo que uno tipo B. Si confeccionaran sólo cinturones tipo B podrían hacer 1.000 diarios. En todo caso, el abastecimiento de piel es suficiente para confeccionar un total combinado de 800 cinturones diarios. Los cinturones usan un diferente tipo de hebilla según su calidad. Se pueden abastecer de 800 hebillas elegantes al día para los cinturones tipo A y 700 hebillas corrientes al día para los cinturones tipo B. Se desea formular y resolver un modelo de Programación Lineal que permita a los artesanos decidir cuántos cinturones de cada tipo fabricar de modo de maximizar sus ganancias.

1.-Variables de Decisión

  • x1: Número de cinturones tipo A a fabricar por semana.
  • x2: Número de cinturones tipo B a fabricar por semana.

2.- Función Objetivo

Cada cinturón tipo A reporta una utilidad de 4 euros y cada cinturón tipo B reporta una utilidad de 3 euros. Se desea maximizar la utilidad total dada por: Max 4x1+3x2

3.-Restricciones

  • No se puede fabricar más cinturones tipo A que la cantidad de hebillas disponibles: x1≤800

  • No se puede fabricar más cinturones tipo B que la cantidad de hebillas disponibles: x2≤ 700

  • Como máximo se puede confeccionar diariamente 800 cinturones del tipo A y del tipo B en conjunto: x1+x2≤800

  • La capacidad de producción  permite fabricar 1.000 cinturones tipo B a la semana si se fabricara sólo cinturones de este tipo. Los cinturones tipo A ocupan el doble de recursos que uno B, esto es se pueden fabricar 500 cinturones a la semana si sólo se fabrican cinturones tipo A: 2x1+x2≤1.000

  • No negatividad de las variables de decisión: x1, x≥ 0

En términos compactos el modelo de Programación Lineal queda definido por:

modelo lineal

Previo a la aplicación del Método Simplex será necesario llevar el modelo a su forma estándar. Para ello llevamos la función objetivo a minimización y agregamos las variables de holgura no negativas x3, x4, x5,  y x6, para las restricciones 1, 2, 3 y 4, respectivamente.

forma estándar programación lineal

Con ello construimos la tabla inicial del Método Simplex donde las variables de holgura previamente identificadas definen una solución básica factible inicial (no óptima):

tabla inicial método simplex

Por el criterio del costo reducido más negativo la variable que ingresa a la base es x1. Luego calculamos en dicha columna el mínimo cuociente que esta dado por: [latex]Min\begin{Bmatrix}\frac{800}{1},\frac{800}{1},\frac{1.000}{2}\end{Bmatrix}=500[/latex].

En consecuencia el pivote se encuentra en la fila 4 y por tanto la variable x6 deja la base. (Notar que para el cálculo del mínimo cuociente o criterio de factibilidad sólo se consideran denominadores que sean estrictamente mayores a cero).

primera iteración método simplex

Ahora la variable no básica que ingresa a la base es x2. Calculamos nuevamente el mínimo cuociente sobre dicha columna obteniendo: [latex]Min\begin{Bmatrix}\frac{700}{1},\frac{300}{1/2},\frac{500}{1/2}\end{Bmatrix}=600[/latex].

Por tanto x5 abandona la base. Con ello realizamos una nueva iteración del Método Simplex:

tabla óptima método simplex

La solución óptima es x1=200 y x2=600, donde el valor de las holguras x3 y x4 corresponde a 600 y 100, respectivamente. Notar adicionalmente que las variables x5 y x6 son no básicas en el óptimo, por tanto su valor es cero, lo que indica que las restricciones 3 y 4 son activas. El valor óptimo del problema es V(P)=2.600.

Para complementar el análisis anterior, se puede apreciar la convergencia del Método Simplex a través de una representación gráfica, realizada en este caso con el software Geogebra. La tabla inicial del Método Simplex corresponde al vértice A (solución básica factible no óptima) del gráfico a continuación, luego al ingresar en primera instancia la variable x1 al cabo de una iteración se alcanza el vértice E (solución básica factible no óptima). Finalmente en la segunda iteración se pasa del vértice E al vértice D, el cual corresponde a la solución básica factible óptima, dado que el costo reducido de las variables no básicas es mayor o igual a cero.

geogebra-simplex

Importante: Una forma de corroborar que el criterio de seleccionar la variable no básica que ingresa a la base como aquella con el costo reducido más negativo se basa en la rapidez de convergencia del Método Simplex y no afecta en su efectividad, consiste en ingresar inicialmente a la base la variable x2. En este caso se puede constatar que se puede alcanzar la solución óptima del problema con un número mayor de iteraciones en comparación al procedimiento detallado en este artículo.

Método Simplex de Dos Fases

El Método Simplex de Dos Fases permite abordar la resolución de aquellos modelos de Programación Lineal que luego de ser llevados a su forma estándar no permite obtener una solución básica factible inicial en las variables del modelo. Para enfrentar esta situación existen distintas estrategias algorítmicas entre las que destacan el Método Simplex de Dos Fases y el Método de la M Grande, las cuales suelen ser discutidas en cursos de Investigación Operativa (Investigación de Operaciones). En el siguiente artículo nos concentraremos en el análisis de la primera alternativa a través de un enfoque teórico – práctico.

Ejemplo Método Simplex de Dos Fases

Considere el siguiente modelo de Programación Lineal usando el Método Simplex de Dos Fases.

modelo-simplex-dos-fases

Fase I (Método Simplex de Dos Fases)

En este caso resulta conveniente multiplicar por -1 la primera restricción de modo que el lado derecho sea positivo, lo cual tiene como efecto adicional que cambia el sentido de la desigualdad. En consecuencia el problema que define la Fase I del Método Simplex de Dos Fases es:

fase-uno-simplex

Donde X3 es variable de exceso y X4 y X5 son variables artificiales de la restricción 1 y 2 respectivamente. Luego estaos en condiciones de confeccionar la tabla inicial de la Fase I donde las variables auxiliares X4 y X5 tienen costo reducido igual a uno (dado sus respectivos coeficientes en la función objetivo de dicha fase).

tabla-inicial-fase-uno

A continuación se llevan a cero los costos reducidos de X4 y X5. Para ello se realizan operaciones filas, por ejemplo, primero multiplicando por -1 la fila 1 y sumándola a la fila 3, para luego multiplicar por -1 la fila 2 y sumarla a la fila 3.

primera-iteracion-fase-uno

Notar ahora que las variables básicas son X4 y X5 y las variables no básicas son X1, X2 y X3. Entre las variables no básicas la que tiene costo reducido negativo es X2, por tanto dicha variable entra a la Base y mediante el criterio de factibilidad o mínimo cuociente se determina aquella variable básica que deja la base. Esto se obtiene de Min{2/1; 10/1}=2. Por tanto X4 sale de la base y se realiza una iteración.

tabla-fase-uno-simplex

Luego de concluir la iteración se dispone ahora de dos variables no básicas con costo reducido negativo: X1 y X3. Teniendo en consideración un criterio de rapidez de convergencia se privilegia la entrada a la base de X1 al tener ésta el costo reducido más negativo. La variable básica que deja la base se obtiene de Min{8/2}=4, determinando que X5 sale de la base. Para actualizar la tabla sumamos la fila 2 a la fila 3 (de modo que el costo reducido de X1 se transforme en cero) y luego multiplicamos por 1/2 la fila 2 y la sumamos a la fila 1 (para que de esta forma X1 sea básica asociada a la fila 2, tomando la estructura de la variable básica saliente X5).

tabla-final-fase-uno-simple

Se verifica que se concluye la Fase I del Método Simplex de Dos Fases. Esta situación se detecta cuando se dispone de una solución básica que satisface las condiciones de no negatividad, donde las variables no básicas tienen costos reducidos mayores o iguales a cero y el valor de la función objetivo es igual a cero.

Fase II (Método Simplex de Dos Fases)

A continuación se da inicio a la Fase II del Método Simplex de Dos Fases. En esta etapa se elimina las columnas asociadas a las variables auxiliares utilizadas en la Fase I del método (en el ejemplo las variables X4 y X5) y se actualiza el vector de costos reducidos considerando la función objetivo del problema original en formato de minimización, esto es MIN -X1–3X2.

tabla-inicial-fase-dos-simp

Cabe recordar que las variables básicas finalizadas la Fase I son X2 y X1 y luego de la actualización de la fila de costos reducidos (fila 3) será necesario llevar sus respectivos costos reducidos a cero, para lo cual se suma la fila 2 a la fila 3 y luego se multiplica por 3 la fila 1 y se suma a la fila 3, obteniéndose lo siguiente:

primera-iteracion-fase-dos-

Del procedimiento anterior resulta que la variable no básica X3 tiene costo reducido y por tanto ingresa a la base. La variable básica que deja la base se obtiene de Min{4/1/2}=8 y por tanto X1 abandona la base. Con ello se realiza una iteración del método obteniendo la siguiente tabla:

tabla-final-fase-dos-simple

Observar que la variable no básica X1 tiene costo reducido igual a 2 (que satisface las condiciones de no negatividad), además de enfrentarnos a una solución básica factible para X2 y X3.

Por tanto se concluye la Fase II del Método Simplex de Dos Fases con solución óptima X1=0, X2=10 y X3=8 y valor óptimo V(P)=30.

Análisis de Sensibilidad o Postoptimal (Método Simplex)

forma estándar programación linealEl Análisis de Sensibilidad o Análisis Postoptimal en el Método Simplex permite flexibilizar un supuesto básico de la Programación Lineal, el cual es asumir que el valor de los parámetros o constantes de un modelo son conocidos, es decir, que no existe incertidumbre (modelo determinista). En este contexto luego de resolver un problema de Programación Lineal con el Método Simplex resulta de interés analizar el impacto en los resultados (solución óptima, valor óptimo, variables básicas óptimas, etc) ante variaciones en la estimación preliminar de dichos parámetros.

A continuación presentamos a través de un ejemplo algunos casos típicos que se abordan sobre el Análisis Postoptimal (Análisis de Sensibilidad) en cursos introductorios de Investigación de Operaciones. Para ello consideremos el siguiente problema de Programación Lineal:

modelo-programacion-lineal

El cual luego de llevar a la forma estándar y resolver por el Método Simplex permite alcanzar la siguiente tabla final:

tableau-final-metodo-simple

Donde [latex]X_{4}[/latex] y [latex]X_{5}[/latex] son las variables de holgura para las restricciones 1 y 2 respectivamente. Se solicita realizar un Análisis Postoptimal (o Análisis de Sensibilidad) que de respuesta a los siguientes escenarios de forma independiente.

Análisis de Sensibilidad o Postoptimal con la Tabla Final del Método Simplex

Interpretación de Resultados Tabla Final del Método Simplex

¿Cuál es la solución óptima y valor óptimo de P)? Indique cuales son las variables básicas y cuales las variables no básicas. ¿La solución óptima es única? ¿Cuáles son las restricciones que se encuentran activas en el óptimo?.

La solución óptima en términos de las variables originales del modelo es: [latex]X_{1}=0,X_{2}=0,X_{3}=9[/latex]. En cuanto a las variables de holgura, [latex]X_{4}=2[/latex] y [latex]X_{5}=0[/latex] (variable básica y no básica, respectivamente). El valor óptimo es [latex]V(P)=126[/latex]. Las variables básicas son [latex]X_{4}[/latex] y [latex]X_{3}[/latex] y las variables no básicas son [latex]X_{1},X_{2}[/latex] y [latex]X_{5}[/latex]. Las restricciones activas en el óptimo, es decir, aquellas que se cumplen en igualdad, es la restricción 2 (dado que su variable de holgura representada por [latex]X_{5}[/latex] es no básica en el óptimo, por tanto adopta un valor igual a cero), además de las restricciones de no negatividad para las variables [latex]X_{1}[/latex] y [latex]X_{2}[/latex].

Intervalo de Variación Coeficiente de una Variable No Básica en la Función Objetivo en el Método Simplex

Encuentre un intervalo de variación para [latex]C_{2}[/latex] (coeficiente asociado a la variable [latex]X_{2}[/latex] en la función objetivo) que mantenga la actual solución óptima.

Este es un caso sencillo de abordar en el Análisis de Sensibilidad. Por simple inspección se observa que el costo reducido de la variable no básica [latex]X_{2}[/latex] es 3/5. Notar adicionalmente que el coeficiente de la variable [latex]X_{2}[/latex] en la función objetivo de maximización es igual a 5. Luego se concluye que para que la variable [latex]X_{2}[/latex] pueda ingresar a la base (y de esta forma cambiar la solución óptima y la base óptima) el parametro correspondiente en la función objetivo ([latex]C_{2}[/latex]) debería ser al menos 5+3/5=28/5. Es decir, se conserva la solución óptima si y solo sí [latex]C_{2}[/latex] varía en el intervalo [latex]]-\infty ,28/5][/latex] en la función objetivo de maximización. Notar que en particular si [latex]C_{2}=28/5[/latex] se da lugar al escenario de infinitas soluciones óptimas (variable no básica con costo reducido igual a cero en la actual solución básica factible óptima).

Intervalo de Variación Coeficiente de una Variable Básica en la Función Objetivo en el Método Simplex

Si el coeficiente para [latex]X_{3}[/latex] en la función objetivo cambia de 14 a 12. ¿Cambia la actual solución óptima?. ¿Cambia la actual base óptima?.

Sea [latex]r_{j}[/latex] el costo reducido correspondiente a una variable no básica en la actual solución óptima e [latex]y_{ij}[/latex] denotan las entradas en la tabla final del Método Simplex correspondiente a la variable básica [latex]x_{i}[/latex] (cuyo coeficiente cambia) y la respectiva variable no básica [latex]x_{j}[/latex]. Dado lo anterior se conserva la solución óptima si la variación propuesta para el parámetro que pondera a una variable básica en la función objetivo se encuentra en el intervalo que provee la fórmula a continuación:

intervalo-funcion-objetivointervalo-variacion-c3

En el ejemplo propuesto esto da origen un aumento permisible de más infinito y una reducción permisible de 3/2 (la interpretación se ha realizado sobre el parámetro [latex]C_{3}[/latex] en la función objetivo de maximización). No obstante la resolución del problema mediante el Método Simplex y el correspondiente análisis de sensibilidad se ha realizado sobre el modelo en su forma estándar, es decir, considerando una función objetivo de minimización. Se concluye a través del Análisis de Sensibilidad que [latex]C_{3}[/latex] puede variar entre 12,5 e infinito y se conserva la actual solución óptima (y base óptima).

Agregar Nueva Restricción en el Método Simplex

Considere que se incorpora la siguiente restricción al problema: [latex]2X_{1}+3X_{2}+5X_{3}\leq 50[/latex]. ¿Cambia la solución óptima y valor óptimo?. En caso de ser afirmativo encuentre la nueva solución óptima y valor óptimo.

En primer lugar corresponde evaluar si la actual solución óptima resulta ser factible al considerar la nueva restricción, es decir,: [latex]2(0)+3(0)+5(9)\leq 50[/latex], lo que claramente se cumple. En consecuencia se conserva tanto la solución óptima como el valor óptimo.

Agregar Nueva Variable de Decisión en el Método Simplex

Asuma ahora que se incorpora una nueva variable de decisión [latex]X_{6}[/latex] con coeficiente en la función objetivo (de maximización) igual a 10 y con parámetros 3 y 5 en la primera y segunda restricción, respectivamente. ¿Cambia la actual solución óptima?.

costo-reducido-nueva-variab

Este análisis requiere evaluar el costo reducido de la nueva variable propuesta y verificar si éste es mayor o igual a cero. En dicho caso se conserva tanto la solución óptima como el valor óptimo (un caso particular sería obtener un costo reducido igual a cero donde se genera el caso de infinitas soluciones óptimas). Por el contrario si el costo reducido para la nueva variable de decisión resulta ser negativo, entonces cambia la solución óptima y esta nueva variable deberá ingresar a la base y obliga a continuar con las iteraciones del Método Simplex. En el ejemplo el costo reducido de la variable [latex]X_{6}[/latex] es -3, por tanto ingresa a la base, agregándose una columna adicional a la tabla con coeficientes [latex]B^{-1}A_{j}[/latex] en las restricciones tal como se muestra a continuación:

agregar-variable-metodo-sim

Indicación: La variable [latex]X_{6}[/latex] ingresa a la base y sale la variable [latex]X_{4}[/latex] considerando el criterio del mínimo cuociente. Se propone al lector continuar las iteraciones a contar de este punto.

Cambio Vector del Lado Derecho en el Método Simplex

Considere que cambia el vector del lado derecho de las restricciones a [latex]b=(10,100)^{T}[/latex]. Indique si las actuales variables básicas óptimas lo son también del nuevo problema.

Se actualiza el vector de las variables básicas considerando la modificación propuesta según se detalla a continuación:

cambio-lado-derecho

La variable básica asociada a la fila 1 ([latex]X_{4}[/latex]) adopta un valor negativo (-10) por tanto cambia la actual base óptima. Para encontrar la nueva solución óptima y valor óptimo se debe continuar las iteraciones utilizando el Método Simplex Dual previa actualización del valor de la función objetivo en la nueva solución básica (de momento infactible).

Cambio Coeficientes Función Objetivo en el Método Simplex

Si cambia la función objetivo de maximización a [latex]-4X_{1}+6X_{2}+13X_{3}[/latex]. ¿Cambia la actual base óptima?. ¿Cuál es la solución óptima y valor óptimo de este nuevo escenario?.
vector-costos-reducidos-no-

En este caso se debe recalcular el vector de los costos reducidos de las variables no básicas del problema que denotamos por [latex]r_{D}[/latex] según se muestra en la imagen. Notar que el costo reducido de la variable [latex]X_{2}[/latex] es negativo (-4/5) lo cual implica que cambia la actual solución óptima (y se deberá actualizar el valor de la función objetivo dado los nuevos coeficientes de la función objetivo). Para encontrar la nueva solución óptima se deberá ingresar la variable [latex]X_{2}[/latex] a la base y seguir con las iteraciones del Método Simplex.

Recomendación: La mayor parte de los resultados presentados en este artículo sobre el Análisis de Sensibilidad pueden ser verificados a través de herramientas de resolución online para modelos de Programación Lineal haciendo uso del Método Simplex. En este sentido se recomienda acceder a la aplicación disponible en Programación Lineal – Método Simplex.