Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок
Решены вопросы оперативной модификации матрицы расстояний, применительно к задачам поиска оптимального порядка обслуживания стоящих в очереди и неравноценных по значимости заявок....
Gespeichert in:
| Datum: | 2007 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6484 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок / А.И. Иванешкин // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 149-154. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-6484 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-64842025-02-10T00:33:43Z Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок Modification of distances matrix in a method of branches and borders to optimaze the structure of demands queue Иванешкин, А.И. Решены вопросы оперативной модификации матрицы расстояний, применительно к задачам поиска оптимального порядка обслуживания стоящих в очереди и неравноценных по значимости заявок. The problems of operative modification of distances matrix in conformity with tasks of search of the optimum order of service of demands, wich are both waiting in queue and unequal on importance are solved. 2007 Article Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок / А.И. Иванешкин // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 149-154. — Бібліогр.: 3 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6484 65.012.122 ru application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Решены вопросы оперативной модификации матрицы расстояний, применительно к задачам поиска оптимального порядка обслуживания стоящих в очереди и неравноценных по значимости заявок. |
| format |
Article |
| author |
Иванешкин, А.И. |
| spellingShingle |
Иванешкин, А.И. Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| author_facet |
Иванешкин, А.И. |
| author_sort |
Иванешкин, А.И. |
| title |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| title_short |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| title_full |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| title_fullStr |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| title_full_unstemmed |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| title_sort |
модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2007 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/6484 |
| citation_txt |
Модификация матрицы расстояний метода ветвей и границ в решении вопроса оптимизации структуры очереди заявок / А.И. Иванешкин // Комп’ютерні засоби, мережі та системи. — 2007. — № 6. — С. 149-154. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT ivaneškinai modifikaciâmatricyrasstoâniimetodavetveiigranicvrešeniivoprosaoptimizaciistrukturyočeredizaâvok AT ivaneškinai modificationofdistancesmatrixinamethodofbranchesandborderstooptimazethestructureofdemandsqueue |
| first_indexed |
2025-12-02T05:25:32Z |
| last_indexed |
2025-12-02T05:25:32Z |
| _version_ |
1850372922589315072 |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2007, № 6 149
A.I. Ivaneshkin
MODIFICATION OF
DISTANCES MATRIX
IN A METHOD OF BRANCHES
AND BORDERS TO OPTIMAZE
THE STRUCTURE
OF DEMANDS QUEUE
The problems of operative modifica-
tion of distances matrix in conformi-
ty with tasks of search of the opti-
mum order of service of demands,
wich are both waiting in queue and
unequal on importance are solved.
Решены вопросы оперативной мо-
дификации матрицы расстояний,
применительно к задачам поиска
оптимального порядка обслужи-
вания стоящих в очереди и нерав-
ноценных по значимости заявок.
А.И. Иванешкин, 2007
УДК 65.012.122
А.И. ИВАНЕШКИН
МОДИФИКАЦИЯ МАТРИЦЫ
РАССТОЯНИЙ МЕТОДА ВЕТВЕЙ
И ГРАНИЦ В РЕШЕНИИ
ВОПРОСА ОПТИМИЗАЦИИ
СТРУКТУРЫ ОЧЕРЕДИ ЗАЯВОК
При решении различного рода оптимизаци-
онных задач практически всегда приходится
иметь дело с ситуацией, связанной с выбо-
ром средств, способных обеспечить получе-
ние результата если не за минимальное, то
за приемлемое время. Решение подобных во-
просов методами пошагового линейного про-
граммирования, как правило, сопряжено с
достаточно громоздкими моделями, содержа-
щими большое число целочисленных пере-
менных, а посему делающих их крайне не-
удобными в реализации.
Имеется и другой [1], равноценный по по-
становке задачи подход, состоящий в форму-
лировке задачи упорядочения конечного
множества элементов = {1,2,…,N} как за-
дачи поиска перестановки *, оптимизирую-
щей значение некоторой целевой функции
(функций), определенной на множестве до-
пустимых на перестановок = {n1,n2,…,
nq, …,nN}. Однако применение для указанных
целей методов, основанных на подлежащих
конструированию, рекуррентно задаваемых
на множестве перестановок функциях (,q),
использующих понятие (s,t)-окрестности q-го
по порядку элемента -перестановки, зачаc-
тую не обладает достаточной степенью эф-
фективности. Если (,q) не является при-
оритетным индексом, сопутствующие ука-
занным методам сложности реализации име-
ют тенденцию возрастать с ростом размер-
ности множества элементов .
Сведение алгоритма поиска решения к фо-
А.И. ИВАНЕШКИН
Комп’ютерні засоби, мережі та системи. 2007, № 6 150
рмированию традиционного графа решений или использование приемов, харак-
терных для метода последовательного конструирования вариантов, в случае
полносвязного графа (практически всегда имеющего место при формировании
очереди заявок, удовлетворяющих некоторому оптимизационному правилу) не
может быть признано достаточно обоснованным. Во-первых, при конструиро-
вании алгоритмов поиска оптимального решения, необходимо предусматривать
использование процедур перебора вариантов, верхняя оценка количества кото-
рых равна !N , что характеризует задачу как не обладающую NP-полнотой и
приводит к большой вычислительной сложности и времени реализации проце-
дуры поиска. Во-вторых, при использовании локальных методов поиска, проце-
дура формирования множества анализируемых решений, не учитывает все до-
пустимые исходы и не может способствовать получению истинно оптимального
решения. Алгоритмы локальной оптимизации, как правило, имеющие полино-
миальную сложность, не гарантируют получение глобально оптимального ре-
шения, предлагая в качестве искомого или локально оптимальное, или просто
лучший среди нескольких, "искусственным" образом выделенных вариантов.
Несколько иная ситуация наблюдается при использовании алгоритмов ме-
тода ветвей и границ. Характеризуясь, в общем случае, экспоненциальной слож-
ностью, они позволяют на любом этапе решения задачи прервать вычисления и
в случае необходимости получить оценку отклонения от оптимума лучшего из
исследованных допустимых решений. Представляя собой de facto вычислитель-
ный метод, а стало быть существенно завися от быстродействия и объема опера-
тивной памяти используемого для просчета ЭВМ, метод ветвей и границ нахо-
дит все более широкое применение, особенно при больших размерностях задач.
Причиной повышенного внимания к указанному методу является прежде всего
простота лежащих в его основе алгоритмов, а также постоянно улучшающиеся
характеристики новых поколений вычислительной техники. Приведенные об-
стоятельства послужили наиболее весомыми аргументами в пользу выбора ме-
тода ветвей и границ в качестве основного средства оптимизации структуры
очереди находящихся в узле заявок, и его использования в созданной версии ин-
струментального комплекса программно-технических средств "Лоцман" [2, 3].
Делая упор на использование метода ветвей и границ, отметим еще одно по-
лезное его свойство. Оперируя одновременно со всеми вершинами графа (заяв-
ками из буфера) и используя для поиска гамильтонова контура отработанную
высокооперативную процедуру, метод исключает значительные затраты мо-
дельного времени на многократные формирования блоков в становящихся
неполносвязными матрицах расстояний. Указанные временные затраты ста-
новятся особо ощутимыми при больших длинах очереди и больших размерно-
стях классов эквивалентных заявок, порождающих блочную структуру матрицы
расстояний.
Цель работы разработка реализуемой в виде независимого программного
блока вспомогательной процедуры [3], модифицирующей матрицу расстояний и
непосредственно предшествующей этапу поиска общего гамильтонова контура.
По сути эта процедура, реализуя блочно-модульное представление матрицы
МОДИФИКАЦИЯ МАТРИЦЫ РАССТОЯНИЙ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В РЕШЕНИИ ВОПРОСА…
Комп’ютерні засоби, мережі та системи. 2007, № 6 151
расстояний, решает вопрос отдельных локальных оптимизаций, упрощая основ-
ную матрицу расстояний, уменьшая ее размер и общее время поиска глобально-
го оптимума. Процедура позволяет эффективно решать как вопрос оптимизации
структуры очереди заявок, так и некоторые вопросы маршрутизации и сетевого
планирования, используемые при построении на базе созданного комплекса
“Лоцман” средств анализа и комплексной оптимизации процессов функциони-
рования узлов адаптивных сетей коммутации пакетов и сообщений. Указанная
доработка обеспечивает формирование на не полносвязном упорядоченном гра-
фе гамильтоновых контуров, минимизирующих времена передачи пакетов и со-
общений (порядок обслуживания заявок в узле сети):
a) из фиксированного начального узла в любой конечный;
б) из любого узла исполняющего роль источника в заданный конечный узел-
приемник;
в) из заданного начального узла в заданный конечный;
г) через заданную совокупность транзитных узлов сети.
Используем для этого геометрическую интерпретацию задачи в форме пол-
ного симметричного ориентированного графа ),( DV , где символом
},...,2,1:{ NiiV обозначено множество вершин, а D
– множество дуг графа
. Каждой дуге ))(,( Ddjid , интерпретируемой элементом матрицы
ijaA , поставлено в соответствие некоторое неотрицательное число ija , в
разных случаях имеющее различную интерпретацию:
1) при оптимизации процесса функционирования компонент узла это могут
быть суммарные доходо-убытки, отражающие:
- доход за обслуживание заявок, штраф за простой незанятых мест в блоках
буфера, штраф за пребывание заявок в очереди в ожидании обслуживания и т.д.;
- штраф за восстановление или перенастройку устройств обслуживания, ко-
гда смена типа поступающего к ним на обработку сообщений требует допол-
нительного расхода времени, вызванного изменением режима их работы и др.
2) для топологической структуры графа сети коммутации пакетов и сообще-
ний значению ija может соответствовать:
- время передачи в узел j содержащегося в узле i сообщения по арендуе-
мому (временно организуемому) каналу связи и др.;
- физическая длина канала связи из узла i в узел j .
Для удобства изложения материала, воспользуемся терминологией теории
расписаний, усматривая за ija смысл "расстояния".
В общем случае ставится задача поиска гамильтонова контура (), удов-
летворяющего одному из условий а) – г), имеющего минимальную длину W
il
N
k
llil Nkki
aaaW
1
1
(1)
А.И. ИВАНЕШКИН
Комп’ютерні засоби, мережі та системи. 2007, № 6 152
и единственный раз проходящего через каждую вершину графа.
Для сохранения общности с ранее разработанными и широко используе-
мыми программными продуктами, в основу рассматриваемых процедур имеет
смысл положить метод приведения матрицы весов ijaA путем последова-
тельного вычитания общих для каждой строки значений полустепеней исхода и
общих для каждого столбца значений полустепеней захода и состоящий в сле-
дующем.
При отсутствии среди элементов конкретного j-го столбца
N
iija 1}{ элемента
с нулевым весом ("нуль-ребра"), значения всех весов ija будет уменьшаться на
величину }{min ij
i
j ab . Процедура приведения осуществляется последователь-
но для всех столбцов )1( Njj .
При отсутствии среди элементов конкретной i-й строки
N
jija 1}{ элемента с
нулевым весом ("нуль-ребра"), значения всех весов ija будет уменьшаться на
величину }{min ij
j
ac . Процедура приведения осуществляется последователь-
но для всех строк )1( Nii .
Рассматривая случай ji , вводится обобщенный, приписываемый i-ой
вершине параметр приведения iii cbd , учитываемый при определении ис-
тинного значения выражения (1).
Минимизация выражения (1) при наличии фиксированного начального, ко-
нечного или пары источник-получатель узлов, исключает возможность возвра-
щения "комивояжера" в исходный пункт, поэтому может рассматриваться как
виртуально размыкаемая в момент прибытия в конечный k-й узел сеть пунктов.
Случай заданного начального пункта. Для рассматриваемой ситуации
алгоритм поиска минимального пути с началом в конкретно выбранном узле бу-
дет содержать такую совокупность шагов:
- элементы j-го столбца, отвечающего выбранному в качестве исходного
j-му узлу, заменяется "нулями" или общим значением }){max( ij
i
aQQ ;
- осуществляется приведение матрицы весов ija . При замене i-го столбца
нулями, приведение марицы A по строкам исключается, ввиду наличия в каж-
дой из них как минимум одного нуль-элемента;
- решается задача оптимизации (1) с использованием метода ветвей и
границ;
- найденный (пока еще) путь регуляризуется путем "разрыва" ребра воз-
вращения в j-й узел, что в случае 0Q означает вычитание из полученного при
минимизации (1) значения
1W величины Q .
МОДИФИКАЦИЯ МАТРИЦЫ РАССТОЯНИЙ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В РЕШЕНИИ ВОПРОСА…
Комп’ютерні засоби, мережі та системи. 2007, № 6 153
Случай заданного конечного пункта. При определении пути следования с
фиксированным конечным пунктом, алгоритм минимизации (1) строится таким
образом:
- элементы i-й строки, соответствующие выбранному в качестве конечного
i-му узлу, заменяется "нулями" или общим значением }){max( ij
i
aDG ;
- осуществляется приведение матрицы весов ija . При замене i-й строки
нулями, приведение матрицы A по столбцам исключается, ввиду наличия в ка-
ждом из них, как минимум, одного нуль-элемента;
- решается задача оптимизации (1) с использованием метода ветвей и гра-
ниц;
- найденный (пока еще) путь регуляризуется путем "разрыва" ребра возвра-
щения в j-й узел, что в случае 0G означает вычитания из полученного при
минимизации (1) значения
2W величины G .
Случай заданной пары пунктов (начальный/конечный). При фиксиро-
ванных начальном и конечном пунктах, алгоритм поиска минимального пути
содержит такие шаги:
- элементы j-го столбца, соответствующие выбранному в качестве началь-
ного j-го узла, заменяется "нулями" или общим значением }){max( ij
i
aQQ ;
- элементы i-й строки, соответствующие выбранному в качестве конечного
i-му узлу, заменяется "нулями" или общим значением }){max( ij
i
aGG ;
- приведение матрицы весов ija осуществляется только по тем составля-
ющим (столбцам или строкам), для которых задаваемые значения Q или G от-
личны от нуля;
- решается задача оптимизации (1) с использованием метода ветвей и гра-
ниц;
- найденный (пока еще) путь регуляризуется путем "разрыва" ребра возвра-
щения ),( ji , вычитанием из полученного в результате минимизации (1) зна-
чения
3W величины QG .
Случай заданный пары пунктов (начальный/конечный) и поcледо-
вательности отрезков путей следования H = {h
k
(i*, i**)}k. Определив k-й
отрезок пути ),( *** iih в графе ),( DV как последовательность дуг
),),...(,(),,( 2110 slsrssss iiiiii , с началом в s-м узле )( 0si и концом в t -м узле )( sli ,
отметим, что настоящий случай отличается от предыдущего наличием дополни-
тельного шага, регламентирующего порядок следования комивояжера по задан-
ным отрезкам пути и реализуемого перед приведением матрицы ija . Этим ша-
гом является удаление (исключение, полагание равными бесконечности) из гра-
А.И. ИВАНЕШКИН
Комп’ютерні засоби, мережі та системи. 2007, № 6 154
фа ),( DV ребер инцидентности ),( ji , не соответствующих регламенти-
рованному порядку прохождения узлов в заданной совокупноcти путей
{ ( , )}.k
s tH h i i
Дополняя известные методы решения задачи комивояжера и содержа в себе
значительную степень универсальности, приведенные алгоритмы позволяют
также эффективно решать задачу поиска максимальных путей следования на
полном симметричном ориентированном графе ),( DV . При этом нахожде-
ние максимальных значений (1) (включая, в том числе, и вышерассмотренные
случаи) эквивалентно поиску минимальных путей следования на сопряженном
графе ),(* DV элементы
*
ija которого получаются из исходных ija с помо-
щью следующего вида преобразования
}){max(,*
,
ij
ji
ijij aBaBa . (2)
Реальная длина пути получается вычитанием из каждого найденного в про-
цессе использования метода ветвей и границ значения
*
ija величины B, опреде-
ленной согласно (2) .
Изложенный дополнительный прием предварительной модификации матри-
цы расстояний и созданные на его основе программные средства в полной мере
реализованы в [3]. Используя подход блочно-модульной структуризации матри-
цы расстояний на группах “эквивалентных” заявок, а посему существенно
уменьшая размер матриц с которыми приходится иметь дело при использовании
метода ветвей и границ, это существенно сокращает общее время расчета моде-
лей анализа, связанных с поиском оптимального порядка обслуживания заявок и
решением задач локальной оптимизации.
1. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. – М.: Наука, 1975. – 300 с.
2. Иванешкин А.И. Программные средства синтеза оптимального управления информаци-
онными процессами в неоднородных распределенных системах управления // Тр. II
Всесоюз. научно-техн. конф. “Микропроцессорные комплексы для управления техно-
логическими процессами”. – Грозный: Грознинское НПО “Промавтоматика”, 1989. –
С. 30 – 31.
3. Dorovskich A.V., Ivaneshkin A.I. Program Analysis of Data Processing Control in Adaptive
Packet Switching Networks // Engineering Simulation. – 1995. – 12. – P. 716 – 722.
Получено 10.01.2007
|