solver Archivos - Página 4 de 13 - Gestión de Operaciones

Problema de Inversión y Selección de Proyectos

Los modelos de Programación Entera constituyen una alternativa eficiente para apoyar la toma de decisiones en aquellos problemas donde se debe implementar (o no) una alternativa o curso de acción que no admite soluciones intermedias. Tal es el caso del Problema de Selección de Cartera de Proyectos donde no es razonable, por ejemplo, si se destina la mitad de los fondos requeridos para un proyecto, asumir que de éste se obtendrá la mitad de sus beneficios o Valor Presente Neto (VPN). Dicho de otro modo, el cumplimiento del supuesto de la proporcionalidad de la Programación Lineal no es adecuado.

El problema que se presenta a continuación aborda estos aspectos y adicionalmente se busca proponer distintas alternativas al momento de establecer las restricciones o condiciones del problema.

Problema de Inversión y Selección de Proyectos

Una empresa está pensando invertir en cuatro proyectos diferentes, cada proyecto se finaliza a lo más en 3 años. Los flujos de caja requeridos en cada año junto con el Valor Presente Neto (VPN) de cada proyecto, concluidos los años de ejecución, y las disponibilidades de recursos financieros se resumen en la siguiente tabla:

Interesa determinar en cuáles proyectos invertir de modo de conseguir el mayor VPN de la inversión.

Variables de Decisión: Se desea determina en cuáles proyectos invertir de las 4 alternativas posibles.

Función Objetivo: Maximizar la sumatoria del Valor Presente Neto (VPN) de los proyectos en los cuales se decida invertir.

Restricciones: Se proponen 3 escenarios para definir las restricciones del problema.

Alternativa 1: Reinvirtiendo el dinero no utilizado en un período, es decir, el dinero que eventualmente quede disponible al final del año 1 y año 2 se puede considerar como parte del presupuesto disponible para el año siguiente. Lo anterior se representa a través de las variables $s_{1}$ y $s_{2}$ , respectivamente.

La implementación computacional del problema haciendo uso de Solver de Excel nos entrega los siguientes resultados:

Se debe invertir en los proyectos 1 y 4. El VPN total es de $51.

Alternativa 2: Sin invertir el dinero no utilizado en un período, pero utilizando el retorno de los proyectos concluidos.

En este caso se debe invertir en los proyectos 1, 2 y 4, alcanzando un VPN total de $69.

Alternativa 3: Reinvirtiendo el dinero no utilizado en un período y también el retorno de los proyectos concluidos.

En este caso la solución óptima y valor óptimo es equivalente al escenario planteado en la Alternativa 3.

Cabe destacar que la Alternativa 3 es la que provee mayor flexibilidad (en cuanto a los presupuestos para inversión) en comparación a las Alternativas 1 y 2, en consecuencia era razonable esperar en este caso que el VPN total de la Alternativa 3 sea mayor o igual que los VPN de las Alternativas 1 y 2.

Notar que el conjunto de las soluciones factibles es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros). En el ejemplo, el número de soluciones factibles no supera el número de las soluciones binarias del problema (variables restringidas sólo a valores 0 o 1) que son $2^{4}=16$ , dado el número de variables utilizadas, de hecho las soluciones factibles son menos de 16 pues en particular $x_{i}=1$ para i=1,2,3,4 no satisface las disponibilidades de capital en cualquiera de las tres alternativas.

Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima

Una vez concluidas las iteraciones del Método Simplex y en el caso de alcanzar una solución básica factible óptima, puede resultar de interés determinar un intervalo de variación para un parámetro del vector de los lados derechos de las restricciones que permita conservar la geometría del problema. Esto implica que se conservan las restricciones activas originales en el nuevo escenario (es decir, se mantiene la base óptima) que se genera a partir de la modificación (individual) de un parámetro o coeficiente del lado derecho. Para ilustrar el resultado anterior consideremos el siguiente modelo de Programación Lineal.

Luego de llevar a la forma estándar el modelo anterior agregando $x_{3}$ , $x_{4}$ y $x_{5}$ como las variables de holgura de las restricciones 1, 2 y 3, respectivamente, y aplicar las iteraciones necesarias del Método Simplex, se alcanza la siguiente tabla final (óptima):

La solución óptima es $x_{1}=15$ y $x_{2}=40$ con valor óptimo $V(P)=615$ . El valor de las variables de holgura en el óptimo $x_{3}$ , $x_{4}$ y $x_{5}$ es 0, 0 y 20, respectivamente. Luego se puede concluir que la solución óptima del problema se alcanza con las restricciones 1 y 2 activas (notar que sus respectivas holguras con variables no básicas en el óptimo) y la base actual esta conformada por las variables $x_{1}$ , $x_{2}$ y $x_{5}$ .

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura $x_{3}$ representa el precio sombra asociado a la primera restricción ( $\pi_{1}=1/2$ ). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente $b_{1}=180$ ) de modo que se conserve la base óptima y por tanto nos permita hacer un correcto uso de la información del precio sombra.

Para ello se propone la siguiente fórmula que permite encontrar el intervalo de variación para un lado derecho que conserva la base óptima:

Max {-bj/yij con yij>0} <= D <= Min {-bj/yij con yij<0}

Por ejemplo determinemos el intervalo para el parámetro $b_{1}$ :

En consecuencia $b_{1}$ puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si $b_{1}\epsilon [150,195]$ se mantiene la base óptima.

El resultado anterior se puede corroborar gráficamente. La solución óptima se encuentra en el vértice C donde las restricciones 1 y 2 son activas (notar la curva de nivel que pasa por el vértice óptimo es la línea punteada de color azul). Si para el lado derecho de la restricción 1 consideramos $b_{1}=150$ se obtiene la línea de color verde y para $b_{1}=195$ la línea de color rojo. En estos casos si bien se modifica el dominio de soluciones factibles, la solución óptima conserva las actuales restricciones activas (y por ende cuando $b_{1}$ adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

Esto es consistente con el Informe de Confidencialidad de Solver. En particular el reporte de restricciones donde se aprecia el aumento y reducción permisible que conserva la actual base óptima:

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es $b_{1}=190$ ?. Como $b_{1}=190\epsilon[150,195]$ , entonces $V(P)=615+\Delta b_{1}\pi _{1}=615+(190-180)*(1/2)=620$ . ¿Cuál es la nueva solución óptima?. Como sabemos que se conservan las restricciones activas en el óptimo para la variación propuesta, la solución óptima del nuevo escenario se obtiene simplemente resolviendo el siguiente sistema de ecuaciones (notar que la restricción 1 y 2 se conservan activas):

De donde $x_{1}=20$ y $x_{2}=110/3$ , que al evaluar en la función objetivo se obtiene: $V(P)=9*(20)+12*(110/3)=620$ corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para $b_{2}$ y $b_{3}$ que conserve la base óptima.

Problema de Generación Eléctrica mediante Programación Entera Mixta

Una de las particularidades de los modelos de Programación Entera es que permiten incorporar en la representación matemática costos fijos que no son proporcionales al nivel de actividad en un sistema. Tal sería el caso, por ejemplo, de una empresa que desea determinar lotes de compra de un producto dado, en los que incurre en costos fijos asociados a la gestión de compra (independiente del volumen de unidades compradas dentro de los límites máximos impuestos por el proveedor) y costos variables (proporcionales) a la cantidad de unidades compradas. En este contexto se presenta a continuación un problema de generación de energía eléctrica donde se debe determinar la utilización y actividad de generadores que busca satisfacer requerimientos proyectados de energía de un día particular.

EGE abastece de electricidad a tres ciudades. La compañía dispone de cuatro generadores que son utilizados para proporcionar la potencia eléctrica requerida. El generador principal es empleado las 24 horas del día y no es materia de planificación en este problema.

Los otros tres generadores (que llamaremos 1, 2 y 3) están disponibles para generar la potencia adicional cuando se requiera. Considerar que se incurre en un costo de arranque cada vez que uno de estos generadores comienza a operar.

Los costos de arranque son de $6.000 para el generador 1, de $5.000 para el generador 2 y de $4.000 para el generador 3. Estos generadores se utilizan (por separado) únicamente de la siguiente manera: se puede poner en operación a las 6am y funcionar 8 horas (hasta las 2pm) o 16 horas (hasta las 10pm), o puede ponerse en funcionamiento a las 2pm y funcionar 8 horas (hasta las 10pm).

Los pronósticos para mañana indican la necesidad de contar con 3.200 MW adicionales entre las 6am y las 2pm, necesidad que se eleva a 5.700 MW entre las 2pm y las 10pm. El generador 1 puede proporcionar hasta 2.400 MW, el 2 hasta 2.100 MW y el 3 hasta 3.300MW. El costo por MW utilizado durante un periodo de 8 horas es de $8 en el caso del generador 1, $9 en el de el generador 2 y $7 en el caso del generador 3.

Formule y resuelva un modelo de Programación Entera Mixta para determinar los niveles óptimos de operación de cada generador para el día de mañana que minimice los costos totales satisfaciendo los requerimientos adicionales de potencia eléctrica.

Variables de Decisión:

Si bien se podría considerar cierta similitud en la definición de $Y_{it}$ y $Z_{it}$ , su utilización se justifica dado que el costo fijo de arranque se debe asociar precisamente a dicho concepto (puesta en marcha de un generador) el cual se produce (en caso de ser utilizado) sólo una vez durante el período de planificación.

Función Objetivo:

Se busca minimizar los costos fijos asociados al arranque de los generadores más el costo variable que resulte de la cantidad de MW aportados por éstos al sistema en los 2 tramos o períodos de planificación.

Restricciones:

Capacidad Generadores: La cantidad de MW que aporta cada generador al sistema no puede superar su capacidad máxima disponible (en caso que se emplee) en cada uno de los períodos de planificación.

Demanda MW: En conjunto los generadores deben aportar la cantidad de MW adicionales para cada tramo horario, es decir, de 6am a 2pm y de 2pm a 10pm.

Relación Arranque Funcionamiento: Un generador sólo podrá ser empleado si arranco en el período de planificación actual o inmediatamente anterior, en caso contrario el generador no arranca (y por tanto no funciona en ninguno de los 2 períodos).

No Negatividad: La cantidad que aporta cada generador en los 2 tramos horarios de 8 horas debe ser mayor o igual a 0 (MW).

Al implementar el modelo anterior haciendo uso de Solver se alcanzan los siguientes resultados:

Notar que sólo arranca el generador 1 (a las 2 pm) y el generador 3 (a las 6 am). El generador 2 no arranca (y en consecuencia no se emplea) durante todo el día. El generador aporta 2.400 MW de 2pm a 10 pm, en tanto el generador 3 aporta con 3.200 MW de 6 am a 2 pm y 3.3o0 MW de 2 pm a 10 pm, respetando en cada caso las capacidadidas disponibles y satisfaciendo los requerimientos de demanda. Finalmente el costo óptimo (mínimo) es de $74.700.

Informe de Confidencialidad de Celdas de Variables y Restricciones de Solver

El siguiente problema tiene por objetivo mostrar la interpretación del Informe de Confidencialidad (o Informe de Sensibilidad) de Solver de Excel en los distintos escenarios que de éste se pueden considerar. Una empresa fabrica 3 productos (A, B y C) y desea planificar la producción semanal de cada uno de estos productos. Para ello dispone de 200 horas semanales en el departamento de corte, 350 horas semanales en el departamento de ensamblaje y 250 horas semanales en el departamento de terminado. Cada producto utiliza una determinada cantidad de horas en estos departamentos según lo muestran los parámetros en el lado izquierdo de las respectivas restricciones. Adicionalmente la empresa ha adquirido contratos con clientes que compran el producto B y C para producir al menos 50 y 30 unidades semanales, respectivamente. Finalmente según el departamento de ventas se ha estimado que la demanda máxima semanal para los productos A, B y C son 60, 120 y 80 unidades respectivamente.

Un modelo de Programación Lineal para la situación anterior es:

Luego de implementar en Solver de Excel el modelo anterior se obtiene el siguiente Informe de Confidencialidad (Informe de Sensibilidad):

1. ¿Cuánto estaría dispuesto a pagar para cancelar el contrato que obliga a producir al menos 30 unidades de C?

El Precio Sombra de la restricción de contrato del producto C es de -2 y su disminución permisible es de 30 unidades. Por tanto podemos utilizar el precio sombra para predecir el cambio en el valor óptimo ante la eliminación de este contrato (que sería equivalente a reemplazar $C\geq 30$ por $C\geq 0$ ). El valor óptimo en consecuencia aumentaría en -2*(0-30)=$60 que determina la máxima disposición a pagar para eliminar este contrato.

2. Suponga que se elimina el contrato que obliga producir al menos 50 unidades de B. ¿Cuál es el impacto en el impacto en el valor óptimo?

El Precio Sombra de la restricción de contrato del producto B es de -19 y su disminución permisible es de 10 unidades. Esto determina que reemplazar $B\geq 50$ por $B\geq 0$ no llevaría la producción de B a cero sino que sólo disminuiría a 40 unidades. Por tanto al eliminar este contrato el valor óptimo aumentaría en -19*(40-50)=$190 que determina la máxima disposición a pagar para eliminar este contrato.

3. Suponga que la empresa tiene $100 para invertir en capacidad. El costo de una hora extra de capacidad en los departamentos de Corte, Ensamblaje y Terminación es de $7, $5, y $6 respectivamente. ¿Cómo invertiría los fondos?. Asuma que sólo puede invertir en una de las 3 alternativas.

No tiene sentido destinar fondos adicionales para contratar horas extraordinarias en los departamentos de ensamblaje y terminado dado que en la actual solución óptima éstas restricciones no se encuentran activas y por tanto existen horas ociosas en dichos departamentos (70 y 80 horas semanales, respectivamente).

Por el contrario el departamento de corte se encuentra operando a máxima capacidad y dispone de un precio sombra de $9 que es mayor al costo de la hora extra de $7, por lo tanto conviene comprar capacidad adicional.

Con un presupuesto de $100 se pueden adquirir 14,2857 horas adicionales en el departamento de corte ($100/7) lo cual está dentro del aumento permisible para el precio sombra (23,3 horas) por tanto se destina la totalidad del presupuesto para dicho propósito.

4. ¿Cuál es el rango de variación para el coeficiente asociado a la variable B en la función objetivo que conserva la actual solución óptima?

Notar que la solución óptima actual es A=20, B=50, C=30. Adicionalmente el valor actual del parámetro en la función objetivo que pondera la variable B es 8, con un aumento permisible de 19 y una reducción permisible de 1E+30 (infinito). Es decir, el intervalo de variación para el parámetro que conserva la solución óptima es ]-1E+30,27]. La cota inferior del intervalo anterior cobra sentido al considerar la restricción de Contrato de B, que, independiente del beneficio (o pérdida) que reporte dicho producto al plan de producción, se debe fabricar de todos modos.

Solución del Problema del Vendedor Viajero

El Problema del Vendedor Viajero (conocido también como Travelling Salesman Problem o simplemente TSP) consiste en encontrar el circuito óptimo (en términos del viaje más corto) que deberá seguir un vendedor en un caso con n ciudades, en el que cada ciudad se visita exactamente una vez. Básicamente es una adaptación del Problema de Asignación que considera restricciones adicionales que garantiza la exclusión de subcircuitos en la solución óptima.

Específicamente en el caso de n ciudades se define las variables de decisión de la siguiente forma:

Sea $d_{ij}$ la distancia de la ciudad i a la ciudad j, donde $d_{ij}=\infty$ , el modelo del agente o vendedor viajero corresponde a:

El conjunto de restricciones (1) y (2) definen un modelo de asignación tradicional. Lamentablemente en general, el problema de asignación producirá soluciones de subcircuito más que circuitos completos que abarque las n ciudades.

Para ilustrar los conceptos de circuito y subcircuito en el contexto del Problema del Vendedor Viajero, consideremos un agente de venta que vive en la ciudad 1. Miami (Florida) en Estados Unidos y debe visitar a importantes clientes en las siguientes ciudades: 2. Chicago (Illinois), 3. Houston (Texas), 4. Las Vegas (Nevada) y 5. San Francisco (California). Para mayor claridad se han destacado los estados mencionados anteriormente con un color distintivo.

Un circuito factible sería viajar en el siguiente orden: Miami (FL), Chicago (IL), Houston (TX), Las Vegas (NV), San Francisco (CA), Miami (FL). Es decir, $x_{12}=x_{23}=x_{34}=x_{45}=x_{51}=1$ .

Por otra parte un subcircuito correspondería, por ejemplo, a Miami (FL), San Francisco (CA), Las Vegas (NV), Miami (FL), junto a Houston (TX), Chicago (IL), Houston (TX). Es decir, $x_{15}=x_{54}=x_{41}=x_{32}=x_{23}=1$ , lo que naturalmente no es una solución factible para el problema que se busca resolver.

El modelo del vendedor viajero se caracteriza por su versatilidad para representar otros casos prácticos en optimización. Uno de ellos es el Problema de Secuenciamiento de la Producción como el que se presenta a continuación:

El programa de producción diaria de una empresa de pinturas incluye lotes de color Blanco (B), Amarillo (A), Negro (N) y Rojo (R). Como la empresa utiliza las mismas instalaciones en las cuatro clases de pintura, es necesario hacer una limpieza entre los lotes. La siguiente tabla resume el tiempo de limpieza, en minutos, donde al color de la fila sigue el color de la columna. Por ejemplo, cuando después de la pintura Blanca sigue la Amarilla, el tiempo de limpieza en 10 minutos. Como un color no puede seguir a sí mismo, a los elementos correspondientes se les asigna un tiempo de setup infinito. Se desea determinar la secuencia óptima para la producción diaria de los cuatro colores, que minimice el tiempo total de limpieza necesario.

Se puede hacer una analogía con el problema del vendedor viajero, asumiendo que cada pintura es una «ciudad» y que las «distancias» representan el tiempo de limpieza necesario para cambiar de un lote de pintura al siguiente. En consecuencia, el problema se reduce a determinar el circuito más corto que se inicie en un lote de pintura y pase exactamente una vez por cada uno de los tres lotes restantes, para regresar al punto de partida.

En este contexto dada la cantidad de pinturas, la secuencia óptima se puede encontrar por enumeración exhaustiva de los 6 circuitos posibles $(n-1)!$ , es decir, $(4-1)!=3!=6$ . En el ejemplo dicha secuencia óptima corresponde a Blanco, Amarillo, Rojo, Negro, Blanco, con un tiempo total de setup de 98 minutos. Naturalmente esta estrategia no es eficiente y queda limitada a problemas muy pequeños.

Alternativamente se puede utilizar implementar en Solver el modelo de asignación presentado anteriormente, haciendo uso de los parámetros descritos en el ejemplo del secuenciamiento de la producción de pinturas. A continuación un extracto de los resultados donde se observa que no se alcanza una solución de circuito.

En la actualidad existen programas computacionales que permiten enfrentar estas dificultades que establece el problema del vendedor viajero. Uno de ellos es el software TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz intuitiva y que a continuación se detalla la implementación de nuestro problema (recordar que la Ciudad 1 correspondería al color Blanco, y así sucesivamente).

Una vez ingresado los datos al seleccionar «Solve» el programa se ejecuta entregando los resultados alcanzados que por cierto coincide con aquellos que identificamos por enumeración.

En términos algorítmicos los métodos disponibles para resolver el problema del agente o vendedor viajero tienen su base en las ideas de los algoritmos generales de ramificación y acotamiento (Branch and Bound) o de Plano de Corte, en los cuales abordaremos en próximos artículos.