Gestión de Operaciones

Cómo resolver un modelo de Programación Lineal con What’sBest!

En el siguiente tutorial mostraremos Cómo resolver un modelo de Programación Lineal con What’sBest!. Para ello por supuesto se requiere previamente descargar e instalar What’sBest! como complemento de Excel tal cual lo explicamos paso a paso en un artículo previo.

Para mostrar cómo utilizar este programa utilizaremos el Problema de Transporte que consiste en determinar una política de distribución que minimice los costos de la logística, al mismo tiempo que satisface la demanda de los clientes y respeta la capacidad de los oferentes.

La información se resume en el siguiente diagrama para un caso particular de 2 plantas y 3 clientes, donde los números sobre las flechas representan los respectivos costos unitarios de transporte entre una planta y un cliente.

Los pasos para implementar este problema de programación lineal en What’sBest! son:

Paso A: Definir las Variables de Decisión: Para ello debes previamente definir en un planilla Excel las celdas que utilizarás como variables. En el ejemplo la Xij: Unidades transportadas desde la planta i al cliente j. Con i=1,2 y j=1,2,3 se tienen 6 variables de decisión.

Importante: Completa las celdas que serán variables de decisión con cero como se muestra en la imagen anterior. Luego selecciona el rango de celdas que corresponde a las variables del modelo y presiona “Make Adjustable”.

Paso B: Definir la Función Objetivo: Como el nombre lo indica, ésta celda corresponde al objetivo del problema de optimización que en este caso es minimizar los costos totales de transporte. La celda contiene una fórmula SUMAPRODUCTO(C3:E4;C12:E13) previamente ingresa que pondera los costos unitarios de transporte para las distintas combinaciones (datos o parámetros) y las variable de decisión previamente definidas. Finalmente nos posicionamos sobre la celda de la función objetivo y seleccionamos en este caso “Minimize”.

Paso C: Definir las Restricciones: Se incorporan las restricciones del modelo de optimización, es decir, las condiciones que deben cumplir las variables de decisión al momento de la resolución. Para ello se selecciona en el menú la opción “Constraints”.

En la imagen a continuación se muestra cómo se incorporó la restricción que garantiza que la cantidad de unidades enviadas por cada planta (L.IZQ) no supere (<=) la capacidad de la misma (L.DER). Como se puede apreciar se incorporan las restricciones de capacidad de la planta 1 y 2 en forma simultanea.

Finalmente para proceder a la resolución del modelo seleccionamos la opción “Solve” del menú:

Luego de lo cual se obtienen los siguientes resultados:

Solución Básica Factible Óptima: X11=80.000; X12=40.000; X13=0; X21=0; X22=30.000; X23=90.000. El Valor Óptimo (mínimo costo) es de $940.000. Para descargar el archivo Excel con la resolución del modelo de transporte con What’sBest! sigue los pasos a continuación:

[sociallocker]Descarga Aquí: http://dlu.jzt.temporary.site/wp-content/uploads/2013/02/PTWB.xlsx[/sociallocker]

Cómo descargar e instalar la versión de Prueba de What’sBest! 11.1 en Excel 2010

What’sBest! es un excelente complemento para Excel que nos permite resolver modelos de optimización lineales, no lineales, enteros y probabilísticos (estocásticos) a través de una interfaz fácil e intuitiva. Este programa es altamente recomendado tanto para estudiantes como profesores del área de la Investigación de Operaciones y está disponible en una versión gratuita de prueba.

El siguiente tutorial muestra cómo, paso a paso, descargar e instalar la versión de prueba de What’sBest! 11.1 si eres usuario de Excel 2010. (Si tienes otro sistema operativo y/o versión de Excel este tutorial de seguro también te servirá).

Paso 1: Verificar el sistema operativo que utilizas y la cantidad de bits asociados. What’sBest! es compatible con Windows 2000, XP, Vista, Windows 7 y Windows 8. En este caso mostraremos cómo activar el complemento en un computador que utiliza Windows 7 Home Premium con un sistema operativo de 64 bits. Para verificar esta configuración ingresa a tu computador a Equipo y luego a Propiedades del sistema.

En la información del Sistema podrás identificar la cantidad de bits asociados a tu sistema operativo según se muestra en la siguiente imagen:

Paso 2: Ingresa a la sección de descarga de What’sBest! en la página web de su desarrollar Lindo, empresa con base en Chicago, Estados Unidos, con más de 21 años de experiencia en el desarrollo de software y aplicaciones para la optimización y apoyo a la toma de decisiones. Luego de acceder al enlace de descarga deberás seleccionar la versión del programa compatible con tu sistema operativo y tu versión de Excel.

Paso 3: Completar el formulario para obtener el archivo con el programa. Los campos con asterisco (*) son obligatorios.

Una vez completado lo anterior de forma correcta y luego presionar “Submit” obtendrás un mensaje que indicará que se ha enviado a tu correo electrónico un enlace de descarga de la versión de What’sBest! que hayas seleccionado.

Paso 4: Ingresa a tu correo electrónico (el que proporcionaste al completar el formulario). Deberías haber recibido un email de LINDO Systems Inc con el enlace para descargar el programa tal como se muestra a continuación. (Se han ocultado con franjas negras información confidencial y con rojo el enlace de descarga). Selecciona el enlace de descarga y se comenzará a bajar a tu computador el programa que viene en un archivo comprimido en formato ZIP.

Paso 5: Una vez completada la descarga (por defecto el archivo se guardará en la sección Descargas de tu computador) abre el archivo ZIP y luego ejecuta el archivo setup.exe a su interior como se muestra en la siguiente imagen:

Esto iniciará la aplicación de instalación que te guiará en el proceso de activación del software.

Paso 6: La instalación se ha completado. En Excel 2010 What’sBest! estará disponible a la derecha del menú Complementos. El programa esta listo para ser utilizado y resolver tus modelos de optimización.

Ahora que What’sBest! está instalado en tu computador estas listo para resolver un modelo de optimización. En el siguiente artículo te mostramos: Cómo resolver un modelo de Programación Lineal utilizando What’sBest!.

Importante: What’sBest! 12 estará disponible en las próximas semanas y será compatible con Excel 2013 y Excel 365. Te informaremos tan pronto sea lanzada esta nueva versión del software.

Ejemplo Lote Económico con Producción y Consumo Simultaneo (POQ)

El modelo de Lote Económico con Producción y Consumo Simultaneo (POQ) considera supuestos similares al Modelo de Cantidad Económica de Pedido (EOQ), sin embargo, asume que el reabastecimiento y consumo se realiza de forma simultanea durante un período de tiempo determinado luego del cual sólo se consume (demanda) a una tasa fija. Dicha característica del modelo de lote económico con producción y consumo simultaneo determina que su rango de aplicabilidad esta principalmente asociado a sistemas con autoabastecimiento, es decir, donde una parte del sistema productivo abastece en sus requerimientos a otra.

Los principales supuestos del modelo son:

La recepción del inventario es constante durante un periodo de tiempo.
La producción y demanda es conocida y constante.
El tiempo de entrega (lead time) se conoce y es constante.
No existen descuentos por cantidad, sin embargo, dicha condición es factible de flexibilizar al igual que el Modelo de Cantidad Económica de Pedidos (EOQ) con descuentos por cantidad.
Los dos únicos costos relevantes son el costo de mantener el inventario y el costo de hacer un pedido.
La falta de existencias (escasez) se evita si la orden se coloca en el momento adecuado.

Una representación gráfica de la evolución del inventario en función del tiempo para este modelo se presenta a continuación:

Donde d: demanda diaria y f: producción diaria. Luego esta implícito que f>d. Adicionalmente si buscamos el mínimo de la función de costos totales en términos del tamaño del lote de producción se obtiene la siguiente solución para el modelo:

Ejemplo Lote Económico con Producción y Consumo Simultaneo (POQ)

Una empresa puede producir un artículo o comprarlo a un contratista. Si lo produce le costará $30 cada vez que prepare sus máquinas. La tasa de producción f es 150 unidades diarias. Si lo compra a un contratista le costará $20 emitir un pedido. El costo de mantener un artículo en existencia, sea producido o comprado, es de $0,02 por unidad y por día. El consumo estimado de ese artículo por la empresa es de 29.200 unidades anuales. Suponiendo que no se permiten unidades faltantes, ¿la empresa debe producir o debe comprar?. Asuma que un año tiene 365 días.

Al utilizar el modelo de Lote Económico con Producción y Consumo Simultaneo se obtiene que la política óptima es generar lotes de producción de 717 unidades cada vez que se requiera. Notar que la demanda diaria d corresponde a 80 unidades (29.200[u/año]/365[días/año]).

El costo total anual asociado a este plan es de $2.443 (POQ). Si utilizamos EOQ el tamaño óptimo de pedido es:

Obteniéndose en este caso un Costo Total Anual (EOQ) de $2.920 por lo cual se recomienda en este caso el autoabastecimiento y por tanto la utilización de los resultados del modelo de lote económico con producción y consumo simultaneo.

Actualización: Con el objeto de detallar el cálculo de los costos totales para el ejemplo anterior, a continuación se presenta el detalle del procedimiento que corrobora los resultados anteriormente expuestos.

El Costo Total Anual para el caso del modelo POQ se obtiene de:

Para el caso del modelo de Cantidad Económica de Pedido o EOQ, el Costo Total Anual se obtiene de:

Método del Gradiente o Método del Descenso más Pronunciado

Para la optimización de modelos de Programación No Lineal sin restricciones se dispone de una categoría de métodos denominados “Algoritmos Generales de Descenso” entre los cuales se destaca el Método del Gradiente o Método del Descenso más Pronunciado (conocido adicionalmente como Método de Cauchy) que reducen el cálculo de un mínimo local a una secuencia de problemas de búsqueda lineal (o búsqueda unidimensional).

Consideremos el siguiente problema de Programación No Lineal no restringido:

Es importante observar lo siguiente: El punto de partida para comenzar las iteraciones es arbitrario y al ser evaluado en la función objetivo se alcanza un valor de V(8,7)=-149.

Si evaluamos la coordenada que se alcanza al realizar una iteración del método la función objetivo obtiene el siguiente valor V(12,5)=-169 que como se puede apreciar reduce el valor de la función objetivo.

En resumen el Método del Gradiente consta de 2 pasos principales:

Primero: El cálculo de una dirección de descenso que esta dado por el negativo del gradiente de la función objetivo evaluado en el punto de partida o en el de la k-ésima iteración. En el ejemplo dicha dirección desde la coordenada original x°=(8,7) esta dada en la dirección del vector d°=(8,-4).

Segundo: Obtener la magnitud del paso α (alfa) que determina cuánto se avanza en una determinada dirección de descenso. Esto se logra generando una función unidimensional en términos de este parámetro (respecto a la función objetivo original). En el ejemplo dicha magnitud del paso es α=1/2.

Finalmente se actualiza la coordenada según lo descrito previamente alcanzando (x1,x2)=(12,5) que como se corroboró otorga un valor en la función objetivo menor al punto de partida (arbitrario).

¿Cómo determinar si se ha alcanzado la solución óptima del problema no restringido a través del Método del Gradiente?

Para ello se debe verificar que la dirección de descenso en la k-ésima iteración es nula (cero).

Se puede corroborar en este ejemplo que esto se logra al intentar realizar una nueva iteración a partir de (x1,x2)=(12,5).

Adicionalmente se generan las condiciones de segundo orden calculando la Matriz Hessiana o de segundas derivadas de la función objetivo:

Donde los determinantes son estrictamente mayores a cero: D1=2>0 y D2=4>0 (la Matriz Hessiana por tanto es Positiva Definida) por lo cual la función objetivo es estrictamente convexa y dada la condición anterior es suficiente para garantizar que (x1,x2)=(12,5) es la solución óptima del problema.

Formulación de un Problema de Asignación en Programación Entera

El siguiente problema fue enviado por uno de nuestros usuarios de la ciudad de Valparaíso, Chile:

En un evento atlético de gimnasia las competencias comprenden cuatro disciplinas: salto, barras asimétricas, viga de equilibrio y manos libres. Cada equipo debe presentar 5 deportistas por disciplina. Un deportista puede participar como especialista en una o dos disciplinas o bien como un all-rounder que participa en las cuatro disciplinas. Al menos 3 de los miembros del equipo deben ser all-rounder. Un deportista es evaluado en una escala de 1 a 10. De acuerdo a las estadísticas del equipo de gimnasia de la universidad, se tienen las siguientes calificaciones para cada uno de los 6 miembros del equipo actual:

Formule y resuelva un modelo de Programación Entera que permita seleccionar a los 5 deportistas que presentará la universidad en cada disciplina del evento.

A continuación detallamos la formulación de este problema de Programación Entera:

1. Variables de Decisión:

Con i=1,…,6 (deportistas) y j=1,….,4 (deportes)

2. Función Objetivo: Maximizar el puntaje a obtener por los deportistas

Donde Pij representa el puntaje que tiene el deportista i en la disciplina j. Estos valores son parámetros del modelo y son los que se resumen en la tabla del enunciado. Por ejemplo: P13=9.

3. Restricciones:

Si un deportista es all-rounder se debe asignar a todas las disciplinas:

Deben haber al menos 3 deportistas all-rounder:

Se requiere de exactamente 5 deportistas por disciplina:

Límite de disciplinas por deportistas según su categoría: