Федеральное агентство по образованию

Байкальский государственный университет экономики и права

Кафедра информатики и кибернетики

Курсовая работа

по дисциплине «Исследование операций»

на тему: «Задача о ранце»

Исполнитель студент гр. Арыштаев Д.Г., Группа УИС-3-11 Руководитель канд. физ. мат. наук, доц. Т.И. Белых

Оглавление

Оглавление 2

Введение 3

1. Основные цели и задачи 4

2. Методы решения задачи о рюкзаке 4

3. Динамическое программирование (ДП–алгоритм) 5

3.1. Полный перебор 8

3.2. Метод ветвей и границ 10

3.3. Жадный алгоритм 11

4. Сравнительный анализ методов 13

4.1. Динамическое программирование (ДП–алгоритм) 13

4.2. Полный перебор 13

4.3. Метод ветвей и границ 14

4.4. Жадный алгоритм 14

5. Пример решения задачи с помощью пакета экономических расчетов (ПЭР) 14

6. Модификации задачи 16

Заключение 17

Список использованной литературы 19

Введение

Наука уделяет все большее и большее внимание вопросам организации и управления, что приводит к необходимости анализа целенаправленных сложных процессов с точки зрения их организации и структуры. Потребности практики вызвали к жизни специальные методы, которые удобно объединять под названием «Исследование операций», под которым понимается применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности.

Целью исследования операций является выявление наилучшего способа действия при решении той или иной задачи. Главная роль при этом отводится математическому моделированию. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений.

Данная курсовая работа предназначена для закрепления знаний по дисциплине «Исследование операций». Одной из задач, изучаемой в рамках данной дисциплины, является задача о ранце. Именно ее мы и рассмотрим.

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.

Воспринимать задачу в буквальном смысле и создавать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход, никто не собирается, т.к. тут все слишком просто, но существует и более широкое применение, а именно данная задача широко применяется на практике в прикладной математике, криптографии, экономике, логистике, генетике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов, склада и т.д.

Задача является NP–полной, то есть для нее не существует полиномиального алгоритма, решающего её за разумное время, в этом и заключается проблема. Либо мы выбираем быстрый алгоритм, но он, как известно, не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным из-за того, что поиск точного решения для больших значений займет слишком много времени.