Исследование методов решения задачи о ранце

Министерство науки и высшего образования Российской Федерации ФГБОУ ВО «Северо-Кавказский горно-металлургический институт (государственный технологический университет)»

Факультет информационных технологий и электронной техники

Направление подготовки: магистратура

Кафедра: информатики и вычислительной техники

ОТЧЕТ

по преддипломной практике на тему «Исследование методов решения задачи о ранце»

с     02.03.2020   по    24.05.2020

Выполнил: Савлаев Г.В.

Группа: ИВм-18-1

Руководитель практики: Мирошников А.С.

Оценка, подпись, дата  [pic 1]

Владикавказ

2020 г.

Оглавление

Введение        3

Глава 1. Аналитический обзор.        5

1.1.        Задача дискретной оптимизации.        5

1.2.        Задача о ранце (рюкзаке).        6

1.2.1. Общие свойства задачи о ранце (рюкзаке).        7

1.2.2. Алгоритм Данцига для линейной одномерной задачи о ранце.        8

1.2.3. Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце.        11

1.3.        Динамическое программирование.        14

1.3.1 Общие понятия.        14

Глава 2. Алгоритмы        17

2.1 Классическая версия динамического программирования.        17

2.2. Композитная версия динамического программирования.        18

2.3. Модифицированная композитная версия динамического программирования.        19

Глава 3. Графические зависимости.        21

Введение

Практика порождает всё новое и новые задачи оптимизации, сложность которых возрастает. Современные методы оптимизации не всегда справляются с решением реальных задач. Требуются новые математические модели и методы, которые позволяют учитывать наличие многих критериев и проводят глобальный поиск оптимума.

Упомянутая Джорджем Баллардом Мэтьюсом в статье «On the Partition of Numbers», датированной в 1897 году, задача о ранце (рюкзаке) (англ. Knapsack Problem) была впервые представлена миру. В дальнейшем получив толчок к интенсивному изучению, после публикации американским математиком Д.Б.Данцигом в 1957 году книги «Discrete Variable Extremum Problem», нашла применение во многих областях знаний:

• Экономике;
• Прикладной математике;
• Криптографии;
• Генетике;
• Информатике;
• Логистике, для нахождения оптимальной загрузки транспорта или склада.

Также задача о ранце (рюкзаке) может служить моделью для промышленных задач:

• Размещение грузов на складе минимальной площади;
• Раскройка ткани – из имеющегося куска материала получить максимальное число выкроек определённой формы;
• Расчёт оптимальных капиталовложений.

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

Существуют ряд методов решения задачи о ранце (рюкзаке), являясь одной из NP-полных задач, для неё не существует полиномиального алгоритма, решающего её за разумное время. Поэтому при решении необходимо выбирать между точными алгоритмами, неприменимы для «больших» рюкзаков, и приближёнными, которые работают быстро, но не гарантируют оптимального решения.

К точным методам можно отнести:

1. Полный перебор;
2. Метод ветвей и границ;
3. Динамическое программирование.

К приближённым относятся:

1. Жадный алгоритм;
2. Генетические алгоритмы.

Выбор использования того или иного метода зависит от постановки задачи, а также от того, какие цели поставлены.