 |
 |
 |
 |
|
 |
 |
87
Очевидным недостатком алгоритма метода ветвей и границ при решении задач большой размерности
является необходимость перебрать слишком большое количество вариантов перед тем, как будет
найден оптимальный план. Однако он отчасти может быть преодолен, если ограничиться поиском не
оптимального, а просто «хорошего» (близкого к оптимальному) плана. О степени такой близости и
скорости приближения к экстремуму нетрудно судить по изменению значений оценок.
Подчеркнем, что приведенная реализация метода ветвей и границ является одной из многих. Помимо
нее, например, очень популярна версия метода решения задачи коммивояжера, в которой для ветвления
и построения оценок используют специфические свойства данной модели. При желании о ней можно
прочесть в [1, 14].
КЛЮЧЕВЫЕ ПОНЯТИЯ
Задачи с неделимостями.
Экстремальные комбинаторные задачи.
Задачи с разрывными целевыми функциями.
Правильное отсечение.
Метод Гомори.
Методы ветвей и границ.
КОНТРОЛЬНЫЕ ВОПРОСЫ
4.1. Какие основные проблемы возникают при решении дискретных задач?
4.2. Сформулируйте задачу о ранце.
4.3. Какие экономико-математические модели могут быть сведены к задаче о коммивояжере?
4.4. Приведите пример моделей с разрывными целевыми функциями.
4.5. Какой принцип используется для построения правильного отсечения в методе Гомори?
4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.
4.7. Какую роль играет алгоритм двойственного симплекс-метода при решении целочисленной
линейной задачи методом Гомори?
4.8. Перечислите принципиальные идеи, лежащие в основе методов ветвей и границ.
4.9. Как производится построение отсечения при решении целочисленной линейной задачи методом
ветвей и границ?
4.10. Опишите схему решения целочисленной задачи линейного программирования методом ветвей и
границ.
4.11. За счет каких преобразований удается построить сопряженный базис при добавлении
отсекающего ограничения?
ГЛАВА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
5.1. ОБЩАЯ СХЕМА МЕТОДОВ
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
5.1.1. Основные идеи вычислительного метода динамического программирования. Некоторые
задачи математического программирования обладают специфическими особенностями, которые
позволяют свести их решение к рассмотрению некоторого множества более простых «подзадач». В