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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 84 >> Следующая

190

Разд. IV. Задачи большой размерности

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

Единственное оптимальное решение этой задачи zо = (1,2,..., гг, 1) с длиной маршрута I (zo) = пр находится с трудоемкостью О (п2) операций с применением алгоритма перехода в ближайшую точку, начиная с первой.

Рассмотрим задачу коммивояжера, для которой сц = Co +? > 0, Eij > 0 И все Eij различны И существенно меньше, чем Co: Eij Co-Обозначим Eі = min Eij1 ?2 = max Eij. Пусть zо — оптимальное решение и z — решение, полученное по правилу перехода в ближайшую точку, начиная с первой. Тогда

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

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

(9.1.1). В то же время задача о поиске г-приближенных решений легко решается с применением правил г-отсева из гл. 5.

При большом числе оптимальных (или г-оптимальных) решений возникают трудности принципиального характера для алгоритмов поиска точного решения задачи (1.1.1). Большое число таких решений, по-видимому, является одной из характеристик задачи большой размерности. Представляет интерес выделение классов задач этого типа. Одной из таких задач является описанная выше задача коммивояжера. В качестве другой можно привести известную задачу о ранце [42], приведенную в гл. 3:

P1 если j = і + 1, г = 1,2,...,7? — 1; P1 если і = Ti1 j = I; q > р во всех остальных вариантах.

п (с0 + Єї) < Z (?) <l(z) <п (с0 + е2), l(z) -I(Z0) < П (б2 -S1).

п (со + Єї) < d < I (z).

п

2Xj —> max,

J=1
Гл. 9. Вычислительная модель и параметризация

191

J=I

1}, j = 1,2,... ,п

п > 4,

п .2.

При нахождении точного решения этой задачи с применением алгоритма ветвей и границ типа Ленд и Дойг число вершин дерева ветвления (т.е. число решенных задач линейного программирования)

2 п

оценивается в асимптотике по п как ——, т.е. близко к полному пере-

уп

бору с трудоемкостью 2П.

Для обеих описанных задач до начала процесса решения известно, что они являются задачами большой размерности. Выделение классов таких задач для общей задачи (1.1.1) является очень важным и актуальным. Результаты такого типа для общей задачи (1.1.1) нам неизвестны. При поиске таких задач следует обратить внимание на TVP-трудные задачи [6].

Далее предлагается модель вычислительного процесса для решения задачи (1.1.1) большой размерности с применением комбинаторных методов; эта модель позволяет выделить некоторые из параметров, характерных для задачи большой размерности.

9.2. Вычислительная модель и основные параметры

Предполагается, что в процессе решения задачи каким-либо из комбинаторных алгоритмов вычисляется значение функции f(x) для всех х Є Go С G, I Go I = No, \G\ = N, 0 < TV0 < N. Все точки (варианты) из множества G\Go отбракованы по каким-либо правилам отсева. Обозначим через So время, необходимое для вычисления одного значения /(ж), через sі среднее время реализации отсева одного варианта (точки) х Є G\Go; T (Go), T (G\Go) и T (G) — времена для вычисления всех значений /(ж), х Є Go, для реализации отсева всех х Є G\Go и для полного перебора соответственно. Тогда

T (Go) + T (G\G0) < T (G), (9.2.1)

причем равенство в (9.2.1) можно опустить, так как оно соответствует алгоритму полного перебора. Соотношения типа (9.2.1) впервые получены в [13] и являются основными при построении вычислительной модели. Из (9.2.1) получаем

SoA^o + Si (N — No) < SoN, Si (N — No) < so (N — No), (9.2.2)

О < р = — < 1. (9.2.3)
192

Разд. IV. Задачи большой размерности

Условие (9.2.3) — это условие реализуемости комбинаторного алгоритма для решения задачи (1.1.1). Ясно, что алгоритм может быть реализован лишь при значениях р, близких к нулевым. Значения р, близкие к 1, характеризуют задачу большой размерности. Целью дальнейшего исследования является выделение областей изменения параметра р, характеризующих задачи обоих типов. Параметры, описывающие эти области, зависят от значения времени Tq, выделенного для решения задачи.

Введем параметры а = —- и s = , 0 < а < 1, 0 < s < 1.

T(G) N

Как следует из (9.1.1), задача большой размерности, в частности, характеризуется условием

T (Go) + T (G\Go) > Tb, (9.2.4)

которое можно переписать в виде

T (G0) + T (G\G0) > аТ (G), S0N0 + S1 (N - N0) > as0N. (9.2.5)

Из (9.2.5) получим

°<Н = ^<^<1- ^2-6)

Если считать, что 0<s<a<l,TO это приводит к естественным условиям
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100