¿Te gustaría disponer de un Apunte con ejercicios resueltos explicados de modo sencillo que te permita aprobar tu Examen de Programación Lineal?
El Libro de Apuntes de Programación Lineal que necesitas esta aquí y ha sido diseñado especialmente para aquellos alumnos que se encuentran cursando una cátedra inicial de Investigación de Operaciones (o Investigación Operativa) que buscan resolver de forma sencilla aquellas preguntas frecuentes relacionadas a los modelos de optimización lineales.
El material contenido en este Apunte es original, es decir, no ha sido tomado de libros o apuntes de terceros. Para ello hemos desarrollado una labor creativa en el diseño de los ejercicios que estamos seguros sabrás apreciar.
El Libro de Apuntes contiene los siguientes capítulos:
Desde Febrero de 2012 el Libro de Apuntes de Programación Lineal ha sido descargado por más de 57.000 100.000 usuarios de distintos países los cuales se han mostrados muy satisfechos por el material recibido. Esto ha permitido consolidar nuestro sitio web como una de las principales referencias sobre la Gestión de Operaciones e Investigación de Operaciones para estudiantes.
El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.
La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.
Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.
El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:
Ruta 1-2-5-7-8: 4+8+17+9=38[km]
Ruta 1-3-4-7-8: 3+12+20+9=44[km]
Ruta 1-3-4-6-8: 3+12+2+22=39[km]
Ruta 1-3-4-8: 3+12+15=30[km]
Ruta 1-3-6-8: 3+4+22=29[km]
La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].
A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:
Variables de Decisión:
Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:
Restricciones:
La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.
Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:
Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).
El tutorial a continuación disponible en nuestro canal de Youtube muestra en detalle la implementación y resolución computacional de este problema:
La Planificación Agregada y el Plan Maestro de la Producción (PMP o MPS según sus siglas en inglés Master Production Schedule) son metodologías ampliamente utilizadas hoy en día en empresas de manufactura para planificar las necesidades de producción de una serie de productos, de modo de responder a un pronóstico de demanda a través de los recursos productivos que se disponen.
En este contexto, la evidencia empírica muestra que existen diversas estrategias que se pueden utilizar para enfrentar la demanda, cada una de las cuales se puede valorar en términos de costos pero también a través de una serie de criterios cualitativos que por su naturaleza son difíciles de estimar en una unidad monetaria.
A continuación se presenta un gráfico con el Pronóstico de Demanda de un producto para el cual propondremos un modelo de optimización que permita cumplir con dichos requerimientos, minimizando los costos asociados a la utilización de los recursos productivos:
Se puede apreciar que la demanda presenta una estacionalidadmarcada donde al inicio y final del año los valores son menores a la demanda de un mes promedio (7.817 unidades).
En contraste con lo anterior en los meses de Junio, Julio y Agosto se presenta un peak de demanda, superando en magnitud claramente lo que correspondería a la demanda de un mes promedio. Adicionalmente consideremos los siguientes antecedentes de operación:
Costo de Contratar un Trabajador: US$1.000
Costo de Despedir un Trabajador: US$1.800
Costo de Almacenamiento Unitario Mensual: US$10
Inventario Inicial: 500 unidades
Costo Remuneración (Sueldo) de un Trabajador al Mes: US$600
Número de Trabajadores al Inicio de la Planificación: 100
Unidades de Producto producidas por un Trabajador al Mes: 50
La pregunta inmediata es: ¿Cómo responder a la demanda pronosticada durante el período de planificación al menor costo posible?. Algunas posibles respuestas son:
Fuerza Laboral Exacta: Esto es mediante contratación y despido de trabajadores para responder de forma exacta a las necesidades de cada mes. Con esta alternativa se busca evitar la acumulación de inventario.
Acumulación y Liquidación de Inventario: Producir en mayor volumen en los meses de menor demanda de modo de acumular inventario para enfrentar los requerimientos adicionales de los meses de mayor demanda. Si se considera adecuado se puede utilizar esta alternativa buscando no afectar el tamaño de la fuerza laboral.
Por cierto también se puede utilizar una estrategia mixta o híbrida que mezcle por ejemplo características de las 2 opciones presentadas anteriormente. Este enfoque generalmente es el que permite alcanzar menores costos.
Adicionalmente cabe destacar que en un Plan Maestro de la Producción (PMP) se podrían considerar otras alternativas o variables de ajuste no consideradas en este ejemplo como la utilización de trabajadores en tiempo extraordinario, la subcontratación parcial de la producción, la eventual postergación de demanda, entre otras opciones.
Luego, en relación a los antecedentes de operación previamente detallados, un modelo de Programación Entera para el Plan Maestro de la Producción es:
1. Variables de Decisión:
2. Función Objetivo:
3. Restricciones:
Satisfacer la Demanda (Balance de Inventario): Donde Dt corresponde a la demanda pronosticada para el mes t (parámetros).
Balance Mano de Obra: La cantidad de trabajadores en operación en cada período corresponde a los trabajadores disponibles al final del mes anterior, más los contratados y menos los despedidos en el mes en curso.
Capacidad de Producción: La producción de cada mes se ve limitada por la disponibilidad de trabajadores y el rendimiento mensual (en unidades de producto) que cada uno de éstos tiene.
No Negatividad e Integralidad: Todas las variables de decisión deben adoptar valores no negativos y adicionalmente ser enteras.
El modelo anterior se puede implementar con Solver y What’sBest! obteniendo los siguientes resultados:
Implementación Computacional en Solver: Se alcanza una solución factible con valor en la función objetivo de US$1.468.700.
El detalle de la resolución la puedes revisar en el siguiente tutorial de nuestro canal de Youtube:
Implementación Computacional con What’sBest!: Se alcanza una solución factible con valor en la función objetivo de US$1.468.400, la cual es ligeramente inferior en costos a la solución obtenida con Solver.
La carga del modelo en What’sBest! y la obtención de los resultados anteriores se puede revisar en el siguiente tutorial de nuestro canal de Youtube:
Una línea aérea está considerando incorporar vuelos desde y hacia su aeropuerto base y por lo tanto necesita contratar más agentes de servicio al cliente. Sin embargo, no está claro cuántos más debe contratar. La administración reconoce la necesidad de controlar el costo y al mismo tiempo brindar un nivel de atención satisfactorio. Se ha realizado un análisis del número mínimo de agentes de servicio que deben encontrarse de guardia en diferentes momentos del día para proporcionar un nivel satisfactorio de servicio.
Se ha acordado que cada agente trabaje un turno de 8 horas en los turnos mostrados en la tabla anterior. Por ejemplo, el turno 3 va desde las 12:00 hasta las 20:00. Los sueldos de cada turno son diferentes debido a que unos son más deseables que otros. Por ejemplo, a cada agente que cumpla el turno 3 debemos pagarle diariamente $175.
Se busca formular y resolver un modelo Programación Entera que permita a la línea aérea encontrar el plan de asignación de agentes al menor costo posible y que cumpla los requerimientos impuestos.
1. Variables de Decisión: Establecer un plan de asignación de agentes a los distintos turnos de trabajo.
Xi: Número de Agentes asignados al Turno i con i=1,2,3,4,5 con Xi>=0 {Enteros}
2. Función Objetivo: Minimizar el costo total de la asignación de agentes.
Minimizar 170X1+160X2+175X3+180X4+195X5
3. Restricciones: Se busca garantizar que en cada período del día se cuenta con la cantidad mínima de agentes requeridos.
X1 >= 48
X1 + X2 >= 79
X1 + X2 >= 65
X1 + X2 + X3 >= 87
X2 + X3 >= 64
X3 + X4 >= 73
X3 + X4 >= 82
X4 >= 43
X4 + X5 >= 52
X5 >= 25
A continuación implementamos el modelo anterior en Solver. Notar que las celdas color amarillo son las asignadas a las variables de decisión y éstas a la vez vinculan las combinaciones posibles entre turnos y períodos atendidos.
Adicionalmente en la columna I se ha guardado el valor del lado izquierdo de las restricciones que garantizan el mínimo número de agentes por período.
Finalmente la función objetivo (celda color naranjo) corresponde a la suma producto entre las variables de decisión y los parámetros que representan el costo diario por agente en los respectivos turnos (SUMAPRODUCTO(C4:G4;C19:G19)).
La implementación del modelo anterior en la interfaz de Solver es la siguiente:
Alcanzando la solución óptima del problema que considera la asignación de 48, 31, 39, 43 y 25 personas a los turnos 1,2,3,4 y 5, respectivamente, con un costo total (mínimo) de $32.560.
El siguiente video de nuestro canal en Youtube muestra la resolución del problema anterior:
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.
Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.
En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.
Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.
A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.
Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.
Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos «Download Now».
Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo «Acerca de Microsoft Excel».
Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).
Paso 4: Una vez completada la descarga ejecuta el archivo «SolverSetup64.exe» (o el nombre que corresponda según la versión de Excel que estés utilizando).
A continuación se desplegará el asistente para la instalación del programa. (Seleccionar «Next»).
Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:
Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar «Next».
En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando «OK».
Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que el programa selecciona por defecto.
Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado «Premium Solver Pro» que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.
El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado («Install»).
Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.
