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

Abstract

UK: Об’єкт дослідження – моделі динамічного програмування в умовах невизначеності.. Предмет дослідження – задача про рюкзак в умовах невизначеності. Мета роботи – дослідження впливу статистичної невизначеності на оптимальний розв’язок задачі про рюкзак та її модифікацій і розроблення програмного забезпечення для розв’язання задачі, що знаходить оптимальні плани та відповідну їм сумарну вартість, та заносить знайдені дані в файл для заданої кількості експериментів. Методи дослідження – метод повного перебору. В дипломній роботі розглянуто задачу про завантаження та задачу про рюкзак в умовах невизначеності. Наведено загальну та математичну постановки задач. Описано алгоритм знаходження оптимальних розв’язків задач з вхідними параметрами, що підпорядковуються довільному закону розподілу. На основі алгоритму розроблено програмну реалізацію на мові програмування С++, що знаходить оптимальні плани задач з рівномірними вхідними параметрами та відповідну їм сумарну вартість, і заносить знайдені дані в файл для заданої кількості експериментів. Розроблено різні варіанти критеріїв оптимальності. Отримано результати розрахунку оптимальних розв’язків для прикладів задачі про завантаження та задачі про рюкзак з рівномірно розподіленими параметрами для різних значень відхилень. Проведено аналіз оптимальних планів розглянутих прикладів для різних критеріїв оптимальності. EN: Object of study - models of dynamic programming under uncertainty. Subject of study - the knapsack problem under uncertainty. Study of the effect of statistical uncertainty on the optimal solution of the backpack problem and its modifications and the development of software for solving the problem, which finds the optimal plans and the corresponding total cost, and records the found data in a file for a given number of experiments. Research methods - a method of complete search. The thesis considers the problem of loading and the problem of backpacking in conditions of uncertainty. General and mathematical setting of problems are given. An algorithm for finding optimal solutions to problems with incoming parameters that obey an arbitrary distribution law is described. Based on the algorithm, a software implementation in the C++ programming language was developed, which finds optimal task plans with uniform input parameters and their corresponding total cost, and records the found data in a file for a given number of experiments. Various options for optimality criteria have been developed. The results of calculation of optimal solutions for examples of problem on loading and problem on backpack with uniformly distributed parameters for different values of deviations are obtained. Analysis of optimal plans of the considered examples for different criteria of optimality has been carried out. RU: Объект исследования - модели динамического программирования в условиях неопределенности. Предмет исследования - задача о рюкзаке в условиях неопределенности. Цель работы - исследования влияния статистической неопределенности на оптимальное решение задачи о рюкзаке и ее модификаций и разработки программного обеспечения для решения задачи, находит оптимальные планы и соответствующую им суммарную стоимость, и заносит найдены данные в файл для заданного количества экспериментов. Методы исследования – метод полного перебора. В дипломной работе рассмотрена задача о загрузке и задачу о рюкзаке в условиях неопределенности. Приведена общая и математическую постановки задач. Описан алгоритм нахождения оптимальных решений задач с входными параметрами, которые подчиняются произвольном закона распределения. На основе алгоритма разработан программную реализацию на языке программирования С ++, что находит оптимальные планы задач с равномерными входными параметрами и соответствующую им суммарную стоимость, и заносит найдены данные в файл для заданного количества экспериментов. Разработаны различные варианты критериев оптимальности. Получены результаты расчета оптимальных решений для примеров задачи о загрузке и задачи о рюкзаке с равномерно распределенными параметрами для разных значений отклонений. Проведен анализ оптимальных планов рассмотренных примеров для различных критериев оптимальности.