Algebraiczne zagadnienia przydziału

Widok

Metadane zasobu

Tytuł	Algebraiczne zagadnienia przydziału Wariant tytułu: Algebraic assignment problems
Osoby	Autorzy: Grażyna Grygiel Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	Zagadnienie przydziału sformułowano tu w uporządkowanych półpierścieniach. Takie uogólnienie obejmuje klasyczne liniowe i minimaksowe zadania przydziału, zagadnienia leksykograficzne, typu czas-koszt, różne warianty Σk – zagadnień przydziału. Skonstruowany jest algorytm wielomianowy, wykazana jego zbieżność. Dla rozpatrywanego problemu optymalizacji udowodnione jest twierdzenie o dualności w terminach systemów niezależności. Podana jest przy tym klasyfikacja tych systemów. Praca zawiera również wyniki przeprowadzonych eksperymentów obliczeniowych, testujących rozmaite heurystyki, oraz formułuje wnioski co do ich efektywności. (Polski) Opis w innym języku: An assignment problem has been formulated in ordered semirings - a generalization that encompasses classical linear and minimax assignment problems, lexicographical, time-cost, as well as Σk – assignment problems. A polynomial algorithm has been constructed and its convergence has been proved. For the optimization problems in question a duality theorem is proved in terms of independence systems. Their classification has been given. The thesis contains also results of various numerical experiments when manifold heuristics were tested, and conclusions regarding efficiency of the heuristics has been presented. (Angielski)
Słowa kluczowe	"dualność"@pl, "zagadnienie przydziału"@pl, "optymalizacja w półgrupach uporządkowanych"@pl, "system niezależny"@pl, "allocation problem"@en, "duality"@en
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / automatyka i robotyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 1994 Liczba stron: 112 Promotor: Stanisław Walukiewicz Język zasobu: Polski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Justyna Kupczak Data udostępnienia: 16-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Grażyna Grygiel. Algebraiczne zagadnienia przydziału. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Dwie interpretacje dualności w programowaniu liniowym. (PN-1985-02)

Stanisław Walukiewicz, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)