176 177

Tablica 3.4S

Chromosom	Numery naruszonych ograniczeń	Długość trasy	Kara	Wartość funkcji przystosowania
c2,		72	0	72
C22	(3.15), (3.16), (3.18). (3.20)	77	400	477
	(3.15), (3.21)	50	200	250
C?4	(3.13), (3.15), (3.19), (3.21)	31	400	431
Ot*	(3.14), (3.17), (3.27)	43	300	343
	(3.17), (3.18), (3.19), (3.20), (3.31)	77	500	577
Suma				2 150

W ten sposób zakończyliśmy symulację działania algorytmu genetycznego w trakcie jednej iteracji. Analogiczne postępowanie powtarzamy w kolejnych iteracjach. W każdej iteracji zapamiętujemy najlepsze uzyskane rozwiązanie oraz średnią wartość funkcji przystosowania. O ile najlepsze rozwiązanie otrzymane w danej iteracji jest lepsze od najlepszego dotychczas uzyskanego rozwiązania, dokonujemy jego wymiany, jeżeli natomiast jest gorsze, pozostawiamy najlepsze uzyskane dotychczas rozwiązanie bez zmian.

Nie ma praktycznej możliwości rozwiązania zadania z wykorzystaniem algorytmu genetycznego za pomocą symulacji odręcznej. Przyjmując warunek zakończenia algorytmu jako przeprowadzenie 400 iteracji możemy się spodziewać, że w trakcie działania algorytmu genetycznego uda się wygenerować rozwiązanie optymalne zadania wyjściowego lub też rozwiązanie bardzo do niego zbliżone¹.

3.7. Przykłady wykorzystania zadania transportowego

Poniżej przedstawimy trzy przykłady zastosowań zadania transportowego. Przykład 3.6 dotyczy minimalizacji pustych przebiegów. Przykład 3.7 łączy ze sobą problematykę produkcji i transportu, stąd nosi nazwę zagadnienia transpor-towo-produkcyjnego. Przykład 3.8 dotyczy przydziału zadań, jakie mają wykonać doradcy firmy konsultingowej, nie jest zatem związany z problematyką transportu. Istnieje jednak wiele zadań, które mają strukturę zagadnienia transportowego, co można wykorzystać w trakcie ich rozwiązywania.

Zadania transportowe rozwiązujemy, stosując program TRANS.EXE. Dalsze zadania problemowe i numeryczne, związane z zagadnieniem transportowym, znajdują się na CD-ROM-ie dołączonym do książki.

3.7.1. Minimalizacja pustych przebiegów

Przykład 3.6'

Mamy układ 8 punktów geograficznych, między którymi istnieją połączenia komunikacyjne. Z każdego z tych punktów wywozi się i do każdego prżywozi określoną masę towaru, wykorzystując do przewozu samochody o tej samej ładowności; odległości między miastami zapisano w tablicy 3.46.

Przewidywany przewóz masy towaru między tymi miastami, mierzony liczbą samochodów o określonej ładowności, przedstawiono w tablicy 3.47.

Dla rozpatrywanych miast wywóz nie jest równy przywozowi. Należy określić taki plan przebiegu pustych samochodów, przy którym łączna liczba samo-chodokilometrów pustych przebiegów będzie minimalna, przy zaopatrzeniu każdego miasta, w którym wywóz przekracza przywóz, w niezbędną liczbę pustych samochodów.

1

Istotnie, korzystając z pakietu PGA 4.0 Petera Rossa rozwiązanie optymalne otrzymywane wykonując jedynie 190 iteracji.

Dane do przykładu zaczerpnięto z książki Z. Czerwińskiego, Matematyku na usługach ekonomii, PWN. Warszawa 1984.