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

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

Б. И. Юхименко, Н. П. Волкова

Анотація


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

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


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

Повний текст:

PDF (Русский)

Посилання


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.


Пристатейна бібліографія ГОСТ


Land A. H. An automatic method of solving discrete programming probems / A. H. Land, A. G. Doig // Econometrica. – 1960. – V. 28, №3. – P. 497–520.

Little J. D. C. An algorithm for the traveling salesman problem / J. D. C. Little, K. G. Murty, C. Karel // Operat. Res. – 1963. – V. 11, №6. – P. 972-989.

Меламед И. И. Задача коммивояжера. Точные алгоритмы / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автоматика и телемеханика. – 1989. – №10. – с. 3-29.

Меламед И. И. Задача коммивояжера. Приближенные алгоритмы / И. И. Меламед, С. И. Сергеев, И. Х. Сигал // Автоматика и телемеханика. – 1989. - №11. – с. 3–20.

Balas E. An additive algorithm for soving linear programs with zero-one variables // Operat. Res. – 1965. – V. 13, №4. – P. 517–546.

Юхименко Б. И. Ускоренный алгоритм метода ветвей и границ для решения задачи целочисленного линейного программирования // Тр. Одес. политехн. ун-та. – 2004. – Вып. 2. – с. 223–226.

Юхименко Б. И. Сравнительная характеристика алгоритмов метода ветвей и границ для решения задач целочисленного линейного программирования / Б. И. Юхименко, Ю. Ю. Козина // Тр. Одес. политехн. ун-та. – 2005. – Вып. 2. – с. 199–204.

Karte B. Kombinatorische Optimierung und algorithmische Principien // Okonomische Prognose, Entscheidungs und Gleichgewichtsmodelle. Weinheim : VCH Verlangsgesellschschact, 1986. – P. 286–341.

Дюбин Г. Н. Жадные алгоритмы для задачи о ранце: поведение в среднем / Г. Н. Дюбин, А. А. Корбут // Сибирский журнал индустриальной математики. Том II, №2(4). – 1999. – c. 68–93.

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

Штобва С. Д. Муравьиные алгоритмы: Теория и применение // Программирование. – 2005, №4. – с. 1–16.

Сигал И. Х. Введение в прикладное дискретное программирование / И. Х. Сигал, А. П. Иванова. – М. : Физматлит, 2007. – с. 304.





ISSN: 2519-206X (Print)

DOI: 10.18524/2519-206X