Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36
The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the impro...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2021
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/155 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479459031941120 |
|---|---|
| author | Barbolina, Tetiana |
| author_facet | Barbolina, Tetiana |
| author_institution_txt_mv | [
{
"author": "Tetiana Barbolina",
"institution": "Полтавський національний педагогічний університет імені В. Г. Короленка, вул. Остроградського, 2, 36003, Полтава"
}
] |
| author_sort | Barbolina, Tetiana |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2021-09-06T07:57:12Z |
| description | The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the improvement of the polynomial algorithm for solving the specified class of problems. This algorithm foresees solving a finite sequence of linear unconstrained problems of combinatorial optimization on arrangements. The modification of the algorithm is based on the use of estimates of the objective function on the feasible set. This allows to exclude some of the problems from consideration and reduce the number of problems to be solved. The numerical experiments confirm the practical efficiency of the proposed approach.
References
Papadimitriou, C. H., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Courier Corporation.
Korte, B. H., Vygen, J. (2008). Combinatorial optimization: theory and algorithms, Berlin Heidelberg: Springer.
Stoyan, Yu. G., Iemets, O. O. (1993). Theory and methods of Euclidean combinatorial optimization. Kyiv: Instytut systemnykh doslidzhen osvity.
Iemets, O. A., Barbolina, T. N. (2017). Polynomial method for solving unconditional linear-fractional problem of combinatorial optimization on arrangements. Journal of Automation and Information Sciences, 49(3), 46-56. DOI doi.org/10.1615/jautomatinfscien.v49.i3.60
Barbolina, T. (2020). Improvement of the polynomial method for solving unconstrained linear-fractional combinatorial optimization problems on arrangements. Collection of researcher works of teachers, students, graduate students of the faculty of physics and mathematics, Poltava: Astraya
Iemets, O. A., Barbolina, T. N. (2017). Properties of combinatorial optimization unconstrained problems on arrangements with linear and linear-fractional objective functions. Journal of Automation and Information Sciences, 49(1), 41 – 52. DOI doi.org/10.1615/jautomatinfscien.v49.i1.40
|
| doi_str_mv | 10.15407/fmmit2021.32.055 |
| first_indexed | 2026-06-09T01:06:36Z |
| format | Article |
| fulltext | |
| id | oai:ojs2.www.fmmit.lviv.ua:article-155 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:06:36Z |
| publishDate | 2021 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-1552021-09-06T07:57:12Z Estimates of objective function minimum for solving linear fractional unconstrained combinatorial optimization problems on arrangements: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 Barbolina, Tetiana евклідова комбінаторна оптимізація дробово-лінійна оптимізація задачі комбінаторної оптимізації поліноміальний алгоритм Euclidean combinatorial optimization fractional-linear optimization combinatorial optimization problems polynomial algorithm The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the improvement of the polynomial algorithm for solving the specified class of problems. This algorithm foresees solving a finite sequence of linear unconstrained problems of combinatorial optimization on arrangements. The modification of the algorithm is based on the use of estimates of the objective function on the feasible set. This allows to exclude some of the problems from consideration and reduce the number of problems to be solved. The numerical experiments confirm the practical efficiency of the proposed approach. References Papadimitriou, C. H., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Courier Corporation. Korte, B. H., Vygen, J. (2008). Combinatorial optimization: theory and algorithms, Berlin Heidelberg: Springer. Stoyan, Yu. G., Iemets, O. O. (1993). Theory and methods of Euclidean combinatorial optimization. Kyiv: Instytut systemnykh doslidzhen osvity. Iemets, O. A., Barbolina, T. N. (2017). Polynomial method for solving unconditional linear-fractional problem of combinatorial optimization on arrangements. Journal of Automation and Information Sciences, 49(3), 46-56. DOI doi.org/10.1615/jautomatinfscien.v49.i3.60 Barbolina, T. (2020). Improvement of the polynomial method for solving unconstrained linear-fractional combinatorial optimization problems on arrangements. Collection of researcher works of teachers, students, graduate students of the faculty of physics and mathematics, Poltava: Astraya Iemets, O. A., Barbolina, T. N. (2017). Properties of combinatorial optimization unconstrained problems on arrangements with linear and linear-fractional objective functions. Journal of Automation and Information Sciences, 49(1), 41 – 52. DOI doi.org/10.1615/jautomatinfscien.v49.i1.40 Стаття присвячена вивченню одного класу задач евклідової комбінаторної оптимізації — задач комбінаторної оптимізації на загальній множині розміщень з дробово-лінійною цільовою функцією та без додаткових (некомбінаторних) обмежень. У роботі обгрунтовано удосконалення поліноміального алгоритму розв’язування зазначеного класу задач, який передбачає розвязування скінченної послідовності лінійних безумовних задач комбінаторної оптимізації на розміщеннях. В основу модифікації алгоритму покладено використання оцінок цільової функції на допустимій множині, що дозволяє виключити з розгляду частину задач і зменшити кількість задач, що підлягають розв’язуванню. Проведені числові експерименти підтверджують практичну ефективність пропонованого підходу. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021-07-06 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/155 10.15407/fmmit2021.32.055 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 32 (2021): Physico-mathematical modeling and informational technologies, 2021, Issue 32; 32-36 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 32 (2021): Фізико-математичне моделювання та інформаційні технології, 2021, Вип. 32; 32-36 2617-5258 1816-1545 10.15407/fmmit2021.32 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/155/145 Авторське право (c) 2021 Tetiana Barbolina (Автор) |
| spellingShingle | евклідова комбінаторна оптимізація дробово-лінійна оптимізація задачі комбінаторної оптимізації поліноміальний алгоритм Barbolina, Tetiana Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title | Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_alt | Estimates of objective function minimum for solving linear fractional unconstrained combinatorial optimization problems on arrangements: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_full | Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_fullStr | Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_full_unstemmed | Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_short | Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| title_sort | урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36 |
| topic | евклідова комбінаторна оптимізація дробово-лінійна оптимізація задачі комбінаторної оптимізації поліноміальний алгоритм |
| topic_facet | евклідова комбінаторна оптимізація дробово-лінійна оптимізація задачі комбінаторної оптимізації поліноміальний алгоритм Euclidean combinatorial optimization fractional-linear optimization combinatorial optimization problems polynomial algorithm |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/155 |
| work_keys_str_mv | AT barbolinatetiana estimatesofobjectivefunctionminimumforsolvinglinearfractionalunconstrainedcombinatorialoptimizationproblemsonarrangementsfizmatmodelinftehnol2021323236 AT barbolinatetiana urahuvannâocínokmínímumucílʹovoífunkcííprirozvâzuvannídrobovolíníjnihbezumovnihzadačkombínatornoíoptimízacíínarozmíŝennâfizmatmodelinftehnol2021323236 |