Substantiation of a heuristic algorithm in the knapsack problem

A. A. Bosov; A. V. Gorbova; N. V. Khalipova

doi:10.15802/stp2012/9390

Substantiation of a heuristic algorithm in the knapsack problem

Authors

A. A. Bosov Dnipropetrovsk National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0002-5348-2205
A. V. Gorbova Dnipropetrovsk National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0002-5612-2715
N. V. Khalipova Academy of Customs Service of Ukraine, Ukraine https://orcid.org/0000-0001-5605-6781

DOI:

https://doi.org/10.15802/stp2012/9390

Keywords:

knapsack problem, set functions, vector optimization, the task of investing

Abstract

Introduction: Formed knapsack problem in terms of set functions and is a heuristic algorithm. The goal: to prove that the heuristic algorithm is essential. Some facts from [2]. The equivalence of the limit order to E.Borelyu and convergence in measure. The theorem about the need to set a maximum of function. The situation is quite the algorithm: We present three cases where a heuristic algorithm is sufficient. Counterexample: An Rear take from [1], and given the addition heuristic algorithm, which allows to obtain the solution of the knapsack problem. Vector optimization: With the knapsack problem is tied vector optimization of investment activities. Conclusions: The proposed algorithm for solving the knapsack problem and for additive functions algorithm for Pareto solutions of vector optimization for the two indicators. Appendix: an agenda for the Maple solutions knapsack problem.

Author Biographies

A. A. Bosov, Dnipropetrovsk National University of Railway Transport named after Academician V. Lazaryan

A. A. Bosov

A. V. Gorbova, Dnipropetrovsk National University of Railway Transport named after Academician V. Lazaryan

A. V. Gоrbоvа

N. V. Khalipova, Academy of Customs Service of Ukraine

N. V. Khalipova

Downloads

PDF (Русский)

Published

2012-12-25

How to Cite

Bosov, A. A., Gorbova, A. V., & Khalipova, N. V. (2012). Substantiation of a heuristic algorithm in the knapsack problem. Science and Transport Progress, (42), 170–175. https://doi.org/10.15802/stp2012/9390

Download Citation

Issue

No. 42 (2012): ISSUE 42

Section

TRANSPORT AND ECONOMIC TASKS MODELING

License

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

Copyright and Licensing

This journal provides open access to all of its content.
As such, copyright for articles published in this journal is retained by the authors, under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0). The CC BY license permits commercial and non-commercial reuse. Such access is associated with increased readership and increased citation of an author's work. For more information on this approach, see the Public Knowledge Project, the Directory of Open Access Journals, or the Budapest Open Access Initiative.

The CC BY 4.0 license allows users to copy, distribute and adapt the work in any way, provided that they properly point to the author. Therefore, the editorial board of the journal does not prevent from placing published materials in third-party repositories. In order to protect manuscripts from misappropriation by unscrupulous authors, reference should be made to the original version of the work.