Badania operacyjne

Przykładowe tematy na prezentacje (egzamin):

Zdanie programowania liniowego Metoda geometryczna Dualność Postać bazowa zadania programowania liniowego Metoda simplex Metoda podziału i ograniczeń Zadanie binarne Zbilansowane zagadnienie transportowe Niezbilansowane zagadnienie transportowe Metoda potencjałów Metody budowania pierwszego rozwiązania dopuszczalnego w zagadnieniu transportowym Algorytm sympleks Algorytmy przybliżone (heurystyczne) Algorytm przeszukiwania lokalnego Algorytm lokalnej optymalizacji Algorytm iteracyjnej poprawy Algorytm symulowanego wyżarzania Algorytm przeszukiwania TABU Algorytmy genetyczne (ewolucyjne) Sformułowanie zagadnienia programowania matematycznego w ujęciu badań operacyjnych

Literatura:

Trzaskalik T., Wprowadzenie do badań operacyjnych z komputerem, Polskie Wydawnictwo Ekonomiczne, Warszawa 2003. Jędzejczyk Z., Kukuła K. (red.), Skrzypek J., Walkosz A., Badania operacyjne w przykładach i zadaniach, Wydawnictwo naukowe PWN, Warszawa 2002 Anderson R., D., Sweeney D., J., Williams T., A., An Introduction to Management Science, [w:] Quantitive Approaches to Decision Making. West Publishing Company St. Paul, New York, Los Angeles, San Francisco 1991. Badania operacyjne w przykładach i zadaniach. Red. Kukuła K., PWN, Warszawa 1993. Grabowski W., Programowanie matematyczne. PWE, Warszawa 1980. Matematyka współczesna. Dwanaście esejów. Praca zbiorowa pod redakcją Steene L.A., WNT Warszawa 1983. Przykładowe modele ilustrujące zastosowania dodatku Microsoft Excel Solver. Microsoft Corporation, 2001. Winston L.,W., Operations Reearch, PWS-KENT Publishing Company, Boston, 1991

Zadania do kolokwium:

Rozwiązanie

Zadanie

Rozwiązanie

Zad 3

Załóżmy, że mamy k kawalerów i p panien oraz dla każdej z panien podany jest zbiór kawalerów, których zna.

Czy jest możliwe wydanie za mąż każdej z kobiet za kawalera, którego zna ?

Sformułowanie przy pomocy grafów.
Zbudujmy graf, którego zbiór wierzchołków składa się z dwóch rozłącznych podzbiorów: zbioru kawalerów K i zbioru panien P. Wierzchołek x ze zbioru K łączymy krawędzia z wierzchołkiem y z P jeśli panna y zna kawalera x.W otrzymanym grafie nie istnieją krawędzie między żadnymi dwoma wierzchołkami ze zbioru P ani żadnymi dwoma ze zbioru K. Jest to więc graf dwudzielny. Poszukiwany jest w tym grafie zbiór krawędzi M taki, że:

1. żadna para krawędzi należących do M nie ma wspólnego wierzchołka (małżenstwa są rozłączne - nie dopuszczamy bigamii!!!),

2. każdy wierzchołek ze zbioru P jest koncem pewnej krawędzi ze zbioru M(każda panna wychodzi za mąż).

Zbiór krawędzi spełniający takie warunki nazywamy skojarzeniem doskonałym.

Kiedy rozwiązanie problemu kojarzenia małżenstw istnieje ?
P. Hall sformułował i udowodnił w 1935 roku twierdzenie, które podaje warunek konieczny i dostateczny na to by problem kojarzenia małżenstw miał rozwiązanie.

Zadanie 4

Komiwojażer ma do odwiedzenia pewna liczbe miast. Chciałby dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Dane sa również odległościmiedzy miastami. Jak powinien zaplanować trase podróży, aby w sumie przebył możliwie najkrótsza droge? Przez 'odległośc' miedzy miastami możemy rozumieć odległość w kilometrach, czas trwania podróży miedzy tymi miastami albo koszt takiej podróży (na przykład cene biletu lotniczego). W tym ostatnim przypadku, poszukiwanie optymalnej trasy polega na zminimalizowaniu całkowitych kosztów podróży. Tak wiec możemy poszukiwać trasy nakrótszej albo najszybszej albo najtańszej. Zakładamy przy tym, że odgłość miedzy dowolnymi dwoma miastami jest nie wieksza niż długość jakiejkolwiek drogi łaczacej te miasta, która wiedzie przez inne miasta. Założenie to tylko z pozoru wydaje sie być zawsze spełnione. Rozważmy nastepujacy przykład. Załóżmy, że interesuje nas czas trwania podróży koleja. Najszybsze połaczenie z Katowic do Białegostoku wiedzie przez Warszawe. 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 sa miastami. Każda pare miast połaczmy krawedziami. Każdej krawedzi nadajemy wage równa 'odległości' miedzy miastami odpowiadajacymi wierzchołkom, które sa końcami tej krawedzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczajac w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, ktory 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 krawedzi.

Przykład
Na rysunku pokazano graf ważony o wierzchołkach odpowiadajacych pieciu miastom polskim. Wagami krawedzi sa odległości podane w kilometrach. Poszukujemy rozwiazania nastepujacego problemu:
Komiwojażer wyrusza z Warszawy i chce odwiedzić wszystkie pozostałe cztery miasta a nastepnie wrócić do Warszawy. Jak powinien zaplanować podróż, aby przebył możliwie najmniejsza liczbe kilometrów?

Już przy pieciu miastach wszystkich możliwych tras podróży komiwojażera jest
. Można zauważyć, że przy wiekszej liczbie miast rozważanie wszystkich możliwości nie jest najlepszym pomysłem.

Dlaczego rozwiazanie tego problemu zawsze istnieje ?
Dowolny graf pełny posiada co najmniej jeden cykl Hamiltona. Ponieważ graf ma skończona liczbe wierzchołków, to w zbiorze cykli Hamiltona istnieje taki (niekoniecznie jedyny), który posiada minimalna sume wag krawedzi.

Algorytmy rozwiazujace problem komiwojażera.
Istnieje wiele algorytmów rozwiazujacych ten problem. Wszystkie maja jedna podstawowa wade. Wymagaja 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 istniejacych w danym grafie cykli Hamiltona. Jest to jednak bardzo skomplikowane już dla liczby miast niewiele wiekszej od pieciu. Na przykład dla 20 miast liczba cykli Hamiltona w grafie pełnym o 20 wierzchołkach wynosi
czyli około
.

Algorytmy przybliżone
Czas rozwiazywania problemu komiwojażera można zmniejszyć stosujac jeden ze znanych algorytmów przybliżonych, które nie wymagaja rozważania aż tak dużej liczby przypadków. Jednak algorytmy takie nie zawsze znajduja optymalne rozwiazanie. Stworzona przez nie trasa może być znacznie 'dłuższa' od najkrótszej. Stosowanie algorytmów przybliżonych wynika z konieczności wyboru pomiedzy szybkościa znajdowania a 'jakościa' znalezionego rozwiazan. Z reguły zakłada sie, że wynik działania takiego algorytmu nie może być gorszy od optymalnego o wiecej niż pewna ustalona z góry wartość.

Jak wygladał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 sie zakończy. Co wtedy robimy ? Stosujemy algorytm przybliżony !!! Możemy przecież 'niedokładnie' obrać ziemniaki lub wyjać z wody 'lekko' niedogotowane. Wynik działania takiego algorytmu nie bedzie może najsmaczniejszy ale zaoszczedzimy na czasie, który bedziemy 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 polegajacy na znalezieniu cyklu Hamiltona jest podobnie jak problem komiwojażera 'trudny' ze wzgledu na długi czas działania znanych algorytmów. Do znalezienia takiego cyklu może wystarczyć 'troche szcześ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.

Twierdzenia Halla
Problem kojarzenia małżenstw ma rozwiązanie wtedy, gdy każde m panien zna łącznie co najmniej m kawalerów, dla m=1,2, ...p.

Przykład.
Oto przykładowy graf dla zbioru P złożonego z trzech panien i zbioru K złożonego z trzech kawalerów.

Każda z panien zna dokładnie dwóch kawalerów. Skojarzenie doskonałe istnieje i może wyglądać następująco:

Ania powinna wyjść za Tomka, Kasia za Arka a Zosia za Jasia. Popatrzmy teraz na następujący graf.

W tym grafie skojarzenie doskonałe nie istnieje. Ania i Kasia znają tylko Tomka. Nie uda sie więc znaleźć równocześnie męża dla obydwu panien.

Zastosowania.
Problem ten posiada bardziej poważne zastosowania. Przy użyciu tej samej metody możemy rozwiązać problem polegający na przydzieleniu pracownikom zajęć zgodnie z ich kwalifikacjami. W tym przypadku przez P należy rozumieć zbiór pracowników, K zbiór zadan do wykonania. Dwa wierzchołki x i y łączymy krawędzią jeśli praca y jest zgodna z kwalifikacjami pracownika x (to znaczy może on ją wykonywać).

6

---