5102077454

4 PROBLEM OPTYMALIZACJI

4.1 ZADANIE

Analizowany problem optymalizacji polega na znajdowaniu optymalnej trasy przejścia z punktu A do punktu B. Poprzez optymalną trasę rozumie się tutaj drogę o najmniejszym koszcie przebycia (niekoniecznie najkrótszą w sensie geograficznym), przy uwzględnieniu pewnych czynników zewnętrznych.

Ukonkretniając, przykładowe zadanie można sformułować następująco:

Żaglówka płynie z punktu A do punktu B. Porusza się po dyskretnej mapie, na której w różnych miejscach znajduję się m.in. statyczne przeszkody. Uwzględniając kierunek wiatru, znaleźć optymalną trasę (minimalizacja czasu przejścia).

4.2 REALIZACJA

4.2.1 Wykorzystana struktura

Do rozwiązania tego zadania przy użyciu JaCoPa wykorzystano ograniczenie NetworkFIow. Definiuje ono problem sieci rozpływu o minimalnym koszcie. Można go przedstawić za pomocą grafu skierowanego i następujących zmiennych:

•    N - zestaw węzłów (node),

•    A-zestaw łuków (arc),

•    I, u - dolna i górna funkcja pojemności łuków,

•    c - funkcja kosztów łuków (cost),

•    b-bilans masowy węzłów (balance).

Pomimo iż teoretycznie struktura wymaga grafu skierowanego (łuki tylko w jednym kierunku), to w praktyce nic nie stoi na przeszkodzie, aby utworzyć łuki w dwóch kierunkach (np. połączenie C->B i B->C). Solver w trakcie obliczeń na pewno uwzględni takie rozwiązanie, ale nigdy go nie wybierze, bo będzie nieoptymalne (cofamy się od punktu docelowego).

Adaptując sieć przepływową do postawionego zadania, zmienne grafu można interpretować jako:

•    węzły - pola mapy (mapa w kształcie prostokąta),

•    łuki - przejścia między węzłami; zakłada się istnienie połączeń poziomych, pionowych i na skos (węzeł wewnętrzny będzie miał 8 połączeń),

•    pominięto dolną i górną funkcję pojemności łuków,

•    funkcja kosztów określa koszt (można go potraktować jako czas) przepłynięcia z jednego węzła do węzła sąsiedniego; odpowiednio dobierając wartości kosztu, możliwe jest zamodelowanie np. pól mapy stanowiących jakąś przeszkodę (bardzo wysoki koszt, niemożliwy do przekroczenia) oraz szybkość poruszania się żaglówki w zależności od kierunku wiatru (np. niski koszt, jeśli kierunek i zwrot łuku jest zgodny z kierunkiem i zwrotem wiatru, wysoki jeśli łuk skierowany jest przeciwnie do wiatru),

•    bilans masowy - założono, że w sieci istnieją tylko dwa węzły o niezerowym bilansie, reprezentują one punkt startowy (bilans = 1) i docelowy (bilans = -1).

Graficzne przedstawienie: