Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements
In the paper Euclidean problems of lexicographic combinatorial; optimization are discussed. These problems are to find lexicographically minimal (for minimization problems) or lexicographically maximal (for maximization problems) points among those that give the extremum of the objective function on...
Saved in:
| Date: | 2019 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Online Access: | http://mcm-math.kpnu.edu.ua/article/view/174058 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543227086110720 |
|---|---|
| author | Барболіна, Тетяна Миколаївна |
| author_facet | Барболіна, Тетяна Миколаївна |
| author_sort | Барболіна, Тетяна Миколаївна |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2020-01-20T08:43:16Z |
| description | In the paper Euclidean problems of lexicographic combinatorial; optimization are discussed. These problems are to find lexicographically minimal (for minimization problems) or lexicographically maximal (for maximization problems) points among those that give the extremum of the objective function on a given Euclidean combinatorial set. The properties of linear and linear-fractional problems of lexicographic combinatorial optimization on a general set of arrangements are substantiated. The results obtained in the work are based on the previously known criteria of extremals of linear and linear-fractional functions on arrangements: any extremal is an element of certain set of polyarrangements (for linear problems the form of the extremal set is established explicitly, for linear-fractional problems the polyarrangement set is formed on the basis of some known extremal). In the paper we substantiate the form of points that are an lexicographic minimal and lexicographic maximal of linear function on the general set of arrangements. In particular if elements of multiset are in nondecreasing order, coefficients of objective function are in nonincreasing order and s is the least index such that corresponding coefficient of objective function is negative, tehn lexicographic minimal if formed as s – 1 first and k – s + 1 (k is the dimension of space) last elements of multiset which are in nondecreasing order. For problems with linear-fractional function we obtain the method of forming solution of lexicographic combinatorial problem on arrangements, if any minimal (for minimization problems) or any maximal (for maximization problems) of objective function on given set of arrangements is known. In this case ordering of components of the extremal is carried out taking into account ordering for nonincreasing of coefficients of special linear function |
| first_indexed | 2025-07-17T10:43:09Z |
| format | Article |
| id | mcm-mathkpnueduua-article-174058 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:43:09Z |
| publishDate | 2019 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-1740582020-01-20T08:43:16Z Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements Властивості Евклідових задач лексикографічної комбінаторної оптимізації на розміщеннях Барболіна, Тетяна Миколаївна In the paper Euclidean problems of lexicographic combinatorial; optimization are discussed. These problems are to find lexicographically minimal (for minimization problems) or lexicographically maximal (for maximization problems) points among those that give the extremum of the objective function on a given Euclidean combinatorial set. The properties of linear and linear-fractional problems of lexicographic combinatorial optimization on a general set of arrangements are substantiated. The results obtained in the work are based on the previously known criteria of extremals of linear and linear-fractional functions on arrangements: any extremal is an element of certain set of polyarrangements (for linear problems the form of the extremal set is established explicitly, for linear-fractional problems the polyarrangement set is formed on the basis of some known extremal). In the paper we substantiate the form of points that are an lexicographic minimal and lexicographic maximal of linear function on the general set of arrangements. In particular if elements of multiset are in nondecreasing order, coefficients of objective function are in nonincreasing order and s is the least index such that corresponding coefficient of objective function is negative, tehn lexicographic minimal if formed as s – 1 first and k – s + 1 (k is the dimension of space) last elements of multiset which are in nondecreasing order. For problems with linear-fractional function we obtain the method of forming solution of lexicographic combinatorial problem on arrangements, if any minimal (for minimization problems) or any maximal (for maximization problems) of objective function on given set of arrangements is known. In this case ordering of components of the extremal is carried out taking into account ordering for nonincreasing of coefficients of special linear function Розглядаються евклідові задачі лексикографічної комбінаторної оптимізації, які передбачають знаходження лексикографічно мінімальної (для задач мінімізації) чи лексикографічно максимальної (для задач максимізації) точки серед тих, які надають екстремум цільовій функції на заданій евклідовій комбінаторній множині. Обґрунтовано властивості лінійних та дробово-лінійних задач лексикографічної комбінаторної оптимізації на загальній множині розміщень без додаткових обмежень. Отримані в роботі результати спираються на відомі раніше критерії екстремалей лінійної та дробово-лінійної функцій на розміщеннях: будь-яка екстремаль є елементом певної множини полірозміщень (для лінійних задач вигляд множини екстремалей встановлений явно, для дробово-лінійних задач множина полірозміщень формується на основі деякої відомої екстремалі). У роботі встановлено вигляд точок, які є лексикографічною мінімаллю та лексикографічною максималлю лінійної функції на загальній множині розміщень. Зокрема, якщо елементи мультимножини упорядковані за неспаданням, а коефіцієнти цільової функції — за незростанням, причому s — найменший індекс такий, що відповідний коефіцієнт цільової функції є від’ємним, то лексикографічна мінімаль формується як упорядковані за неспаданням s – 1 перших та k – s + 1 (k — вимірність простору) останніх елементів мультимножини. Для задач з дробово-лінійною цільовою функцією встановлений спосіб формування розв’язку задачі лексикографічної комбінаторної оптимізації на розміщеннях, якщо відома будь-яка з мінімалей (для задач мінімізації) чи максималей (для задач максимізації) цільової функції на заданій множині розміщень. Упорядкування компонент екстремалі у цьому випадку здійснюється з урахуванням упорядкування за незростанням коефіцієнтів лінійної функції спеціального вигляду Кам'янець-Подільський національний університет імені Івана Огієнка 2019-01-31 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/174058 10.32626/2308-5878.2019-19.5-11 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2019: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 19; 5-11 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2019: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 19; 5-11 2308-5878 10.32626/2308-5878.2019-19 uk http://mcm-math.kpnu.edu.ua/article/view/174058/173969 Авторське право (c) 2021 Тетяна Миколаївна Барболіна |
| spellingShingle | Барболіна, Тетяна Миколаївна Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title | Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title_alt | Властивості Евклідових задач лексикографічної комбінаторної оптимізації на розміщеннях |
| title_full | Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title_fullStr | Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title_full_unstemmed | Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title_short | Properties of Euclidean Problems of Lexicographic Combinatorial Optimization on Arrangements |
| title_sort | properties of euclidean problems of lexicographic combinatorial optimization on arrangements |
| url | http://mcm-math.kpnu.edu.ua/article/view/174058 |
| work_keys_str_mv | AT barbolínatetânamikolaívna propertiesofeuclideanproblemsoflexicographiccombinatorialoptimizationonarrangements AT barbolínatetânamikolaívna vlastivostíevklídovihzadačleksikografíčnoíkombínatornoíoptimízacíínarozmíŝennâh |