DEFINITIONS OF SUBOPTIMISTIC AND SUBPESSIMISTIC SOLUTIONS AND THEIR CONSTRUCTION IN THE INTERVAL BOOLEAN PROGRAMMING PROBLEM

K. Sh. Mamedov, A. H. Mamedova

Abstract


The work considers an interval examples of Bulian programming.Given some economic interpretation to this problem which result in the
constructed economic-mathematical model.Introduced the definitions of optimistic, pessimistic, and suboptimistic, subpessimistic solutions
for the Boolean programming problem with integer interval data are introduced. On the basis of the economic interpretation of the problem
two algorithms are developed for the constructing of the suboptimistic and subpessimistic solutions of this task. Of course, when solutions may
different from suboptimistic and subpessimistic solutions.It is therefore necessary to estimate the relative error of the found to estimate the
error of the suboptimistic and subpessimistic solutions from optimistic and pessimistic solutions appropriately. For this purpose Lagrange type
majoring function is constructed. It is proved, that the minimum value of this function is the upper bound of the optimistic and pessimistic
values of the objective function appropriately. Minimization of this function is in the upper border of the suboptimistic and subpessimistic
values of the performance function. Numerous computational experiments on the examples with different dimensions are provided.

Keywords


Boolean programming problem, integer interval data, optimistic solution, pessimistic solution, suboptimistic solution, subpessimistic solution, non-linear penalty function, Lagrange function, computational experiments.

References


Libura M. Integer programming problems with inexact objective function / M. Libura // Contr. And Cybern. – 1980. – Vol. 9, № 4. – P. 189–202. 2. Ватолин А. А. О задачах линейного программирования с интервальными коэффициентами / А. А. Ватолин // ЖВМ и МФ. – 1984. – Т. 24, № 11. – C. 1629–1637. 3. Семенова Н. В. Решение одной задачи обобщенного целочисленного программирования / Н. В. Семенова // Кибернетика. – 1984. – № 5. – С. 25–31. 4. Леонтьев В. К. Устойчивость решений в задачах линейного булева программирования. / В. К. Леонтьев, К. Х. Мамутов // ЖВМ и МФ. – 1988. – Т. 28, № 10.– C. 1475–1481. 5. Рощин В. А. Вопросы решения и исследования одного класса задач неточного целочисленного программирования / В. А. Рощин, Н. В. Семенова, И. В. Сергиенко // Кибернетика. – 1989. – № 2. – С. 42–47. 6. Рощин В. А. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными / В. А. Рощин, Н. В. Семенова, И. В. Сергиенко // ЖВМ и МФ. – 1990. – Т. 30, №5. – C. 786–791. 7. Сергиенко Т. И. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач / Т. И.Сергиенко, Л. Н. Козерацкая, Т. Т. Лебедева. – К. : Наукова думка, 1995. – 170 с. 8. Emelichev V. A. On the radius of stability of a vector problem of linear Boolean programming / V. A. Emelichev, V. N. Krichko, D. P. Podkopaev // Discrete Math. Appl. – 2000. – Vol. 10. – P. 103–108. 9. Devyaterikova M. V. L-class enumeration algorithms for knapsack problem with interval data / M. V. Devyaterikova, A. A Kolokolov // International Conference on Operations Research: Book of Abstracts. – Duisburg, 2001. 10. Девятерикова М. В. Алгоритмы перебора L-классов для задачи о рюкзаке с интервальными данными / М. В. Девятерикова, А. А. Колоколов. – Омск : Ом ГУ, 2001. –20 с. 11. Devyaterikova M. V. L-class enumeration algorithms for one discrete production planning problem with interval input data / M. V. Devyaterikova, A. A. Kolokolov, A. P. Kolosov // Computers and Operations Research. – 2009. – Vol. 36, Issue 2. – P. 316–324. 12. Девятерикова М. В. Алгоритмы перебора L-классов для булевой задачи о рюкзаке с интервальными данными / М. В. Девяте- рикова, А. А. Колоколов, А. П. Колосов // Материалы III Всероссийской конференции «Проблемы оптимизации и экономическое приложение». – Омск : Изд-во Ом ГТУ, 2006. – C. 87. 13. Девятерикова М. В. Решение задачи о рюкзаке с интервальными данными на основе перебора L-классов / М. В. Девятерикова, А. А. Колоколов, А. П. Колосов // Материалы III международной конференции «Танаевские чтения». – Минск, 2007. – С.51–55. 14. Emelichev V. A. Stability criteria in vector combinatorial bottleneck problems in terms of binary realitions / V. A. Emelichev, K.G.Kuzmin // Cybernetics and Systems Analysis. – 2008. – Vol. 44, № 3. – P. 397–404. 15. Emelichev V.A. Quantitative stability analysis for vector problems of 0–1 programming / V. A. Emelichev, D. P. Podkopaev // Discrete Optimitation. – 2010. – №7. – P. 48–63. 16. Мамедов К. Ш. Один метод решения нечеткой задачи о ранце / К.Ш.Мамедов, С.Я. Гусейнов // Современные проблемы информатизации Кибернетики и Информационные проблемы : респ. конф.: материалы. – Баку, 2003. – Т. 3. – С. 10–13. (на азерб. языке) 17. Бабаев Дж. А. Методы построения субоптимальных решений многомерной задачи о ранце / Дж. А. Бабаев, К. Ш. Мамедов, М. Г. Мехтиев // ЖВМ и МФ. – 1978. – Т. 28, № 6. – C. 1443–1453. 18. Мамедов К. Ш. Понятия субоптимических и субпессимистических решений и методы построения их в задаче о ранце с интервальными данными / К. Ш. Мамедов, А. Г. Мамедова, С. Я. Гусейнов // Изв. НАН Азербайджана. – 2013. – № 6. – С. 164–173. (на азерб. языке) 19. Мамедов К. Ш. Методы построения субоптимических и субпессимистических решений в задаче Булевого программиро- вание с интервальными данными / К. Ш. Мамедов, А. Г. Мамедова // Изв. НАН Азербайджана. 2014. – № 3. – C. 125–131.


GOST Style Citations






DOI: https://doi.org/10.15588/1607-3274-2016-3-13



Copyright (c) 2016 K. Sh. Mamedov, A. H. Mamedova

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.