Метод решения комбинаторной задачи условной оптимизации на комбинаторном множестве размещений
Loading...
Date
2019
Authors
Колечкина, Людмила
Нагорная, Алла
Семенов, Виктор
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
В данной статье формулируется постановка задачи оптимизации на комбинаторном множестве размещений и предложен метод ее решения с учетом выполнения условий, налагаемых на приросты ограничений и целевой функции. Новый метод обеспечивает нахождение оптимального решения оптимизационной задачи
на множестве размещений с учетом дополнительных ограничений за определенное количество шагов. Для демонстрации работы метода представлены численные
эксперименты, характеризующие его конечность и результативность, а также
приведен анализ их результатов.
Розглянуто постановку задачі на комбінаторній множині розміщень і запропоновано метод її розв'язання з урахуванням виконання умов, що накладаються на прирости обмежень і цільової функції. Метод складається з трьох кроків, де на початковому етапі будуються матриці нормалізації та відповідності, які забезпечують перетворення елементів множини розміщень в необхідну форму для цільової функції і заданих обмежень. Другий крок полягає в знаходжені першого опорного розв'язку з урахуванням властивості множини розміщень. Слід зазначити, що для знаходження першого опорного розв'язку достатньо розрахувати прирости обмежень. Якщо допустимий розв'язок задовольняє даним нерівностям, то фіксуються початкові дані, які будуть умовами перевірки наступного покращеного розв'язку. Значення функції цілі знаходиться розрахунком приростів цільової функції без необхідності обчислення всієї попередньої функції. Третій крок методу забезпечує знаходження оптимального розв'язку за безпосереднього покращення знайденого опорного розв'язку. На даному етапі сформульовано достатні і необхідні умови для пошуку оптимального розв'язку. Розглянуто числові приклади пошуку екстремумів функцій на множині розміщень, а також представлено числовий експеримент для випадку А3k, при зростанні кількості елементів вибірки множини розміщень (k). Також слід зазначити, що кількість кроків знаходження оптимального розв'язку істотно не збільшується за різкого зростання кількості елементів множини розміщень. Аналізуючи показник процентного співвідношення кількості розглянутих точок при знаходженні оптимального розв'язку до кількості елементів множини розміщень, слід зазначити його значне зменшення, що свідчить про ефективність запропонованого методу. Отже, користуючись даним методом, можна за скінчене число кроків знайти екстремум функції на множині розміщень.
Defining a problem of optimization on a combinatorial set of arrangements is considered and presenting the method of its solution, taking into account satisfaction of the conditions imposed on gains of restrictions and objective function is proposed. The method consists of three steps where at the initial stage matrixes of normalization and compliance are built, which provide elements arrangement set transformation to a necessary form for criterion function and the defined restrictions. The second step consists in finding the first basic solution, taking into account property of arrangement set. It should be noted that for finding the first basic solution it is enough to calculate gains of restrictions. If the allowable solution satisfies presented inequalities, then initial data is fixed, which will be the verification conditions for the following improved solution. The value of the goal function is determined at the expense of calculating the increments of the target function, without the need to calculate the entire previous function. The third step of a method provides finding of an optimal solution at direct improvement of the found basic solution. On this step sufficient and necessary conditions for search of an optimal solution are formulated. Numerical examples of search functions's extrems on a set of arrangements are considered and also the numerical experiment for the case A3k is presented, at increase of sample units quantity of an arrangements set (k). Also it should be noted that the finding steps quantity of an optimal solution considerably does not increase, at sharp increase of elements quantity in a set of arrangements. Analyzing an indicator of percentage correlation of the considered points quantity when finding an optimal solution to quantity of elements on an arrangements set, it should be noted its considerable reduction that gives evidence about efficiency of the offered method. So, this method allows to find a function extremum on a set of arrangements during a finite number of steps.
Розглянуто постановку задачі на комбінаторній множині розміщень і запропоновано метод її розв'язання з урахуванням виконання умов, що накладаються на прирости обмежень і цільової функції. Метод складається з трьох кроків, де на початковому етапі будуються матриці нормалізації та відповідності, які забезпечують перетворення елементів множини розміщень в необхідну форму для цільової функції і заданих обмежень. Другий крок полягає в знаходжені першого опорного розв'язку з урахуванням властивості множини розміщень. Слід зазначити, що для знаходження першого опорного розв'язку достатньо розрахувати прирости обмежень. Якщо допустимий розв'язок задовольняє даним нерівностям, то фіксуються початкові дані, які будуть умовами перевірки наступного покращеного розв'язку. Значення функції цілі знаходиться розрахунком приростів цільової функції без необхідності обчислення всієї попередньої функції. Третій крок методу забезпечує знаходження оптимального розв'язку за безпосереднього покращення знайденого опорного розв'язку. На даному етапі сформульовано достатні і необхідні умови для пошуку оптимального розв'язку. Розглянуто числові приклади пошуку екстремумів функцій на множині розміщень, а також представлено числовий експеримент для випадку А3k, при зростанні кількості елементів вибірки множини розміщень (k). Також слід зазначити, що кількість кроків знаходження оптимального розв'язку істотно не збільшується за різкого зростання кількості елементів множини розміщень. Аналізуючи показник процентного співвідношення кількості розглянутих точок при знаходженні оптимального розв'язку до кількості елементів множини розміщень, слід зазначити його значне зменшення, що свідчить про ефективність запропонованого методу. Отже, користуючись даним методом, можна за скінчене число кроків знайти екстремум функції на множині розміщень.
Defining a problem of optimization on a combinatorial set of arrangements is considered and presenting the method of its solution, taking into account satisfaction of the conditions imposed on gains of restrictions and objective function is proposed. The method consists of three steps where at the initial stage matrixes of normalization and compliance are built, which provide elements arrangement set transformation to a necessary form for criterion function and the defined restrictions. The second step consists in finding the first basic solution, taking into account property of arrangement set. It should be noted that for finding the first basic solution it is enough to calculate gains of restrictions. If the allowable solution satisfies presented inequalities, then initial data is fixed, which will be the verification conditions for the following improved solution. The value of the goal function is determined at the expense of calculating the increments of the target function, without the need to calculate the entire previous function. The third step of a method provides finding of an optimal solution at direct improvement of the found basic solution. On this step sufficient and necessary conditions for search of an optimal solution are formulated. Numerical examples of search functions's extrems on a set of arrangements are considered and also the numerical experiment for the case A3k is presented, at increase of sample units quantity of an arrangements set (k). Also it should be noted that the finding steps quantity of an optimal solution considerably does not increase, at sharp increase of elements quantity in a set of arrangements. Analyzing an indicator of percentage correlation of the considered points quantity when finding an optimal solution to quantity of elements on an arrangements set, it should be noted its considerable reduction that gives evidence about efficiency of the offered method. So, this method allows to find a function extremum on a set of arrangements during a finite number of steps.
Description
Keywords
комбинаторное множество, оптимизационная задача, матрица нормализации, экстремум функции, статья, задача умовної оптимізації, комбінаторна множина розміщень, екстремум функції, матриця нормалізації, conditional optimization problem, combinatorial set of allocations, function extremum, normalization matrix
Citation
Колечкина Л. Н. Метод решения комбинаторной задачи условной оптимизации на комбинаторном множестве размещений / Л. Н. Колечкина, А. Н. Нагорная, В. В. Семенов // Проблемы управления и информатики. - 2019. - № 4. - С. 62-72.