1 Badania operacyjne Wykład 5

2 Rozwiązywanie zadań programowania całkowitoliczbowego: wyliczenie możliwości

3 Algorytm Branch and boundDany jest następujący problem optymalizacji całkowito-liczbowej:

4 Rozwiązujemy problem w wersji ciągłej (z liczbami rzeczywistymi)

5 Dzielimy na dwa podproblemy wykluczając rozwiązania niedopuszczalne

6 Dwa podproblemy również rozwiązujemy w liczbach rzeczywistych

7 Dzielimy na dwa podproblemy wykluczając rozwiązania niedopuszczalne

8 Kolejno rozbijamy na problemy z coraz mniejszym zbiorem dopuszczalnym

9 L3 ignorujemy, bo jest niedopuszczalne

10 Kontynuujemy aż otrzymamy rozwiązanie całkowitoliczboweMożemy przerwać procedurę przy L5, jeśli chcemy być w 10% od minimum

11

12 Nawet, gdybyśmy nie znaleźli rozwiązania całkowitego w L2 za pierwszym razem, a dostalibyśmy rozwiązanie o funkcji celu nie większej niż 40 (dotychczasowe rozwiązanie z L6), moglibyśmy przerwać procedurę i wywnioskować, że rozwiązanie z L6 jest optymalne Po analizie L6, wiemy, że optimum jest pomiędzy 40 a 41. Jeśli wystarczy nam 2.5% dokładności możemy przerwać. Jeśli nie, musimy sprawdzić L2. L2 jednak okazuje się nie przynieść poprawy.

13 Skojarzenia http://mathsite.math.berkeley.edu/smp/smp.html x HelenaGosia Irena rowsums Dawid 1 Edward Filip colsums kompatybliność 0.5 0.75 2 2.5 1.5 funkcja celu 4.5

14 Wprowadzenie do grafów: Mosty w KoenigsberguLeonard Euler zastanawiał się, czy można przejść przez każdy most tylko raz (1736)

15 Konceptualizacja - węzły

16 Konceptualizacja - krawędzie

17 Czy istnieje spacer po wszystkich mostach, tak aby żaden się nie powtórzył?

18 Gdyby tak zbudować dwa dodatkowe mosty.

19 Każdy taki spacer musi wejść i wyjść z każdego wierzchołka dokładnie raz. Czyli stopień każdego wierzchołka musi być parzysty.

20 Cykl Eulera Cykl Hamiltona Problem komiwojażera

21 Problem komiwojażera – objazd cyklCzas trwania: 2 d 7 h 2 m Długość trasy: 3615 km

22 Problem komiwojażera – objazd ścieżkaCzas trwania: 2 d 4 h 37 m Długość trasy: 3436 km

23 Problem komiwojażera – prawdziwy spacerCzas trwania: 29 d 11 h 21 m Długość trasy: 3485 km

24

25 Problem komiwojażera (travelling salesman problem TSP)Problem można zapisać matematycznie jako Zmienna decyzyjna xij równa się 1, gdy komiwojażer przejeżdża z miasta i do miasta j, 0 w przeciwnym przypadku Możliwość przejazdu z danego miasta do tego samego miasta jest zabroniona

26 Problem komiwojażera Koszt przejazdu z miasta do miasta to dijFunkcja celu to łączny koszt przejazdu trasy Pierwsze ograniczenie oznacza, że komiwojażer musi opuścić każde miasto dokładnie raz Drugie ograniczenie oznacza, że komiwojażer musi wjechać do każdego miasta dokładnie raz Czy to już wszystko? Załóżmy, że w problemie z 5 miastami rozwiązanie optymalne to x12=x23=x31=x45=x54=1 To rozwiązanie spełnia powyższe ograniczenia i może być optymalne. Jednak zawiera podtrasy (subtours) – rozłączne pętle o rozmiarze mniejszym niż wszystkie miasta Trzeba wprowadzić dodatkowe ograniczenia

27 Eliminacja podtras Pętle dla dwóch miast Pętle dla trzech miastPętle dla czterech miast Itd. Jednak w praktycznej implementacji takich ograniczeń byłoby stanowczo za dużo – w problemie z 30 miastami byłoby 870 ograniczeń likwidujących tylko pętle dla dwóch miast

28 Eliminacja podtras – drugie podejścieWprowadzamy dodatkowe nieujemne zmienne ciągłe ui: Podtrasy są wyeliminowane Ile jest takich ograniczeń? (N-1)2-N, czyli w problemie z 30 miastami wszystkich ograniczeń byłoby 812, a wcześniej tylko ograniczeń dla pętl o długości dwa było 870.

29

30 Gra