Автор работы: Пользователь скрыл имя, 03 Июня 2012 в 11:43, реферат
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.
Введение 3
1. Понятие о методе ветвей и границ 5
2. Общая схема метода ветвей и границ 6
3. Применение метода ветвей и границ в решении прикладных задач 8
3.1. Задача о ранце 8
3.1.1. Математическая модель задачи. 8
3.1.2. Пример решения задачи о ранце 9
3.2. Задача Коммивояжера 13
3.2.1 Определения 14
3.2.2. Постановка задачи 15
3.2.3. Решение задачи 15
3.2.4. Разбиение множества маршрутов на подмножества 17
3.2.5. Пример решения задачи коммивояжера методом ветвей и границ 17
3.3. Решение целочисленных задач линейного программирования 24
3.3.1. Алгоритм решения: 24
3.3.2 Иллюстрация метода ветвей и границ на примере 27
Заключение 31
Список использованных источников: 32
| Задача 6 | Задача 7 |
| Z=3x1+x2→max
при ограничениях: 4xl + Зх2 < 18 x1 + 2x2 £ 6 0 £ x1 £ 3 1 £ x2 £ 4 х1, x2 — целые числа. |
Z=3x1+x2→max
при ограничениях: 4xl + Зх2 < 18 x1 + 2x2 £ 6 4 £ x1 £ 4 1 £ x2 £ 4 х1, x2 — целые числа. |
Список задач: 6 и 7. Значение Z0 = 12.
VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.
Получим, что условия задачи 7 противоречивы.
VII этап. Решаем задачу 6 симплексным методом.
Получим Zmax = 10,5 ,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5).
Так какZ(X6*) = 10,5 < Z0 = 12, то задача исключается из списка.
Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X* = Х4* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax = 12
Замечание 1. Нетрудно видеть, что каждая последующая задача, составляемая в процессе применения метода ветвей и границ, отличается от предыдущей лишь одним неравенством — ограничением. Поэтому при решении каждой последующей задачи нет смысла решать ее симплексным методом с самого начала (с I шага). А целесообразнее начать решение с последнего шага (итерации) предыдущей задачи, из системы ограничений которой исключить "старые" (одно или два) уравнения — ограничения и ввести в эту систему "новые" уравнения — ограничения.
Заключение
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Очевидным недостатком алгоритма метода ветвей и границ при решении задач большой размерности является необходимость перебрать слишком большое количество вариантов перед тем, как будет найден оптимальный план. Однако он отчасти может быть преодолен, если ограничиться поиском не оптимального, а просто «хорошего» (близкого к оптимальному) плана. О степени такой близости и скорости приближения к экстремуму нетрудно судить по изменению значений оценок.
Список использованных источников: