Un supuesto básico asociado a la Programación Lineal es que los parámetros o constantes son valores conocidos con exactitud al momento de resolver el modelo de optimización. Este supuesto de asumir que no existe incertidumbre claramente implica una simplificación en el modelamiento de problemas de naturaleza real y es conocido como el supuesto de modelo determinista.
La optimización también permite incorporar explícitamente la incertidumbre en los parámetros en el modelamiento, asumiendo que la totalidad o un conjunto de éstos se distribuyen aleatoriamente, lo cual se puede representar a través de una función de probabilidad conocida o una distribución empírica que modela distintos escenarios para los parámetros, asociando una probabilidad de ocurrencia en cada caso. Esta categoría de modelos de optimización (por cierto más complejos en comparación al caso determinista) se llaman modelos estocásticos, los cuales en rara oportunidad se analizan en cursos introductorios de Investigación de Operaciones, de modo que forman parte del programa de estudios en cursos de Magíster y Doctorado asociado al área de optimización matemática.
En relación a lo anterior, si bien un modelo determinista considera valores fijos para los parámetros, aún podemos analizar los cambios en los resultados del modelo (solución óptima y valor óptimo principalmente) en comparación a lo obtenido en una instancia de resolución original o escenario base. Esto se conoce como análisis de sensibilidad o análisis postoptimal.
Recordemos que la estructura de la tabla final del Método Simplex se puede representar de la siguiente forma:
Donde:
I: Matriz Identidad (Diagonal de “1”)
0: Vector de costos reducidos asociados a las variables básicas
B: Matriz de variables básicas
D: Matriz de variables no básicas
b: Vector de “lado derecho”
Cb: Coeficientes en la función objetivo asociados a las variables básicas
Cd: Coeficientes en la función objetivo asociados a las variables no básicas
A continuación presentamos los Análisis de Sensibilidad más recurrentes asociados a los modelos de Programación Lineal y utilizando como fuente de información la tabla final del Método Simplex. El siguiente es un listado de los artículos que hemos desarrollado para cada uno de estos temas los cuales te recomendamos visitar:
La Teoría de Colas o Líneas de Espera hace uso de modelos matemáticos para encontrar un balance adecuado entre el nivel de servicio ofrecido a los clientes y los costos asociados a su prestación. El objetivo es reducir el impacto desfavorable de la espera de los clientes o usuarios de un sistema a niveles tolerables.
Notar que la tolerancia de un cliente a la espera depende de muchos factores que resulta imposible enumerar de forma exhaustiva, incluso en un análisis introspectivo se puede apreciar que nuestra propia tolerancia no es rígida y se ve afectada por condiciones del ambiente, congestión del sistema, temperatura, urgencia, etc.
Una descripción general de la estructura de los modelos que representan lo que sucede en un proceso o línea de espera es la siguiente:
Clientes con una fuente de entrada (población finita o infinita). Una población finita se refiere a un conjunto limitado de clientes que usarán el servicio y en ocasiones formarán una línea. Por el contrario una población infinita es lo bastante grande en relación con el sistema de servicio.
Clientes entran al sistema y se unen a una cola (tiempo entre llegada de clientes). Por lo general se supone que el tiempo entre llegada de clientes se distribuye de forma exponencial. No obstante se puede corroborar lo anterior a través de un ajuste de curva para lo cual se puede utilizar software estadístico como Easyfit.
Se proporciona el servicio (tiempos de servicio) por un servidor (uno y/o múltiples servidores) a un miembro de la cola, según una disciplina de servicio (disciplina de la cola). La disciplina de la cola más común es FIFO, es decir, se atiende por orden de llegada.
El cliente sale del sistema.
En este contexto uno de los escenarios más sencillo para el análisis es aquel donde existe una fase de servicio, un único servidor, con una fuente de entrada infinita y una longitud permisible de la fila ilimitada.
Ley de Little
Un importante resultado matemático es el demostrado por John Little en 1961, el cual relaciona las siguientes variables:
L : Número promedio de clientes en un sistema W : Tiempo promedio de espera en un sistema λ : Número promedio de clientes que llegan al sistema por unidad de tiempo
Luego la Ley de Little establece que el número promedio de clientes en un sistema (L) es igual a la tasa promedio de llegada de los clientes al sistema (λ) por el tiempo promedio que un cliente esta en el sistema (W).
La fórmula es válida para sistemas y para subsistemas, es decir:
Donde Lq es el número promedio de clientes que esperan en la fila y Wq el tiempo promedio que un cliente espera en la fila. Adicionalmente µ representa el ritmo del servicio o capacidad del sistema.
Ejemplo Ley de Little
Un pequeño banco está considerando abrir un servicio para que los clientes paguen desde su automóvil. Se estima que los clientes llegarán a una tasa promedio de 15 por hora. El cajero que trabajará en la ventanilla puede atender a los clientes a un ritmo promedio de uno cada tres minutos. Suponiendo que el patrón de llegadas es Poisson y el patrón de servicios es Exponencial, encuentre:
La utilización promedio del cajero:
El número promedio de clientes en la línea de espera es:
El número promedio de clientes en el sistema:
El tiempo promedio de la espera en la fila:
El tiempo promedio de espera en el sistema:
En el libro de Investigación de Operaciones de Hamdy Taha se puede encontrar un archivo en formato Excel que permite automatizar este tipo de cálculos y que facilita el análisis de las líneas de espera. El archivo lo puedes descargar aquí: Formulas Sistemas de Espera.
Para la utilización de la planilla se deben completar los datos de entrada (Input Data) y se obtienen automáticamente los resultados que son consistentes con lo detallado anteriormente.
El ejemplo que hemos presentado ha sido obtenido del Libro de Administración de Operaciones duodécima edición de los autores Chase, Jacobs y Aquilano el cual puede ser adquirido a través del siguiente enlace:
El orden o secuencia en el cual se programan n trabajos en una máquina es significativo a la hora de estimar los tiempos de setup para pasar de un determinado trabajo a otro o incluso comenzar con cualquiera de ellos al inicio de la planificación.
En este contexto se reconoce formalmente como tiempo de setup la cantidad de tiempo necesario para preparar una máquina para realizar una operación diferente y cumplir con las especificaciones del cliente (estos tiempos de setup pueden representar por ejemplo calibración de la máquina, cambio de formatos, limpieza, mantención preventiva, etc).
En el siguiente artículo formularemos y resolveremos un modelo de Programación Entera que permita encontrar una secuenciación óptima de n trabajos en una máquina, lo cual será contrastado con la solución que se puede obtener por simple enumeración de secuencias, naturalmente para un número de trabajos “pequeño” (para fines académicos).
En general si se deben programar n trabajos en una máquina, la cantidad de secuencias posibles son n!.
Por ejemplo si tenemos 3 trabajos (n=3) que debemos asignar a una máquina la cantidad de secuencias posibles son 6 (3!=3*2*1). Lo anterior implica que aún para centros de trabajos pequeños es útil contar con un procedimiento que permita identificar aquella secuencia que minimice el makespan sin tener la necesidad de hacer una evaluación exhaustiva de cada una de ellas.
Consideremos un conjunto de trabajos que necesitan ser asignados a una cierta máquina, todos los cuales están disponibles al inicio de la programación y se conoce los tiempos de proceso y fechas de entrega como muestra la siguiente tabla:
Sin embargo, el tiempo de setup, correspondiente al tiempo requerido para preparar la máquina antes de cada trabajo, depende del trabajo que le precede. A continuación se indica los tiempos de setup aij cuando al trabajo j le precede el trabajo i:
Adicionalmente hay un tiempo de setup a0j asociado al primer trabajo a programar de acuerdo a los siguientes valores:
El objetivo entonces es programar las actividades de modo de minimizar el tiempo de utilización de la máquina (makespan) como resultado de la asignación propuesta. Notar que según lo descrito anteriormente el problema admite 6 secuencias posibles las cuales se enumeran a continuación para poder obtener el makespan de la programación.
Secuencia 1-2-3: 1+9+1+13+3+10=37[t]
Secuencia 1-3-2: 1+9+0+10+1+13=34[t]
Secuencia 2-1-3: 3+13+2+9+0+10=37[t]
Secuencia 2-3-1: 3+13+3+10+3+9=41[t]
Secuencia 3-1-2: 4+10+3+9+1+13=40[t]
Secuencia 3-2-1: 4+10+1+13+2+9=39[t]
Naturalmente la secuencia óptima es 1-3-2 con un makespan de 34[t]. Como el trabajo 1 es el que inicia la secuencia tiene un setup inicial de a01=1 y requiere de 9[t] para ser completado. A continuación sigue el trabajo 3 que dura 10[t] y como es el trabajo 1 el que le precede no se requiere tiempo de setup (a13=0). Finalmente se realiza el trabajo 2 con duración de 13[t], necesitándose 1[t] para pasar del trabajo 3 al trabajo 2 (a32=1).
Para abordar el problema anterior a través de un modelo de optimización definiremos el siguiente problema de Programación Entera que claramente permite extender su aplicación a problemas de mayor tamaño (número de trabajos):
Variables de Decisión:
Para i=1,2,3 y j=0,1,2,3 con i≠j. Por ejemplo si X10=1 esto indica que el trabajo 1 es el que se realiza inmediatamente después del trabajo 0, es decir, el trabajo 1 es el que inicia la secuencia.
Función Objetivo:
En la implementación computacional con Solver de Excel la función objetivo se representa a través de la siguiente fórmula:
Para mayor claridad a continuación un extracto de la pantalla del modelo computacional:
Se busca minimizar el makespan de la secuencia. Notar que se suman las constantes asociadas al tiempo de proceso de cada trabajo (las cuales son independientes de la secuencia y justifican que inicialmente el valor de la celda que representa la función objetivo sea igual a 32[t]) y que eventualmente se pueden omitir de la función objetivo (en dicho caso el valor óptimo representaría la sumatoria de los tiempos de setup de la secuencia y no el makespan de la programación).
Restricciones:
Se deben realizar los 3 trabajos:
A lo más una tarea sigue a la j-ésima al menos que sea la última de la secuencia:
Alternativas infactibles: (celdas color rojo en la planilla de cálculo)
Debe existir un trabajo inicial en la secuencia:
Luego de resolver con Solver el problema anterior se alcanza la siguiente solución óptima y valor óptimo:
Donde se corrobora que la secuencia óptima es 1-3-2 con un makespan de 34[t]. A continuación puedes descargar el archivo Excel con la resolución del problema anterior en el siguiente enlace: Minimizar Tiempos de Setup.
En el contexto de las relaciones de dualidad en Programación Lineal, los teoremas de dualidad fuerte y dualidad débil constituyen importantes resultados teóricos que contribuye a la comprensión y resolución de modelos de optimización lineales. En el siguiente artículo ilustraremos su utilización haciendo uso de un ejemplo sencillo para fines académicos que por supuesto puede ser extendido a problemas de mayor tamaño.
Consideremos los siguientes problemas Primal (P) y Dual (D) en su formato matricial:
Lo anterior no constituye una pérdida de generalidad dado que el problema primal puede ser de maximización o de minimización con la consecuente incidencia en la interpretación de los resultados.
Teorema de Dualidad Débil
El Teorema de Dualidad Débil establece que si x є IRn, es una solución factible del problema Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:
Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del problema dual de minimización al ser evaluada en su respectiva función objetivo, representa una cota superior del valor óptimo del problema primal de maximización.
Análogamente, una solución factible del problema primal de maximización al ser evaluada en dicha función objetivo representa una cota inferior del valor óptimo del problema dual de minimización. En conclusión: V(P)<=V(D).
En general si el problema primal tiene un dominio de soluciones factibles no acotado sin solución óptima (es decir, es un problema no acotado) el respectivo problema dual resultará ser infactible (y viceversa).
Para corroborar el Teorema de Dualidad Débil consideraremos un problema primal y su respectivo dual: (si tienes dudas respecto a las relaciones de dualidad te recomendamos leer previamente el artículo Cómo pasar de Primal a Dual y viceversa).
Una representación gráfica realizada con Geogebra del problema primal permite apreciar que el dominio de factibilidad es no acotado y su solución óptima se encuentra en el vértice C donde X1=2/5 y X2=6/5 con valor óptimo V(P)=16/5.
Notar adicionalmente que cualquier par ordenado que pertenece al área achurada es factible, por ejemplo X1=2 y X2=2 es una Solución Básica Factible para el problema primal con V(P)=8 (cota superior del valor óptimo del problema dual de maximización).
En cuanto al problema dual su dominio de factibilidad es acotado y su solución óptima se encuentra en el vértice C con Y1=2/5 e Y2=2/5 y valor óptimo V(D)=16/5. Adicionalmente existen otros puntos factibles como el origen (Y1=0 e Y2=0) con V(D)=0 lo cual permite corroborar que cualquier solución factible del problema dual al ser evaluada en la función objetivo (de minimización) genera una cota inferior del valor óptimo del problema primal de minimización.
Teorema de Dualidad Fuerte
Si un problema (Primal) de Programación Lineal tiene una solución óptima, entonces el correspondiente problema Dual también tiene una solución óptima, y los respectivos valores en la función objetivo son idénticos.
En consecuencia, del Teorema de Dualidad Fuerte se deduce que ambos problemas (primal y dual) al ser evaluados en sus respectivas soluciones óptimas (en caso de existir) proveen idéntico valor óptimo, es decir, V(P)=V(D). Es más, resulta suficiente resolver uno de ellos y luego utilizar las propiedades del Teorema de Holguras Complementarias para encontrar la solución óptima (y valor óptimo) de su problema equivalente. En nuestro ejemplo V(P)=16/5=V(D).
El método de multiplicadores de Lagrange (el cual es generalizado por las condiciones de optimalidad de Karush-Kuhn-Tucker) permite abordar la resolución de modelos de programación no lineal que consideran restricciones de igualdad. En este sentido y como resulta natural, el dominio de soluciones factibles considerará exclusivamente aquellas soluciones que permiten verificar el cumplimiento de la igualdad de dichas restricciones. Por el contrario, un problema de optimización que considera inecuaciones como restricciones, sólo requiere que éstas se cumplan y no necesariamente se deberá forzar el cumplimiento de ellas en igualdad (activas).
En general las condiciones de Lagrange se aplican a un problema que tiene la siguiente estructura:
Que da origen a la función Lagrangiana asociada a dicho problema:
Consideremos el siguiente problema de Programación No Lineal restringido que nos permitirá ilustrar la aplicación del método de Lagrange.
Notar que el problema adopta la estructura estándar previamente descrita y considera una única restricción de igualdad. No se incluye en particular condiciones de no negatividad, que en caso de estar presentes justificarían la aplicación del Teorema de Karush-Kuhn-Tucker.
En este contexto, un mínimo local para el problema propuesto debe satisfacer las condiciones necesarias de primer orden de Lagrange:
Que da origen al siguiente sistema de ecuaciones:
Donde la resolución es trivial y corresponde a x1=2, x2=2 y λ1=-4. Notar que el multiplicador de Lagrange asociado a una restricción de igualdad es libre de signo, en consecuencia la solución propuesta satisface las condiciones necesarias de primer orden.
Adicionalmente se cumplen las condiciones de segundo orden pues:
Es positiva definida (función objetivo estrictamente convexa y restricción lineal que define un conjunto convexo). Luego, el problema es convexo y en consecuencia x1=2 y x2=2 es mínimo global y solución óptima del problema. Este resultado por cierto es consistente con la representación gráfica del problema, donde la solución óptima corresponde al punto A, donde la restricción (color naranjo) es tangente a la curva de nivel que representa a la circunferencia de menor radio que intercepta el dominio de soluciones factibles.
