Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 40

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 84 >> Следующая


Теорема 3.2. Если правило отсева в методе ветвей и границ имеет вид ^p(Gk) > / (ж) + Rj то для любого х Є Gk выполнено неравенство f(x) > f(x°) + Rj т.е. х ?. S(R).

Доказательство. Пусть х є Gk и множество Gk отсеяно. Тогда по определению оценки / (х) > ^p (Gk). Отсюда получим / (х) > > ip (Gk) > / (х) + R> / (ж0) + Rj т.е. f(x) > f(x°) + Rj и, значит, х ?. S(R). Теорема доказана.

Как следует из теоремы 3.2, обобщенное правило отсева имеет вид

<p(Gk)>f(x)+R. (3.7.2)

Как уже отмечалось в 3.3.4, предложенный подход может быть применен для решения многокритериальных задач дискретной оптимизации. При этом под решением многокритериальной задачи понимается пересечение всех множеств і^-близких решений по каждому из критериев.

3.7.2. Аппроксимационно-комбинаторный метод решения задач дискретной оптимизации. Описанный выше алгоритм нахождения множества всех і^-близких решений применяется в аппрок-симационно-комбинаторном методе. Этот метод предложен В. Р. Хачатуровым [43] и широко применяется при решении задач [13, 44]. В этом методе реализуется основная идея комбинаторных методов: выделяется множество G1 С Gj содержащее оптимальное решение исходной задачи (1.1.1); множество G\G' исключается из дальнейшего рассмотрения. Изложим, следуя [43], основные понятия этого метода.
Гл. 3. Метод ветвей и границ

115

На множестве G определяется аппроксимизирующая функция F(X)1 ТаКаЯ’ЧТ° f(x°)>F(X°). (3.7.3)

Предполагается, что для аппроксимизирующей функции F(x) на множестве G можно решить не только задачу

F(x) = minF(x), (3.7.4)

но и задачу определения всех точек х Є G1 удовлетворяющих при R > 0 условию

F (х) < F (х) < F (х) + R. (3.7.5)

Обозначим через G(R) множество точек, удовлетворяющих условию

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

F (х) > F (x) + R. (3.7.6)

Аппроксимизирующая функция F(x) должна быть введена так, что

IG(R)\ <С N1 так как в дальнейшем задача (1.1.1) решается на множестве G(R)1 множество G\G(R) исключается из рассмотрения.

Выберем число D такое, что F (х) < D и определим подмножество G(R) точек, удовлетворяющих условиям (3.7.5) и (3.7.6) при F (ж) + R = D. На множестве G(R) решим задачу

/(ж*) = min / (х) (3.7.7)

и примем X* и f(x*) в качестве решения задачи (1.1.1). Покажем, что если /(ж*) < D1 то х* = X01 т.е. ж* есть решение задачи (1.1.1). Покажем, что х° Є G(R)1 т.е. выполнено условие (3.7.5). Действительно, F(x) +R = D > /(ж*) > f(x°) > F(x°) > F(x).

Это означает, что оптимальное решение исходной задачи находится в множестве всех і^-близких решений аппроксимизирующей задачи.

Учитывая условия (3.7.7) и f(x*) < D1 получаем, что х* = X01 f(x*) = f(x°).

Приведем графическую иллюстрацию для функции одной переменной (рис. 3.27). Множество G(R) содержит оптимальное решение исходной задачи, множество G\G(R) исключаются из рассмотрения.

Рассмотрим применение изложенного подхода для решения симметричной задачи коммивояжера. В качестве нижней оценки рассмотрим длину кратчайшего 1-дерева. Пусть Z — множество всех маршрутов замкнутой задачи и T — множество всех 1-деревьев; очевидно, что ZcT. При этом длина маршрута l(z) и аппроксимирующая функция L(t) — длина 1-дерева t Є T — определены на различных множествах Z и Т. Доопределим длину маршрута следующим образом:

(Iyz), если z ? Z1

I (z) — \

\ M1 если ^ Є T\Z,
116

Разд. II. Комбинаторные методы решения задач

Рис. 3.27

здесь M > О — сколь угодно большое положительное число. Зададим R > О, найдем кратчайшее 1-дерево to с длиной L (to) и все 1-деревья, удовлетворяющие условию

L(to) < L(t) < L(to) + R. (3.7.8)

Решение задачи коммивояжера ищем среди 1-деревьев, степени всех вершин которых равны 2, при условии (3.7.8). Если среди 1-деревьев нет таких, у которых степени всех вершин равны 2, то необходимо увеличить R.

В [13] рассматриваются задачи дискретной оптимизации, для решения которых применяется аппроксимационно-комбинаторный метод.
Глава 4

Применение метода динамического программирования для решения некоторых аддитивных задач дискретного программирования

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

Мы не будем описывать методологические основы динамического программирования, они описаны в многих работах, например [1, 4, 10-12]. Далее рассмотрим три известные задачи дискретного программирования, для каждой из которых описан алгоритм динамического программирования, сформулирован принцип оптимальности и выписано уравнение Веллмана как формальное описание принципа оптимальности.
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100