Problema de Asignación en Programación Entera resuelto con Solver

Cuando necesitamos asignar recursos escasos a determinadas funciones y dichos recursos no son fraccionables, la utilización de modelos de Programación Entera resultan ser de utilidad para la toma de decisiones. En este contexto los problemas de asignación de personal a determinadas tareas es una aplicación típica de la Programación Entera que a continuación desarrollaremos a través de un ejemplo.

Problema de Asignación

Consideremos una empresa que dispone de 5 ingenieros que deben desarrollar 7 proyectos. La tabla a continuación resume el tiempo que demora cada ingeniero (en horas) en completar un determinado proyecto. El problema consiste en determinar una asignación óptima que permita realizar cada uno de los proyectos con la limitante que por motivos estratégicos cada ingeniero debe desarrollar al menos un proyecto y en ningún caso hacer más de 2 proyectos. Por supuesto se busca que el tiempo requerido para realizar los 7 proyectos sea el menor posible.

Tabla Asignación

Una alternativa sería buscar intuitivamente una asignación que cumpla con los requisitos de la empresa y tenga un bajo tiempo asociado. Sin embargo, este tipo de estrategias de resolución queda claramente acotada a problemas de tamaño menor y ni siquiera en ese tipo de situaciones nos asegura la mejor solución posible. Por ello definiremos el siguiente modelo de optimización de Programación Entera:

1. Variables de Decisión: Utilizamos las siguientes variables de decisión binarias

Variables de Decisión Asignación

2. Función Objetivo: Minimizar el tiempo total requerido para completar los proyectos

Función Objetivo Asignación

Donde Tij (parámetros) es el tiempo (en horas) requerido por el ingeniero i en realizar el proyecto j. Por ejemplo T(A,P5)=7.

3. Restricciones:

Cada proyecto debe ser realizado por un solo ingeniero:

Restricción Asignación

Cada ingeniero debe ser al menos un proyecto y no puede hacer más de 2:

Restricción Asignación Ingenieros

El siguiente tutorial muestra cómo resolver este problema de asignación con Solver de Excel:

Se puede observar que para efectos de Solver, las variables de decisión binarias se deben definir como una restricción adicional. También puede resultar que luego de resolver Solver no encuentre inmediatamente la mejor solución posible. Para enfrentar esta situación se puede «volver a resolver» sobre la solución que el programa nos haya proporcionado hasta el momento para verificar si se puede lograr algo mejor. Esta situación es la que sucedió en el tutorial y a continuación se muestra la solución óptima (final) encontrada por Solver.

Solución Óptima Problema de Asignación

En total se requieren 56 horas para realizar los 7 proyectos. El ingeniero A realiza el P7, el ingeniero B el P3 y P5, el ingeniero C el P6, el ingeniero D el P2 y P4 y el ingeniero E el P1. Notar que cada proyecto es realizado por un ingeniero y cada ingeniero al menos realiza un proyecto, pero no más de 2 proyectos.

Problema de Transporte resuelto con Solver de Excel

Un Problema de Transporte consiste básicamente en determinar una política de distribución óptima que permita satisfacer los requerimientos de un determinado número de clientes asociado a la capacidad o logística de un cierto conjunto de oferentes.

Este tipo de problemas es una aplicación clásica de los modelos de Programación Lineal debido a que nos permite abordar problemas de naturaleza real y adicionalmente, se puede incorporar elementos adicionales que hacen más compleja la representación a través de un modelo de optimización, pero que, sin embargo, en la mayoría de los casos resulta ser más realista.

En el siguiente artículo podrás encontrar un vídeo que describe la formulación general de un problema de transporte básico, como también el detalle de un caso específico o instancia y su posterior resolución computacional.

Problema de Transporte

A continuación se presenta probablemente el caso más simple a considerar para un Problema de Transporte. Asumamos que tenemos 2 oferentes (P1 y P2) con capacidad de producción de 160.000 y 120.000 unidades de un producto homogéneo. Estos oferentes deben abastecer a 3 clientes (C1, C2 y C3) con demandas unitarias de 80.000, 70.000 y 90.000 unidades, respectivamente. El gráfico a continuación muestra sobre las flechas los costos unitarios de transporte entre un origen (oferente) a un cliente (demandante).

Problema de Transporte

El problema consiste en determinar una política óptima de abastecimiento desde los oferentes a los demandantes de modo de cumplir los requerimientos y lograr los costos más bajos posibles. Para ello definiremos el siguiente modelo de Programación Lineal:

1. Variables de Decisión:

Xij : Unidades Transportadas desde la Planta i hasta el Cliente j (Con i=1,2, y j=1,2,3)

2. Función Objetivo:

Consiste en minimizar la función que representa los costos de transporte entre los oferentes y los demandantes.

Minimizar 3X11 + 4X12 + 6X13 + 5X21 + 3X22 + 5X23

3. Restricciones:

  • X11 + X21 = 80.000   (Satisfacer Demanda Cliente 1)
  • X12 + X22 = 70.000   (Satisfacer Demanda Cliente 2)
  • X13 + X23 = 90.000   (Satisfacer Demanda Cliente 3)
  • X11 + X12 + X13 <= 160.000   (Capacidad Planta 1)
  • X21 + X22 + X23 <= 120.000   (Capacidad Planta 2)
  • Xij >= 0   (No Negatividad)

Luego de implementar este modelo en Solver de Excel se obtiene la Solución Ó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. A continuación un video tutorial con el detalle de la resolución.

El ejemplo de transporte anterior es sin duda una de las versiones más sencillas que se puede encontrar de esta clase de problemas. Una extensión interesante y generalmente objeto de estudio en los cursos de Investigación de Operaciones es el Modelo de Transporte con TransbordoProblema de Transbordo en una Red Logística de Transporte Multiperíodo.

Cómo resolver un modelo de Programación Lineal utilizando Solver de Excel

El complemento Solver de Excel nos permite resolver modelos de Programación Lineal de forma muy sencilla e intuitiva. Para ello necesitamos tener previamente Instalado el complemento de Solver en Excel. Sin embargo, en caso que el modelo a implementar sea de un mayor tamaño (usualmente más de 150 variables de decisión y 300 restricciones) a los que usualmente se abordan en cursos introductorios de Investigación Operativa se recomienda utilizar Premium Solver Pro tal como se describe en Cómo descargar e instalar la versión de Prueba de Premium Solver en Excel 2010.

En este contexto hemos desarrollado un tutorial que compara distintas herramientas computacionales para resolver modelos de optimización en una interfaz de Excel. Al respecto recomendamos al lector revisar el artículo: Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte.

Cómo Resolver un modelo de Programación Lineal con Solver de Excel

El proceso se puede describir en 3 simples pasos y a continuación se aplica un problema típico de Producción y Transporte:

1. Definir las Variables de Decisión: Estas celdas serán las que estarán vinculadas a la función objetivo y restricciones a través de funciones lineales.

variables-solver

2. Definir la Función Objetivo: Esta celda debe ser única y ser adicionalmente una fórmula. Su valor dependerá del valor que se obtenga para las variables de decisión y su ponderación por los parámetros (constantes) que multiplican a dichas variables en la función objetivo.

definir-funcion-objetivo-so

3. Definir las Restricciones: Se recomienda dejar al Lado Derecho las constantes y al Lado Izquierdo fórmulas. El valor del Lado Izquierdo usualmente representa la ponderación de los parámetros relacionados con las restricciones con las variables de decisión.

definir-restricciones-solve

El siguiente tutorial muestra la resolución de un modelo de Programación Lineal de dos variables utilizando Solver de Excel. Este ejemplo es similar al descrito en el Tutorial de Geogebra. Adicionalmente se pueden encontrar otros ejemplos resueltos en el Canal de Youtube de nuestro sitio cuya dirección es https://www.youtube.com/user/GEOTutoriales/videos.