Multimedialny system wspomagający badania symulacyjne na potrzeby zamkniętego zagadnienia transportowego cd.

2. ALGORYTMY

2.1. METODA KĄTA PóŁNOCNO-ZACHODNIEGO (MKP-Z)

Działanie MKP-Z [5] polega na wypełnianiu macierzy przewozów [xij] (6) począwszy od pola (komórki) w jej lewym górnym rogu, tzn. x(1,1). W komórkę tę wpisywana jest mniejsza z liczb {A1,B1}, a następnie operację powtarza się dla pola położonego na prawo (gdy towar dostawcy nie został jeszcze całkowicie rozdysponowany) lub poniżej (gdy całą podaż dostawcy rozdysponowano odbiorcom). Ponieważ MKP-Z abstrahuje od kosztów transportu, dlatego algorytm ten wymaga zwykle większej liczby iteracji niż w przypadku stosowania innych metod. MKP-Z została ulepszona na potrzeby programu TRANSPORTER. W kolejnych iteracjach algorytm zmienia pole startowe i dzięki temu można uzyskać różne rozwiązania. Kolejno uzyskane wyniki cząstkowe z każdej iteracji, są przechowywane i porównywane, w celu znalezienia rozwiązania optymalnego.


2.2. METODA MINIMALNEGO ELEMENTU MACIERZY (MMEM)

MMEM polega na rozmieszczeniu przewozów głównie na tych trasach, na których koszty są najniższe [5]. Punktem wyjścia jest przekształcenie macierzy kosztów do takiej postaci, by w każdym wierszu i każdej kolumnie występowało, co najmniej jedno zero [1]. Mając tak przekształconą macierz kosztów staramy się rozmieścić przewozy na trasach, gdzie koszty są najmniejsze. Jeżeli uda się rozmieścić przewozy wyłącznie w polach, w których występują zera, to otrzymane rozwiązanie jest optymalnym planem przewozów.

MMEM została ulepszona na potrzeby programu TRANSPORTER. W przypadku nie znalezienia rozwiązania optymalnego, uruchamiany jest mechanizm, który analizuje pozostałe elementy macierzy, uwzględniając historię poprzednich przydziałów. Spośród wszystkich wariantów rozwiązań wybierane są te, które osiągnęły najmniejszy koszt, a w ich zakresie przeprowadzane są dodatkowo permutacje tego zbioru elementów, przy którym istnieje podejrzenie, że jego dalsza optymalizacja może spowodować poprawę wyników.

2.3. METODA RENT RóŻNICOWYCH (MRR)

Działanie tej metody opiera się na stwierdzeniu, że rozwiązania ZZT nie zmienią się, jeżeli wszystkie elementy dowolnego wiersza macierzy kosztów zostaną powiększone lub pomniejszone o dowolną stałą [3]. W metodzie tej pierwszym krokiem jest znalezienie wyjściowego planu prze-wozów [xij] (6), spełniającego zasadę najtańszego przyporządkowania i warunek (3). Następnie są wyznaczane deficyty i nadwyżki, które powstałyby u dostawców, przy realizacji planu wyjściowego. Dla każdego wiersza obliczana jest różnica (7) i na jej podstawie określani są tzw. dostawcy i odbiorcy deficytowi oraz nadwyżkowi [3].


Rozpatrujemy odbiorców deficytowych pomijając odbiorców nadwyżkowych. U dołu każdej kolumny deficytowej zapamiętujemy tzw. rentę [3].


Po obliczeniu rent wybieramy najmniejszą z nich dla kolumn deficytowych i modyfikujemy rozkład kosztów (9). Po dokonaniu tej operacji konstruujemy ponownie plan spełniający zasadę najtańszego przyporządkowania, biorąc tym razem pod uwagę koszty c1(i,j).


Należy przy tym likwidować nadwyżki i deficyty, przesuwając przewozy w pola tabeli, w których można obecnie przewozy umieścić bez naruszania zasady najtańszego przyporządkowania [3]. Procedurę tę powtarzamy tak długo, aż nie nastąpi całkowita likwidacja nadwyżek i deficytów.

MRR została ulepszona na potrzeby programu TRANSPORTER. W przypadku, gdy zadana ilość iteracji jest mniejsza niż wymagana do znalezienia rozwiązania optymalnego, algorytm ocenia otrzymany podział i to jak się zmieniały nadwyżki i deficyty w poprzednich iteracjach. Następnie dokonywany jest rozdział począwszy od dostawcy, przy którym koszt transportu jest najmniejszy.

3. SYSTEM EKSPERYMENTOWANIA Program TRANSPORTER umożliwia znalezienie optymalnego (lub najbardziej zbliżonego do optymalnego) rozwiązania zadania optymalizacyjnego sformułowanego w pkt.2. Rozwiązania mogą być generowane przy wykorzystaniu jednego z trzech algorytmów: MMEM, MKP-Z lub MRR. Program umożliwia również badania porównawcze własności algorytmów (jakości, szybkości uzyskania wyników) i zastosowań każdego z nich do rozwiązywania określonej grupy problemów ZZT.

Program TRANSPORTER zawiera trzy moduły: okno główne, okno wy-ników i okno wykresów. Każde z nich posiada także swoje podokna, najczęściej pełniące fun-kcje informacyjne. Okno główne samo-czynnie pojawia się po uruchomieniu programu, natomiast inne okna wy-świetlane są dopiero wtedy, gdy są potrzebne lub na żądanie użytkownika. Okno to posiada funkcje multimedialne (efekty dźwiękowe/wizualne, odtwarzanie muzyki oraz odtwarzanie animacji będącej krótką informacją o programie). Każda opcja multi-medialna może zostać wyłączona lub włączona w dowolnym momencie działania programu.



W głównej części okna (rys. 2) znajduje się tabela, do której użytkownik wprowadza lub wczytuje z pliku parametry brzegowe rozwiązywanego ZZT oraz koszty przewozu między poszczególnymi odbior-cami i dostawcami. Wpro-wadzone dane mogą zo-stać zapisane do pliku w celu ich późniejszego wykorzystania. W panelu ALGORYTM I ILOŚĆ ITERA-CJI może zostać wybrana metoda, która posłuży do rozwiązania zadanego problemu ZZT oraz jej dokładność (ilość iteracji algorytmu w przedziale od 1 do 1000). Przycisk LICZ powoduje rozpoczęcie szukania rozwiązania przez wybrany algorytm. Stopień zaawansowania przedstawia pasek postępu w dolnej części okna.


Okno wyników (rys. 3) pojawia się po zakończeniu obliczeń przez wybrany algorytm i prezentuje uzyskane wyniki: plan przewozu, jego koszt oraz czas pracy algorytmu. Podobnie jak w oknie głównym, także i tutaj dostępne są funkcje multimedialne. Okno to posiada także inne funkcje: wyłączenia wyświetlania zer w tabeli (zwiększenie przejrzystości tabeli), zapisu wyników do pliku tekstowego oraz wywołania okna wykresów. Okno wykresów (rys. 4) zostaje wywołane z okna wyników przyciskiem RYSUJ WYKRES. Jest ono, w pełni skalowalne, a także może zostać zmaksymalizowane w celu dokładniejszego przedstawienia wyświetla-nej treści. Prezentuje ono w formie graficznej rezultaty badań przepro-wadzonych od momentu uruchomienia programu. W oknie tym istnieje także możliwość usuwa-nia wyników, zapis wy-kresów do pliku graficz-nego w formacie bitmapy oraz ich bezpośredni wydruk.