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.

    Введение: Сформирована задача о ранце в терминах функций множества и приведен эвристический алгоритм. Цель: доказательство того, что эвристический алгоритм является необходимым условием. Некоторые факты из работы [2]. Показана эквивалентность предела последовательности по Э. Борелю и сходимостью по мере. Доказана теорема о необходимости максимума функции множества. Ситуации достаточности алгоритма: Приведены три ситуации,  когда эвристический алгоритм является достаточным.  Контрпример: Приведен контрпример из работы [1] и дано добавление в эвристический алгоритм, что позволяет получать решение задачи о ранце. Векторная оптимизация: С задачей о ранце завязывается задача векторной оптимизации инвестирования мероприятий. Выводы: Предложен алгоритм решения задачи о ранце и для аддитивных функций алгоритм определения Парето решения задачи векторной оптимизации по двум показателям. Приложение: Приведена программа в среде Maple решения задачи о ранце. 

    Вступ:  Сформована завдання про ранці в термінах функцій множини і приведений евристичний алгоритм.  Мета:  доказ того,  що евристичний алгоритм є необхідною умовою.  Деякі факти з роботи [2].  Показана еквівалентність границі послідовності по Е. Борелю і збіжністю по мірі. Доведено теорему про необхідність максимуму функції безлічі.  Ситуації достатності алгоритму:  Наведено три ситуації,  коли евристичний алгоритм є достатнім.  Контрприклад:  Наведено контр прийме з роботи [1]  і дано додавання в евристичний алгоритм,  що дозволяє отримувати рішення задачі про ранці. Векторна оптимізація: Іззавданням про ранцізав'язується завдання векторної оптимізації інвестування заходів. Висновки: запропоновано алгоритм рішення задачі про ранці і для адитивних функцій алгоритм визначення Парето рішення задачі векторної оптимізації за двома показниками. Додаток: наведена програма в середовищі Maple рішення задачі про ранці. 


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Substantiation of a heuristic algorithm in the knapsack problem.
    Обоснование эвристического алгоритма в задаче о ранце.
    Обґрунтування евристичного алгоритму в задачі про ранці


    Beteiligte:
    Bosov, A. A. (Autor:in) / Gоrbоvа, A. V. (Autor:in) / Khalipova, N. V. (Autor:in)


    Erscheinungsdatum :

    2012-12-25


    Anmerkungen:

    Science and Transport Progress ; No. 42 (2012): ISSUE 42; 170-175



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Russisch




    Substantiation of a heuristic algorithm in the knapsack problem

    Н.В. KHalipovа / А.В. Gоrbоvа / А.А. Bоsоv | DOAJ | 2012

    Freier Zugriff