Logo GenDocs.ru

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

Загрузка...

Лекции по ТПР - файл Лекция№9-тпр.doc


Загрузка...
Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№9-тпр.doc

Реклама MarketGid:
Загрузка...
Лекция №9.

Метод ветвей и границ.

Метод ВИГ (или метод направленного перебора) относится к группе комбинаторных методов решения как линейных, так и нелинейных ЗДП. Этот метод дает общий подход к решению ЗДП, содержащих конечное число допустимых планов, и за конечное число шагов позволяет найти точное решение задач конечной размерности. Разные реализации метода объединяются общей идеей перехода от полного перебора планов к целенаправленному, сокращенному перебору. Сокращение перебора осуществляется за счет массового отсечения неперспективных планов.

Пусть имеет место задача ДП в общем виде:

(1)

Здесь f(X)- скалярная функция своих аргументов, G- конечное множество.

Несмотря на большое разнообразие алгоритмов, разрабатываемых для решения прикладных задач вида (1), им всем свойственны общие основные этапы:

  1. Вычисление нижней границы целевой функции f(X) на множестве G и его подмножествах (в случае решения задачи на максимум – вычисление верхней границы),

  2. Разбиение множества G на дерево подмножеств,

  3. Пересчет нижней границы f(X) на подмножествах,

  4. Вычисление допустимых планов,

  5. Проверка планов на оптимальность,

  6. В случае получения приближенного решения – оценка его точности.

Рассмотрим все эти этапы.

  1. Вычисление нижней границы (оценки) целевой функции f(X) на множестве планов G или его подмножествах Gi G сводится к определению числа , для которого справедливо неравенство , или .

  2. Разбиение (ветвление) множества G на дерево подмножеств.

Определение. Множества и называются разбиением множества G на подмножества Gi.

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

Ветвление происходит по следующей схеме:

0-й шаг. Имеется исходное множество G=G0. Некоторым способом его разбивают на конечное число подмножеств .

к-тый (k>0) шаг. Имеются множества , еще не подвергшиеся ветвлению. По определенному правилу, указанному ниже, среди них выбирают подмножества и разбивают их на конечное число подмножеств . Затем еще не подвергавшиеся на этом шаге разбиению множества и новые подмножества , обозначают (перенумеровывают) как .(Рис.1.)





  1. Пересчет нижних границ целевой функции f(X) на подмножествах.

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

  1. Вычисление допустимых планов.

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

  1. Проверка планов на оптимальность.

Пусть имеется разбиение и найден некоторый план . Если при этом , то - оптимальный план исходной задачи (1).

Действительно, из последнего неравенства следует, что для , а так как , то окончательно можно записать для .

  1. Оценка точности приближенного решения.

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

Формальная схема метода ветвей и границ.

0 шаг. Обозначается . Вычисляется нижняя граница целевой функции . Если при этом удается найти такой план , что , то - оптимальный план задачи (1).

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

1 шаг. Вычисляют нижние границы на полученных подмножествах: . Если удается найти такой план , что и , то - оптимальный план задачи (1).

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

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

В противном случае снова выбирают для разбиения наиболее перспективное множество по правилу: . Далее не подвергшиеся разбиению и , на данном шаге переобозначают как .

Этот процесс ветвления продолжается до тех пор, пока не будет найдено решение задачи (1).

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


Скачать файл (681.7 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru