WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 10 | 11 || 13 |

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

В общем случае (n > 3) определение оптимального положения точки x рассматриваемым методом смещений также начинается с вычислений совмещенной матрицы кратчайших маршрутов (табл. 48). В каждой строке i = k определяется наиболее длинный маршрут (табл. 48, столбец Lmax ):

k Lmax = max{L0, j}= L0 m, k =1,n, 0 m, jm, (7.15) k k k, j k, j 1 jn где jm – номер концевого пункта Aj m наиболее длинного маршрута.

Номер пункта i = k1 начального размещения точки x определяется из условия minL0 m = min max{L0, j}= L01 m i = k1. (7.16) k k, j k, j k 1k n1 jn Таким пунктом для рассматриваемого примера (табл. 47) является пункт A6 k1 = 6. Дальнейшая оптимизация возможна путем смещения точки x от пункта Ak = A6 по начальной дуге (6;4) маршрута 0 = 6,1. Условие (7.15) разбивает множество I номеров пунктов на m k1, j две группы: {j}m = {1,4,5}m – номера концевых пунктов тех маршрутов, длина которых убывает (индекс m) при смещении точки x по начальной дуге (ребру) маршрута (7.15); {j}B = {2,3,6} – множество номеров пунктов, длина маршрутов к которым возрастает при этом. Номер jB концевого пункта Aj B наибольшего по длине маршрута находится из условия B max {L0, j}= L0 B 0 B, j. (7.17) k k, j k, j j{j}B Для рассматриваемого примера согласно (7.15), (7.17) имеем L0 m = L0;1 = 5, L0 B = L0;2 = 4, j =1, jB = 2 (k = k1 = 6).

6 k, j k, j При смещении точки x от пункта A6 по дуге (6;4) величина смещения x определяется из условия, что длина убывающего маршрута сравняется с длиной возрастающего маршрута:

L0 m = L0 B, т.е. Lk, j m - x = Lk, j B + x, (k = k1). (7.18) x, j x, j Из (7.18) для рассматриваемого примера имеем x = 0,5 L01 m - L01 B = 0,5(5 - 4)= 0,5. (7.19) k, j k, j Оптимальное положение точки x находится на расстоянии 0,5 ед. от пункта A6 по дуге (6;4), (рис.1). При этом длина каждого из множества {j}m убывающих маршрутов уменьшится на 0,5 ед., а возрастающих – увеличится на 0,5 ед. Длины кратчайших маршрутов из оптимальной точки x0 станут равными (сравни с L0, j ; табл. 47):

Таблица j 1 2 3 4 5 L4,5 4,5 3,5 1,5 4,5 0,x0, j Длина маршрута до наиболее удаленного пункта при этом минимальна и равна L(x0)= 4,5 ед.

Примечание. Был использован сокращенный метод смещения, при котором начальное положение точки x выбрано из условия (7.16), что сокращает число смещений точки x при оптимизации.

Например, при начале в пункте A1 будем иметь (табл. 47, i = 1):

{j}m = {2,3,4,5,6}, {j}B = {1}. L0 = 9, L0 = 0.

1, jm 1, jB Согласно (7.19) x = 0,5(9 - 0) = 4,5 ед., однако x не может быть больше длины начальной дуги (1;4), c1,4 = 3, поэтому при x = min{4,5;3}= 3 первое смещение точки x приводит к пункту A4.

Далее имеем {j}m = {2;6}, {j}B = {1,3,4,5}. L0 = 6, L0 = 3, x = 1,5 < C4,6 = 4, jm 4, jB Смещая точку x по дуге (4;6) на x = 1,5 ед., приходим к тому же решению x0 (табл. 49).

Начальным не может быть тот пункт, для которого смещение x = 0 ( A3 ).

В зависимости от исходных данных и в первую очередь размеров района размещения n пунктов, даже при оптимальном решении x0, расстояние Lm(x0, R) при R = 1 может оказаться больше максимально допустимого значения Lдоп, обусловленного некоторыми практическими требованиями. Возникает задача такого покрытия района сетью обслуживающих точек x =(xr), при котором выполняется условие R Lm(x, R) Lдоп, r = 1, R, (7.20) а количество R обслуживающих точек минимально (обратная задача покрытия).

Примечание. Прямая задача покрытия состоит в таком размещении заданного количества R точек x0 =(x0,r), которое для R каждого ( r = 1, R ) обслуживаемого участка района с пунктами r Aj, j {j}k обеспечивает наименьшее расстояние (время достижения) до наиболее удаленного пункта Lm(x0,1) (7.14).

Решение обратной задачи можно получить, решив несколько раз (при различных значениях R ) прямую задачу. Далее рассмотрим возможный подход к решению прямой задачи при R > 1. На примере табл. 47 найдем решение для случая R = 2.

Основная идея решения состоит в том, чтобы путем попарного ( R = 2 ) сравнения строк (их элементов L0, j ) найти такую пару, при i которой согласно (7.7) будет возможно максимально уменьшить наибольшие элементы L0, j. Далее такое сравнение производится до i смещения точек xr от их пунктов размещения (проверка на такое смещение является заключительным этапом решения).

Из строки i = 6 табл. 47 видно, что наибольшие элементы L0,1 и L0,6 можно уменьшить, если базу r = 2 (точка x2 ) поместить в пункте A4. При полученном текущем решении (xr) = (A6, A4) согласно (7.7) имеем L0 r (R) ={34;1, 46;2, 34;3, 04;4, 34;5, 06;6}, maxL0 r (R) = 46; k, j k, j j n ЭiТ j, Элемент L6;2 = 4 из всех значащих элементов столбца j = 2 является наименьшим, поэтому уменьшить его значение можно только путем перемещения точки x1 из пункта A6 в пункт A2. При решении (xr) = (A2, A4) имеем Lm(x,2) = max34;1, 02;2,, 34;3, 04;4, 34;5, 24;6 = 3, x0 :(A2, A4). (7.21) Уменьшить значение Lm(x,2) = 3 возможно только путем введения еще трех дополнительных точек xr в пунктах A1, A3, A5, при этом получим Lm(x,5) = 2.

Улучшить решение путем смещения любой из точек x1 (A2), x2(A4) также невозможно. Сдвиг х2, например, по дуге (4;5) на x > 0 приведет к увеличению на x расстояний до пунктов A1 и A3 (табл. 47, i = 4 ).

Решение (7.21) оптимально.

Получим решение обратной задачи. Например, при 3 Lдоп < 4,условие (7.20) будет выполнено при двух ( R = 2 ) пунктах обслуживания, размещенных в точках A4 и A2 (7.21).

Ориентированный граф G(A, M ) отражает более жесткие требования к сети (городская дорожная сеть), и при прочих равных условиях решение не может улучшиться. Например, из табл. 46 точка x (R = 1) может быть расположена в одном из трех пунктов A1, A3, A6, при этом расстояние до любого из других пунктов не превысит 9 ед. Из этих пунктов предпочтение может быть отдано одному, исходя из каких-либо иных соображений.

Например, полагая, что все n маршрутов будут использоваться с одинаковой частотой 1/ n, можно найти среднюю длину маршрута по формуле Lср = L n, k {1,3,6}.

k k В этом случае предпочтение должно быть отдано варианту размещения точки x в пункте A6, т.к. при этом средняя длина маршрута будет минимальна.

При размещении точки x в любом из пунктов ее смещение может быть целесообразно, как правило, только по ребру, что дает право транспортным средствам двигаться в обоих направлениях. Проверим, что поместив точку x в пункте A3, невозможно далее уменьшить самый длинный маршрут L0,2 = 9 и улучшить решение. Действительно, сдвинув точку x от пункта A3 по дуге (3;4) на величину x > 0, получим уменьшение длин маршрутов к пунктам A2, A4, A5, A6 (табл. 46, строка i = 3) на величину x, однако длины маршрутов к пунктам A1 и Aнамного увеличатся:

L0,1 = (с3,4 - x)+ L0,1 = (3 - x)+ 10 =13 - x >10, (x < 3).

3 Ухудшение решения обусловлено тем, что при смещении точки x от пункта A3 к пункту A4 добираться к пункту A1 придется окольным путем через пункт A4.

Примечание. Если на участке от A3 до A4 разрешить двухстороннее движение (дугу (3;4) заменить ребром c3,4 = с4,5 = 3), то согласно (7.19) получим x = 2 и решение улучшится:

L(x,1) = max{7,7,2,1,4,3}= 7.

1 jn Наибольшее улучшение решения аналогичным путем будет получено при начальном размещении точки x в пункте A1 при замене дуги (1;4) ребром (c1,4 = c4,1 = 3). Точка x сместится в пункт A4, при этом L(x,1) = 6.

Вводить очередную точку следует, максимально улучшив вариант размещения предыдущих точек. Для этого в строке i = 3 (пусть в Aнаходится точка x1) следует найти по крайней мере два наибольших элемента L0, j (L0,2 = 9, L0,5 = 6) и путем выбора пункта размещения точки 3 3 x2 попытаться уменьшить значение найденных элементов, начиная с наибольшего. Помещая точку x2 в любом из пунктов с номерами {j}x = {2,4,5,6} (табл. 46, Li,2 L3,5 = 6), согласно (7.7) получим улучшенное решение Lm(x,1) = 6. Из множества {}x теперь следует i попытаться выбрать пункт размещения точки x2, при котором новое значение целевой функции (7.14) станет меньше шести. Номер i {j}x оптимального пункта размещения точки x2 следует искать в столбце j = 5, в котором находится второй из наибольших элементов (L0,5 = 6).

i Строки с номерами i {2;6} сразу отпадают, т.к. они только ухудшат решение (L0,5 = 12, L0,5 = 9 > 6). Выбор любой из оставшихся строк {4;5} 2 также не позволяет улучшить решение:

i = 4 : Lm(x,2) = max{53;1, 64;2, 03;3, 04;4, 34;5, 24;5}= 6, Lср 2,7, (7.22) j i = 5 : Lm(x,2) = max53.1, 65.2, 03.3, 33.4, 05.5, 53.6 = 6, Lср 3,2.

j Смещением точек x1, x2 от вершин решения не улучшаются, поэтому окончательный выбор можно сделать из условия минимума средней длины маршрута, поместив точку x2 в пункте A4.

Обслуживаемые пункты распределятся на обслуживание следующим образом [см. (7.22)]:

из точки x1 (A3) пункты {A1, A3}, из точки x2 (A4) пункты {A2, A4, A5, A6}.

Маршрут к каждому из них и его длина записаны в табл. 46.

Выводы 1. Определение экстремальных точек на графе (минисуммных и минимаксных) согласно рассмотренной методике выполняется в два этапа:

- построение полного множества кратчайших маршрутов (предварительный этап);

- размещение R точек xr (r = 1, R) на графе, удовлетворяющих заданным требованиям, методом перемещений.

2. Решения минисуммной и минимаксной задач совпадают по мере увеличения числа точек R, покрывающих граф. При R = n покрывающие точки находятся в вершинах графа, а значения целевых функций равны нулю.

3. Решение минисуммной задачи соответствует вершинам графа.

4. Решение минимаксной задачи, как правило, лежит на ребрах графа (граф неориентированный, смешанный) или в вершинах (граф ориентированный).

ЗАКЛЮЧЕНИЕ Любая сложная практическая задача, математическую модель которой не удается представить в форме, доступной для решения и анализа известными методами, требует поиска и разработки новых подходов и методов решения. Поиск таких подходов и методов, как правило, начинается с неформального анализа задачи, сопутствующих ей условий, частных случаев, отражающих отдельные её стороны, изучение которых раскрывает проблему в целом и позволяет наметить наиболее перспективные пути дальнейших исследований.

Задача коммивояжера, весьма простая в своей концептуальной постановке, является довольно сложной для формализации и ещё более сложной для решения, особенно в том случае, когда речь идёт о задаче большого размера (n > 500). На первый план при этом выступают неформальные (эвристические) методы, основанные, как правило, на использовании некоторых специфических особенностей задачи или её физических аналогов.

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

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

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

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

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

Принудительное включение не вошедших в цикл пунктов является основным содержанием метода расширения цикла. Поскольку на каждом шаге процесса используются все интервалы цикла, то можно предполагать и дальновидность решения, принимаемого на каждом шаге процесса.Анализ численных решений, полученных для рассмотренных примеров, приводит к выводу о целесообразности включения в тот или иной интервал цикла не просто очередного индекса j Gt, а совместно с некоторыми участками кратчайших маршрутов, соединяющими этот элемент с границами интервала. Эта идея положена в основу модифицированных методов решения классической и обобщенной задач коммивояжера. Указанная идея позволила найти решение важного класса задач коммивояжера для случая, когда матрица расстояний cij не является полной ( <1). Рассмотренная идея, позволившая модифицировать метод расширения цикла и расширить класс задач, решаемых на его основе, снова приводит к необходимости применения Процесс «на каждом шаге иди к ближайшему пункту» такой «дальновидностью» не обладает и может привести к грубым ошибкам [12].

эстафетного метода как одного из важных этапов решения задач коммивояжера.

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

Практический интерес может представлять случай, когда задача состоит в построении гамильтонова цикла, обеспечивающего минимальное время доставки грузов, при условии, что скорость передвижения транспортного средства меняется по некоторому закону в зависимости от степени его загрузки (0< <1). Решение такой задачи пока неизвестно и для случая линейной зависимости скорости движения по участку i, j от степени загрузки Vij () = (Vijmin - Vij ) + Vij, где Vijmin – скорость на участке i, j при полной загрузке ( =1) ; Vij – скорость без загрузки ( = 0).

Рассмотренные методы позволяют предложить различные подходы при дополнительных условиях: наличие двух и более коммивояжеров;

ограничения по грузоподъемности транспортного средства и т.п.

Приложение Определение пропускной способности сети методом Форда-Фалкерсона и методом улучшения оценок В работе [14, с. 549] приведен пример графа сети, который несмотря на малый размер (п = 4) при определении пропускной способности сети из пункта А1 в пункт А4 методом Форда-Фалкерсона может, в силу специфики метода, потребовать при решении 2 000 000 (2 · 106) итераций.

Данный пример представлен в графическом и матричном виде на рис. 1.

j = 1 2 3 A106 i = 106 = c С2,3=AA106 AРис. 1. Представление графа сети В [14] подробно рассматривается данный пример. Столь низкая вычислительная эффективность обусловлена той особенностью метода, что в ходе решения предусматривается возможность манипуляций с отрицательными плотностями потоков и отрицательными пропускными способностями. Получим решение данного примера методом улучшения оценок (раздел 6).

Согласно 2° алгоритма (рис. 6) имеем начальную оценку сверху искомой пропускной способности оптимального маршрута 1 = min 106;106 = 106.

{ } 1,По начальной оценке 1 (в матрице с игнорируется только элемент 1,c2,3=1) строятся маршруты из пункта А1 в пункт А4:

А 1, = 1,2,4,1,4 =106, (1) = 1,3,4, 1,4 =106.

1, А1 ААТак как оба полученных оптимальных маршрута независимы (не имеют общих дуг), то они и составят пропускную способность сети 0 0 1,4 = 1,4 + 1,' = 106 +106 = 2 106.

В остаточной матрице согласно 5° (рис. 7) только один значащий элемент – c2,3 = 1, что исключает возможность дальнейшего увеличения пропускной способности сети (рис. 7, 6о).

Pages:     | 1 |   ...   | 10 | 11 || 13 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.