АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Метод ветвей и границ. Задача о рюкзаке

Читайте также:
  1. F. Метод, основанный на использовании свойства монотонности показательной функции .
  2. FAST (Методика быстрого анализа решения)
  3. I этап Подготовка к развитию грудобрюшного типа дыхания по традиционной методике
  4. I. 2.1. Графический метод решения задачи ЛП
  5. I. 3.1. Двойственная задача линейного программирования
  6. I. 3.2. Двойственный симплекс-метод.
  7. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  8. I. Метод рассмотрения остатков от деления.
  9. I. Методические основы
  10. I. Методические основы оценки эффективности инвестиционных проектов
  11. I. Организационно-методический раздел
  12. I. Предмет и метод теоретической экономики

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

Предположим, что задача состоит в отыскании минимума функции f на конечном множестве X. Для успешного применения метода ветвей и границ нужно уметь на подмножествах X1⊆X находить оценку снизу для функции f (при нахождении максимума – оценку сверху). Число f1, равное нашей оценке функции f на множестве X1, называется границей для функции f на X1.

Процесс решения задачи методом ветвей и границ проходит по следующему алгоритму:

1) Разбиваем множество X на два подмножества X1 и X2, находим на каждом из них границу f1 и f2;

2) Выбираем множество, на котором оценка минимальна (при поиске минимума), разбиваем его на два подмножества X3 и X4 (этот процесс называется ветвлением), находим на каждом из них границу f3 и f4 (при этом само это множество исключается из списка подмножеств);

3) На каждом шаге мы имеем разбиение исходного множества X на конечное число подмножеств (на первом этапе это два множества X1 и X2, на втором – три множества и т.д.), для каждого из которых известна граница целевой функции f. Повторяем пункт 2 до тех пор, пока в каком-то из получающихся подмножеств не найдется настоящий минимум (подмножество будет иметь настолько небольшой размер, что нахождение минимума будет не очень сложной задачей). Такой минимум тоже является оценкой для множества, только в отличие от остальных данная оценка является точной;

4) Отбрасываем те подмножества из нашего списка, граница у которых не меньше, чем значение функции f в найденной точке (т.к. в этих подмножествах минимум функции f не может находиться).

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

При воплощении этого алгоритма часто используется дерево вариантов. Вершинам данного дерева соответствуют множества X, X1, X2, …, Xn и их оценки. Из каждой вершины-множества дуги ведут к его подмножествам, получающимся при ветвлении. Если у вершины (множества) имеется точная оценка, такую вершину помечаем звездочкой (в этой вершине далее ветвление не происходит, а ее оценка используется для прекращения ветвления в тех вершинах, у которых оценки больше).

Таким образом, для того, чтобы решать задачу методом ветвей и границ, необходимо:

1.Предложить метод ветвления, т.е. разбиения множества всех вариантов X на подмножества;

2.Для каждого из подмножеств, получающихся при ветвлении указать способ для вычисления границы (оценки целевой функции на данном подмножестве).

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)