Оглавление
Введение
1 Полиномиальные алгоритмы решения задачи 1 г Ьтлх
1.1 Постановка задачи.
1.2 Обозначения и определения основных понятий
1.3 Абсолютная погрешность приближенного решения
1.4 Схема нахождения приближенного решения
1.4.1 Вариант схемы на основе случая Лазарева.
1.4.2 Вариант схемы на основе случая Хогевена.
1.5 Экспериментальное исследование полиномиальных алгоритмов решения задачи Ьтах
1.5.1 Способ генерации примеров.
1.5.2 Оценка практического значения абсолютной погрешности
1.5.3 Эффективность применения полиномиальных
алгоритмов для общего случая задачи
2 Алгоритмы оптимального решения задачи 1 г Ьтих
2.1 Существующие методы решения задачи 1 г тах.
2.1.1 Алгоритм Карлье.
2.1.2 Метод программирования в ограничениях.
2.2 Алгоритмы решения задачи 1 Лтах .
2.3 Экспериментальное сравнение алгоритмов
решения задачи г, Лтах
2.4 Модифицированный алгоритм Карлье.
3 Алгоритм ветвей и отсечений для решения задачи г,
3.1 Гибридная схема решения одного класса задач целочисленного линейного программирования.
3.2 Постановка задачи
3.3 Формулировка задачи 1 ту1 как задачи ЧЦЛП.
3.4 Дополнительные ограничения.
3.5 Генерация отсечений
3.6 Гибридный алгоритм ветвей и отсечений.
3.7 Экспериментальная оценка эффективности
Заключение
Список литературы
- Киев+380960830922