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 рішення задачі про ранці.
Substantiation of a heuristic algorithm in the knapsack problem.
Обоснование эвристического алгоритма в задаче о ранце.
Обґрунтування евристичного алгоритму в задачі про ранці
2012-12-25
Science and Transport Progress ; No. 42 (2012): ISSUE 42; 170-175
Article (Journal)
Electronic Resource
Russian
Metadata by SPU is licensed under CC BY 3.0
Scientific Periodicals of Ukraine | 2011
|Scientific Periodicals of Ukraine | 2008
|Scientific Periodicals of Ukraine | 2019
|Scientific Periodicals of Ukraine | 2007
|