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

Abstract

W ramach systemu eksperymentowania TRANSPORTER, zaimplementowano trzy algorytmy służące do znajdowania rozwiązania zamkniętego zagadnienia transportowego (ZZT). System umożliwia prowadzenie badań porównawczych własności algorytmów i prezentację ich wyników. W pracy umieszczono analizę wyników przykładowych cykli badań oraz przedstawiono zastosowane środki multimedialne. W trakcie pracy z programem odtwarzana jest muzyka z plików MIDI, w oknach programu odtwarzane są klipy prezentujące informacje o programie, a w trakcie przeprowadzania badań ważniejsze wydarzenia potwierdzane są adekwatnymi efektami wizualnymi i dźwiękowymi. System umożliwia prezentację wyników cyklu badań na wykresie.
Autorzy: Łukasz GUŹDZIOŁ, Tomasz HOŁODNIAK, Sławomir MAZUR

1. PROBLEM TRANSPORTOWY (ZZT)

Problem transportowy jest zagadnieniem, które znajduje zastosowanie przede wszystkim przy szukaniu optymalnego planu przewozu i wyznaczaniu trasy transportu między dostawcami i odbiorcami [6]. W projekcie zaimplementowano trzy algorytmy służące do znajdowania rozwiązania ZZT oraz stworzono kompletny system ekspertowy pozwalający porównać ich jakość. Użyte metody to:
- metoda kąta północno-zachodniego (MKP-Z) [5],
- metoda minimalnego elementu macierzy (MMEM) [5],
- metoda rent różnicowych (MRR) [3].

Ogólny model zagadnienia można sformułować następująco.

Dane: R dostawców pewnego jednorodnego towaru, z których każdy dysponuje A(i) (i=1, 2, ..., R) jednostkami tego towaru zaopatruje N odbiorców. Zapotrzebowanie każdego z odbiorców wynosi B(j) jednostek (j=1, 2, ..., N). Dane są ponadto jednostkowe koszty transportu towaru od i-tego dostawcy do j-tego odbiorcy: c(i, j) (i=1, 2, ..., R; j=1, 2,..., N). Całkowity koszt transportu jest sumą kosztów transportu na poszczególnych trasach.

Szukane: należy opracować plan przewozu towaru pomiędzy dostawcami i odbiorcami tak, aby całkowity koszt transportu był najmniejszy poprzez wyznaczenie ile towaru powinien dostarczyć i-ty dostawca j-temu odbiorcy x(i, j) (i=1, 2, ..., R; j=1, 2, ..., N). W rozpatrywanym zagadnieniu ZZT występują następujące ograniczenia: równość podaży i popytu (1), wymagania dostawców (2) i odbiorców (3) oraz zapewnienie sensowności rozwiązania (4).


Rozpatrywany problem (ZZT) jest zadaniem optymalizacyjnym. Szukane:

wyznaczyć x(i,j) takie, że funkcja celu (5) osiąga minimalne wartości.

Do ZZT można sprowadzić wiele różnych zagadnień (w tym również pewne zagadnienia nie dotyczące transportu), które mają tę samą strukturę problemu optymalizacyjnego.