Дослідження впливу невизначеності на оптимальний розв'язок задачі про рюкзак

Abstract

UK: Об’єкт дослідження – задача пакування рюкзака. Предмет дослідження – вплив статистичної невизначеності на оптимальний розв’язок задачі про рюкзак. Мета роботи – розроблення підходу знаходження оптимального розв’язку задачі, вхідні параметри якої є системою незалежних випадкових величин і розроблення застосунку з інтерфейсом, який знаходить оптимальні розв’язки та сумарну вартість і записує результати в файл з заданою кількістю експериментів та дослідження впливу статистичної невизначеності за рівномірним і нормальним законами розподілу на оптимальний розв’язок задачі про рюкзак. Методи дослідження – метод повного перебору. В дипломній роботі проаналізовані роботи авторів, що розглядали задачу про рюкзак. Наведено загальну та математичну постановки задачі упакування рюкзака з вхідними параметрами, що утворюють систему незалежних випадкових величин. Описано підхід для знаходження оптимальних розв’язків задачі. Розроблено застосунок на мові програмування С++, що має інтерфейс та знаходить оптимальні розв’язки вище вказаної задачі та відповідну їм сумарну вартість, та створює файл, в який записуються отримані дані для заданої кількості експериментів. Розроблені універсальні критерії оптимальності. Продемонстровані приклади задачі про рюкзак. Отримані та проаналізовані оптимальні розв’язки першої задачі з варіюванням вартості, другої задачі з варіюванням об’єму і третьої задачі з варіюванням вартості та об’єму згідно нормальному та рівномірному законам розподілу. EN: Object of study – the task of packing a backpack. Subject of study – the influence of statistical uncertainty on the optimal solution of the knapsack problem. The purpose of the work is to develop an approach to finding the optimal solution to a problem whose input parameters are a system of independent random variables and to develop an application with an interface that finds optimal solutions and the total cost and writes the results to a file with a given number of experiments and research on the impact of statistical uncertainty by uniform and normal distribution laws for the optimal solution of the backpack problem. Research methods – the method of exhaustive search. In the thesis, the works of the authors who considered the backpack problem were analyzed. The general and mathematical formulation of the problem of packing a backpack with input parameters forming a system of independent random variables is given. An approach to finding optimal solutions to the problem is described. An application in the C++ programming language has been developed, which has an interface and finds the optimal solutions of the above-mentioned problem and the corresponding total cost, and creates a file in which the obtained data for a given number of experiments are recorded. Universal optimality criteria have been developed. Examples of the knapsack problem are demonstrated. The optimal solutions of the first problem with cost variation, the second problem with volume variation, and the third problem with cost and volume variation according to the normal and uniform distribution laws were obtained and analyzed.