5.4: Optimización no lineal

Como se discutió anteriormente, la mayoría de los problemas de optimización de la administración de infraestructura se formulan como problemas Sin embargo, en algunos casos, puede ser necesaria una optimización no lineal. La forma general del problema de optimización no lineal es:

\ [\ text {Minimizar o Maximizar} f (x)\ texto {sujeto a } g_ {i} (x)\ leq 0\ texto {y} h_ {j} (x) =0\]

Donde\(x\) es un vector de variables de decisión,\(f(x)\) es una función objetiva no lineal,\(g_i(x)\) y\(h_j(x)\) son conjuntos de restricciones que pueden ser lineales o no lineales.

Una fuente de no linealidades es la de las economías de escala en la realización de una tarea de mantenimiento o rehabilitación. Esto podría ocurrir si hay costos fijos de movilización para emprender una tarea que luego se reparten sobre la cantidad de trabajo. Los componentes como los tanques también tienen economías de escala ya que su volumen crece más rápido que la superficie (costosa) del tanque a medida que aumenta el tamaño del tanque. La Figura 5.4.1 ilustra las economías de escala en dos gráficas relacionadas. En la gráfica superior, el costo por unidad de trabajo disminuye a medida que aumenta la cantidad de trabajo. En la gráfica inferior, el costo total sube más lento que el incremento en la cantidad de trabajo.

Figura\(\PageIndex{1}\): Ilustración de las economías de escala con respecto a la cantidad de trabajo.

Otra fuente de no linealidad para la gestión de la infraestructura proviene de los efectos de flujo. Por ejemplo, la congestión del tráfico vial no es lineal, ya que un pequeño aumento en el tráfico puede resultar en grandes cantidades de retraso. Con el mantenimiento vial bloqueando carriles de tránsito, se reduce la capacidad de la red vial y la congestión puede aumentar considerablemente. La Figura 5.4.2 ilustra el incremento no lineal en el tiempo promedio de viaje.

Figura\(\PageIndex{2}\): Ilustración de Efectos de Tiempo de Viaje No Lineal con respecto a Volúmenes de Vehículos.

La optimización no lineal tiene algunas dificultades. En primer lugar, las soluciones obtenidas pueden no ser óptimas globales sino solo valores locales máximos o mínimos de la función objetiva. Segundo, formulaciones particulares pueden conducir a resultados físicamente imposibles. Por ejemplo, en un caso de economías de escala, una optimización no lineal puede desear construir los pies superiores de una presa en lugar de la presa completa, ya que los dos pies superiores contendrían más agua que el promedio y ¡sería más barato de construir!

La mayor parte de la optimización no lineal utiliza alguna forma de enfoque de gradiente en el que se elige un conjunto de valores de variables de decisión factibles y luego estos se alteran para mejorar la función objetivo y seguir siendo factibles. Solver en el programa de hojas de cálculo EXCEL utiliza este tipo de técnica. En muchos casos, es útil utilizar múltiples puntos de partida para reducir la posibilidad de terminar con un óptimo local.
Como ejemplo de optimización no lineal útil para la gestión de infraestructura, podemos sugerir un problema de flujo que se puede aplicar al flujo de tráfico en redes viales o al flujo de agua en redes de tuberías. Los costos de los trabajos de mantenimiento o rehabilitación se pueden estimar comparando los costos de flujo antes y durante la interrupción de la red. El mismo enfoque se puede utilizar para evaluar nuevas capacidades o procedimientos operativos. El problema aparece en Hendrickson (1984).

Suponemos que existe una red con un conjunto de nodos (intersecciones) N y arcos (enlaces de tubería o calles) A. Hay un costo de flujo en enlace\(ij\)\(f(y)\) que se supone que está aumentando monótonamente como en la Figura 5.4.2. Esta suposición es físicamente realista y asegura la convexidad para el espacio de solución de problemas haciendo que una solución sea más fácil.

El problema general del flujo de equilibrio es:

\ [P1:\ texto {minimizar}\ suma_ {(i, j)\ en A}\ int_ {0} ^ {x_ {i j}} f_ {i j} (y) d y\]

sujeto a:

\ [\ suma_ {(i, k)\ en A} x_ {i k} -\ suma_ {(k, j)\ en A} x_ {k j} =q_ {k} \ texto {para todos} k\ en N\]

\[x_{i, j}>0 \text { for all }(i, j) \in A\]

Dónde\(x_{ij}\) está el flujo en el enlace\(ij\) y\(qk\) es la entrada o salida neta en el nodo k El objetivo es minimizar la 'impedancia' del flujo en cada enlace, y las restricciones conservan el flujo a través de los nodos y requieren que todos los flujos sean positivos.

Para aplicaciones hidráulicas de tuberías, el flujo sería flujo de fluido medido en volumen por unidad de tiempo. La función de impedancia sería pérdida de cabeza (o ganancia) por unidad de distancia. La función de impedancia debe incluir diferencias de elevación de nodos así como pérdida de fricción de tubería (a través de una función como la función Hazen-Williams\(f(x) = k*x^m\).

Para las redes de tráfico, se debe utilizar una forma ligeramente más complicada del problema para realizar un seguimiento de los flujos entre orígenes y destinos particulares. La impedancia es el tiempo de viaje y se relaciona con el flujo total en el enlace\(ij\). El problema P2 a continuación muestra el problema del flujo de tráfico con la notación rs para el tráfico del nodo r al nodo s, una restricción para asegurar la conservación del flujo a través de los nodos de intersección y una restricción para agregar los flujos de origen-destino individuales para cada enlace.

\ [\ text {P2: minimizar}\ suma_ {(i, j)\ en A}\ int_ {0} ^ {x_ {i j}} f_ {i j} (y) d y\]

\ [\ suma_ {s\ en A}\ izquierda [\ suma_ {(i, k)\ en A} x_ {i k} ^ {r s} -\ suma_ {(k, j)\ en A} x_ {k j} ^ {r s}\ derecha] =q_ {r k}\ texto {para todos } k\ en N, r\ en N\]

\ [\ sum_ {s\ in N} ^ {r\ in N} x_ {i j} ^ {r s} =x_ {i j}\ texto {para todos } (i, j)\ en A\]

Para la aplicación de flujo de tráfico, el conjunto de flujos de solución representa una 'solución de equilibrio de usuario' en la que el tiempo de viaje en cada ruta utilizada entre el origen r y el destino s tiene el mismo tiempo de viaje general (si no, los viajeros cambiarían la ruta y reducirían su tiempo de viaje). Los caminos no utilizados entre el origen r y el destino s tendrían mayor tiempo de viaje y serían poco atractivos.

Como se señaló anteriormente, el problema P2 podría resolverse para obtener tiempos de viaje y flujos en una red existente. Después de que la red se altere debido a la construcción, se podría modelar el tiempo de viaje de equilibrio después de la alteración. Señaló que en este sencillo formulario de solicitud, el flujo origen-destino no cambiaría. Un análisis más elaborado podría relajar esta suposición para permitir nuevos destinos u otras opciones de viaje.

Existen algoritmos de solución de gradiente para los problemas P1 y P2 que pueden acomodar fácilmente miles de nodos y enlaces. Autor, (Hendrickson, 1984) presenta un algoritmo de solución así como aplicaciones adicionales del formulario modelo para proyectar la programación de tareas y el análisis estructural. Existen numerosos programas de software para este tipo de formulación de modelos.