Blog sobre la Gestión e Investigación de Operaciones con tutoriales y ejercicios resueltos.
Categoría: Programación Lineal
Programación Lineal. Ejercicios resueltos de Programación Lineal, Método Simplex, Método Simplex de 2 Fases, Método Simplex Dual, Dualidad en Programación Lineal, Análisis de Sensibilidad o Postoptimal. Tutoriales en Excel de Solver, What’sBest! y OpenSolver.
En este oportunidad queremos compartir con nuestros usuarios una noticia reciente que de seguro será de interés para quienes en alguna oportunidad han utilizado la versión web o instalado en sus computadores el popular software Geogebra. El software Geogebra permite entre otras cosas hacer representaciones gráficas de funciones (lineales y no lineales), lo cual hemos abordado ampliamente en la resolución de modelos de Programación Lineal mediante el Método Gráfico, construir Histogramas para análisis estadístico, realizar pruebas de hipótesis, entre otros análisis.
En este contexto hemos recibido un correo de notificación de parte del Equipo de GeoGebra informando que se encuentra disponible para su descarga gratuita GeoGebra Calculadora Gráfica el cual es compatible con smatphones y tablets con sistema operativo Android y que prontamente estará disponible para los usuarios de iPhone.
A la fecha de este artículo GeoGebra Calculadora Gráfica cuenta con el orden de 10.000 descargas y una valoración (puntuación) de 4,8. Adicionalmente no requiere mayores privilegios para su instalación. Todo esto sin duda constituye un excelente respaldo respecto a la calidad de este programa el cual hemos tenido el privilegio de utilizar durante varios años con excelentes resultados.
Una de las ventajas de la versión para Android de GeoGebra es la posibilidad de exportar los archivos a Dropbox, OneDrive, Google Drive, enviar por correo electrónico, entre otros. Esto permite respaldar fácilmente los archivos que utilicemos en nuestro smartphone o tablet para ser utilizado posteriormente (la siguiente imagen muestra la utilización del programa para la representación gráfica de un modelo de Programación Lineal).
Te recomendamos decididamente descargar GeoGebra Calculadora Gráfica y desde ya te agradecemos compartir tu experiencia en su utilización, dejándonos un comentario al final de este artículo.
El siguiente artículo aborda la formulación y resolución computacional haciendo uso de AMPL y el solver CPLEX de un modelo de Programación Lineal que trata sobre el manejo óptimo de aves en un criadero con el objetivo de maximizar el valor comercial de su explotación transcurrido un horizonte de planificación de 4 semanas. Se busca dar un especial énfasis al modelamiento matemático y la interpretación intuitiva de la solución óptima y valor óptimo alcanzado de modo de visualizar de forma más sencilla la naturaleza del problema.
Suponga que a un ave de criadero le toma dos semanas poner 12 huevos para la venta o, alternativamente, tener 4 pollos (al empollar 4 huevos). Formule y resuelva un modelo de optimización que provea el mejor programa de manejo de las aves si al cabo de la cuarta semana todas las aves y pollos acumulados son vendidos a USD 0.60 cada unidad y los huevos a USD 0.10 cada unidad. Suponga un inventario inicial de 100 aves y 100 huevos.
Variables de Decisión:
xe0: cantidad de aves empolladoras de huevos inicial
xe2: cantidad de aves empolladoras de huevos al término de la semana 2
xe4: cantidad de aves empolladoras de huevos al término de la semana 4
xp0: cantidad de aves ponedoras de huevos inicial
xp2: cantidad de aves ponedoras de huevos al término de la semana 2
xp4: cantidad de aves ponedoras de huevos al término de la semana 4
ye0: cantidad de huevos inicial para ser empollados
ye2: cantidad de huevos empollados al término de la semana 2
yi0: cantidad de huevos inicial para inventario
yi2: cantidad de huevos en inventario al término de la semana 2
Función Objetivo:
Se desea maximizar el valor comercial del manejo de las aves, donde se obtendrá USD 0.60 por cada una de las 100 aves iniciales y los pollos que se obtienen al empollar (un pollo por cada huevo empollado). Adicionalmente se percibe un ingreso de USD 0.10 por los huevos obtenidos por las aves ponedoras y aquellos que quedan en inventario.
Max 0.6 (100 + ye0 + ye2) + 0.1 (12 xp2 + yi2)
Restricciones:
La cantidad de aves destinadas a empollar (o poner huevos, denominadas también ponedoras) deben ser menor o igual a 100 tanto al inicio del horizonte de planificación como al final de la segunda y cuarta semana. Por supuesto adicionalmente se debe satisfacer las condiciones de no negatividad.
La cantidad de aves destinadas para poner huevos o empollar durante al inicio del horizonte de planificación, al final de la semana 2 y al final de la semana 4, debe ser igual a 100 aves (que son las aves iniciales). Por supuesto los pollitos que puedan haber nacido durante el período de evaluación no están en condiciones de empollar o poner huevos.
xp0 + xe0 = 100 xp2 + xe2 = 100 xp4 + xe4 = 100
Los 100 huevos iniciales pueden ser destinados sólo para 2 propósitos: almacenar en inventario o ser utilizados para ser empollados.
ye0 + yi0 = 100
Por cada ave destinada a empollar (al inicio del horizonte de planificación o al término de la semana 4) se necesitarán exactamente 4 huevos.
ye0 = 4 xe0 ye2 = 4 xe2
La cantidad de huevos inicial para inventario, más los que se obtengan de las aves destinadas inicialmente como ponedoras (12 huevos por cada una de ellas), menos aquellos huevos empollados al término de la semana 2, deberá ser igual a la cantidad de huevos en inventario al término de la semana 2.
yi0 + 12xp0 – ye2 = yi2
Una vez definido el modelo de optimización lineal para el problema de manejo de las aves de criadero, se propone una formulación matemática del mismo en el lenguaje de programación matemática AMPL que da origen al siguiente código (se ha utilizado para estos efectos el software Notepad como editor de texto y el archivo se debe guardar con la extensión .mod).
A continuación podemos seleccionar algunos de los solvers compatibles con AMPL disponibles en la plataforma NEOS Solvers, en particular uno ad hoc a un modelo de Programación Lineal como resulta ser este caso. En este contexto hemos seleccionado CPLEX, cargando el archivo del modelo (que hemos llamado modeloaves.mod) de forma similar a la que usualmente se utiliza para adjuntar un archivo a un correo electrónico. Finalmente ingresamos un email donde deseamos recibir los resultados.
Al cabo de unos segundos recibiremos un correo electrónico con la solución óptima y valor óptimo del problema. Un extracto del mismo se muestra a continuación:
El valor óptimo corresponde a USD 410 que representa el valor comercial de las aves y huevos al final del período de planificación. En cuanto a la solución óptima esta corresponde a:
xe0: cantidad de aves empolladoras de huevos inicial = 25
xe2: cantidad de aves empolladoras de huevos al término de la semana 2 = 100
xe4: cantidad de aves empolladoras de huevos al término de la semana 4 = 0
xp0: cantidad de aves ponedoras de huevos inicial = 75
xp2: cantidad de aves ponedoras de huevos al término de la semana 2 = 0
xp4: cantidad de aves ponedoras de huevos al término de la semana 4 = 100
ye0: cantidad de huevos inicial para ser empollados = 100
ye2: cantidad de huevos empollados al término de la semana 2 = 400
yi0: cantidad de huevos inicial para inventario = 0
yi2: cantidad de huevos en inventario al término de la semana 2 = 500
Esquemáticamente y con el objetivo de facilitar la interpretación de la solución alcanzada, a continuación se presente una representación de la situación abordada.
Inicio: Se dispone de 100 aves y 100 huevos. De las 100 Aves, 25 de ellas son destinadas a empollar (utilizando cada una ella 4 huevos, por tanto se utiliza la totalidad del inventario inicial de huevos) y 75 aves serán ponedoras.
Semana 2: Transcurridas las 2 primeras semanas se habrán obtenido 900 huevos (12*75) por parte de las Aves ponedoras y adicionalmente tendremos 100 pollitos (que nacieron luego de que 25 Aves empollaran 4 huevos cada una por un lapso de 2 semanas). Luego se destinan las 100 Aves (por supuesto omitiendo los pollitos) a empollar (requiriendo un total de 400 huevos) y quedando de esta forma 500 huevos en inventario.
Semana 4: Se dispondrá de 500 pollitos (400 de ellos recién nacidos y los 100 restantes aquellos que nacieron en la Semana 2) y 100 Aves (que son aquellas iniciales y que en suma a los pollitos da un total de 600 aves, cada una con un valor comercial de USD 0.60, es decir, un total de USD 360). Como no se destinaron aves como ponedoras al término de la semana 2, sólo se podrán vender de forma directa aquellos huevos que quedaron en inventario al final de la semana 2 (500 huevos) a un valor unitario de USD 0.10, es decir, USD 50 en total. Se concluye que la valorización total de las aves (incluyendo los pollitos) más los huevos alcanza por tanto USD 410 (360+50).
¿Quieres tener el archivo .mod con la formulación del modelo de optimización en AMPL resuelto en este artículo? (El archivo .mod estará al interior de un archivo comprimido .zip).
La Programación Estocástica reúne aquellos modelos de optimización en donde uno o más parámetros del problema son modelados a través de variables aleatorias. Una manera de enfrentar esta aleatoriedad consiste en reemplazar los parámetros aleatorios por su valor esperado, lo cual lleva a resolver un problema determinístico de programación matemática, los cuales son de especial interés en cursos introductorios de Investigación de Operaciones y donde la variabilidad inherente a los parámetros se aborda a través del Análisis de Sensibilidad o Postoptimal.
No obstante, la solución obtenida de esta manera puede no ser representativa de la realidad, al no considerar la dispersión de los valores que toman los parámetros en torno al valor esperado, lo cual entre otras cosas puede invalidar su implementación al resultar finalmente escenarios muy diferentes del promedio.
De este modo y en general, una forma de incorporar esta situación de incertidumbre es considerar un número finito de posibles realizaciones o escenarios para los parámetros aleatorios.
El impacto de la incorporación explicita de la incertidumbre en modelos de programación matemática afecta la factibilidad y optimalidad del sistema en estudio. En efecto, la solución que entrega la resolución de un modelo determinista que considera reemplazar los parámetros aleatorios por su valor esperado, puede ser infactible para un escenario en particular.
En este contexto la connotación que tiene el término factibilidad en programación estocástica es más extensa que en el caso determinista, debido a que no se puede garantizar que la solución del modelo estocástico sea factible para todas las posibles realizaciones de la variable aleatoria. Frecuentemente se incluye términos de penalización en la función objetivos que castigan estas posibles infactibilidades ponderada por un cierto costo según se constata por ejemplo en las investigaciones de Sen, S. and Higle, J.L. (1999). Introductory Tutorial on Stochastic Linear Programming Models. Interfaces 29, No.2, 33-61.
En cuanto al impacto que tiene la incertidumbre sobre la optimalidad del modelo formulado se puede observar que a mayor variabilidad de los parámetros aleatorios, el valor que alcanza la función objetivo varía en torno a una media en mayor magnitud. En este sentido la literatura reúne una serie de indicadores que cuantifica este impacto (Birge, J and Louveaux, F (1997). Introduction to Stochastic Programming, Springer – Verlag, New York, USA) de la incorporación explícita de la incertidumbre en la formulación del modelo y permite al tomador de decisiones dilucidar el real impacto de ésta.
Clasificación de los modelos de Programación Estocástica
Los modelos de optimización estocástica se dividen en dos grandes categorías, estos son: Modelos con Restricciones Probabilísticas y Modelos con Recurso. Una referencia general al respecto lo constituye un tutorial desarrollado por Sen y Higle (1999) sobre programación estocástica para el caso lineal y libros como el de Birge y Louveaux (1997).
Modelos con Recursos en 2 Etapas
En un modelo con recurso en dos etapas se pueden distinguir aquellas variables de decisión que son implementadas antes de la realización particular del parámetro aleatorio denominadas de primera etapa o here and now, que se debe tomar antes de conocer la realización de la variable aleatoria, es decir que se escoge tomando en cuenta la aleatoriedad de los parámetros, pero cuyo valor es independiente de la realización particular que finalmente vaya a tomar dicha variable aleatoria. Las variables de primera etapa pueden ser vistas como decisiones proactivas y están asociadas frecuentemente a decisiones estratégicas como la planificación y expansión de sistemas de producción.
En tanto las variables que son determinadas una vez conocida la realización particular de la variable aleatoria son llamadas de segunda etapa o de recurso, es decir, su valor es tomado en respuesta al medio. En este sentido las variables de segunda etapa son de naturaleza reactiva y generalmente están asociadas a decisiones operativas.
El Análisis de Sensibilidad en Programación Lineal permite analizar el impacto en los resultados del modelo (solución óptima y valor óptimo) en aquellos casos donde uno o varios parámetros sufren modificaciones en relación a sus valores originales, sin la necesidad de resolver nuevamente el problema (sin reoptimizar). En dicho contexto en el siguiente artículo presentamos un ejemplo de dicho análisis para un problema de optimización lineal que considera 2 variables de decisión.
Ejemplo Análisis de Sensibilidad (Método Gráfico)
Un productor tabaquero posee 85 hectáreas (ha) de terreno para plantar dos variedades de tabacos Virginia y Procesado. La variedad Virginia tiene un ingreso de 9.600 USD/ha y necesita 3 horas/ha de uso de maquinaria y 80 horas/ha de mano de obra. Además, el Estado limita su explotación a 30 ha como máximo. La variedad Procesado tiene un ingreso de 7.500 USD/ha y utiliza 2 horas/ha de uso de maquinaria y 60 horas/ha de mano de obra. La cooperativa local le ha asignado un máximo de 190 horas de uso de maquinaria y solo se dispone de 5.420 horas de mano de obra a 12 USD/hora.
Formule y resuelva gráficamente un modelo de Programación Lineal que permita determinar cuánto se debe plantar de cada variedad de tabaco de manera de maximizar la utilidad total.
En primer lugar definimos el modelo de optimización para este problema. Esto consiste en identificar las variables de decisión, función objetivo y restricciones. Detalle de este procedimiento aplicado a problemas de 2 variables puede ser consultado en el artículo Programación Lineal (Método Gráfico).
Variables de Decisión:
X1 = Número de Ha a plantar de la variedad Virginia
X2 = Número de Ha a plantar de la variedad Procesado
Una representación gráfica del problema para el productor de tabaco se puede realizar a través del software Geogebra:
Sabemos según el Teorema Fundamental de la Programación Lineal que en caso de existir solución óptima ésta se encontrará en un vértice o en un tramo en la frontera del dominio de soluciones factibles (en el ejemplo área achurada en color verde). Adicionalmente podemos apreciar que no es tan evidente que el vértice C reporte una mayor utilidad en la función objetivo que el vértice D, por lo cual, inspeccionaremos ambos puntos.
En el caso del vértice C éste se encuentra en la intersección de las restricciones 2 y 4. La coordenada respectiva se obtiene al resolver el siguiente sistema de ecuaciones:
X1 + X2 = 85
80X1 + 60X2 = 5.420
De donde X1=16 y X2=69, lo cual reporta un valor en la función objetivo de V(P)=8.640*(16)+6.780(69)=606.060.
Análogamente en el caso del vértice D las restricciones activas son 3 y 4:
3X1 + 2X2 = 190
80X1 + 60X2 = 5.420
Luego de resolver el sistema lineal anterior se obtiene X1=28 y X2=53, lo cual reporta un valor en la función objetivo de V(P)=8.640*(28)+6.780(53)=601.260.
En consecuencia la solución óptima del problema es X1=16 y X2=69, con valor óptimo V(P)=8.640*(16)+6.780(69)=606.060.
Una vez resuelto el escenario original a continuación se presentan algunos análisis adicionales que representan por separado modificaciones en los coeficientes de la función objetivo y restricciones del problema.
Intervalo Variación Coeficiente Función Objetivo
Determine cuánto podría variar la utilidad por hectárea del tabaco Virginia, manteniendo constante la utilidad por hectárea del tabaco procesado, de forma que la actual solución óptima no cambie. Para este caso determine el intervalo de variación de la utilidad total.
Sea en términos generales la función objetivo Z=C1X1+C2X2, donde inicialmente en el ejemplo C1=8.640 y C2=6.780. La pendiente de las curvas de nivel de la función objetivo es -C1/C2. De este modo se conserva la actual solución óptima (vértice C) en la medida que:
En este caso la utilidad por hectárea del tabaco Virginia puede variar entre 6.780 USD y 9.040 USD, de tal forma que el actual nivel de producción (solución óptima) sería el mismo. Lo anterior permite concluir que el intervalo de variación para la utilidad total será .
Precio Sombra (Método Gráfico)
Si se pudiese contratar más mano de obra disponible en el mercado, ¿Cuántas horas de mano de obra en total estaría dispuesto a utilizar?¿Cuál sería el aporte adicional de esas horas extras que utilizaría en términos monetarios? Responda lo anterior utilizando el concepto de Precio Sombra.
Para calcular gráficamente el precio sombra necesitamos identificar la máxima y mínima variación para el lado derecho de la restricción de mano de obra que permita garantizar que se conserva la actual base óptima (restricciones activas originales). En este sentido en el caso de aumentar el lado derecho de dicha restricción la solución óptima podrá ser encontrada manteniendo las restricciones activas (e incorporando una adicional) hasta la coordenada (20,65) que es donde se interceptan la segunda y tercera restricción. En el caso de disminuir la disponibilidad de horas en mano de obra se mantiene la base óptima hasta el vértice B cuya coordenada es (0,85). De esta forma se obtiene el precio sombra de la siguiente forma:
En consecuencia el lado derecho de la restricción 4 (disponibilidad de mano de obra) puede variar entre [5.100, 5.500] y se conservan las actuales restricciones activas. Adicionalmente dado que en el óptimo actual se utilizan 5.420 horas de mano de obra se deben contratar 80 horas adicionales (de modo de alcanzar las 5.500 horas). Luego, la variación de 80 horas adicionales implicaría un aumento en la utilidad total de 80*USD93=7.440USD.
El Método Simplex desarrollado por George B. Dantzig en 1947 es sin duda el algoritmo más popular a la hora de enfrentar la resolución de un modelo de Programación Lineal y ocupa un lugar destacado en los cursos introductorios a la Investigación de Operaciones.
En esta oportunidad hemos buscado resumir 10 conceptos principales sobre el uso y la aplicación del Método Simplex con el objetivo de que nuestros usuarios puedan tener una primera aproximación al método observando algunos aspectos característicos. Esta recopilación se basa sobre nuestra experiencia docente dictando cursos de Investigación Operativa y las preguntas que frecuentemente recibimos por parte de los alumnos de pregrado.
10 Cosas que Necesitas Saber sobre el Método Simplex
Te invitamos a revisar y compartir esta infografía en las redes sociales. Adicionalmente si consideras si un elemento importante quedo fuera de la lista anterior utiliza la herramienta de comentarios al pie de la página para hacernos saber tu opinión. De esta forma podremos ir actualizando periódicamente el artículo con las características principales del Método Simplex.
.
