Celem niniejszej rozprawy jest przedstawienie pewnej me­tody rozwiązywania wybranych zagadnień z zakresu badań operacyjnych, określanych jako zagadnienia programowania dyskretnego. Praca jest skupiona na poszukiwaniu bardziej efektywnych metod rozwiązywania sformułowanych zadań. Rozprawa rozpoczyna się od sformułowania za­dań operacyjnych oraz przeprowadzeniu analizy porównawczej ogólnych dokładnych metod ich rozwiązania. Następnie, podano teoretycz­ne podstawy metody dróg elementarnych w postaci opisu algeb­ry dróg elementarnych. W języku tej algebry sformułowano i udowodniono warunek konieczny i dostateczny istnienia cyklu Hamiltona w dowolnym grafie skończonym. Uogólniając wyżej wspomniane twierdzenie, podano warunek kanoniczny i dostateczny istnie­nia drogi (łańcucha) Hamiltona w dowolnym grafie skończonym. Opisano również metodę dróg elementarnych dla przy­padku zagadnienia komiwojażera oraz modyfikacje, jakim powinna ulec ta metoda w przypadku innych zadań operacyjnych oraz podano schemat blokowy ogólnego algorytmu rozwiązania. W części eksperymentalnej przytoczono i opisa­no algorytm rozwiązania zagadnienia komiwojażera oraz wyniki badania tego algorytmu na maszynie cyfrowej ZAM-41. Podano oszacowania zajętości pamięci oraz szybkości działania tego algorytmu.
Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)
Algebra dróg elementarnych i jej zastosowanie do badań operacyjnych (PD-1971-01)
naukowcy
studenci
uczniowie
algebra dróg elementarnych
Instytut Badań Systemowych PAN w Warszawie
discrete programming
elementary paths algebra
problem komiwojażera
programowanie dyskretne
traveling salesman problem
badania operacyjne
Operations Research