Задать вопрос юристу

12. Метод ветвей и границ решения задач целочисленного программирования

В основу метода ветвей и границ положен целенаправленный поиск оптимального решения по дереву линейной задачи ЦП.

Метод основан на следующих рассуждениях:

· любая переменная хj в результате решения имеет какую-либо целую часть J;

· тогда оптимальное решение ЗЛП (1)…(3) будет удовлетворять либо линейному ограничению , либо линейному ограничению .

· (1)

· (2)

· (3)

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

Затем каждая подзадача решается как ЗЛП. Если полученный оптимум оказывается допустимым для целочисленной задачи, то данное решение фиксируется как наилучшее, в противном случае подзадача разбивается на две подзадачи с получением наилучшего решения и его фиксации.

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

<< | >>
Источник: Шпаргалка по дисциплине Методы оптимизации. 2017
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 12. Метод ветвей и границ решения задач целочисленного программирования:

  1. 49.Метод ветвей и границ решения целочисленных задач.
  2. 48.Метод метод ветвей и границ для решения целочисленной задачи ЛП.
  3. 10 Классификация методов решения задач целочисленного программирования
  4. 11 Метод Гомори решения задач целочисленного программирования
  5. 46. Общая постановка задач дискретного и целочисленного программирования. Экономические задачи, относящиеся к задачам целочисленного программирования.
  6. Целочисленные задачи линейного программирования: сфера применения, основные понятия, задача о коммивояжере, задача календарного планирования.
  7. Целочисленное программирования. Задача о коммивояжере. Метод на основевыигрышей.
  8. Целочисленное программирования. Задача о коммивояжере. Метод на основе выигрышей.
  9. Метод ветвей и границ.
  10. 7.2.Сведение задач линейного программирования к целочисленным.
  11. Целочисленное программирование. Задача о ранце.
  12. Лекция №9. Метод ветвей и границ.
  13. Формальная схема метода ветвей и границ.
  14. Задача линейного программирования. Графический метод решения.
  15. 47. Графический метод решения задач линейного программирования.
  16. Симплекс-метод решения задачи линейного программирования.
  17. Оценка оптимальности решения задачи линейного программирования симплекс-методом
  18. 7.1.Целочисленное дискретное программирование
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -