Оптимізація для одного класу комбінаторних задач в умовах невизначеності
DOI:
https://doi.org/10.20535/1560-8956.1.2019.178233Ключові слова:
Комбінаторна оптимізація, невизначеність, ймовірність, ефективний алгоритм, розв’язання невизначеності, ПДС-алгоритм, NP-трудні задачіАнотація
Для досить загального класу задач комбінаторної оптимізації, функціонал яких містить лінійну згортку ваг і довільних числових характеристик допустимого розв’язку, формалізуються поняття невизначеності, компромісного розв’язку, компромісні критерії та умови. Наводяться алгоритми знаходження компромісних розв’язків як оригінальна реалізація відомої ідеї лінійної згортки критеріїв. Ефективність запропонованих алгоритмів однозначно визначається ефективністю розв’язання задачі комбінаторної оптимізації в детермінованій постановці. Показано, що отримані раніше ефективні ПДС-алгоритми для NP-трудних задач комбінаторної оптимізації – мінімізація сумарного зваженого запізнення виконання завдань одним приладом, мінімізація сумарного зваженого моменту закінчення виконання взаємозв’язаних завдань (довільний ациклічний орієнтований граф) одним приладом – дозволяють ефективно розв’язувати ці задачі в умовах невизначеності.
Библ. 7
Посилання
Garey M.R., Johnson D.S. Computers and Intractability: a Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Co., 1979. 347 p.
Zgurovsky M.Z., Pavlov A.A. Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications. 1st ed. Cham: Springer, 2019. 526 p. DOI:10.1007/978-3-319-98977-8
Уткин Л.В. Лекции по курсу «Принятие решений в условиях неопределенности». Глава 6 «Многокритериальное принятие решений» [Електронний ресурс] // http://levvu.narod.ru. 2007. URL: http://levvu.narod.ru/Papers/Multicrit.pdf. Дата обращения: 15.02.2019
Ehrgott M. Multicriteria Optimization. 2nd edition. Berlin, Heidelberg: Springer, 2005. 336 p. DOI: 10.1007/3-540-27659-9
Ногин В.Д. Линейная свертка критериев в многокритериальной оптимизации // Искусственный интеллект и принятие решений. 2014. № 4. C.73-82.
Кравцов М.К., Янушкевич О.А. Линейная свертка критериев в бикритериальной оптимизации // Известия высших учебных заведений. Математика. 1998. № 12 (439). C.63-70 URL: http://mi.mathnet.ru/rus/ivm/y1998/i12/p63
Меламед И.И. Линейная свертка критериев в многокритериальной оптимизации // Автоматика и телемеханика. 1997. № 9. C.119-125 URL: http://mi.mathnet.ru/eng/at/y1997/i9/p119
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у нашому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована нашим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у нашому журналі.
3. Політика журналу дозволяє і заохочує розміщення рукопису роботи авторами в мережі Інтернет (наприклад, на arXiv.org або на особистих веб-сайтах). Причому рукописи статей можуть бути розміщенні у відкритих архівах як до подання рукопису до редакції, так і під час його редакційного опрацювання. Це сприяє виникненню продуктивної наукової дискусії, позитивно позначається на оперативності ознайомлення наукової спільноти з результатами Ваших досліджень і як наслідок на динаміці цитування вже опублікованої у журналі роботи. Детальніше про це: The Effect of Open Access.
