GEO Tutoriales, Autor en Gestión de Operaciones

Método del Centroide aplicado a un Problema de Localización de Instalaciones

El Método del Centroide es una técnica para ubicar instalaciones que considera las instalaciones existentes, las distancias entre ellas y la cantidad de productos a transportar entre las mismas. Se suele suponer que los costos de envío o transporte de entrada y salida son iguales y no incluye costos de envío especiales.

La aplicación del Método del Centroide requiere ubicar las instalaciones existentes en un sistema de coordenadas. La elección de dicho sistema de coordenadas es completamente arbitraria, no obstante, actualmente son populares las medidas de longitud y latitud debido a la rápida adopción de los sistemas GPS. Sin perjuicio de lo anterior y con el objetivo de representar ejemplos sencillos se pueden utilizar coordinadas arbitrarias (X,Y).

El Centroide se encuentra calculando las coordenadas X e Y que dan como resultado el costo de transporte mínimo. Para ello se utilizan las fórmulas:

Donde:

Ejemplo Método del Centroide

Se desea determinar la ubicación óptima de una planta productiva (en adelante Planta E) mediante el Método del Centroide con respecto a otras 3 plantas demandantes a las cuales abastece de un cierto producto, que en lo sucesivo denotaremos por A, B y C y cuyas coordenadas (X,Y) son (150,75), (100,300) y (275,380), respectivamente. En este contexto, las plantas A, B y C requieren 6.000, 8.200 y 7.000 unidades anuales, respectivamente, las cuales serán transportadas desde la Planta E. Se supone una relación lineal entre los volúmenes enviados y los costos de envío (sin cargos adicionales).

Dada la información anterior calculamos las coordenadas en X e Y de la Planta E.

¿Minimizará la localización propuesta para la Planta E por el Método del Centroide la sumatoria de la distancia euclidiana respecto a las plantas demandantes A, B y C?. Para responder esta pregunta formulamos el siguiente modelo de Programación No Lineal no restringida:

Luego de implementar el problema anterior en Solver de Excel obtenemos la coordenada (X,Y)=(175,00, 251,67) que determina una sumatoria de distancias totales de 66.266,67[u] que es levemente inferior a la obtenida a través del Método del Centroide donde la sumatoria de las distancias alcanza las 66.662,80[u].

Esta diferencia menor se explica por la relativa similitud de los resultados obtenidos a través de los 2 métodos según se aprecia en la siguiente representación gráfica:

Teorema Fundamental de la Programación Lineal

En el siguiente artículo abordaremos a través de una discusión conceptual y ejemplos prácticos y sencillos las propiedades que establece el Teorema Fundamental de la Programación Lineal. Estas propiedades son indispensables tener en consideración al momento de la resolución algorítmica de este tipo de modelos de optimización matemática, destacando entre ellos el Método Simplex como así también la resolución de modelos lineales a través del Método Gráfico.

Teorema Fundamental de la Programación Lineal

Cada problema de Programación Lineal en su forma estándar cumple con las siguientes tres propiedades:

Propiedad 1: «Si el problema no tiene solución óptima entonces es no-acotado o infactible»

Notar que un problema lineal con dominio de soluciones factible no acotado puede (o no) admitir solución óptima, es decir, el hecho de enfrentar un modelo de estas características no determina a priori la presencia (o ausencia) de solución óptima.

En la aplicación del Método Simplex se detecta un problema no acotado sin solución óptima cuando al realizar el cálculo de la variable que deja la base, todos los elementos y_kj de la columna j en la tabla, son negativos para j el índice de una variable no básica con costo reducido negativo. Por ejemplo consideremos el siguiente problema de Programación Lineal:

Luego de llevar a la forma estándar el modelo anterior, agregando X3 y X4 como variables de holgura para la restricción 1 y 2, respectivamente, se obtiene la siguiente tabla inicial.

X2 es una variable no básica con costo reducido negativo y en consecuencia la incorporamos a la base. Sin embargo no es factible calcular el criterio de factibilidad o mínimo cuociente debido a que las entradas en la columna de X2 son negativas o cero. Lo anterior deja en evidencia que el problema es no acotado sin solución óptima.

Por otra parte un modelo lineal es infactible (dominio de soluciones factibles vacío y por tanto no admite solución) si el valor de la función objetivo al finalizar la Fase I del Método Simplex de 2 Fases es distinto a cero.

Propiedad 2: «Si tiene una solución factible, tiene una solución básica factible»

Una propiedad básica de los modelos de Programación Lineal es que en caso de admitir solución óptima, ésta se encontrará necesariamente en un vértice o tramo en la frontera del dominio de soluciones factibles.

En este contexto en la aplicación del Método Simplex como estrategia algorítmica de resolución, se busca proveer soluciones que cumplan con Ax=b (restricciones de la forma estándar) y x≥0, definiendo una solución básica factible (no necesariamente óptima).

Por ejemplo en el siguiente gráfico que representa un modelo lineal en 2 variables se puede apreciar que los vértices A, B, C, D y E son soluciones básicas factibles.

Propiedad 3: «Si el problema tiene solución óptima, tiene una solución básica factible óptima»

Siguiendo con el ejemplo anterior el vértice C no sólo es una solución básica factible sino también una solución básica factible óptima. Si todos los costos reducidos (de las variables no básicas: S1 y S3) son mayores o iguales que cero y estamos en presencia de una solución básica factible (X=100, S2=400, Y=350 todas ≥0), se cumple con el criterio de parada del Método Simplex y en consecuencia la actual solución básica factible es óptima.

Como resolver un modelo de Programación Lineal con LINGO 14.0

LINGO es un popular software de optimización matemática para uso tanto académico como empresarial desarrollado por LINDO Systems Inc (quienes desarrollaron What’sBest!) que provee una alternativa para enfrentar el problema de modelamiento matemático e implementación computacional en una plataforma distinta a Excel (en contraste a los complementos que han tenido un lugar preferente en nuestro sitio como Solver, Premium Solver Pro, What’sBest! y OpenSolver).

En el siguiente artículo detallaremos cómo descargar e instalar el programa LINGO para luego utilizar éste en la resolución de un modelo de Programación Lineal con 2 variables de decisión. Dado lo anterior consideremos el siguiente problema:

Paso 1: Descarga e instalar la última versión disponible de LINGO desde la sección de descargas del sitio web de LINDO Systems. Se debe tener especial atención en seleccionar de forma correcta la versión compatible con nuestro sistema operativo (Windows o Linux) y la cantidad de bits asociado a dicho sistema. Para verificar este último aspecto te recomendamos leer el artículo “Cómo descargar e instalar la versión de Prueba de What’sBest! 11.1 en Excel 2010”. En dicho artículo se detalla adicionalmente el procedimiento de registro y activación de la licencia.

Paso 2: Una vez instalado LINGO en nuestro computador ejecutamos el programa y luego implementamos el modelo de optimización. El software es compatible con distintos tipos de sintaxis las cuales iremos abordando en próximos artículos en el Blog). Por el momento a continuación detallamos una notación intuitiva que nos permite representar nuestro ejemplo:

Una vez incorporado definido el problema ejecutamos el botón “Solve”:

Paso 3: Se obtienen los resultados para el modelo. La ventana “Lingo 14.0 Solver Status” detalla las características del problema: LP (Programación Lineal) con Valor Óptimo de 2.025.

El detalle de los resultados se aprecia en el informe de respuestas que genera el programa de forma automática. La salida computacional se muestra a continuación:

La Solución Óptima es A=60 y C=27,5 con Valor Óptimo V(P)=2.025. Notar adicionalmente que los resultados son consistentes con los que obtendríamos de utilizar Solver para este ejemplo y haciendo uso del Informe de Confidencialidad (Sensibilidad).

Con color verde destacamos el precio sombra de cada una de las restricciones del problema. Estos valores se identifican en la columna etiquetada “Dual Price” en el informe de resultados de LINGO en las Filas (Row) 2, 3 y 4, respectivamente.

Una representación gráfica del problema anterior con Geogebra nos permite corroborar los resultados anteriores de forma intuitiva, por ejemplo la restricción C<=50 no está activa, en consecuencia su precio sombra es igual a cero.

Reglas de Prioridad en la Programación de Trabajos con el Software LEKIN®

LEKIN® es un software gratuito e intuitivo que permite entre otras cosas la programación de n trabajos en una máquina. Este programa fue desarrollado en Stern School of Business, NYU, siendo la mayor parte de su diseño y programación a cargo de estudiantes de la Universidad de Columbia en Estados Unidos. El software LEKIN® fue creado como herramienta educacional con el propósito principal de difundir en los estudiantes conceptos de programación de trabajos y sus aplicaciones en la industria.

En el siguiente artículo detallaremos como implementar la regla de prioridad FIFO (First In First Out) o análogamente en su acrónimo en español PEPS (Primero en Entrar Primero en Salir). Para ello consideraremos un problema que consiste en la programación de 5 trabajos a una máquina, donde los tiempos de proceso son determinísticos (es decir, se asume que no hay incertidumbre respecto a la duración de cada trabajo) y el patrón de llegada es estático (Todos los trabajos llegan simultáneamente y de manera previa al inicio de las operaciones).

Paso 1: Descargar el software LEKIN® (seleccionando Lekin.exe (1.67MB) según se muestra en la imagen) y seguir las instrucciones las instrucciones para su instalación.

Paso 2: Una vez instalado el programa y dadas las características de nuestro ejemplo, en el Menú Principal debemos seleccionar “Single Machine” (Una Máquina).

Paso 3: A continuación ingresamos la cantidad de trabajos que necesitamos programar. En nuestro ejemplo son 5 trabajos. Luego seleccionamos “OK”.

Paso 4: Ingresamos los datos de los trabajos en la interfaz que se muestra a continuación. Notar que hemos editado el nombre o etiqueta que identifica el trabajo (Job ID) el Tiempo de Procesamiento (Processing Time) y la Fecha de Entrega (Due Date). Al presionar “OK” se puede repetir el procedimiento para el resto de los trabajos.

Paso 5: En el menú del programa seleccionamos “Schedule” ==> “Rule” ==> “4 FCFS” (FCFS es equivalente a FIFO o PEPS).

LEKIN® genera una Carta Gantt donde se muestra la programación de los trabajos y el tiempo total o makespan para concluir la totalidad de éstos (80 días). Adicionalmente según se aprecia en “Job Pool” se detalla el día en que se da inicio y término a cada uno de los trabajos.

Paso 6: Finalmente en el Menú “Tools” (Herramienta) ejecutamos la opción “Performance”.

Esto permite obtener un cuadro resumen con los principales indicadores de gestión de la programación según se observa en la imagen:

De donde se corrobora los siguientes resultados según lo obtenido previamente en el artículo: “Reglas de Prioridad para la Programación de n Trabajos en una Máquina”.

Tiempo de Flujo Promedio = 245[días]/5[trabajos]=49[días/trabajo]
Tiempo de Atraso Promedio = 108[días]/5[trabajos]=21,6[días/trabajo]
Atraso Máximo = 40[días]
Número de Trabajos Atrasados = 3[trabajos]
Makespan = 80[días]

Conclusiones: El software LEKIN® puede ser utilizado tanto para la aplicación de otras reglas de prioridad en el contexto del ejemplo anterior (según se puede apreciar en el Paso 5 de este tutorial) como también en otras problemáticas relativas a la Programación de Tareas. Una de las ventajas del programa es que su distribución es gratuita y además resulta ser compatible aún con las versiones más recientes de Windows (teniendo en cuenta que su última actualización data de Abril de 2002). Lo anterior ha sido corroborado en la utilización de este software sin inconvenientes en un computador con sistema operativo Windows 7 Home Premium de 64 bits. Lo anterior constituye una ventaja en comparación a otras herramientas como WINQSB que requiere el uso de máquinas virtuales si se desea utilizar en versiones recientes del sistema operativo Windows.

Actualización (Febrero 2017): Se dispone de una versión más reciente del software LEKIN® que la utilizada en este tutorial y cuya fecha de actualización corresponde al mes de Octubre de 2010 y puede ser descargada en el siguiente enlace: Descargar LEKIN® (2010).

Cambio en un coeficiente de la Función Objetivo asociado a una Variable Básica

En el contexto del Análisis de Sensibilidad o Postoptimal en Programación Lineal y una vez alcanzada la tabla (tableau) final en la aplicación del método simplex, resulta de interés evaluar el impacto en la solución óptima del problema si cambia un coeficiente o parámetro en la función objetivo asociado a una variable básica. Se busca dar respuesta a este escenario sin la necesidad de reoptimizar, es decir, de resolver el problema original nuevamente.

Para conservar la solución óptima identificada inicialmente, se debe cumplir que el costo reducido de todas las variables debe ser mayor o igual a cero (recordar que el costo reducido de las variables básicas es cero por tanto dicha condición en la práctica se establece sobre las variables no básicas). Lo anterior se garantiza si el incremento es cualquiera en el siguiente intervalo:

Donde rj es el costo reducido de la respectiva variable no básica en la actual solución óptima y los coeficientes yij denotan las entradas en la tabla final del método simplex asociadas a la variable básica xi (cuyo costo cambia) y la respectiva variable no básica xj.

Para presentar el concepto anteriormente expuesto consideremos el siguiente problema de Programación Lineal:

Luego de llevar a la forma estándar, incorporando S1, S2 y S3 como las variables de holgura de las restricciones 1, 2 y 3 respectivamente y resolver el modelo lineal anterior a través del método simplex se alcanza la siguiente tabla óptima:

La solución básica factible óptima es Y1=40 e Y2=40 con valor óptimo V(P)=100. A continuación determinaremos un intervalo de variación para los coeficientes que ponderan a las variables Y1 e Y2 en la función objetivo de modo que conservar la actual solución óptima. En este sentido tanto Y1 como Y2 son variables básicas en el óptimo según se aprecia en la tabla anterior.

Luego el intervalo de variación para C1 (en adelante coeficiente asociado a la variable Y1 en la función objetivo de minimización) que mantiene la solución óptima original es:

Del cálculo anterior se obtiene que C1 (coeficiente que multiplica a la variable Y1 en la función objetivo de minimización) puede variar en el intervalo entre C1℮[-1-1/2, -1+1/4], es decir, C1℮[-3/2, -3/4] y se conserva la actual solución óptima. Si hacemos la equivalencia en la función objetivo de maximización original el intervalo corresponde a C1℮[3/4, 3/2], es decir, existe una reducción permisible de 1/4 y un aumento permisible de 1/2 para el valor actual del parámetro que mantiene la solución óptima inicial. De forma análoga se puede verificar que el intervalo de variación para C2 (en la función objetivo de maximización) corresponde a C2℮[1, 2], con un aumento y disminución permisible de 1/2 en cada caso.

Los resultados obtenidos son consistentes con los que provee el informe de confidencialidad o sensibilidad de Solver según se resume a continuación:

Una alternativa para corroborar los resultados anteriores de una forma intuitiva consiste en realizar una representación gráfica del problema anterior. La solución óptima se encuentra en el vértice C, donde la línea punteada de color rojo representa la curva de nivel que intersecta dicha solución. Por otra parte la línea punteada de color verde se obtiene al modificar C1 a 3/4 (reducción permisible de 1/4), lo cual conserva la solución óptima actual pero deja de ser única (en efecto se genera el caso de infinitas soluciones óptimas en el tramo entre los vértices B y C). Finalmente la línea color azul representa la curva de nivel que resulta de cambiar el coeficiente de C1 a 3/2 (aumento permisible de 1/2) que también conserva la solución actual y denota el caso de infinitas soluciones en el tramo CD).