Автомобільні затори: коли раціональність веде до колапсу

Навчання 26 серпня 2022 Перегляди: 59

Введення

Коли ми тільки починали писати цю статтю, нам на очі попався прекрасний слоган в одній соціальній рекламі: «Ви не застрягли в заторі. Ви і є пробка «. Мало хто з водіїв, що стоять у заторі, замислюється про те, що він сам стає причиною затримки тих людей, хто їде слідом за ним, а навіть якщо і замислюється, то не надає цьому великого значення. При цьому, підрізаючи чергову машину, водії скаржаться на те, як мало будується доріг.

Ще в XVIII столітті британський економіст Адам Сміт посіяв в умах вчених і громадських діячів захоплюючий образ спільноти незалежних економічних агентів — споживачів і виробників, кожен з яких, діючи в своїх інтересах, в результаті створює ефективне громадське виробництво. Можна сказати, що це було першою редакцією гасла «Анархія — мати порядку!». Однак ще раніше інші, не менш видатні, уми людства сумно відзначили сумний виняток з цього правила — те, що еколог Хардін вдало охрестив «трагедією спільної власності».

Це означає наступне. Якщо деякий ресурс знаходиться у спільній власності і для його використання немає ніяких обмежень, то він буде піддаватися надмірній експлуатації і зникне. Стелерова корова або Аральське море, яке майже зникло, тому наочні приклади, і цей сумний список можна продовжити. Економісти описують «трагедію спільної власності» як такий варіант суспільного устрою, коли з точки зору окремого споживача вигоди від споживання ресурсу дістаються йому одному, а негативні наслідки діляться на всіх. У сучасному світі одним з таких ресурсів є автомобільні дороги, а «сині мигалки» — найбільш яскраве тому свідчення, посилене узурпованим переважним правом деяких користувачів на цей ресурс. Але і незалежно від наявності або відсутності «мигалки» кожен новий автомобіль на дорозі приносить своєму власнику певну користь або задоволення, а негативні наслідки — зростаюча щільність автомобілів, уповільнення руху, затори і затори — діляться на всіх. Для принципового виходу з цієї ситуації потрібна ціла система заходів, які примирили б егоїстичну поведінку водіїв і суспільну користь, але це занадто велика тема, для знайомства з якою можна порекомендувати загальнодоступну книгу В. Вучика «Транспорт у містах, зручних для життя» («Transportation for Livable Cities»). Але в будь-якому випадку, коли вчені збираються щось радити, то вони насамперед вивчають явище і визначають, як на нього вплинуть різні впливи. У даному випадку найбільш видимим і засмучувальним є вуличні пробки. Так що ж таке пробки і як з ними боротися?

Звідки беруться пробки

Взагалі кажучи, перш потрібно зрозуміти, що таке пробка. Деякі водії говорять про затор, коли їм доводиться їхати зі швидкістю 20 км/год через щільний рух, замість бажаних 100 км/год. Інші ж мають на увазі під затором майже глухий затор. Обидва ці випадки мають спільну природу — занадто багато автомобілістів вирішили використовувати одну і ту ж дорогу. Все впирається в те, що розуміється під «занадто багато».

Можна було б вказувати на те, що у кожної дороги від перехрестя до перехрестя є цілком конкретні ширина і довжина і там «фізично» не може поміститися занадто багато автомобілів. Але цього аргументу недостатньо, адже важлива ще швидкість руху. Якби водії могли практично без зазорів між машинами їхати на швидкості 1000 км/год, то пропускна здатність будь-якої дороги була б майже необмеженою. Відповідь у тому, що рух на дорозі визначається тим, які рішення приймають водії. Для більшості з них «некомфортно» їхати на швидкості 100 км/год в режимі «бампер до бампера» — занадто великі ризики пошкодити автомобіль або потрапити у велику аварію. Наприклад, у США ще в школах водіння вчать «правилу 3 секунд» — підтримуйте між собою і попереду відстань, яку ви на цій швидкості проїдете за 3 секунди. У негоду цей час рекомендують втрачати. Годі й говорити про те, що це правило написано кров’ю тих водіїв, які його не виконували… Цікаво, що якщо при цьому знехтувати власними розмірами автомобілів, то їх потік, тобто кількість автомобілів, що перетинають за одиницю часу деяку контрольну лінію, не залежить від швидкості і становить 1200 автомобілів на годину на одну смугу руху, що вважається нормативною пропускною здатністю дороги. Якщо врахувати власні розміри автомобіля, то пропускна здатність істотно зменшується, особливо при малих швидкостях. Але це випливає з найпростіших моделей руху автомобілів, в реальності потрібно враховувати масу інших факторів, одне перерахування яких може зайняти не одну сторінку. Тому обмежимося добре встановленим експериментальним фактом — середня швидкість руху на дорозі залежить від щільності автомобілів, тобто їх кількості на одиницю довжини дороги, в якості якої зазвичай розглядається кілометр. При цьому чим більша щільність, тим нижче швидкість. У найпростішому випадку передбачається лінійна залежність між щільністю R і швидкістю:

R() = –a + R₀,

де a — деяка константа.

Ця модель була запропонована американським інженером-транспортником Брюсом Гріншилдсом (Bruce Greenshields) в 1933 році і досі широко використовується в системах моделювання дорожнього руху! Нещодавно на її честь був навіть проведений міжнародний симпозіум, який відзначив 75-річчя першої публікації. Причина такої уваги до цієї моделі полягає в тому, що вона вперше ввела поняття фундаментальної діаграми потік-швидкості продемонструвала наявність максимального потоку. Дійсно, якщо ми визначимо потік Q () автомобілів в одиницю часу як твір R, то

Q() = –a² + R₀,

і графік цієї квадратичної функції (рис. 1) має максимум в точці = R0_/ (2a).

Ріс. 1

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

Ріс. 2

Уявіть собі перехрестя 1 (рис. 2) і два маршрути, за якими можна доїхати до пункту призначення у вершині 3. Причому дорога (1,3) — «коротка», а шлях через вершину 2 — довгий об’їзд. Нехай дорога (1,3) буде двосмуговою. У центрі дороги (1,3) одна зі смуг закрита не ремонт. У початковий момент часу, коли обидві дороги порожні (наприклад, о 5 ранку), всі водії, які бажають доїхати з 1 в 3, скористаються дорогою (1,3). Якщо одна смуга може обслужити 1500 авт ./год, а на дорогу в якийсь момент почне надходити потік в 2500 авт ./год, постане питання — куди подінуться 1000 авт ./год? Звичайно, встануть прямо перед вузьким місцем. Більш того, через необхідність перебудовуватися, по працюючій смузі потік буде нижче 1500 авт ./год. З плином часу пробка буде рости. Питання номер два — коли пробка рости перестане? Логіка і закони збереження нам підказують, що це станеться, якщо кількість в’їжджаючих на дорогу водіїв зрівняється з кількістю виїжджаючих, тобто стане приблизно 1500 авт ./год. Але куди подінуться зайві 1000 авт ./год, які раніше використовували цю дорогу в своєму маршруті? Очевидно, почнуть (через затор) використовувати об’їзд. Перемикання на об’їзну дорогу відбудеться рівно в той момент, коли водіям буде байдуже, який з маршрутів (короткий або об’їзний) використовувати. Але ж якби об’їзд використовувався з самого початку, пробки б не виникло! Водіїв можна зрозуміти, кому ж захочеться їхати в далекий об’їзд, якщо поруч коротка дорога, і нехай вона працює на межі, але вже ми як-небудь прорвемося (а за нами хоч потоп!). Ось так і починається пробка.

Модель

Надалі ми розглянемо модель для опису поведінки водіїв і транспортної системи в цілому на конкретному прикладі. Мережа, зображена на малюнку 3, зазвичай використовується для ілюстрації так званого парадоксу Браєса.

Рис. 3

На час забудемо про малюнок 3, б (він знадобиться нам пізніше) і будемо працювати тільки з графом на малюнку 3, а.

Міська транспортна мережа задається зваженим орієнтованим графом Г (V, E, T), або, кажучи простіше, дороги представляються ребрами графа, вони мають заданий напрямок (тому граф спрямований, тобто орієнтований), перехрестя — вершини графа, при цьому кожному ребру відповідає певний час, який водій повинен витратити на проїзд. Цей час і є «вагою» ребра (тому граф виважений). Тут V — безліч вершин графа (безліч перехресть), на малюнку 3, а вони позначені цифрами 1, 2, 3 і 4, а E — безліч ребер графа (дороги), на малюнку 3, а дороги позначені буквами a, b, c і d. Кожній дорозі відповідає своя «вага», яка, взагалі кажучи, залежить від того, скільки людей цю дорогу використовує. Зрозуміло, що чим більше машин використовує якусь конкретну дорогу, тим більше затор і тим більше часу буде потрібно на проїзд. «Вага» дороги описує залежність часу на проїзд по ребру від того, скільки автомобілів його використовує. Позначимо функції терезів доріг чере_з fa_, fb_, fc _і fd для ребер a, b, c і dсоответственно.

У нашому модельному прикладі ми будемо вважати, що у всіх ребер функції терезів лінійні, зокрема, f_a (t) = _fd (t) = 50 + t, fb (t) ₌ fc (t) = 10t. Ще раз пояснюємо, що, наприклад, запис fd (t) = 50 + t слід розуміти приблизно так: якщо по дорозі d їде t водіїв в одиницю часу, то проїзд по ребру d займе 50 + t хвилин.

Припустимо, що водії їдуть з вершини 1 у вершину 4, причому в одиницю часу з 1 в 4 прямує одне і те ж число водіїв. У нашому прикладі воно дорівнює 6. При цьому, як легко показати, з 1 в 4 можна потрапити по одному з двох маршрутів: 1-а-3-c-4 і 1-b-2-d-4. У нашій грубій моделі водій не витрачатиме час на проїзд через перехрестя. Тоді час у дорозі для маршрутів буде визначатися як сума терезів, що входять в маршрут ребер. Наприклад, для маршруту 1-a-3-c-4 час в дорозі складе f_a + f_c, а для маршруту 1-b-2-d-4 час в дорозі складе f_b + f_d. Позначимо через x транспортний потік на маршруті 1-a-3-c-4, а через y — транспортний потік на маршруті 1-b-2-d-4. Під транспортним потоком на маршруті мається на увазі кількість водіїв, які виїжджають з 1 в 4 за цим маршрутом в одиницю часу. При цьому, очевидно, x + y = 6.

Легко показати, що для графа на малюнку 3, а потік на ребрах a і c дорівнює x, а потік за ребрами b і d дорівнює y. Відповідно, час у дорозі для маршруту 1—a-3—c-4 дорівнюватиме _fa (x) + fc (x), а для маршруту 1-b—2-d-4 час у дорозі дорівнюватиме fb (y) + fd (y).

Водії, вибираючи свій маршрут прямування, поводяться егоїстично. У нашому випадку це означає, що вони вибирають маршрут з найменшими очікуваними витратами. Але чим більше водіїв вибирають той чи інший маршрут, тим вище витрати на даному маршруті. З іншого боку, ми зафіксували загальне число машин, що виїжджають з вершини 1 в вершину 4 в одиницю часу, а значить, якщо якимось маршрутом стала користуватися більша кількість автомобілістів, тобто якийсь маршрут, який став використовуватися менше. Ймовірно, що на цьому другому маршруті витрати, навпаки, впадуть. Таким чином, перший, раніше привабливий, маршрут стає більш обтяжливим, а альтернативні маршрути при цьому стають більш привабливими. Це мотивує водіїв знову змінити свій маршрут. Але така «базіка» відбувається не завжди.

Введемо поняття рівноваги (Неша-Вардропа). Назвемо розподіл потоків за маршрутами рівноважними, якщо час проїзду за всіма використовуваними маршрутами однаково і не перевершує часу в дорозі на невикористовуваних ^{маршрутах.}

Сенс цього твердження дуже простий: рівноважний розподіл потоків за маршрутами — це коли водії так обирають свої маршрути, що нікому окремо не вигідно змінювати свій вибір. Якби, наприклад, для графа на малюнку 3, а реалізувалася рівновага і ми б розглянули довільного водія, що використовує маршрут 1-b-2-d-4, то ми могли б сказати, що цьому водієві не вигідно змінювати свій маршрут.

Для нашого прикладу знайти рівновагу дуже просто. Всього можливі три варіанти:

1) x = 6,  y = 0,  f_a(6) + f_c(6) ≤ f_b(0) + f_d(0);

    2) x = 0,  y = 6,  f_a(0) + f_c(0) ≥ f_b(6) + f_d(6);

    3) x + y = 6,  x > 0,  y > 0,  f_a(x) + f_c(x) = f_b(y) + f_d(y).

Зауважимо, що у нашому випадку f_a (t) + _fc (t) = 11t + 50 ₌ fb (t) + fd (t). Звідси маємо fa (₀) + fc ₍0) = fb (0) + fd (0) = 50 і _fa (6) + fc (6) ₌ fb (6) + fd (6) = 116. Отже, варіанти 1) і 2) відпадають. Для того щоб знайти рівноважний розподіл потоків, потрібно вирішити систему рівнянь 3):

Легко довести, що отримане рішення задовольняє умовами рівноваги. Дійсно, час у дорозі на використовуваних маршрутах збігається і дорівнює 11· 3 + 50 = 83, а невикористовуваних маршрутів просто немає.

Резюмуючи, техніка пошуку рівноваг наступна:

1. Всі маршрути діляться на використовувані і невикористовувані в рівновазі. Виходить величезна кількість варіантів поділів.
2. Вибирається конкретний поділ.
3. Шукається такий розподіл сумарного потоку за використовуваними маршрутами, щоб час у дорозі на всіх використовуваних маршрутах був однаковим. Якщо такого не існує, поділ «бракується». Якщо є, переходимо до наступного пункту.
4. Перевіряється, що для всіх невикористовуваних маршрутів час у дорозі не нижче, ніж на використовуваних.

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

Приклад вище ілюструє той факт, що в рівновазі жоден з водіїв не може виграти, змінивши свій маршрут. Тому, якщо система знаходиться в рівновазі, то вона в цій рівновазі і залишиться (взагалі кажучи, ми повинні були б вимагати стійкість рівноваги, але зараз не хотілося б говорити про це). Ця рівновага носить ім’я Неша і Вардропа (про це вже згадувалося трохи вище) з наступних причин. Якщо розглянути гру, в якій водії є гравцями, маршрути — стратегіями (іншими словами, можливими діями гравців), а витрати, що відповідають маршрутам і взяті зі знаком «мінус», — виграшами, то виписане визначення буде визначенням рівноваги Неша в побудованій грі. Власне, існування рівноваги гарантується теоремою Неша, з якою можна познайомитися в будь-якому підручнику з теорії ігор. У ній, загалом, і постулюється існування рівноваги в іграх, подібних до розглянутої нами. Вардроп же запропонував два принципи, що описують можливу поведінку водіїв. Перший з них передбачає, що всі водії діють опортуністично і вважають власний вплив нікчемним. Другий принцип, навпаки, говорить, що водії можуть діяти узгоджено з метою мінімізувати суспільні витрати. Власне цими двома принципами і їх комбінаціями, на думку Вардропа, і описуються всі можливі і суттєві для аналізу варіанти поведінки.

Парадокс Браєса і неефективні дороги

Німецький математик Дітхард Браєс увійшов в історію як автор найпростішого прикладу, який демонструє, до чого призводить егоїстична поведінка.

Браєс розглянув найпростішу транспортну мережу, що з’єднує двома незаперечними маршрутами початковий і кінцевий пункти 1 і 4 (див. рис. 3).

Ми вже шукали рівновагу для графа на малюнку 3, а й отримали, що x = y = 3,

f_a(3) + f_c(3) = f_b(3) + f_d(3) = 83.

Однак Браєс на цьому не зупинився і розглянув модифікацію первісної мережі, де побудована додаткова дорога, що безпосередньо з’єднує проміжні пункти (ризи.3, б), яку ми назвемо e. Дорога вийшла пристойної якості і відносно коротка, так що час проїзду по ній визначається формулою

f_e(t) = t + 10.

Зауважимо, що у водіїв, які їдуть з 1 в 4, з’явився новий маршрут 1-b-2-e-3-c-4. Якою буде нова рівновага і яким буде час проїзду?

Можна собі уявити, що в перший час, поки ця дорога ще мало кому відома, потік по ній дорівнює 0 і, отже, у того водія з нижнього маршруту, який першим згорнув на неї, час проїзду складе

f_b(3) + f_e(0) + f_c(3) = 30 + 10 + 30 = 70.

Це явно менше 83 хвилин. Ура, згортаємо! Але що відбувається далі? За нами згортають нові машини, водії яких, мабуть, провели ті ж самі розрахунки! Та ж сама логіка, яка застосовувалася і для вихідної мережі, повинна бути застосована і в цьому випадку — потоки перерозподіляться так, що час проїзду по кожному маршруту буде однаково і нікому з водіїв не буде сенсу змінювати маршрут. Ми отримаємо нову рівновагу.

Діючи за нашою схемою, ми повинні визначити можливі поділи маршрутів на використовувані і невикористані. Всього у нас буде 7 варіантів:

1-a-3-c-4	1-b-2-d-4	1-b-2-e-3-c-4
+	0	0
0	+	0
0	0	+
+	+	0
+	0	+
0	+	+
+	+	+

Нехай нам відомо, що рівновага виходить у випадку, коли всі маршрути використовуються. Позначимо через z транспортний потік на новому маршруті 1-b-2-e-3-c-4. Вирішимо систему рівнянь, яка виходить з умови рівноваги:

У першому рівнянні ми написали, що часи проїзду в рівновазі для маршрутів 1-a-3-c-4 і 1-b-2-d-4 рівні. У другому рівнянні ми записали ту ж вимогу для маршрутів 1-a-3-c-4 і 1-b-2-e-3-c-4.

Перетворюємо систему, підставивши замість функцій їх значення:

Вирішуючи систему, отримуємо x = 2, нові машини y = 2, нові машини z = 2, тобто у рівновазі сумарний потік розподілиться за маршрутами в рівних частках x = y = z = 2, а час у дорозі для всіх маршрутів складе

f_a(2) + f_c(4) = 50 + 2 + 40 = 92.

Зауваження. Те, що тут і раніше в рівновазі потоки за маршрутами виявилися рівні між собою, — чиста випадковість і результат підбору таких функцій терезів, щоб «вийшло красиво». У рівновазі у маршрутів рівні часи в дорозі (!), а не потоки.

Що чудово (з дослідницької точки зору, з практичної ж точки зору це жахливо), час у дорозі після додавання нового ребра для всіх водіїв зріс. Це збільшення є наслідком того, що ми дозволили кожному водієві чинити егоїстично, вибираючи маршрути так, щоб нікому не було вигідно відхилитися від рівноваги.

Описаний вище парадокс Браєса зростає з неефективності рівноваги Неша-Вардропа з точки зору суспільного блага. Говорячи простіше, через егоїстичність водіїв сумарні витрати всіх водіїв в рівновазі вище, ніж взагалі могли б бути при деякому іншому розподілі.

Визначимо тепер поняття соціального оптимуму. Соціальний оптимум — це такий розподіл потоків за маршрутами, при якому сумарний час в дорозі у всіх водіїв мінімально.

Тим самим, для того щоб знайти соціальний оптимум в нашій системі, нам потрібно було б вирішити наступну задачу — знайти

min (x·(f_a(x) + f_c(x + z)) + y·(f_b(y + z) + f_d(y)) + z·(f_b(y + z) + f_c(x + z) + f_e(z)))

за умови x + y + z = 6, де x, y, z неотрицательны, тобто знайти

min (50·x + 11·x² + 20·xz + 50·y + 11·y² + 20·yz + 21·z² + 10·z).

Виразивши z, зводимо завдання до пошуку

min (816 – 92·x – 92·y + 2·xy + 12·x² + 12·y²).

Можна довести, що точкою мінімуму за умови неотрицательности змінних буде трійка (3, 3, 0).

Всі описані проблеми з заторами виникають через те, що соціальний оптимум зазвичай (як у нашому випадку) не є рівновагою.

Звичайно, можливі ситуації, коли рівновага Неша-Вардропа є соціальним оптимумом, але в загальному випадку це не так.

Зауважимо, що в соціальному оптимумі ребро e не використовується. Воно неефективне. Егоїзм водіїв призводить до його використання. Можна показати, що це вірно для будь-яких неефективних ребер (тобто таких, від чийого видалення хтось із водіїв виграє, але ніхто не програє). Їх поява є наслідком неефективності рівноваги.

Отже, ми показали, що через егоїзм водіїв можуть виникати неефективні ребра та інші проблеми. Невелика заслуга. Питання тільки в тому, наскільки (!) це погано.

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

Вплив егоїстичності водіїв можна оцінити за різницею між часом у дорозі в реалізованому розподілі (тобто рівновагою) і часом у дорозі при оптимальній поведінці водіїв (тобто соціальному оптимумі). У нашому випадку ця величина дорівнює 92 — 83 = 9.

Багато це чи мало? Відповідь залежить від графа і завантажень. Традиційно мірою неефективності є так звана «ціна анархії» — ставлення часу в дорозі в гіршій рівновазі до часу в дорозі при оптимальному розподілі потоків. У нашому випадку «ціна анархії» дорівнює ^ 1,1084.

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

Платні дороги

Чудова властивість неефективних ребер полягає в тому, що з ними можна ефективно боротися. Дійсно, достатньо заборонити проїзд по неефективному ребру, як транспортна ситуація покращиться. Поставив кордон — і справу зроблено!

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

Щойно ми сказали «поставив кордон — і справу зроблено». Але жоден чиновник ніколи не поставить кордон. Як же так: спочатку за 29 мільярдів побудуємо дорогу, а потім її закривати? Нонсенс. Вже краще нехай змиє (як це сталося у Владивостоці в 2012 році). Тим більше, ребро є неефективним тільки при певних завантаженнях. Можливо, ситуація і завантаження мережі з часом зміняться і наявність ребра (раніше неефективного) буде корисним. Було б неприємно закрити дорогу, дати їй зруйнуватися, а через десять років будувати на тому ж місці нову, так як вона знову стала потрібна.

Куди більш прагматичним буде рішення зробити проїзд за неефективними ребрами платним. З одного боку, встановивши дуже велику плату, ми можемо звести потік по неефективному ребру до мінімуму. З іншого боку, ми дозволяємо планувальникам зберегти обличчя. Дорога ж працює і справна — їдь на здоров’я! Ну і нарешті, якщо раптом ситуація зміниться так, що ребро знову стане ефективним, то плату можна буде знизити або зовсім прибрати.

З точки зору математики, це буде виглядати так. Призначення плати за проїзд по ребру е в розмірі ^ відповідає заміні f_e (x) на f_e (x) + ^. Це призводить, взагалі кажучи, до зміщення рівноваги. Правильне призначення плати робить можливим зміну рівноваги в сприятливий бік. Продемонструємо це на прикладі.

Призначимо плату за проїзд по ребру e графа на малюнку 3, б у розмірі 6,5. Вирішуючи заново систему, ми отримаємо, що новою рівновагою буде крапка. Витрати за проїзд водіїв знизилися з 92 до 87,5. Чудово! Давайте збільшимо плату в 1,5 рази до 9,75. Повторюючи процедуру, знайдемо нову рівновагу. Витрати знову впадуть до 85,25. Згадуючи, що мінімальні витрати за проїзд, які взагалі можливі (для цього графа і завантажень), складуть 83, можна сказати, що ми вже зовсім близькі до мети. Дії