Przeskocz do treści

Delta mi!

Loading

Kłopoty z komunikacją

Wojciech Czerwiński

o artykule ...

  • Publikacja w Delcie: sierpień 2015
  • Publikacja elektroniczna: 31 lipca 2015
  • Autor: Wojciech Czerwiński
    Afiliacja: adiunkt, Instytut Informatyki, Uniwersytet Warszawski

"W takich Niemczech to mają dobre drogi, a w Polsce... No cóż, średni czas potrzebny na przejazd np. z Warszawy do Rzeszowa jest stanowczo za długi." Wielu Czytelników zapewne zgodzi się z tym stwierdzeniem lub doda, że jest zbyt eufemistyczne, inni zaś powiedzą, że przecież nie jest znowu aż tak źle. Z kolei ktoś może konstruktywnie zaproponować, żeby zamiast zastanawiać się, jak jest, zastanowić się, co zrobić, by było lepiej.

"Jak to co? Nic prostszego - trzeba zacząć budować nowe drogi!" - chciałoby się odpowiedzieć. Wydaje się, że to naturalne rozwiązanie, które powinno poprawić naszą sytuację. Spójrzmy jednak na problem od strony matematycznej, by przekonać się, że nie zawsze musi to być prawda.

obrazek

Rozważmy następujący, hipotetyczny Problem Kierowcy Tira. Powiedzmy, że z Warszawy do Rzeszowa może on jechać na dwa sposoby: albo przez Lublin, albo przez Radom. Droga z Warszawy do Lublina jest szeroka, ale długa; jedzie się nią zawsze 100 minut. Natomiast droga z Warszawy do Radomia jest krótka, ale wąska, więc czas przejazdu istotnie zależy od natężenia ruchu na tej drodze. Na nasze potrzeby przypuśćmy (dość nierealistycznie), że jeśli jedzie nią jednocześnie n tirów, to czas przejazdu dla każdego z nich wynosi n minut. Analogiczna sytuacja ma miejsce dla dojazdu do Rzeszowa. Tyle że teraz podróż z Radomia do Rzeszowa zawsze trwa 100 minut, a z Lublina do Rzeszowa |n minut, jeśli drogą jedzie n tirów. Przypuśćmy teraz, że codziennie z Warszawy do Rzeszowa jedzie 100 tirów. Jeśli wszystkie jechałyby przez Lublin, to czas przejazdu dla każdego z nich wyniósłby 100 + n minut, gdzie n = 100, czyli w sumie 200 minut. Analogicznie, gdyby wszystkie tiry pojechały przez Radom. Jednak gdyby połowa tirów pojechała przez Radom, a druga połowa przez Lublin, to czas przejazdu dla każdego z nich zmniejszyłby się do 150 minut, i łatwo wykazać, że byłoby to optymalne rozwiązanie. Powinno więc powstać Stowarzyszenie Kierowców, które dbałoby o to, żeby codziennie dokładnie połowa kierowców jechała przez Radom, a druga połowa przez Lublin.

obrazek

Jako że przewóz towarów z Warszawy do Rzeszowa okazał się jednym z filarów naszego przemysłu, GDDKiA postanowiła poprawić sytuację kierowców. W tym celu pomiędzy Radomiem a Lublinem zbudowana została droga (niesamowicie) szybkiego ruchu, która, dzięki wykorzystaniu najnowszych technologii, oferuje natychmiastowy przejazd w czasie 0 minut. Niestety, projekt ten nie został skonsultowany z żadnymi ekspertami-matematykami, co okazało się fatalne w skutkach.

Zastanówmy się, jak wybudowanie nowej drogi wpłynęło na sytuację kierowców. Ponieważ przejazd pomiędzy Radomiem a Lublinem jest natychmiastowy, to drogę z Warszawy do Rzeszowa można w praktyce podzielić na dwa odcinki: z Warszawy do Radomio-Lublina oraz z Radomio-Lublina do Rzeszowa. Jasne jest, że na pierwszym odcinku bardziej opłaca się jechać drogą, która zajmuje |n minut, niż tą, która zajmuje 100 minut, bo zawsze n ⩽100. Na drugim odcinku jest tak samo. A zatem najprawdopodobniej wszyscy kierowcy, nie zwracając uwagi na zalecenia Stowarzyszenia Kierowców, pojadą trasą Warszawa-Radom-Lublin-Rzeszów, co zajmie każdemu z nich |n+ 0 +n = 200 minut! Co więcej, żaden z kierowców nie będzie żałował swojej decyzji, będzie bowiem myślał tak: "gdybym pojechał z Warszawy na Lublin, a nie na Radom, to zamiast n = 100 minut wąską drogą jechałbym, tak czy siak, 100 minut, tyle że szeroką drogą". Co prawda wtedy jego koledzy przejechaliby trasę Warszawa-Radom w 99 minut, więc może jeden z kierowców dałby się przekonać do zmiany trasy, ale kolejni z pewnością nie (gdyż pogarszaliby oni swój czas przejazdu z |n = 99 minut na 100 minut).

obrazek

Więc jak to - wybudowaliśmy nową drogę i w praktyce czas przejazdu wydłużył się? Niestety, tak właśnie jest! A to dlatego, że każdy z kierowców działa na własną korzyść i w ten sposób szkodzi innym kierowcom. Widać, że warto czasami konsultować się z matematykami w sprawach z pozoru z matematyką niezwiązanych. A że zjawisko nie jest czysto wydumane, świadczą rzeczywiste sytuacje. W Stuttgarcie w 1969 roku inwestycje drogowe doprowadziły do istotnego pogorszenia przejezdności centrum, w Nowym Jorku zaś w 1990 roku zaobserwowano efekt odwrotny: zamknięcie 42. ulicy spowodowało zwiększenie płynności ruchu. Oba zdarzenia tłumaczy się paradoksem Braessa, bo tak właśnie (od nazwiska niemieckiego matematyka Dietricha Braessa) nazywa się omawiany przez nas efekt.

Paradoks Braessa jest dobrą ilustracją zastosowania teorii gier. Opisana sytuacja jest szczególnego rodzaju grą, w której graczami są kierowcy rywalizujący (a czasem współpracujący), aby uzyskać jak najkrótszy czas przejazdu. Ich strategiami zaś są różne wybory dróg. Sytuacja, w której żadnemu z kierowców nie opłaca się zmienić swojej strategii, nazywa się równowagą Nasha. Okazuje się, że w naszej grze równowaga Nasha nie musi dawać optymalnego rozwiązania. Co więcej, po zbudowaniu dodatkowej drogi nowa równowaga Nasha może dać jeszcze gorsze rozwiązanie. Teoria gier zna dużo więcej przykładów, gdy egoistyczne działanie prowadzi do sytuacji niekorzystnych społecznie, jednym z najbardziej znanych jest dylemat więźnia (pisaliśmy o nim m.in. w Delcie 5/2015).

obrazek

Powyższy przykład rodzi pytanie o to, jak bardzo może nam zaszkodzić nieprzemyślane budownictwo dróg. Czy może się okazać, że na skutek inwestycji GDDKiA czas przejazdu z Warszawy do Rzeszowa wydłuży się np. dwa albo pięć razy? Na szczęście nie! Przy założeniu, że czas przejazdu dla każdego odcinka drogi jest liniową funkcją natężenia ruchu (czyli jest postaci |an +b, gdzie n to liczba kierowców, a a i b to ustalone liczby rzeczywiste), można wykazać, że sytuacja może zostać pogorszona co najwyżej o jedną trzecią, czyli tak, jak ma to miejsce w naszym przykładzie (ze |150 minut na 200 ). Jak to wykazano - to już zupełnie inna historia. Co ciekawe, za sformułowanie problemu, rozwiązanie go oraz kilka wyników w pobliżu przyznano w 2012 roku bardzo prestiżową nagrodę Gödla za wybitne osiągnięcia w dziedzinie informatyki teoretycznej.

Okazuje się również, że nasze rozważania mają związek z informatyką. Śmiało można sobie wyobrazić, że zamiast miast mamy systemy komputerowe, które przesyłają między sobą nie tiry, a informacje i nie po drogach, ale łączami o pewnych przepustowościach - a efekty jak w paradoksie Braessa mogą być identyczne. Jak widać, matematycy, przynajmniej niektórzy, zajmują się wciąż pytaniami, które każdy z nas może zrozumieć i są istotne w praktyce.