5.4: Нелінійна оптимізація

Як обговорювалося раніше, більшість задач оптимізації управління інфраструктурою формулюються як завдання лінійного програмування . Однак в деяких випадках може знадобитися нелінійна оптимізація. Загальна форма задачі нелінійної оптимізації:

\ [\ text {Згорнути або збільшити} f (x)\ text {підлягає } g_ {i} (x)\ leq 0\ текст {і} h_ {j} (x) =0\]

Де\(x\) є вектор змінних рішень,\(f(x)\) є нелінійною цільовою функцією,\(g_i(x)\) і\(h_j(x)\) є множинами обмежень, які можуть бути лінійними або нелінійними.

Одним з джерел нелінійності є економія масштабу при виконанні завдання технічного обслуговування або реабілітації. Це може статися, якщо існують фіксовані витрати на мобілізацію для виконання завдання, які потім розподіляються на обсяг роботи. Такі компоненти, як резервуари, також мають економію масштабу, оскільки їх обсяг зростає швидше, ніж (дорога) поверхня резервуара, оскільки розмір резервуара збільшується. Рисунок 5.4.1 ілюструє економію масштабу на двох пов'язаних графіках. У верхньому графіку вартість одиниці робіт знижується в міру збільшення обсягу робіт. На нижньому графіку загальна вартість йде вгору повільніше, ніж збільшення обсягу робіт.

Малюнок\(\PageIndex{1}\): Ілюстрація економії масштабу щодо обсягу роботи.

Ще одне джерело нелінійності для управління інфраструктурою походить від ефектів потоку. Наприклад, затори дорожнього руху нелінійні в тому, що невелике збільшення трафіку може призвести до великих обсягів затримки. При утриманні проїжджої частини, блокуючи смуги руху, пропускна здатність мережі проїжджої частини зменшується, а затори можуть значно збільшитися. Малюнок 5.4.2 ілюструє нелінійне збільшення середнього часу в дорозі.

Малюнок\(\PageIndex{2}\): Ілюстрація нелінійних ефектів часу подорожі щодо обсягів транспортного засобу.

Нелінійна оптимізація має деякі підводні камені. По-перше, отримані рішення можуть бути не глобальними оптимальними, а лише локальними максимальними або мінімальними значеннями цільової функції. По-друге, конкретні склади можуть призвести до фізично неможливих результатів. Наприклад, у випадку економії масштабу, нелінійна оптимізація може побажати побудувати верхні кілька футів греблі, а не всю греблю, оскільки верхні два фути утримували б більше води, ніж середнє, і було б дешевше будувати!

Більшість нелінійних оптимізацій використовує певну форму градієнтного підходу, в якому вибирається набір можливих значень змінних рішень, а потім вони змінюються для поліпшення цільової функції і все ще залишаються здійсненними. Розв'язувач в програмі електронних таблиць EXCEL використовує цей тип техніки. У багатьох випадках корисно використовувати кілька відправних точок, щоб зменшити ймовірність отримати локальний оптимум.
Як приклад нелінійної оптимізації, корисної для управління інфраструктурою, можна запропонувати проблему потоку, яка може бути застосована до транспортних потоків у дорожніх мережах або потоку води в трубопровідних мережах. Витрати на технічне обслуговування або реабілітаційні роботи можна оцінити, порівнявши витрати на потік до та під час зриву мережі. Цей же підхід може бути використаний для оцінки нових потужностей або робочих процедур. Проблема з'являється в Хендріксоні (1984).

Припустимо, що існує мережа з набором вузлів (перетинів) N і дуг (трубних зв'язків або вулиць). Існує вартість потоку на ланці,\(ij\)\(f(y)\) яка, як передбачається, монотонно збільшується, як на рис. 5.4.2. Це припущення є фізично реалістичним і забезпечує опуклість для простору вирішення проблем, що полегшує рішення.

Загальна проблема рівноважного перебігу така:

\ [P1:\ текст {мінімізувати}\ sum_ {(i, j)\ in A}\ int_ {0} ^ {x_ {i j}} f_ {i j} (y) d y\]

за умови:

\ [\ sum_ {(i, k)\ in A} x_ {i k} -\ sum_ {(k, j)\ в А} x_ {k j} =q_ {k} \ text {для всіх} k\ in N\]

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

Де\(x_{ij}\) є потік на зв'язку\(ij\) і\(qk\) чистий приплив або відтік у вузлі k Мета полягає в тому, щоб мінімізувати «імпеданс» потоку на кожній ланці, а обмеження зберігають потік через вузли і вимагають, щоб всі потоки були позитивними.

Для гідравлічних застосувань трубопроводів потік буде витратою рідини , виміряним в обсязі за одиницю часу. Функцією імпедансу буде втрата напору (або посилення) на одиницю відстані. Функція імпедансу повинна включати перепади висот вузлів, а також втрати на тертя труби (через таку функцію, як функція Хейзена-Вільямса \(f(x) = k*x^m\).

Для мереж трафіку слід використовувати дещо складнішу форму проблеми для відстеження потоків між конкретними джерелами та пунктами призначення. Імпеданс - це час у дорозі і відноситься до загального потоку по посиланню\(ij\). Задача P2 нижче показує проблему потоку трафіку з позначенням rs для трафіку від вузла r до вузла s, обмеженням для забезпечення збереження потоку через вузли перетину та обмеженням для агрегування окремих потоків походження та призначення для кожного посилання.

\ [\ текст {P2: мінімізувати}\ сума_ {(i, j)\ in A}\ int_ {0} ^ {x_ {i j}} f_ {i j} (y) d y\]

\ [\ sum_ {s\ in A}\ ліворуч [\ sum_ {(i, k)\ в A} x_ {i k} ^ {r s} -\ sum_ {(k, j)\ в A} x_ {k j} ^ {r s}\ право] =q_ {r k}\ текст {для всіх } k\ в N, r\ в N\]

\ [\ sum_ {s\ in N} ^ {r\ in N} x_ {i j} ^ {r s} =x_ {i j}\ текст {для всіх } (i, j)\ в А\]

Для програми трафіку набір потоків рішення являє собою «рішення рівноваги користувача», в якому час у дорозі на кожному шляху, що використовується між початком r та пунктом призначення s, має однаковий загальний час подорожі (якщо ні, мандрівники змінюватимуть шлях та зменшуватимуть час у дорозі). Шляхи, які не використовуються між початком r та пунктом призначення s, мали б більший час у дорозі і були б непривабливими.

Як зазначалося раніше, проблему Р2 можна було б вирішити для отримання часу в дорозі і потоків по існуючій мережі. Після зміни мережі через будівництво, час подорожі рівноваги після зміни може бути змодельований. Зазначено, що в цій простій формі заявки потік походження-призначення не зміниться. Більш детальний аналіз може послабити це припущення, щоб дозволити нові напрямки або інші варіанти подорожей.

Алгоритми градієнтного рішення існують для задач P1 та P2, які можуть легко вмістити тисячі вузлів та зв'язків. Автор (Hendrickson, 1984) представляє один алгоритм розв'язку, а також додаткові застосування форми моделі для планування завдань проекту та структурного аналізу. Для цього типу формулювання моделей існують численні програмні програми.