THE CONCEPT OF GUARANTEED SOLUTION THROUGH THE FUNCTIONAL FOR MUTIDIMENTIONAL KNAPSACK PROBLEM AND METHODS OF ITS CONSTRUCTION
DOI:
https://doi.org/10.15588/1607-3274-2018-1-19Keywords:
one-dimensional and multidimensional knapsack problems, guaranteed solution and guaranteed suboptimal solution through the functional, non-linear multicriteria the problem of Boolean programming, dichotomy approach, computational experiment.Abstract
Contex. The problem of constructing a guaranteed suboptimal (approximate) solution with respect to a functional in one-dimensional and multidimensional knapsack problems is considered. The object of the study was a model with an increment of the coefficients of the objective function.Objective. The methods of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional
knapsack problem has been developed.
That is it is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the solution
found guarantees the value of the functional not less than the predetermined value.
Method. The concept of guaranteed solution and guaranteed suboptimal solution relative to the objective function in the satchel problem
is introduced. It is necessary to find such minimal changes coefficient of the objective function in the set of integer intervals so that the
solution found guarantees the value of the functional not less than the predetermined value. Such kind of solution we name as guaranteed
solution through the functional for one-dimensional and multidimensional knapsack problem. The methods of their construction has been developed. A software package was developed to find these solutions and numerous computational experiments were performed on random large-dimensional problems.
Results. The algorithm of constructing guaranteed suboptimal solution through the functional in one-dimensional and multidimensional
knapsack problem has been developed.
Conclusions. A software package was developed to find the concept of guaranteed solution and guaranteed suboptimal solutions and
numerous computational experiments were performed on random large-dimensional problems.
References
Korbut A. A., Finkel’shtejn Yu. Yu. Diskretnoe programmirovanie.
Moscow, Nauka, 1969. – 368 p.
Kovalev M. M. Diskretnaya optimizaciya (celochislennoe
programmirovanie). Moscow, URSS, 2003, 246 p.
Martello S., Toth P. Knapsack problems, Algorithm and Computers
implementations. John Wiley & Sons, Chichster, 1990, 296 p.
Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin,
Heidelberg, New-York, Springer Verlag, 2004, 546 p.
Sigal I. X., Ivanova A. P. Vvedenie v prikladnoe diskretnoe
programmirovanie: modeli, vychislitel’nye algoritmy. Moscow,
Fizmat lit., 2007, 304 p.
Sergienko I. V., Lebedeva T. T., Roshin V. A. Priblizhennye metody
resheniya diskretnyx zadach optimizacii. Kiev, Naukova dumka,
, 276 p.
Sergienko I. V. Matematicheskie modeli i metody resheniya zadach
diskretnoj optimizacii. AN USSR, Institut Kibernetiki, Naukova
Dumka, 1988, 471 p.
Sergienko I. V., Kozerackaya L. N., Lebedeva T. T. Iscledovanie
ustojchivosti i parametricheskij analiz diskretnyx
optimizacionnyx zadach. Kiev, Nauk. dumka, 1995, 169 p.
Sergienko I. V., Shilo V. P. Zadachi diskretnoj optimizacii:
problemy, metody, resheniya, issledovaniya. Kiev, Nac. akad.
nauk Ukrainy, In-t kibernetiki im. V. M. Glushkova Nauka. dumka,
, 261 p.
Mamedov K. Sh. Issledovanie po celochislennoj optimizacii
(metody, algoritmy i vychislitel’nye e’ksperimenty). Germaniya,
Lambert Academic Publishing, 2012, 276 p.
Babaev Dzh. A., Mamedov K. Sh., Mextiev M. G. Metody
postroeniya suboptimal’nyx reshenij mnogomernoj zadachi o
rance, ZhVM i MF, 1978, Vol. 28, No. 6, pp. 1443–1453.
Nuriev U. G. Gibridnyj metod dlya resheniya mnogomernoj zadachi
o rance. Preprint IK AN USSR, 1983, 45 p.
Vladimir Emelichev, Podkopaev Dmitry Quantitative stability
analysis for vector problems of 0-1 programming, Discrete
Optimization, 2010, Vol. 7, pp. 48–63.
Mamedov N. N., Mamedov K. Sh., Algoritmy postroeniya
garantirovannogo resheniya i garantirovannogo priblizhennogo
resheniya mnogomernoj zadachi o rance, Mezhdunarodnyj
nauchno-texnicheskij zhurnal «Problemy Upravleniya i
Informatiki», 2014, No. 5, pp. 30–37.
Mamedov N. N., Mamedov K. Sh. Guaranteed solution and its
finding in the Integer Programming Problems, International
Journal of Applied Science and Tecnology, 2015, August, Vol. 5,
No. 4, pp. 46–54.
Mamedov N. N., Mamedov K. Sh. Ponyatie garantirovannogo
resheniya i garantirovannogo suboptimalnogo resheniya
otnositelno celevoj funkii v zadache o rance i ego postroenie (na
azerb. yazyke), Izv. NAN Azerb. Baku, 2016, No. 3, pp. 42–49.
Senjy S., Toyoda Y. An approach to linear programming with 0–
variables, J. Manag. Sci, 1978, Vol.15, No. 4, pp. 196–207.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2018 К. Sh. Mamedov, N. N. Mamedov
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
