Wydział Mechaniczny Kierunek: Mech. i Bud. Masz. |
Laboratorium z podstaw eksploatacji. |
||
Ćw. nr 5 .
|
Temat: Planowanie optymalnego ruchu transportu.
|
||
Gr. IZK-K02b
|
Imię i nazwisko: Paweł Urban |
Rok akademicki: 1996/97 |
|
Data wykonania
|
Ocena |
Data zaliczenia |
Podpis prowadzącego |
11.12.96
|
|
|
|
1.Cel ćwiczenia
Celem ćwiczenia jest nabycie umiejętności rozwiązywania problemów decyzyjnych przy użyciu modeli matematycznych, na przykładzie `problemu komiwojażera' (przy pomocy uproszczonego modelu matematycznego - metodą Little'a).
2.Dane wyjściowe.
Dla pewnej sieci transportu wewnątrzzakładowego (wybiera się 10 punktów
dostawczych), wyznaczyć optymalną drogę okrężną pojazdu dostawczego przybliżoną
metodą Little'a.
Warunki:
- do każdego punktu dostawczego muszą być min.3 drogi
- na schemacie min.3 drogi jednokierunkowe
- w każdym punkcie dostawczym możemy być tylko jeden raz
- każdą drogę możemy wykorzystać tylko jeden raz
- są drogi jednokierunkowe oraz dwukierunkowe.
Rys1. Szkic sieci transportu wewnątrzzakładowego.
Dla badanych punktów odbiorczych sporządzamy tabelę odległości - tabelę danych . Długości odcinków wyrażone są w kilometrach.
Tabela nr. 1
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
---- |
4 |
8 |
12 |
3 |
8 |
10 |
10 |
6 |
6 |
2 |
4 |
----- |
4 |
8 |
3 |
3 |
6 |
6 |
6 |
8 |
3 |
8 |
4 |
----- |
4 |
6 |
3 |
3 |
6 |
8 |
11 |
4 |
12 |
8 |
4 |
----- |
10 |
6 |
3 |
8 |
11 |
14 |
5 |
7 |
3 |
6 |
10 |
----- |
4 |
8 |
7 |
4 |
5 |
6 |
8 |
7 |
3 |
6 |
4 |
----- |
4 |
4 |
5 |
8 |
7 |
12 |
6 |
3 |
3 |
8 |
4 |
----- |
5 |
8 |
12 |
8 |
10 |
6 |
6 |
8 |
7 |
4 |
5 |
----- |
4 |
8 |
9 |
6 |
6 |
10 |
11 |
4 |
8 |
8 |
4 |
----- |
4 |
10 |
6 |
8 |
11 |
14 |
5 |
8 |
12 |
8 |
4 |
----- |
Zgodnie z metodą Little'a, przekształcam tabelę danych tak, aby w każdym
wierszu i w każdej kolumnie był co najmniej jeden element zerowy `0', co obrazuje
tabela nr. 2. Przekształcenie to odbywa się w ten sposób, że od wszystkich wyrazów
danego wiersza (kolumny) odejmujemy wyraz najmniejszy.
Tabela nr. 2 9 ⇒ 10
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
--- |
1 |
5 |
9 |
01 |
5 |
7 |
7 |
3 |
7 |
2 |
01 |
--- |
1 |
5 |
00 |
00 |
3 |
3 |
3 |
5 |
3 |
4 |
1 |
--- |
1 |
3 |
00 |
00 |
3 |
5 |
8 |
4 |
8 |
5 |
1 |
--- |
7 |
3 |
00 |
5 |
8 |
11 |
5 |
3 |
02 |
3 |
7 |
--- |
1 |
5 |
4 |
1 |
2 |
6 |
4 |
4 |
01 |
3 |
1 |
--- |
1 |
1 |
2 |
5 |
7 |
8 |
3 |
1 |
0 |
5 |
1 |
--- |
2 |
5 |
9 |
8 |
5 |
2 |
2 |
4 |
3 |
00 |
1 |
--- |
00 |
4 |
9 |
1 |
2 |
6 |
7 |
00 |
4 |
4 |
01 |
--- |
02 |
10 |
1 |
4 |
7 |
10 |
1 |
4 |
8 |
4 |
01 |
--- |
Skreślam drogę 10 ⇒ 9
Następnie wyszukuję najmniejsze wartości w wierszach i kolumnach każdego elementu
zerowego i przyporządkować elementom zerowym sumy tych wartości jako indeksy
np.01. Wpisujemy ją jako indeks danego elementu zerowego do tabeli. Element zerowy o
największym wykładniku jest elementem rozwiązującym, co zaznaczamy w tabeli jako
linią ciągłą. W każdej tabeli skreślamy znakiem X jeden z elementów nie znajdujący się
na skreślonym wierszu i kloumnie, który mógłby być nie chcianym przez nas skrótem
drogi. Pomijając skreślony wiersz i kolumnę oraz wpisując w miejsce skreślonego
znaku'—`,budujemy następną tabelę. Tabela nr. 3 zawiera pierwsze rozwiązanie.
Tabela nr. 3 5 ⇒ 2
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
--- |
1 |
5 |
9 |
01 |
5 |
7 |
6 |
3 |
2 |
02 |
--- |
1 |
5 |
00 |
00 |
3 |
2 |
3 |
3 |
4 |
1 |
--- |
1 |
3 |
00 |
00 |
2 |
5 |
4 |
8 |
5 |
1 |
--- |
7 |
3 |
00 |
4 |
8 |
5 |
3 |
02 |
3 |
7 |
--- |
1 |
5 |
3 |
1 |
6 |
4 |
4 |
00 |
3 |
1 |
--- |
1 |
01 |
2 |
7 |
8 |
3 |
1 |
0 |
5 |
1 |
--- |
1 |
5 |
8 |
5 |
2 |
2 |
4 |
3 |
00 |
1 |
--- |
01 |
10 |
1 |
4 |
7 |
10 |
1 |
4 |
8 |
3 |
--- |
Skreślam drogę 2⇒ 5.
Tabela nr.4 1 ⇒ 5
|
1 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
--- |
5 |
9 |
04 |
5 |
7 |
6 |
3 |
2 |
01 |
1 |
5 |
--- |
00 |
3 |
2 |
3 |
3 |
4 |
--- |
1 |
3 |
00 |
00 |
2 |
5 |
4 |
8 |
1 |
--- |
7 |
3 |
01 |
4 |
8 |
6 |
4 |
00 |
3 |
1 |
--- |
1 |
01 |
2 |
7 |
8 |
1 |
01 |
5 |
1 |
--- |
1 |
5 |
8 |
5 |
2 |
4 |
3 |
00 |
1 |
--- |
01 |
10 |
1 |
7 |
10 |
1 |
4 |
8 |
3 |
--- |
Skreślam drogę 2 ⇒ 1.
Tabela nr. 5 10 ⇒ 1
|
1 |
3 |
4 |
6 |
7 |
8 |
9 |
2 |
--- |
1 |
5 |
01 |
3 |
2 |
3 |
3 |
3 |
--- |
1 |
00 |
00 |
2 |
5 |
4 |
7 |
1 |
--- |
3 |
01 |
4 |
8 |
6 |
3 |
00 |
3 |
--- |
1 |
01 |
2 |
7 |
7 |
1 |
01 |
1 |
--- |
1 |
5 |
8 |
4 |
2 |
4 |
00 |
1 |
--- |
02 |
10 |
06 |
7 |
10 |
4 |
8 |
3 |
--- |
Tabela nr. 6 6 ⇒ 3
|
3 |
4 |
6 |
7 |
8 |
9 |
2 |
1 |
5 |
01 |
3 |
2 |
3 |
3 |
--- |
1 |
00 |
00 |
2 |
5 |
4 |
1 |
--- |
3 |
01 |
4 |
8 |
6 |
01 |
3 |
--- |
1 |
00 |
1 |
7 |
1 |
01 |
1 |
--- |
1 |
5 |
8 |
2 |
4 |
00 |
1 |
--- |
01 |
Skreślam drogę 3 ⇒ 6.
Tabela nr. 7 8 ⇒ 9
|
4 |
6 |
7 |
8 |
9 |
2 |
5 |
01 |
3 |
1 |
3 |
3 |
1 |
--- |
01 |
1 |
5 |
4 |
--- |
3 |
03 |
3 |
8 |
7 |
01 |
1 |
--- |
01 |
5 |
8 |
4 |
00 |
1 |
--- |
03 |
Tabela nr. 8 4 ⇒ 7
|
4 |
6 |
7 |
8 |
2 |
5 |
02 |
3 |
1 |
3 |
1 |
--- |
01 |
1 |
4 |
--- |
3 |
03 |
3 |
7 |
01 |
1 |
--- |
01 |
Skreślam drogę 7 ⇒ 4.
Tabela nr. 9 3 ⇒ 4
|
4 |
6 |
8 |
2 |
4 |
02 |
1 |
3 |
05 |
--- |
1 |
7 |
--- |
1 |
01 |
Tabela nr. 10 2 ⇒ 6 , 7 ⇒ 8
|
6 |
8 |
2 |
02 |
1 |
7 |
1 |
01 |
Rys. 2. Schemat najkrótszej drogi okrężnej.
Najkrótsza droga wyniosła 6 + 3 + 3 + 3 + 3 + 4 + 3 + 5 + 4 + 4 = 38 [km]