Badania operacyjne – metody, etapy, dziedziny zastosowań
Dziedzinę wiedzy zajmująca się metodami analizy celowych czynności (operacji) i obiektywną oceną decyzji, przy użyciu najczęściej techniki komputerowej nazywamy badaniami operacyjnymi. W badaniach operacyjnych stosuje się modelowanie matematyczne, wykorzystując teorię prawdopodobieństwa, teorię gier i inne techniki, co umożliwia określenie stopnia ryzyka i uwzględnienie go przy podejmowaniu decyzji, czy realizowaniu zamierzonego przedsięwzięcia.
Historia
Badania operacyjne zostały zapoczątkowane w Anglii na krótko przed II wojną światową i rozwijały się dynamicznie po jej zakończeniu wraz z rozwojem elektronicznej techniki obliczeniowej. Wiele metod badań operacyjnych wymaga bowiem wykonania dużej liczby obliczeń, co jest w praktyce możliwe dopiero przy zastosowaniu techniki elektronicznej
Metody
Metody stosowane w badaniach operacyjnych skupiają się na porównaniu efektywności różnych sposobów rozwiązywania zagadnień i poszukiwania rozwiązania optymalnego, pozwalają przeanalizować wybrany wycinek rzeczywistości oraz ocenić ilościowo rezultaty możliwych do podjęcia decyzji. Przy analizie możliwych skutków podejmowanych decyzji badania operacyjne uwzględniają takie czynniki, jak przypadkowość i ryzyko. Do rozwiązywania tak złożonych zagadnień angażuje się przedstawicieli różnych specjalności (m.in. ekonomistów, matematyków, statystyków, inżynierów, socjologów, psychologów), co przesądza o kompleksowym, systemowym podejściu badań operacyjnych do rozwiązywanych problemów.
Etapy badań operacyjnych
W metodach stosowanych w badaniach operacyjnych wyróżnić można szereg etapów, które najogólniej dzieli się na:
- budowę modelu matematycznego opisującego rozwiązywany problem,
- rozwiązanie modelu polegające na określeniu najlepszej w danych warunkach decyzji,
- weryfikację modelu i uzyskanego rozwiązania oraz dokonanie ewentualnych poprawek,
- kontrolę mającą zapewnić dopływ informacji wpływających na ewentualne zmiany optymalnej decyzji, jak również umożliwiać wprowadzenie korekt decyzji w przypadku zmian różnych czynników wpływających na optymalną decyzję.
Dziedziny zastosowań
Badania operacyjne są szczególnie często stosowane przy rozwiązywaniu problemów gospodarczych, w tym produkcyjnych. Rozwój techniki i technologii, coraz bardziej komplikujący powiązania między elementami systemów produkcyjnych i ich funkcjonowanie, wzmaga zapotrzebowanie na metody analizy i obiektywnej oceny decyzji podejmowanych w szeroko rozumianym planowaniu i zarządzaniu działalnością gospodarczą. Każda bowiem działalność, w tym szczególnie działalność gospodarcza, związana jest z określonymi celami, których osiągnięcie wymaga posiadania określonych środków. ¦rodki te bardzo często są ograniczone i mogą być użyte w różny sposób, o czym przesądzają konkretne warunki, w jakich prowadzona jest działalność (techniczne, organizacyjne, prawne itp.). W działalności gospodarczej powstaje zatem zawsze problem podjęcia decyzji dotyczącej sposobu zastosowania rozporządzalnych środków i zasobów oraz realizacji zamierzonego celu.
Ciekawe problemy:
Problem chińskiego listonosza
Dlaczego listonosza?
W swojej pracy, listonosz wyrusza z poczty, dostarcza przesyłki adresatom, by na końcu powrócić na pocztę. Aby wykonać swoją pracę musi przejść po każdej ulicy w swoim rejonie co najmniej raz. Oczywiście chciałby, aby droga, którą przebędzie, była możliwie najkrótsza.
Dlaczego chińskiego?
Problem ten został sformułowany po raz pierwszy w języku teorii grafów przez chińskiego matematyka Mei Ku Kwana w 1962 roku.
Sformułowanie problemu
Rozważmy graf, którego krawędzie odpowiadają ulicom w rejonie, obsługiwanym przez listonosza. Wierzchołki to po prostu skrzyżowania ulic. Krawędziom nadajemy wagi, które oznaczają odległości między dwoma skrzyżowaniami. Znalezienie możliwie najkrótszej drogi, którą musi przejść listonosz sprowadza sie do znalezienia w tym grafie drogi o minimalnej sumie wag krawędzi, która przechodzi przez każdą krawędź co najmniej raz
Jeśli graf posiada cykl Eulera
Jeśli dany graf posiada cykl Eulera, to istnieje taka droga, która zaczyna i kończy się w tym samym punkcie i wymaga przejścia po każdej ulicy dokładnie raz. Zauważmy, że ponieważ każdy cykl Eulera przechodzi raz przez każdą krawędź to suma wag krawędzi (długość drogi, którą musi przejść listonosz) jest zawsze taka sama (nie zależy od wierzchołka, w którym cykl ten zaczyna się i kończy). Rozwiązaniem jest więc dowolny cykl Eulera w tym grafie.
Jeśli graf nie posiada cyklu Eulera
W takim przypadku listonosz będzie zmuszony przejść niektórymi ulicami wielokrotnie. Rozwiązanie jest więc cyklem, w którym suma długości krawędzi wybranych więcej niż raz jest możliwie najmniejsza.
Przykład
Na rysunku pokazany jest układ ulic niedaleko Politechniki Warszawskiej. Załóżmy, że fragmenty tych pięciu ulic tworzą rejon listonosza.
Obok nazw ulic umieszczone są odległości w metrach. Prostokąt oznaczony literą P oznacza miejsce, w którym umieściliśmy pocztę, na której pracuje 'nasz' listonosz. (Na marginesie: nazwy i układ ulic są prawdziwe, jednak podane odległości oraz umiejscowienie poczty nie odpowiadają rzeczywistości. Oto jak wygląda graf odpowiadający danemu układowi ulic. Zauważmy, że graf ten nie ma cyklu Eulera ponieważ posiada dwa wierzchołki, z których wychodzi nieparzysta liczba krawędzi. Na rysunku zaznaczono również rozwiązanie czyli optymalną trasę listonosza.
Zwróćmy uwagę, że listonosz musi przejść dwukrotnie tylko ulicę Noakowskiego, zaś pozostałe ulice dokładnie raz. Powyższa droga jest najkrótszą z możliwych ponieważ odcinek, po którym przechodzi dwukrotnie liczy tylko 500 metrów i nie istnieje trasa spełniająca zadane warunki o krótszym odcinku, który listonosz musi pokonać więcej niż raz.
Problem komiwojażera
Dlaczego komiwojażera?
Komiwojażer ma do odwiedzenia pewna liczbę miast. Chciałby dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Dane są również odległości miedzy miastami. Jak powinien zaplanować trasę podróży, aby w sumie przebył możliwie najkrótsza drogę? Przez 'odległość' miedzy miastami możemy rozumieć odległość w kilometrach, czas trwania podróży miedzy tymi miastami albo koszt takiej podróży (na przykład cenę biletu lotniczego). W tym ostatnim przypadku, poszukiwanie optymalnej trasy polega na zminimalizowaniu całkowitych kosztów podróży. Tak wiec możemy poszukiwać trasy najkrótszej albo najszybszej albo najtańszej. Zakładamy przy tym, że odległość miedzy dowolnymi dwoma miastami jest nie większa niż długość jakiejkolwiek drogi łączącej te miasta, która wiedzie przez inne miasta. Założenie to tylko z pozoru wydaje się być zawsze spełnione. Rozważmy następujący przykład. Załóżmy, że interesuje nas czas trwania podróży koleją. Najszybsze połączenie z Katowic do Białegostoku wiedzie przez Warszawę. Czas trwania tej podróży traktujemy w tym przypadku jako 'odległość' z Katowic do Białegostoku.
Sformułowanie problemu
Zbudujmy graf ważony, którego wierzchołki są miastami. Każda parę miast połączmy krawędziami. Każdej krawędzi nadajemy wagę równa 'odległości' miedzy miastami odpowiadającymi wierzchołkom, które są końcami tej krawędzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy wiec w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawędzi.
Przykład
Na rysunku pokazano graf ważony o wierzchołkach odpowiadających pięciu miastom polskim. Wagami krawędzi są odległości podane w kilometrach. Poszukujemy rozwiązania następującego problemu: Komiwojażer wyrusza z Warszawy i chce odwiedzić wszystkie pozostałe cztery miasta a następnie wrócić do Warszawy. Jak powinien zaplanować podróż, aby przebył możliwie najmniejsza liczbę kilometrów?
Można zauważyć, że przy większej liczbie miast rozważanie wszystkich możliwości nie jest najlepszym pomysłem.
Dlaczego rozwiązanie tego problemu zawsze istnieje?
Dowolny graf pełny posiada co najmniej jeden cykl Hamiltona. Ponieważ graf ma skończona liczbę wierzchołków, to w zbiorze cykli Hamiltona istnieje taki (niekoniecznie jedyny), który posiada minimalna sumę wag krawędzi.
Algorytmy rozwiązujące problem komiwojażera
Istnieje wiele algorytmów rozwiązujących ten problem. Wszystkie maja jedna podstawowa wadę. Wymagają rozważenia bardzo dużej liczby przypadków i czas ich działania może być bardzo długi. Niewielki przyrost liczby miast powoduje 'duży' wzrost ilości przypadków do rozważenia i tym samym czasu działania algorytmu. Jeden z możliwych algorytmów polega na obliczeniu całkowitej długości wszystkich istniejących w danym grafie cykli Hamiltona. Jest to jednak bardzo skomplikowane już dla liczby miast niewiele większej od pięciu. Na przykład dla 20 miast liczba cykli Hamiltona w grafie pełnym o 20 wierzchołkach wynosi około 6000000.
Algorytmy przybliżone
Czas rozwiązywania problemu komiwojażera można zmniejszyć stosując jeden ze znanych algorytmów przybliżonych, które nie wymagają rozważania aż tak dużej liczby przypadków. Jednak algorytmy takie nie zawsze znajdują optymalne rozwiązanie. Stworzona przez nie trasa może być znacznie 'dłuższa' od najkrótszej. Stosowanie algorytmów przybliżonych wynika z konieczności wyboru pomiędzy szybkością znajdowania a 'jakością' znalezionego rozwiązań. Z reguły zakłada się, że wynik działania takiego algorytmu nie może być gorszy od optymalnego o więcej niż pewna ustalona z góry wartość.
Jak wyglądałby algorytm przybliżony dla problemu gotowania ziemniaków?
Załóżmy, że nie możemy czekać aż pół godziny do czasu gdy proces gotowania ziemniaków się zakończy. Co wtedy robimy ? Stosujemy algorytm przybliżony !!! Możemy przecież 'niedokładnie' obrać ziemniaki lub wyjąć z wody 'lekko' niedogotowane. Wynik działania takiego algorytmu nie będzie może najsmaczniejszy ale zaoszczędzimy na czasie, który będziemy mogli wykorzystać na przykład na poczytanie o teorii grafów. Oczywiście z góry zakładamy dopuszczalna jakość. Musimy określić, co to znaczy 'lekko' niedogotowane. Nie możemy przecież jeść ziemniaków surowych! Znajdowanie cyklu Hamiltona w dowolnym grafie. W grafie pełnym cykl Hamiltona zawsze istnieje. W dowolnym grafie może jednak nie istnieć. Problem polegający na znalezieniu cyklu Hamiltona jest podobnie jak problem komiwojażera 'trudny' ze względu na długi czas działania znanych algorytmów. Do znalezienia takiego cyklu może wystarczyć 'trochę szczęścia'. Gorzej jest kiedy cykl Hamiltona w badanym grafie nie istnieje. W takim przypadku możemy nawet być zmuszeni do sprawdzenia wszystkich możliwych permutacji zbioru wierzchołków, aby uzyskać pewność, że cykl taki nie istnieje.
Znajdowanie indeksu chromatycznego grafu
Przykładowe zastosowanie
Rozważmy następujący problem. Dany jest zbiór m nauczycieli oraz zbiór n klas. Podane są także liczby godzin zajęć jakie musi odbyć w ciągu tygodnia dany nauczyciel z każdą z klas. Szukana jest minimalna liczba godzin w tygodniu, w czasie których mogą odbyć się wszystkie zajęcia. Wiadomo, że w danym momencie czasu nauczyciel może uczyć tylko jedną klasę i każda klasa może być uczona przez tylko jednego nauczyciela.
Jak rozwiązać problem układania planu zajęć przy pomocy grafów?
Stwórzmy graf dwudzielny, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory odpowiadające nauczycielom oraz klasom. W grafie tym dopuszczamy istnienie wielu krawędzi między każdą parą wierzchołków. Wierzchołek odpowiadający nauczycielowi łączymy tyloma krawędziami z wierzchołkiem odpowiadającym klasie ile godzin zajęć musi on odbyć z tą klasą w ciągu tygodnia. Zauważmy, że jeśli pokolorujemy krawędzie tego grafu tak, aby każde dwie mające wspólny koniec były różnych kolorów, to krawędzie pokolorowane tym samym kolorem odpowiadają zajęciom, które mogą odbywać się równocześnie. Poszukujemy więc minimalnej liczby kolorów potrzebnych do pokolorowania w ten sposób wszystkich krawędzi. Innymi słowy, poszukiwany jest indeks chromatyczny tego grafu. Problem ten można oczywiście skomplikować dodając założenia dotyczące sal, w których zajęcia mogą się odbywać, bądź narzucając pewne terminy, w których dane zajęcia muszą się odbyć.
Przykład
Przypuśćmy, że mamy 5 nauczycieli: profesorów Mroza, Nowaka, Pawlaka, Cicho i Lisa oraz 4 klasy maturalne. Na poniższym rysunku pokazany jest graf stworzony na podstawie informacji o tym ile godzin zajęć w tygodniu z daną klasą ma poprowadzić każdy z nauczycieli. Dla przykładu: profesor Mróz ma 2 godziny z IVa i 1 godzinę z IVb a profesor Nowak po 1 godzinie z IVa i IVc. Indeks chromatyczny tego grafu wynosi 4. Czyli w ciągu 4 godzin uda się przeprowadzić wszystkie zajęcia. Widać, że mniejsza liczba godzin nie wystarczy ponieważ profesor Lis musi przeprowadzić 4 godziny zajęć. Również klasy IVa, IVc oraz IVd mają zaplanowane po 4 godziny. A oto jak wygląda pokolorowanie krawędzi tego grafu na 4 kolory, w którym żadne dwie krawędzie o wspólnym wierzchołku nie mają tego samego koloru.
Źródła:
- http://badania-operacyjne.ugi.pl/
- http://www.badaniaoperacyjne.webpark.pl/
- http://www.ds5.agh.edu.pl/~evolic/badania_op/
Aby dodawać komentarze musisz być zalogowany!