Наближені алгоритми розв'язання задачі про багатовимірний ранець

Автор(и)

  • Б. И. Юхименко Одеський національний політехнічний університет, Україна
  • Н. П. Волкова Одеський національний політехнічний університет, Україна

DOI:

https://doi.org/10.18524/2519-206x.2017.2(30).135745

Ключові слова:

комбінаторні методи, наближене рішення, багатовимірна задача про ранці, жадібний алгоритм, мурашина колонія, рекорд, відсіювання

Анотація

Робота присвячена створенню комбінаторних алгоритмів розв'язання багатовимірної задачі про ранці. Показана актуальність проблеми. Дан невеликий історичний аналіз досліджень і публікацій комбінаторних алгоритмів дискретної оптимізації. Звернуто увагу на складність обчислень при вирішенні такого роду завдань. Припущено використовувати наближені алгоритми. В роботі наведені три способи отримання наближених рішень, розроблених на ідеях жадібного алгоритму, генетичного алгоритму мурашиної колонії, а також деякого комбінованого підходу. Сутність алгоритмів полягає в тому, що конкретизація компонент вектора рішень слідує сформованої пріоритетної черзі. Відповідно до неї присвоюється значення <> поки це допустимо. Отримана послідовність залежить від використаної ідеї. Значення цільової функції (рекорд) отриманого рішення є основою відсіювання варіантів при його поліпшенні. Саме поліпшення здійснюється через подвійний підхід комбінаторних алгоритмів. Наведено числовий приклад.

Посилання

Land, A. H. & Doig, A. G. (1960). An automatic method of solving discrete programming probems, Econometrica, vol. 28, №3, pp. 497–520.

Little, J. D. C., Murty & K. G., Karel, C. (1963). An algorithm for the traveling salesman problem, Operat. Res., vol. 11, №6, pp. 972–989.

Melamed, I. I., Sergeev, S. I. & Sigal, I. H. (1989). Zadacha kommivoyazhera. Tochnyie algoritmyi, Avtomatika i telemehanika, no. 10, pp. 3–29.

Melamed, I. I., Sergeev, S. I. & Sigal, I. H. (1989). Zadacha kommivoyazhera. Priblizhennyie algoritmy, Avtomatika i telemehanika, no. 11, pp. 3–20.

Balas, E. (1965). An additive algorithm for soving linear programs with zero-one variables, Operat. Res., vol. 13, no. 4, pp. 517–546.

Yuhimenko, B. I. (2004). Uskorennyiy algoritm metoda vetvey i granits dlya resheniya zadachi tselochislennogo lineynogo programmirovaniya, Tr. Odes. politehn. un-ta, issue 2, pp. 223–226.

Yuhimenko, B. I. & Kozinam, Yu. Yu. (2005). Sravnitelnaya harakteristika algoritmov metoda vetvey i granits dlya resheniya zadach tselochislennogo, lineynogo programmirovaniya, Tr. Odes. politehn. un-ta, issue 2, pp. 199–204.

Karte, B. (1986). Kombinatorische Optimierung und algorithmische Principien, Okonomische Prognose-, Entscheidungs- und Gleichgewichtsmodelle, Weinheim : VCH Verlangsgesellschschact, pp. 286–341.

Dyubin, G. N. & Korbut, A. A. (1999). Zhadnyie algoritmyi dlya zadachi o rantse: povedenie v srednem, Sibirskiy zhurnal industrialnoy matematiki, vol. II, no. 2(4), pp. 68–93.

Dorigo, M. (1992). Optimization, Learning and Natural Algorithms, PhD Thesis. Dipertamento di Ellettronica, Politechnico Di Milano, Italy, 140 p.

Shtobva, S. D. (2005). Muravinyie algoritmyi: Teoriya i primenenie, Programmirovanie, no. 4, pp. 1–16.

Sigal, I. H. & Ivanova, A. P. (2007). Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, Moscow, 304 p.

##submission.downloads##

Опубліковано

2017-06-18

Номер

Том 22 № 2(30) (2017)

Розділ

Математика та механіка

Ліцензія

Авторське право (c) 2020 Дослідження в математиці і механіці

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution-ShareAlike 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Attribution-NonCommercial 4.0 International (CC BY-NC 4.0).
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).