Planowanie tras z wykorzystaniem narzędzia Solver

Август 5, 2022

Главная
Разное
Planowanie tras z wykorzystaniem narzędzia Solver

Содержание

2. Znaczenie słowa komiwojażer ? Wyobraźmy sobie akwizytora, który podróżuje od miasta do miasta, sprzedając swoje produkty
3. Wprowadzenie Podejmowanie decyzji we współczesnej organizacji jest procesem rozwiązywania złożonych problemów, z których dużą grupę stanowią
4. -problemy alokacji środków produkcji optymalny przydział surowców, zdolności produkcyjnej maszyn oraz dysponowanego czasu pracy ludzi pomiędzy
5. -zarządzanie zapasami surowców: gospodarka zapasami i obliczanie optymalnej partii zapasów towarów, materiałów oraz wyliczenie zapasu buforowego
6. Solver, jako narzędzie optymalizacji procesów logistycznych Narzędzie Solver jest jednym z najbardziej zaawansowanych narzędzi analitycznych MS
7. komórki celu (funkcja celu) - jest to komórka w modelu arkusza, która w wyniku zastosowania Solvera
8. Propozycja rozwiązania problemu wyboru tras Zagadnienie rozpatrywane na potrzeby firmy kurierskiej należy do problemów optymalizacyjnych, a
9. Cykl Hamiltona Znalezienie właściwego cyklu Hamiltona jest zadaniem bardzo trudnym obliczeniowo. Wyobraźmy sobie graf zupełny (ang.
10. Ile różnych cykli Hamilton zawiera taki graf? Otóż pierwszą krawędź cyklu można wybrać na 9 różnych
11. Wynik jest bardzo niekorzystny, ponieważ prowadzi do wykładniczej klasy złożoności obliczeniowej O(n!). Dla każdego znalezionego cyklu
12. Grafy odwzorowujące rzeczywiste sieci połączeń zwykle nie są zupełne - ekonomicznie nieuzasadnione byłoby budowanie osobnych dróg
13. Załóżmy, iż każdy wierzchołek łączy się z czterema innymi wierzchołkami grafu. Zatem ich stopień wynosi 4.
14. Istnieją algorytmy znajdujące przybliżone rozwiązania problemu wędrującego komiwojażera w czasie wielomianowym, lecz są one bardzo zaawansowane
15. Przykład W prezentowanym przypadku kurier musi dotrzeć do 9 miast i na koniec dojechać do bazy
17. Rozwiązanie w solverze Przykładowo mamy 10 różnych miejscowości i musimy każdą z nich odwiedzić przy tym
18. Układając trasę w kolejności od 1 do 10 za pomocą funkcji indeks. Jako sumę kilometrów otrzymujemy
21. Jedynym warunkiem jaki przyjmujemy jest, że komórki które aktualnie przyjmują wartości od 1-10 muszą być różne
22. Wynik wyszedł 318km, przypomnijmy poprzedni przy trasie od 1-10 to 769km a to jest 2,41 razy
24. Скачать презентацию

Слайд 2

Znaczenie słowa komiwojażer ?
Wyobraźmy sobie akwizytora, który podróżuje od miasta do

miasta, sprzedając swoje produkty lub zawierając różne oferty handlowe. Wyrusza z miasta rodzinnego, po czym jego trasa przebiega dokładnie jeden raz przez każde z miast. Na koniec komiwojażer powraca do swojego miasta rodzinnego. Z oczywistych powodów chce, aby trasa podróży była najkrótszą ze wszystkich możliwych tras. W ten sposób powstaje problem wędrującego komiwojażera

Слайд 3

Wprowadzenie
Podejmowanie decyzji we współczesnej organizacji jest procesem rozwiązywania złożonych problemów, z których

dużą grupę stanowią logistyczne zagadnienia optymalizacyjne. Zasada racjonalności działania ekonomicznego wymaga od decydentów respektowania reguły, że każda decyzja powinna spowodować maksymalizację korzyści. Obszary optymalizacji procesów logistycznych rozwiązywalnych przy użyciu metod z zakresu badań operacyjnych obejmują zagadnienia, wśród których można wymienić:

Слайд 4

-problemy alokacji środków produkcji optymalny przydział surowców, zdolności produkcyjnej maszyn oraz

dysponowanego czasu pracy ludzi pomiędzy poszczególne wyroby (produkty), jakie może produkować firma (kryterium optymalizacji: maksymalizacja zysku);
-zagadnienia transportowe optymalizacja przewozów towarów między różnymi dostawcami i odbiorcami z uwzględnieniem punktów przeładunkowych (kryterium optymalizacji : minimalizacja łącznego kosztu przewozu towaru);
-problemy komiwojażera komiwojażer ma za zadanie odwiedzić określoną liczbę klientów i wrócić do bazy tak, aby cała jego podróż była jak najkrótsza (kryterium optymalizacji: minimalizacja długości drogi w sieci łączącej wszystkie węzły);

Слайд 5

-zarządzanie zapasami surowców: gospodarka zapasami i obliczanie optymalnej partii zapasów towarów,

materiałów oraz wyliczenie zapasu buforowego (kryterium optymalizacji: minimalizacja kosztów działalności przedsiębiorstwa);
-zagadnienia wymiany ustalenie optymalnego momentu wymiany pracującego środka trwałego na nowy (teoria odnowy) w przedsiębiorstwie, wyważenie pomiędzy kosztami eksploatacji i amortyzacji (kryterium optymalizacji: minimalizacja kosztów działalności firmy);
-problemy przydziału zadań do wykonania w taki sposób, aby osiągnąć np. najkrótszy łączny czas wykonania zadania (kryterium optymalizacji minimalizacja czasu realizacji przedsięwzięć przy posiadanych środkach).

Слайд 6

Solver, jako narzędzie optymalizacji procesów logistycznych
Narzędzie Solver jest jednym z najbardziej zaawansowanych

narzędzi analitycznych MS Excel i jednocześnie jednym z prostszych w obsłudze. Można z niego korzystać po jednokrotnym zainstalowaniu. Solver wykorzystywany jest do rozwiązywania jednokryterialnych zadań optymalizacyjnych, w których liczba zmiennych decyzyjnych nie przekracza 200. Jego zastosowanie wymaga zapisania modelu matematycznego w obszarze roboczym arkusza kalkulacyjnego. Model optymalizacji składa się z trzech elementów:

Слайд 7

komórki celu (funkcja celu) - jest to komórka w modelu arkusza, która w wyniku zastosowania Solvera ma

przyjąć wartość minimalną, maksymalną lub ustaloną w postaci liczby rzeczywistej;
komórek zmiennych (zmienne decyzyjne) są one komórkami zawierającymi poszukiwane wartości, które są zmieniane iteracyjnie i podstawiane przez dodatek Solver do funkcji celu, dopóki nie zostanie znalezione rozwiązanie optymalne;
komórek ograniczeń (mogą być zastosowane w stosunku do wartości komórki celu i komórek zmienianych) wprowadzone warunki ograniczające stanowią formułę w komórce arkusza, której wartość musi mieścić się w określonych granicach lub osiągać wartości docelowe.

Слайд 8

Propozycja rozwiązania problemu wyboru tras
Zagadnienie rozpatrywane na potrzeby firmy kurierskiej należy do

problemów optymalizacyjnych, a do jego rozwiązania należy zastosować tzw. Problem komiwojażera. Rozwiązanie problemu komiwojażera dotyczy wyznaczenia najkrótszej trasy przejazdu pomiędzy pewną liczbą punktów w taki sposób, aby każdy punkt został odwiedzony przez kierowcę tylko jeden raz. Problem komiwojażera związany jest z tzw. cyklem Hamiltona w grafie, tzn. takim cyklem, w którym każdy z wierzchołków danego grafu wystąpi dokładnie jeden raz.

Слайд 9

Cykl Hamiltona
Znalezienie właściwego cyklu Hamiltona jest zadaniem bardzo trudnym obliczeniowo. Wyobraźmy

sobie graf zupełny (ang. Complete graph - graf, w którym każdy wierzchołek jest połączony z każdym) o 10 wierzchołkach.

Слайд 10

Ile różnych cykli Hamilton zawiera taki graf?
Otóż pierwszą krawędź cyklu można

wybrać na 9 różnych sposobów, ponieważ każdy wierzchołek grafu jest połączony krawędzią z pozostałymi dziewięcioma. Po wyborze pierwszej krawędzi pozostaje nam 8 możliwych wyborów, później 7, 6 5 ... 1. W efekcie otrzymujemy liczbę cykli Hamiltona równą:
LH = 9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 9! = 362880
Dla n wierzchołków:
LH = (n - 1) • (n - 2) • ... • 3 • 2 • 1 = (n - 1)!

Слайд 11

Wynik jest bardzo niekorzystny, ponieważ prowadzi do wykładniczej klasy złożoności obliczeniowej O(n!).

Dla każdego znalezionego cyklu Hamiltona liczymy sumę wag krawędzi i zapamiętujemy cykl o najmniejszej sumie wag. Na przykład w naszym grafie może to być następujący cykl (nie sugeruj się długością krawędzi na rysunku - ważne są wagi, a nie długość kreski - czasami miasta mało odległe w linii prostej mogą być połączone długą trasą ze względu na warunki terenowe: góry, jeziora, bagna itp.):

Слайд 12

Grafy odwzorowujące rzeczywiste sieci połączeń zwykle nie są zupełne - ekonomicznie

nieuzasadnione byłoby budowanie osobnych dróg pomiędzy każdą parą miast. Zwykle drogi przebiegają od jednego miasta do drugiego, a w niektórych się rozchodzą. Dlatego opisany powyżej przypadek jest przypadkiem pesymistycznym. Jednakże problem dalej posiada wykładniczą klasę złożoności obliczeniowej. Rozważmy dla przykładu graf posiadający 100 wierzchołków.

Слайд 13

Załóżmy, iż każdy wierzchołek łączy się z czterema innymi wierzchołkami grafu.

Zatem ich stopień wynosi 4. W pesymistycznym przypadku ilość cykli Hamiltona do przebadania może wynosić:
pierwszego wierzchołka możemy pójść na 4 różne sposoby, z drugiego na 3, z trzeciego na 3, ..., i z 99 na trzy. Otrzymujemy zatem:
LH = 4 • 399 ≈ 3100 ≈ 5,15 • 1047
Zatem dla grafu posiadającego n wierzchołków o stopniu s otrzymamy
LH ≈ (s - 1)n
Czyli liczba cykli lub ścieżek do przebadania rośnie wykładniczo. Nawet na szybkim komputerze wyznaczenie rozwiązania może przekroczyć stulecia. Problemy algorytmiczne o złożoności wykładniczej są traktowane jako nierozwiązywalne dla dużych n.

Слайд 14

Istnieją algorytmy znajdujące przybliżone rozwiązania problemu wędrującego komiwojażera w czasie wielomianowym,

lecz są one bardzo zaawansowane i trudne w implementacji. Jeśli liczba wierzchołków w grafie nie jest duża (np. do 20) i graf nie jest grafem zupełnym (złożoność O(n!)), to rozwiązanie problemu komiwojażera możemy uzyskać prostym algorytmem, który wyznacza wszystkie cykle Hamiltona, liczy sumę wag krawędzi i zwraca cykl o najmniejszej sumie wag. Rozwiązanie to jest o tyle dobre, iż zawsze zwróci cykl optymalny, a nie przybliżony. Również jest łatwe do zrozumienia i implementacji. Podstawowa wada to wykładnicza złożoność obliczeniowa, która uniemożliwia analizę większych grafów.

Слайд 15

Przykład
W prezentowanym przypadku kurier musi dotrzeć do 9 miast i na

koniec dojechać do bazy w Gdyni. Należy wyznaczyć, zatem taką trasę (rysunek 1), aby całkowita długość drogi do przejechania była jak najmniejsza (aby zminimalizować koszty transportu i jednocześnie osiągnąć najkrótszy czas pracy kierowcy). Znalezienie właściwego cyklu Hamiltona jest zadaniem trudnym obliczeniowo. ponieważ w grafie pełnym składają cym się z 10 wierzchołków, liczba cykli Hamiltona wynosi 9!,czyli 362 880.
Gdyby kurier miał do odwiedzenia jeszcze tylko jedną dodatkową miejscowość, niż w prezentowanym przypadku to liczba ta wzrosłaby do3 628 800.
W przypadku 25 miejscowości to aż 15 511 210 043 330 985 984 000 000 różnych wariantów wybrania kolejnych lokalizacji podczas realizacji zadania. Obrazuje to wyraźnie jak wiele możliwości uszeregowania tras można zaproponować i wskazuje dobitnie, że realizacja tego zadania dotychczasową metodą (bez wsparcia informatycznego) byłaby nie tylko trudna i czasochłonna, ale czasami wręcz niemożliwa. Dodatkowo nie dawałaby też pewności, co do wybrania optymalnego rozwiązania z punktu widzenia założonych kryteriów.

Слайд 16

Слайд 17

Rozwiązanie w solverze
Przykładowo mamy 10 różnych miejscowości i musimy każdą z

nich odwiedzić przy tym robiąc jak najmniej kilometrów żeby ograniczyć koszty, jako przekątną macierzy wstawiamy jakieś duże liczby bo wtedy solver jako rozwiązanie pokaże nam te własne dane.

Слайд 18

Układając trasę w kolejności od 1 do 10 za pomocą funkcji

indeks.

Jako sumę kilometrów otrzymujemy 769km czyli wynik do którego minimalizacji będziemy dążyli.

Слайд 19

Слайд 20

Слайд 21

Jedynym warunkiem jaki przyjmujemy jest, że komórki które aktualnie przyjmują wartości

od 1-10 muszą być różne czyli wybieramy warunek DIF czyli AllDifferent czyli każda z liczb musi być różna od siebie. A jako metodę wybieramy Evolutionary i dajemy Solve.

Слайд 22

Wynik wyszedł 318km, przypomnijmy poprzedni przy trasie od 1-10 to

769km a to jest 2,41 razy trasy mniej a więc nasz Salesman zaoszczędzi dosyć sporo na tej trasie. Solverowi zajmuje to około kilkudziesięciu sekund a musi rozparzyć 9! możliwości czyli 362 880 więc człowiekowi z kalkulatorem i kartką zajęło by to prawdopodobnie więcej czasu niż przejechanie tej całej trasy ☺

Planowanie tras z wykorzystaniem narzędzia Solver

Содержание

Znaczenie słowa komiwojażer ?Wyobraźmy sobie akwizytora, który podróżuje od miasta do

WprowadzeniePodejmowanie decyzji we współczesnej organizacji jest procesem rozwiązywania złożonych problemów, z których