investigación de operaciones Archivos - Página 6 de 26

Problema de Arriendo de Camiones y Distribución de Carga en Programación Entera

Los problemas de optimización asociados a redes logísticas de distribución o cadenas de suministro, admiten distintas variantes que buscan representar los aspectos más relevantes de estas problemáticas. Tal es el caso del problema de localización y transporte, problema de producción y transporte, problema de transporte con transbordo, entre otros. En el siguiente artículo presentamos la formulación y resolución con Solver de Excel de un problema de arriendo de camiones y distribución de carga, que por su naturaleza se puede clasificar como un modelo de Programación Entera Mixta.

Una empresa debe transportar grava a tres construcciones. La empresa puede comprar hasta 18 toneladas de grava al norte de la ciudad (Foso 1) y hasta 14 toneladas al sur de la ciudad (Foso 2). Se necesitan 10, 5 y 10 toneladas de grava en las construcciones 1, 2 y 3, respectivamente. Los costos de transporte por tonelada desde cada foso a cada construcción y el precio de compra por tonelada de material en cada foso están dados en la siguiente tabla:

Adicionalmente, suponga que los camiones necesarios para el transporte de dicho material deben ser arrendados. Cada camión puede ser usado para llevar grava de un solo foso a una sola construcción. El arriendo de un camión es de $5 por camión. Un camión puede transportar 5 toneladas pero no tiene que ir necesariamente lleno. Formule y resuelva un modelo de programación lineal entera-mixta que permita tomar una decisión óptima del número de camiones a usar y la cantidad de material que va a transportar cada uno.

Variables de Decisión: Se debe establecer las toneladas de grava a transportar desde cada foso a cada construcción y adicionalmente especificar la cantidad de camiones utilizados para transportar grava para cada combinación origen destino.

Función Objetivo: Se busca minimizar los costos totales de compra, la logística de distribución y arriendo de camiones. En color amarillo se observan los costos de compra, con color verde los costos de transporte y con color celeste el costo de arriendo de los camiones.

Restricciones: A continuación se detallan las condiciones que deben satisfacer las variables de decisión para este problema.

Demanda de las Construcciones: cada construcción (1, 2 y 3, respectivamente) debe recibir las toneladas de grava.

Capacidad de Abastecimiento de los Fosos: la cantidad de toneladas de grava que cada foso puede despachar a las distintas construcciones no puede superar el máximo de compra.

Capacidad de Transporte de los Camiones: cada camión puede transportar como máximo 5 toneladas de grava. En consecuencia las toneladas de grava que como máximo se pueden transportar en cada combinación origen destino estará limitada a la cantidad de camiones contratados en dicho trayecto. Por ejemplo, si se arriendan 2 camiones para transportar grava desde el foso 1 a la construcción 1 (el lector podrá apreciar que en efecto eso es lo que sucede en la solución óptima que se detalla más abajo) la cantidad máxima a transportar serán 10 toneladas.

No Negatividad y Enteros: el número de camiones contratados para transportar grava en cada combinación origen destino necesariamente deberá ser un número entero mayor o igual a cero.

No Negatividad: las toneladas de grava a transportar desde cada foso a cada construcción deberá respetar las condiciones de no negatividad (se permite transportar fracciones de tonelada de grava).

Al implementar el modelo de optimización anterior haciendo uso de Solver de Excel se alcanza la siguiente solución óptima y valor óptimo.

Se observa que se arriendan en total 5 camiones (por un total de $25 por concepto de costo de arriendo): 2 camiones para llevar grava del foso 1 a la construcción 1 (transportando 10 toneladas), un camión para llevar grava del foso 2 a la construcción 2 (transportando 5 toneladas), un camión para transportar grava del foso 1 a la construcción 3 (transportando 5 toneladas) y un camión del foso 2 a la construcción 3 (transportando 5 toneladas). En consecuencia el costo de transporte total es de $90, asumiendo adicionalmente un costo de compra de $270. Finalmente el costo total (valor óptimo) es de $385 (sumatoria de los costos de arriendo de camiones, costo de transporte y costo de compra).

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.

Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando $X_{4}$ y $X_{5}$ como variables de exceso y $X_{6}$ y $X_{7}$ como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

A continuación podríamos seleccionar como variable que ingresa a la base tanto a $X_{1}$ , $X_{2}$ o $X_{4}$ , al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable $X_{2}$ que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable $X_{2}$ , siendo éste: $Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3$ , por tanto $X_{1}$ deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

Eliminamos las columnas de las variables auxiliares $X_{6}$ y $X_{7}$ y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

Luego llevamos a cero los costos reducidos de las variables $X_{3}$ y $X_{2}$ :

Ahora entra la variable $X_{1}$ a la base. El criterio de factibilidad o mínimo cuociente determina que $Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4$ la variable $X_{3}$ deja la base. Se actualiza la tabla:

Que corresponde a la tabla final de la Fase II donde $X_{1}=1/4$ , $X_{2}=1/2$ y $X_{3}=0$ y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla intermedia de la Fase I se ingresa a la base a la variable $X_{1}$ . Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables $x_{3}$ y $x_{4}$ se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable $x_{2}$ la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable $x_{1}$ se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.

Cambio de Variables como alternativa al Método Simplex de 2 Fases

Una empresa que fabrica tres artículos A, B y C, desea encontrar un Plan de Producción semanal que le permita maximizar sus beneficios netos totales. Los productos son procesados en tres máquinas siendo la producción mínima semanal de 100, 60 y 60 unidades respectivamente. El beneficio neto por unidad vendida de estos artículos son 2, 2 y 4 mil pesos para los artículos A, B y C, respectivamente. Las horas que se necesitan por unidad y máquina son:

Siendo el número de horas disponibles de cada máquina 240, 400 y 360 respectivamente. Formule un modelo de Programación Lineal para abordar el problema propuesto. Resuelva a través del Método Simplex dicho modelo, indicando cuántas unidades de A, B y C se deben fabricar semanalmente y el beneficio final de este plan.

Variables de Decisión: Se debe definir cuántas unidades de cada uno de los 3 productos se fabricarán durante el período de evaluación.

Función Objetivo: Consiste en maximizar el beneficio neto asociado al plan de producción.

Restricciones: Se debe garantizar que se fabrique los mínimos semanales exigidos para cada producto como también que se respete la disponibilidad de horas máquinas.

El problema anterior se puede resolver por el Método Simplex de 2 Fases agregando variables de exceso y auxiliares para cada una de las restricciones que establecen los mínimos semanales de producción. Además se debe agregar variables de holguras para cada una de las restricciones de disponibilidad de horas máquinas. En consecuencia el problema de la Fase 1 tendría 3 variables auxiliares (cuya sumatoria se minimiza en la función objetivo) lo cual genera una instancia de resolución al menos tediosa para este problema (en caso se ser abordada manualmente).

Una alternativa más eficiente de resolución se alcanza al imponer un cambio de variables, lo que permite simplificar las restricciones de mínimos de producción semanal. Sea $X=A-100\geq 0$ , $Y=B-60\geq 0$ y $Z=C-60\geq 0$ . Luego $A=X+100$ , $B=Y+60$ y $C=Z+60$ , obteniendo la siguiente instancia de modelamiento equivalente:

A continuación llevamos a la forma estándar el modelo anterior, transformando la función objetivo a minimización y agregando $s_{1},s_{2},s_{3}$ como variables de holgura de las restricciones 1, 2 y 3, respectivamente:

Lo que da origen a la siguiente tabla inicial del Método Simplex:

A continuación incorporamos a la base a la variable Z considerando el criterio que favorece la rapidez de convergencia del algoritmo. Luego calculamos el criterio de factibilidad o mínimo cuociente en la columna de la variable Z: $Min\begin{Bmatrix}\frac{60}{2}; \frac{180}{1}; \frac{40}{1}\end{Bmatrix}=30$ , lo que determina que la variable $s_{1}$ deja la base. Se actualiza la tabla realizando una iteración del Método Simplex:

Se procede a incorporar a la variable $X$ a la base y $s_{3}$ abandona la base dado que $Min\begin{Bmatrix}\frac{150}{1}; \frac{10}{2}\end{Bmatrix}=5$ . Se realiza una iteración adicional que permite alcanzar la siguiente solución básica factible óptima:

La solución óptima es $X=5$ , $Y=0$ y $Z=30$ que al remplazar en las variables originales permite obtener $A=X+100=5+100=105$ , $B=Y+60=0+60=60$ y $C=Z+60=30+60=90$ . Notar que el valor óptimo es $V(P)=130+560=690$ luego de sumar el valor de la constante 560 al valor obtenido para la función objetivo del problema auxiliar. Se propone al lector corroborar los resultados anterior a través de la aplicación del Método Simplex de 2 Fases que por cierto permite alcanzar idénticos resultados pero con una mayor esfuerzo en la resolución.

Problema de Arriendo de Buses para Transporte de Pasajeros en Programación Lineal

El siguiente problema de Programación Lineal consiste en determinar una política óptima de arriendo de buses para el transporte de pasajeros que minimice los costos asociados a su arriendo y satisfaga los requerimientos de transporte y otras condiciones adicionales que se deseen imponer.

El Centro de Alumnos de Ingeniería Industrial de una respetada universidad desea celebrar el día del alumno en la playa. Este paseo está planificado para 1.200 alumnos como mínimo. Una empresa de transporte ofrece 2 tipos de buses pero solo cuenta con 28 conductores. La tabla de abajo indica la capacidad y el costo de arriendo de cada tipo de bus:

Para mantener el equilibrio de su flota, la empresa de transporte impone la condición de que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. Formule y resuelva un modelo de Programación Lineal que permita determinar cuántos buses de cada tipo hay que arrendar para el paseo de modo que resulte lo más económico para el Centro de Alumnos.

Variables de Decisión:

$x$ : Cantidad de Buses Tipo A arrendados
$y$ : Cantidad de Buses Tipo B arrendados

Función Objetivo:

Minimizar $80.000x+110.000y$

Restricciones:

Cantidad de Alumnos: $40x+60y\geq 1.200$
Cantidad de Conductores: $x+y\leq 28$
Condición de Flota: $x-y\geq 0$
No Negatividad: $x,y\geq 0$

El dominio de soluciones factibles del problema esta dado por el polígono ABC según se detalla a continuación (representación gráfica realizada con el software Geogebra). En particular la solución óptima corresponde al vértice A donde $x=12$ e $y=12$ , con valor óptimo $V(P)=80.000*12+110.000*12=2.280.000$ .

Notar que si bien el problema fue modelado como uno de Programación Lineal, dadas las características del problema sería deseable obtener una solución entera para las variables de decisión (dado que no es posible arrendar una fracción de buses y asumir por ejemplo que el costo del mismo es proporcional a la capacidad ocupada). No obstante en el ejemplo propuesto la solución óptima obtenida cumple de forma natural con las condiciones de integralidad, lo que indica que sus resultados son idénticos al problema de Programación Entera asociado (es decir, aquel al cual se le agregan de forma explícita las condiciones de enteros para las variables de decisión).

De forma complementaria al análisis anterior se pueden responder las siguientes preguntas correspondientes al análisis de sensibilidad o postoptimal:

1. Determine cuánto podría variar el costo de arriendo del Bus tipo A que conserve la solución óptima. Si C1 (costo arriendo del Bus tipo A) varía en el intervalo entre [73.333,3 , ∞[ se conserva la actual solución óptima.

2. Determine el impacto en el valor óptimo del problema si se elimina la condición que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. El precio sombra de la restricción de condición de flota es 4.000. Luego si se elimina la condición de flota la solución óptima se alcanza en la mínima variación $(x,y)=(0,20)$ para una reducción permisible del lado derecho de dicha restricción en 20 unidades. Luego el nuevo valor óptimo es $V(P)=2.280.000+(-20-0)*4.000=2.200.000$ .