Optymalizacja sieci transportowych Janusz Woch

[ Pobierz całość w formacie PDF ]
.Istnieje duża szansa na to, że w momencie rozpoczynania procesuwyznaczania ruchu, prawie wszystkie relacje korzystać będą z połączeń 2 4 lub 4 2.Gdy ruchna tych połączeniach staje się większy, dalsze korzystanie z nich nie jest zyskowne; jednakpotok ruchu przyporządkowany im w pierwszych iteracjach nie może być teraz przerzucony gdzie indziej.Istnieje więc stosunkowo duża szansa na to, że SALMOF nie darozwiązania poprawnego, nawet w nieskończonej liczbie iteracji.Dla metody SALMOFobliczenia wykonuje się w 400 krokach, wszystkie o wielkości 0,0025.W marginalnej funkcjicelu stosuje się ilorazy różnicowe, w których różnica "x równa się 2,5.W celu zbadania czy znalezione rozwiązanie jest rozwiązaniem optymalnym, zapisano irozwiązano zadanie programowania kwadratowego.Do rozwiązania zadania programowaniakwadratowego wykorzystaliśmy program komputerowy opracowany w Holenderskiej SzkoleEkonomicznej w Rotterdamie, oparty na algorytmie van de Panne i Whinstona (1969).W celu zapisania zadania, tak jak przedstawiają to zależności (5.2.2) i wykorzystujączależności (1.2.11) oraz (1.2.12) jako ograniczenia sieci, byłyby potrzebne 432 zmiennedecyzyjne, 108 różnoważności i 432 warunki nieujemności.Aby zredukować rozmiaryzadania, traktujemy potoki dla różnych ścieżek jako zmienne decyzyjne oraz z górywyłączamy ścieżki mało prawdopodobne.W takiej sytuacji potrzeba jedynie 66 zmiennychdecyzyjnych.12 równoważności i oczywiście 66 warunków nieujemności.Uzyskane wartości funkcji celu są następujące:F (SALMOF) = 17160F (programowanie kwadratowe) = 16970Możemy stąd wyciągnąć dwa ważne wnioski:a) metoda SALMOF nie dała rozwiązania optymalnego;b) rozwiązanie SALMOF różniło się od optymalnego jedynie o prawie 1%.Lepsza analiza wyników wymaga przyjrzenia się wartościom zmiennych decyzyjnych,w tym wypadku używanym ścieżkom oraz potokom ruchu na nich, oraz spojrzenia nawynikające z nich potoki na poszczególnych połączeniach.Wszystkie te wielkości podane sąw tabl.5.7.1 oraz 5.7.2.Przed przyjrzeniem się tym wynikom, musimy zaznaczyć że wykorzystywane ścieżkinie zawsze są jednoznacznie określone.Z sytuacją taką mamy do czynienia, gdy niektóreścieżki rozkładają się wachlarzem , pózniej łączą się i rozkładają powtórnie.Potoki na nichnie są wtedy jednoznacznie określone.Potoki na rys.5.7.3 zawsze dawać będą taką samąwartość dla funkcji celu.Rozwiązanie zadania programowania kwadratowego jestrozwiązaniem jedynym.Dlatego też potoki na połączeniach w rozwiązaniu tego zadania sąokreślone jednoznacznie.Ost5-1015.Nowa metoda Steenbrinka (1978) wyznaczania iteracyjnego według najmniejszej wartościmarginalnej funkcji celuPorównując obydwa rozwiązania widzimy, że we wszystkich relacjach, z wyjątkiemrelacji 4 2 i 5 4, różnią się zarówno wykorzystywane ścieżki, jak i liczby podróży na nichrealizowane.Ale różnice te nie są znaczne, szczególnie przy dużych potokach ruchu.Ponadtoza pomocą programowania kwadratowego otrzymujemy tylko jedno rozwiązanie.X384 = � - �X384 = �X3784 = � +�X3784 = �X37894 = � -�X37894= �X3894 = a + � -� +�X3894 = � + � -�Rys.5.7.3.Różne potoki na ścieżkach (sieci z rys.5.7.1.), dla których funkcja celu mataką samą wartość (�, � , � , � e" 0, � d" � + �; � d" � )Tablica 5.7.1.Zcieżki i związane z nimi liczby podróży w rozwiązaniach otrzymanychdla programowania kwadratowego i metody SALMOFProgramowanie kwadratowe SALMOFRelacja wykorzystywana liczba podróży wykorzystywana liczba podróżyścieżka na tej ścieżce ścieżka na tej ścieżce23 213 562 213 585a273 1438 273 141524 24 1694 24 15302894 306 2894 115-40b284 280-3552784 75-027894 0-7525 285 856 285 730-5832785 144 2785 0-1472895 50-19727895 147-02495 7232 312 39 312 56372 161 372 14434 384 918 384 582-2573894 82 3894 13-3373784 0-32537894 325-03724 8035 35 1430 35 1420385 0 385 406-3153895 11 3895 0-903785 206 3785 60-15037895 353 37895 90-0372495 2542 42 200 42 20043 483 100 483 684273 284213 445 465 275 465 292495 725 495 707Ost5-1025.Nowa metoda Steenbrinka (1978) wyznaczania iteracyjnego według najmniejszej wartościmarginalnej funkcji celu52 582 64 582 255942 36 5942 7553 53 199 53 173583 1 583 14594273 1254 594 100 594 100aWszystkie potoki zaokrąglono do liczby całkowitej, b Występuje tutaj efekt z rys.5.7.3.dla x2894 = 115 �,x284 = 280 + �, x2784 = 75 �, x27894 = � oraz 0 d" X d" �Najważniejsze jest to, że (prawie) wszystkie różnice pomiędzy powiązaniamiotrzymanymi za pomocą programowania kwadratowego i metody SALMOF wytłumaczyćmożna efektem, o którym wspominamy w p.5.4.2, a który wywołany jest kształtem funkcjicelu dla połączeń 2 4 i 4 2.W początkowej fazie stosowania metody, korzystanie z tychpołączeń jest bardzo zyskowne.Tablica 5.7.2 Potoki na połączeniach obliczone za pomocą programowaniakwadratowego i SALMOFPotoki PotokiPołączenie Połączenieprogramowanie programowanieSALMOF SALMOFkwadratowe kwadratowe12 39 56 64 - -13 562 589 65 275 2917 - - 69 - 2 -21 562 589 71 - -24 1,694 1,707 72 161 24927 1,582 1,677 73 1,438 1,45528 1,162 1,175 78 703 69731 39 56 82 64 2535 1,430 1,420 83 101 8337 720 724 84 918 9338 1,011 1,000 85 1,206 71,19587 - -42 236 319 89 752 7446 275 292 048 100 68 94 524 6349 725 805 95 1,089 91,096 - 92 -53 199 173 98 - -56 - -58 65 3959 136 187Widzimy, że relacje 2 4, 2 5, 3 4 a nawet częściowo 3 5 korzystają z połączenia 2 4,natomiast relacje 4 2, 4 3, 5 2 oraz 5 3 korzystają z połączenia 4 2.W programowaniukwadratowym jedynie relacja 2 4 korzysta z połączenia 2 4 oraz relacje 4 2, 4 3 i 5 2korzystają z 4 2.Przy końcu postępowania według metody SALMOF, potok na połączeniu 2Ost5-1035.Nowa metoda Steenbrinka (1978) wyznaczania iteracyjnego według najmniejszej wartościmarginalnej funkcji celu4 staje się tak duży, że używanie innych ścieżek dla relacji 2 4 jest lepszym wyjściem.Możemy zobaczyć, że używana jest nawet ścieżka 2 7 8 9 4 [ Pobierz całość w formacie PDF ]

Formularz