Введение
1 Полиномиальные алгоритмы решения задачи 12
1.1 Постановка задачи 13
1.2 Обозначения и определения основных понятий 15
1.3 Абсолютная погрешность приближенного решения 17
1.4 Схема нахождения приближенного решения 22
1.4.1 Вариант схемы на основе случая Лазарева 25
1.4.2 Вариант схемы на основе случая Хогевена 32
1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи 36
1.5.1 Способ генерации примеров 37
1.5.2 Оценка практического значения абсолютной погрешности 40
1.5.3 Эффективность применения полиномиальных алгоритмов для общего случая задачи 42
2 Алгоритмы оптимального решения задачи 46
2.1 Существующие методы решения задачи 48
2.1.1 Алгоритм Карлье 48
2.1.2 Метод программирования в ограничениях 53
2.2 Алгоритмы решения задачи 59
2.3 Экспериментальное сравнение алгоритмов решения задачи 65
2.4 Модифицированный алгоритм Карлье 71
3 Алгоритм ветвей и отсечений для решения задачи 80
3.1 "Гибридная" схема решения одного класса задач целочисленного линейного программирования 81
3.2 Постановка задачи 89
3.3 Формулировка задачи как задачи 91
3.4 Дополнительные ограничения 94
3.5 Генерация отсечений 98
3.6 "Гибридный" алгоритм ветвей и отсечений 109
3.7 Экспериментальная оценка эффективности 111
Заключение 119
Список литературы 121
