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]