Zeszyt 3/ 2012, Artykuł 1

Autorzy: Izabela Kudelska

Tytuł: METODY WYKORZYSTYWANIA ROZWIąZANIA QUADRATIC ASSIGNMENT PROBLEM

Słowa kluczowe: QAP, problem kwadratowego przydziału, algorytm podziału i ograniczeń, algorytmy genetyczne, symulowane wyżarzanie, algorytm Tabu Search

Streszczenie:

Wstęp: Kwadratowy Problem Przydziału (QAP) jest jednym z najciekawszych zagadnień optymalizacji kombinatorycznej. Został przedstawiony przez Koopmana i Beckamanna w roku 1957, jako matematyczny model lokalizacji niepodzielnych zadań. Problem ten należy do klasy zagadnień NP.-trudnych. Wymusza to stosowanie do jego rozwiązania metod przybliżonych już dla zadań o niewielkim rozmiarze (powyżej 30).

Mimo że jest ono znacznie trudniejsze niż inne zagadnienia optymalizacji kombinatorycznej, to cieszy się powszechnym zainteresowaniem, ponieważ modeluje ważną klasę problemów decyzyjnych.

Metody: Dyskusji poddano narzędzia sztucznej inteligencji, które pozwoliły rozwiązać problem QAP, między innymi są to: algorytmy genetyczne, Tabu Search, Branch and Bound

Wyniki i wnioski: Sam problem bezpośrednio nie powstał jako model pewnych działań, jednak znalazł on swoje zastosowanie w wielu dziedzinach. Przykładowymi  zastosowaniami problemu jest: rozmieszczenie budynków na kampusie uczelnianym, projektowanie rozmieszczenia elementów elektronicznych w układach o wielkiej skali integracji (VLSI), projekt szpitala, rozmieszczenie klawiszy na klawiaturze.

Pełen tekst dostępny w języku angielskim w formacie: Adobe Acrobat pdf artykuł nr 1 - pdf

Abstract in English Abstract in English.

Zusammenfassung in Deutsch Zusammenfassung in Deutsch.

© Wyższa Szkoła Logistyki, ul.E.Estkowskiego 6, 61-755 Poznań, tel. 061 850 47 81, fax. 061 850 47 89