TWO METHODS FOR CONSTRUCTION OF SUBOPTIMISTIC AND SUBPESSIMISTIC SOLUTIONS OF THE INTERVAL PROBLEM OF MIXED-BOOLEAN PROGRAMMING
DOI:
https://doi.org/10.15588/1607-3274-2018-3-7Keywords:
an interval problem of mixed Boolean programming, optimistic, pessimistic, sub-optimistic and sub-pessimistic solutions, upper and lower bounds, errors, experiments.Abstract
Context. The interval problem of mixed Boolean programming having numerous economic applications is considered. Theobject of the study was a model of the integer programming.
Objective. Development of methods for constructing suboptimistic and subpessimistic solutions of the mixed Boolean
programming interval problem. Two methods for constructing suboptimistic and subpessimistic solutions of mixed Boolean programming problems with interval initial data are introduced. These methods are based on some economic interpretation of the model considered.
Method. Two methods for constructing suboptimistic and subpessimistic solutions of mixed Boolean programming problems
with interval initial data are introduced. These methods are based on some economic interpretation of the considered model. In the
first method a criterion of selecting unknowns for assigning values, which is based on the principle of profit maximum for each unit
of expenditure is introduced. Since the coefficients of the problem are intervals, two strategies are chosen: optimistic and pessimistic.
In the optimistic strategy, the idea of choosing unknowns is used, which corresponds to the maximum ratio of the corresponding
maximum profit to the minimum expenditure. And in the pessimistic strategy, the idea of maximum ratio of the minimum profit to
the maximum expenditure is used. In the second method, the concept of a non-linearly increasing penalty (price) for using a unit of
the remaining resources is introduced, that on the right side is bounded. Taking into account the principles of the above first and
second methods, using this concept of penalty (price), methods for constructing suboptimistic and subpessimistic solutions have been
developed.
Results. The algorithms for constructing suboptimistic and subpessimistic solutions to the interval problem of mixed Boolean
programming are developed.
Conclusions. A software package was developed for constructing suboptimistic and subpessimistic solutions to the interval problem
of mixed Boolean programming. A number of computational experiments have been carried out over random problems of various
dimensions.
References
Gary M., Johnson D. M. Vichislitelniye mashini i trudnoreshayemiye zadaci. Mir, 1982, 416 p.
Aho А., Hopcroft J., Ullman J. Postroyeniye i analiz
vichislitelnix alqoritmov. Mir, 1979, 536 p.
Libura M. Integer programming problems with inexact
objective function, Control And Cybernetics, 1980,
Vol. 9, No. 4, pp. 189–202.
Roshin V. А., Semenova N. V., Sergiyenko I. V. Dekompozicionniy podxod k resheniyu nekotorix zadac celocislennoqo proqrammirovaniya s netocnimi dannimi,
Journal Vicislitelnoy Matematiki i Matematiceskoy Fiziki,
, Vol. 30, No. 5, pp. 786–791.
Devyaterikova М. V., Kolokolov А. А., Kolosov А. P.
Alqoritmi perebora L-klassov dla bulevoy zadaci o ryukzake s
intervalnimi dannimi. Materiali III Vserossiyskoy konferencii
“Problemi optimizacii I ekonomiceskoye prilojeniye”. Omsk,
Izd-vo Ом ГТУ, 2006, P. 87.
Emelichev V. A., Podkopaev D. P. Quantitative stability analysis for vector problems of 0–1 programming, Discrete Optimitation, 2010, No. 7, pp. 48–63.
Mamedov К. Sh., Маmedli N. О. Metodi postroyeniya suboptimisticeskoqo i subpessimisticeskoqo resheniy chasticno-Bulevoy zadaci o ranche s intervalnimi dannimi, Izv. NAN Azerbaijan, 2016, No. 6, pp. 6–13.
Mamedov К. Sh., Мamedova А. H. Ponyatiya suboptimisticeskoqo I subpessimisticeskoqo resheniy i postroyeniye ix v intervalnoy zadace Bulevoqo proqrammirovaniya, Radio Electronics,
Computer Science, Control, 2016, No. 3, pp. 99–107.
Martello S., Toth P. Knapsack problems, Algorithm and Computers implementations. Chichster, John Wiley & Sons, 1990, 296 p.
Kovalev M. М. Diskretnaya optimizaciya (celocislennoye proqrammirovaniye). Мoscow, U.RSS, 2003, 192 p.
Babayev J. А. Мamedov К. Sh., Mextiyev М. Q. Metodi postroyeniya suboptimalnix resheniy mnoqomernoy zadaci o
rance, Journal Vicislitelnoy Matematiki i Matematiceskoy
Fiziki, 1978, Vol.28, No. 6, pp. 1443–1453.
Аlefeld Q., Herzberger J. Vvedeniye v intervalniye vicisleniya. Translation from eng. Мoscow, Mir, 1987, 360 p.
Toyoda Y. A simplified algorithm for obtaining approximate solutions to zero-one programming problems, Management Science, 1975, No. 12, pp. 1417–1427.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2018 К. Sh. Mamedov, N. O. Mammadli
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.
