Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы

Описано метод аналізу вершин графа переставного багатогранника для розв’язання лінійних умовних оптимізаційних задач на перестановках. Запропоновано програмну реалізацію методу для багатопроцесорної системи. Теоретично досліджено складність даного алгоритму....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Емец, О.А., Емец, Е.М., Ольховский, Д.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Оптимальное управление и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207497
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:	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы / О.А. Емец, Е.М. Емец, Д.Н. Ольховский // Проблемы управления и информатики. — 2012. — № 3. — С. 46–55. — Бібліогр.: 16 назв. - рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207497
record_format	dspace
spelling	irk-123456789-2074972025-10-09T00:16:19Z Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы Метод аналізу графа переставного багатогранника для лінійних умовних оптимізаційних задач з реалізацією для багатопроцесорної системи Method of Analysis of the Permutable Polytope Graph for Linear Conditional Optimization Problems with the Implementation for a Multiprocessor System Емец, О.А. Емец, Е.М. Ольховский, Д.Н. Оптимальное управление и методы оптимизации Описано метод аналізу вершин графа переставного багатогранника для розв’язання лінійних умовних оптимізаційних задач на перестановках. Запропоновано програмну реалізацію методу для багатопроцесорної системи. Теоретично досліджено складність даного алгоритму. A method of analysis of vertices of a permutable polyhedron graph for solving linear conditional optimization problems on permutations is suggested. Its implementation for a multiprocessor system is proposed. The complexity of the algorithm is theoretically investigated. 2012 Article Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы / О.А. Емец, Е.М. Емец, Д.Н. Ольховский // Проблемы управления и информатики. — 2012. — № 3. — С. 46–55. — Бібліогр.: 16 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207497 519.85 10.1615/JAutomatInfScien.v44.i6.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Емец, О.А. Емец, Е.М. Ольховский, Д.Н. Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы Проблемы управления и информатики
description	Описано метод аналізу вершин графа переставного багатогранника для розв’язання лінійних умовних оптимізаційних задач на перестановках. Запропоновано програмну реалізацію методу для багатопроцесорної системи. Теоретично досліджено складність даного алгоритму.
format	Article
author	Емец, О.А. Емец, Е.М. Ольховский, Д.Н.
author_facet	Емец, О.А. Емец, Е.М. Ольховский, Д.Н.
author_sort	Емец, О.А.
title	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
title_short	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
title_full	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
title_fullStr	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
title_full_unstemmed	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
title_sort	метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207497
citation_txt	Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы / О.А. Емец, Е.М. Емец, Д.Н. Ольховский // Проблемы управления и информатики. — 2012. — № 3. — С. 46–55. — Бібліогр.: 16 назв. - рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT emecoa metodanalizagrafaperestanovočnogomnogogrannikadlâlinejnyhuslovnyhoptimizacionnyhzadačsrealizaciejdlâmnogoprocessornojsistemy AT emecem metodanalizagrafaperestanovočnogomnogogrannikadlâlinejnyhuslovnyhoptimizacionnyhzadačsrealizaciejdlâmnogoprocessornojsistemy AT olʹhovskijdn metodanalizagrafaperestanovočnogomnogogrannikadlâlinejnyhuslovnyhoptimizacionnyhzadačsrealizaciejdlâmnogoprocessornojsistemy AT emecoa metodanalízugrafaperestavnogobagatogrannikadlâlíníjnihumovnihoptimízacíjnihzadačzrealízacíêûdlâbagatoprocesornoísistemi AT emecem metodanalízugrafaperestavnogobagatogrannikadlâlíníjnihumovnihoptimízacíjnihzadačzrealízacíêûdlâbagatoprocesornoísistemi AT olʹhovskijdn metodanalízugrafaperestavnogobagatogrannikadlâlíníjnihumovnihoptimízacíjnihzadačzrealízacíêûdlâbagatoprocesornoísistemi AT emecoa methodofanalysisofthepermutablepolytopegraphforlinearconditionaloptimizationproblemswiththeimplementationforamultiprocessorsystem AT emecem methodofanalysisofthepermutablepolytopegraphforlinearconditionaloptimizationproblemswiththeimplementationforamultiprocessorsystem AT olʹhovskijdn methodofanalysisofthepermutablepolytopegraphforlinearconditionaloptimizationproblemswiththeimplementationforamultiprocessorsystem
first_indexed	2025-10-09T01:08:29Z
last_indexed	2025-10-12T01:07:21Z
_version_	1845736234190635008
fulltext	© О.А. ЕМЕЦ, Е.М. ЕМЕЦ, Д.Н. ОЛЬХОВСКИЙ, 2012 46 ISSN 0572-2691 УДК 519.85 О.А. Емец, Е.М. Емец, Д.Н. Ольховский МЕТОД АНАЛИЗА ГРАФА ПЕРЕСТАНОВОЧНОГО МНОГОГРАННИКА ДЛЯ ЛИНЕЙНЫХ УСЛОВНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С РЕАЛИЗАЦИЕЙ ДЛЯ МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ Введение Задачи комбинаторной оптимизации находят все большее практическое при- менение. Это обусловлено тем, что многие прикладные задачи описываются мо- делями, у которых решение определено на комбинаторных множествах. Такие за- дачи, в частности, возникают при исследовании большого количества теоретиче- ских и прикладных проблем [1–5]. Появляются новые или неисследованные задачи и модели, которые имеют большую размерность, специальную структуру и т.д. Их решение требует разработки новых или модификации имеющихся мето- дов. При этом важным является изучение структуры комбинаторных конфигура- ций, в частности, с применением теории графов. Кроме разработки новых матема- тических подходов, существенная роль отводится применению современной вы- числительной техники, а именно наличию мощных многопроцессорных систем. В последнее время широкое применение получили методы отсечения для ре- шения задач комбинаторной оптимизации на вершинно расположенных множе- ствах с линейными дополнительными ограничениями [4, 6–9], а также [10, 11] с нелинейной целевой функцией и нелинейными дополнительными ограничениями. Известно, что алгоритмы этих методов не являются полиномиальными. Другим подходом к решению задач на перестановках является подход, который использу- ет аппарат теории графов [12, 13]. Достаточно исследованы [5, 14] свойства евклидового множества перестано- вок )(GEk и его выпуклой оболочки )(conv GEk — перестановочного много- гранника ).(Gk Актуальна разработка полиномиальных методов решения за- дач комбинаторной линейной оптимизации, более эффективных, чем существую- щие, ввиду свойств множества перестановок и перестановочного многогранни- ка [5, 14]. В данной работе предлагается приближенный полиномиальный метод анали- за графа многогранника [15] для перестановочного многогранника. Постановка задачи Рассматривается решение линейной условной комбинаторной задачи на пе- рестановках [5]: найти максимальное значение целевой функции max 1   jj k j xc (1) при комбинаторных условиях )()...,,( 1 GExxx kk  (2) и дополнительных ограничениях ,kRXx  (3) Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 47 где 1Rc j  ;kJj )(GEk — множество перестановок из элементов мультимно- жества },...,,{ 1 kggG  v — количество элементов его основы )...,,()( 1  eeGS — упорядоченного множества разных элементов из G. Если X — многогранное мно- жество, то задача (1)–(3) — линейная условная задача евклидовой комбинаторной оптимизации на множестве перестановок, в противном случае — нелинейная с линейной целевой функцией условная задача оптимизации на перестановках. Под kJ понимаем множество первых k натуральных чисел },...,,2,1{ kJk  а .0 J Метод анализа графа перестановочного многогранника Как известно, перестановочный многогранник )(conv)(П GEG kk   являет- ся выпуклой оболочкой множества перестановок ),(GEk совпадающего с мно- жеством вершин )(Пvert Gk перестановочного многогранника :)(П Gk ).(convvert)( GEGE kk   Вершины ),...,,( 1 k ggg  )...,,( 1 k ggg  согласно критерию смежно- сти вершин многогранника )(П Gk являются смежными (лежат на одном ребре), если g и g  отличаются перестановками двух неравных элементов ,ie 1ie 1 Ji основы )...,,()( 1  eeGS мультимножества G при условии ....... 11   eeee ii (4) Решением безусловной линейной задачи оптимизации на множестве переста- новок (1), (2) при выполнении условия упорядочения коэффициентов целевой функции kccc  ...21 и элементов множества перестановок kggg  ...21 является точка )...,,( ** 1 * kxxx  такая, что ii gx * .kJi Как известно [15], граф, вершинами которого являются вершины многогран- ника, а ребрами — его ребра, есть 1-скелетом многогранника. Такой граф назовем графом многогранника. Граф многогранника )(П Gk назовем графом перестано- вочного многогранника. Введем понятие графа множества перестановок: ,,ГП MEk где kE — множество всех перестановок из разных элементов kggg ...,,, 21 , M — множество ребер графа .ГП Граф множества перестановок, в отличие от графа перестановочного многогранника, в общем случае имеет другое множество ребер. Частичным графом множества перестановок будем называть граф ,,Г SPkP  где , kk EP S — множество ребер графа .ГP На практике ис- пользование частичного графа PГ множества перестановок позволяет уменьшить количество вычислений за счет того, что в граф включаются не все вершины и ре- бра графа перестановочного многогранника, они постепенно добавляются (и затем удаляются) к частичному графу множества перестановок. Алгоритм 1. Рассмотрим алгоритм метода решения линейной условной зада- чи (1)–(3) методом анализа графа перестановочного многогранника. Алгоритм метода анализа графа перестановочного многогранника состоит в постепенном анализе вершин графа перестановочного многогранника с использо- ванием частичного графа множества перестановок. Поэтапный анализ вершин осуществляется переходом от вершины к вершине по ребрам графа. 48 ISSN 0572-2691 1. Задаются начальные данные задачи, а именно: элементы множества пере- становок, коэффициенты линейной целевой функции, дополнительные линейные ограничения и точность вычислений. 2. Решается безусловная задача линейной оптимизации (1), (2). В результате получаем начальную вершину maxx для дальнейшего процесса решения задачи, которая добавляется ко множеству вершин частичного графа первоначально пу- стого множества перестановок. 3. Случайным образом выбирается допустимая вершина rndx (или несколько вершин при реализации для многопроцессорной системы) в графе перестановоч- ного многогранника, которая удовлетворяет условиям (2), (3). 4. При работе алгоритма происходит постепенный переход к следующим вершинам решения: от вершин maxx (в направлении минимизации целевой функ- ции) и rndx (в направлении максимизации целевой функции), пока не будет до- стигнута необходимая точность вычисления задачи  либо не будет получено точ- ное решение задачи, или достигнут другой критерий останова (максимальное ко- личество вершин графа частичного графа множества перестановок, максимальное время вычислений). 5. Для получения следующей вершины решения к текущей вершине частич- ного графа множества перестановок добавляются смежные с ней вершины (согласно критерию смежности вершин), а также ребра, которые связывают эти вершины с текущей. Из смежных вершин выбирается вершина с максимальным или минимальным (для вершин maxx и rndx соответственно) значением целевой функции. Эти вершины будут следующими анализируемыми вершинами при решении. 6. При переходе по смежным вершинам частичного графа множества пере- становок происходит удаление проанализированных вершин из множества вер- шин графа, а также ребер, инцидентных с ними (из множества ребер графа). 7. Алгоритм продолжает работу до тех пор, пока не будет получена вершина — решение с заданной точностью, которая удовлетворяет всем ограничениям задачи, или не будут проанализированы все вершины графа перестановочного много- гранника и будет установлен факт неразрешимости задачи. Рассмотрим алгоритм метода анализа графа перестановочного многогранни- ка для решения линейной условной задачи (1)–(3): Шаг 0. Задаем элементы множества перестановок }...,,,{ 21 kgggG  (упо- рядоченные таким образом: ),...21 kggg  коэффициенты целевой функции ,...,,, 21 kccc дополнительные линейные ограничения задачи (1)–(3), необходи- мую точность вычисления задачи , максимально допустимое количество вер- шин maxvert в частичном графе множества перестановок и максимальное время maxtime работы алгоритма. Шаг 1. Упорядочиваем коэффициенты целевой функции по неубыванию: .... 21 kiii ccc  Шаг 2. Находим максимальное значение линейной целевой функции )( * maxxf задачи (1), (2) без учета дополнительных линейных ограничений, .,...,11 kii gxgx k  Шаг 3. Ко множеству вершин частичного графа множества перестановок до- бавляем начальную вершину .* maxxxcurr  Шаг 4. Согласно критерию смежности вершин перестановочного многогран- ника находим вершины 1,12,11,1 ...,,, kxxx , смежные с вершиной .currx Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 49 Шаг 5. Добавляем вершины 1,12,11,1 ...,,, kxxx ко множеству kP вершин ча- стичного графа PГ множества перестановок. Шаг 6. Соединяем вершину 1x с каждой смежной с ней вершиной 1,12,11,1 ...,,, kxxx путем добавления соответствующих ребер в множество S графа .ГP Шаг 7. Проверяем, удовлетворяет ли найденная вершина currx дополнитель- ным линейным ограничениям (3). Если да, то задача решена с оптимальным ре- шением — вершиной ,currx иначе — переход на шаг 8. Шаг 8. Определяем количество prc доступных процессоров в вычислитель- ной системе. Шаг 9. Случайным образом генерируем вершины rnd ix ,prcJi которые должны удовлетворять условиям (2), (3) задачи. Текущими вершинами при реше- нии задачи принимаем вершины rnd i eval i xx  .prcJi Шаг 10. Проверяем условия останова алгоритма.  Разность между значением целевой функции (1) в любой из вершин eval ix prcJi и максимальным значением целевой функции (1) среди висячих вершин частичного графа множества перестановок PГ (при движении от точки )currx меньше . Если условие выполняется, то задача решена с оптимальным решени- ем — вершиной .currx  Количество вершин в частичном графе множества перестановок больше значения .maxvert Если условие выполняется, то выход из алгоритма с текущим решением — вершиной .currx  Время работы алгоритма превышает значений .maxtime Если условие вы- полняется, то выход из алгоритма с текущим решением — вершиной .currx Точность полученного решения определяется как разность между макси- мальным значением целевой функции (1) среди висячих вершин частичного графа множества перестановок PГ (при движении от точки )currx и максимальным (по i) значением целевой функции (1) в вершинах eval ix .prcJi Если ни одно из условий не выполнилось, переходим на шаг 11. Шаг 11. Переходим от вершины currx к смежной вершине в направлении минимизации значения целевой функции (1), используя алгоритм перехода к смежной вершине .nextx Получим очередную вершину .nextcurr xx  Если в ча- стичном графе множества перестановок отсутствуют вершины, смежные с ,currx то устанавливается неразрешимость задачи, остановка алгоритма. Шаг 12. Проверяем, удовлетворяет ли вершина currx дополнительным ли- нейным ограничениям (3). Если да, то задача решена с оптимальным решением — вершиной ,currx иначе — переход на шаг 13. Шаг 13. Переходим от вершин eval ix prcJi к смежным вершинам next eval i xx  prcJi в направлении максимизации значения целевой функции, используя алгоритм перехода к следующей смежной вершине. Шаг 14. Генерируем новую случайную допустимую вершину ,eval ix если вершины в частичном графе перестановочного многогранника, смежные с eval ix ,prcJi отсутствуют. Переходим на шаг 10 алгоритма. 50 ISSN 0572-2691 При реализации данного метода предлагается использовать преимущества современных вычислительных систем, а именно, возможность проведения парал- лельных вычислений на нескольких процессорах одновременно, что сократит время решения задачи. Это происходит за счет создания нескольких (за счет количества имеющихся процессоров в системе) рабочих потоков вычисления од- новременно. 1. Переход к смежной вершине в шаге 11 и переход к каждой из смежных вершин в шаге 13 предлагается выполнять одновременно и параллельно на каж- дом из доступных процессоров. 2. Шаг 10 алгоритма предлагается выполнять при каждом переходе (в каждом потоке отдельно и параллельно) к смежным вершинам eval ix и .currx Алгоритм 2. Переходим к следующей смежной вершине nextx графа пере- становочного многогранника из текущей вершины. Шаг 1. Определяем номер )(num текущей вершины в множестве вершин ча- стичного графа множества перестановок. Шаг 2. Проверяем, существуют ли нерассмотренные смежные вершины с вершиной numx графа. Если нет, то работа алгоритма завершена. Иначе — переход на шаг 3. Шаг 3. Согласно критерию смежности вершин перестановочного многогран- ника находим вершины, смежные с текущей num t numnumnum xxxx ...,,,: 21 (t — коли- чество смежных вершин). Шаг 4. С каждой вершиной num jx )( tJj выполняем следующие действия: 1) устанавливаем связь вершины num jx со всеми другими вершинами num ix tJi ; ,ji  добавив соответствующее ребро в множество ребер S частичного графа PГ множества перестановок; 2) удаляем из множества ребер S частичного графа PГ множества переста- новок ребро, которое соединяет вершину numx с .num jx Шаг 5. Среди вершин num jx )( tJj определяем вершину numxopt с макси- мальным (или минимальным — согласно направлению движения) значением це- левой функции (1). Шаг 6. Удаляем из множества kP вершин графа вершину .numx Шаг 7. Согласно критерию смежности вершин находим вершины ,...,,, 121  kxxx смежные с .opt numx Шаг 8. Проверяем вершины 121 ...,,,  kxxx на наличие во множестве вер- шин kP графа .ГP Если вершина 1x 1 kJi отсутствует в множестве, то вы- полняем с ней следующие действия: 1) добавляем вершину ix во множество вершин kP частичного графа PГ множества перестановок; 2) добавляем ребро во множество ребер S графа ,ГP которое соединяет вер- шину ix с вершиной ;opt numx 3) находим смежные с вершиной ix вершины ;...,,, 121  kxxx 4) добавляем вершины 121 ...,,,  kxxx во множество вершин kP графа ;ГP 5) ко множеству ребер S графа PГ добавляем ребра между вершиной ix и вершинами ....,,, 121  kxxx Шаг 9. Приняв следующей смежной вершиной вершину num next xx opt , выхо- дим из алгоритма. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 51 Оценка сложности алгоритма Для расчетов сложности [16] алгоритма представим работу алгоритма на од- ной итерации в виде таблиц (табл. 1–3), в которых в столбце «Алгоритм» записа- ны фрагменты программной реализации метода анализа вершин графа перестано- вочного многогранника (один этап алгоритма). Время выполнения разных строк алгоритма разное, но одна и та же строка i выполняется за время ,ic где ic — кон- станта. Пусть строка алгоритма выполняется j раз. В табл. 1–3 параметр k — это количество элементов во множестве перестановок ,kP n — количество вершин в частичном графе множества перестановок на текущем этапе алгоритма. Также введем количество )( itKK итераций, которое зависит от значения точности . Алгоритм состоит из двух основных частей: удаление текущей вершины из множества вершин графа и добавление смежных вершин к следующей вершине решения. Эти части алгоритма представлены в табл. 1 и 2, общая сложность од- ной итерации алгоритма представлена в табл. 3. Вычислив сложность процедуры удаления вершины из множества вершин частичного графа с помощью табл. 1, получим  32134333231302928 )()(1 kcccncccccccT  2018171613121187654 2 ( cccccccccccck )()() 24231514 3 19109 2 2726252221 cccckcccnkccccc  или ).()()()()()1( 322 kOnkOkOnOkOOT  Учитывая, что ))(())((:0 nfOnfcOc  , имеем  )()()( 2kOnOkOT ).()( 32 kOnkO  Известно, что если   c ng nf n )( )( lim , то )),()(())(())(( ngnfOngOnfO  т.е. ).()()()( 322 kOnkOkOnkOT  Если   )( )( lim ng nf n , то )),(())(())(( nfOngOnfO  имеем ).( 223 knkkOT  Воспользовавшись табл. 2, определим сложность процедуры добавления вершины во множество вершин частичного графа множества перестановок:  )()()(1 302976 2 52143 cccckkcccnccT  242322212019181713111098 3( ccccccccccccck )() 16151412 4 28272625 cccckcccc  или ).()()()()()1( 432 kOkOkOkOnOOT  Известно, что :0c ))(( nfcO )).(( nfO Имеем ).()()()()( 432 kOkOkOkOnOT  Если   c ng nf n )( )( lim , то )),()(())(())(( ngnfOngOnfO  имеем ).( 234 knkkkOT  52 ISSN 0572-2691 Таблица 1 Алгоритм jc j for i:=0 to cvlist.Count-1 do 1c n if cvlist.Items[i].Num = anum then 2c n begin — — for j:=0 to cvlist.Items[i].Next.Count-2 do 3c kk 1 for k:=j+1 to cvlist.Items[i].Next.Count-1 do 4c 2)1)(1( kkk  begin — — n1 := cvlist.Items[i].Next.Items[j]; 5c 2k n2 := cvlist.Items[i].Next.Items[k]; 6c 2k b1 := false; 7c 2k b2 := false; 8c 2k for Node in cvlist do 9c 2nk if Node.Num = n1 then 10c 2nk begin — — if (Max < Node.Funcval) then 11c 2k begin — — Max := Node.Funcval; 12c 2k Maxind1 := Node.Num; 13c 2k end; — — if (not Node.Next.Contains(n2)) then 14c 32 kkk  Node.Next.Add(n2); 15c 3k Node.Next.Remove(anum); 16c 2k b1 := true; 17c 2k if (b1) and (b2) then Break; 18c 2k end — — else if (Node.Num = n2) then 19c 2nk begin — — if (Max < Node.Funcval) then 20c 2k begin — — Max := Node.Funcval; 21c 2k Maxind1 := Node.Num; 22c 2k end; — — if (not Node.Next.Contains(n1)) then 23c 32 kkk  Node.Next.Add(n1); 24c 3k Node.Next.Remove(anum); 25c 2k b2 := true; 26c 2k if (b1) and (b2) then Break; 27c 2k end; — — end; — — cmaxfuncval := Max; 28c 1 cmaxfuncnode := Maxind1; 29c 1 cvlist.Delete(i); 30c 1 if (cvlist.Count = 1) then 31c 1 begin — — cmaxfuncnode := cvlist.Items[0].Num; 32c 1 cmaxfuncval := cvlist.Items[0].Funcval; 33c 1 end; — — Break; 34c 1 end; — — Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 53 Таблица 2 Алгоритм jc j for Node in cvlist do 1c n if Node.Num = anum then 2c n begin — — scount := 0; 3c 1 Setlength(tarr, cgdim+1); 4c 1 for i:=1 to cgdim-1 do 5c k for j:=i+1 to cgdim do 6c 2)1( kkk  begin — — if abs(Node.Perm[i]-Node.Perm[j]) = 1 then 7c 2k begin — — for k:=1 to cgdim do 8c 32 kkk  if k=I then tarr[k] := Node.Perm[j] 9c 3k else if k=j then tarr[k] := Node.Perm[i] 10c 3k else tarr[k] := Node.Perm[k]; 11c 3k if Nodeexists(tarr) = -1 then 12c 43 kkk  begin — — t := 0; 13c 3k for k:=1 to cgdim do 14c 43 kkk  Newnode.Perm[k] := tarr[k]; 15c 4k t := t + cg[tarr[k]] * cf[k]; 16c 4k if t > Node.Funcval then Continue; 17c 3k Newnode.Funcval := t; 18c 3k inc(scount); 19c 3k inc(clastnodenum); 20c 3k Node.Next.Add(clastnodenum); 21c 3k Newnode.Num := clastnodenum; 22c 3k Newnode.Next := Tlist<Integer>.Create; 23c 3k Newnode.Next.Add(Node.Num); 24c 3k cvlist.Add(Newnode); 25c 3k inc(Addedvert); 26c 3k if aaddnext then 27c 3k Addedvert := Addedvert + Addnode (Newnode.Num, adir, False); 28c 3k end; — — Finalize(tarr); 29c 2k Result := Addedvert; 30c 2k end; — — end; — — end; — — 54 ISSN 0572-2691 Таблица 3 Алгоритм Время jc j if cqueue.Count <> 0 then 1c 1 Nodenum := cqueue.Items[0].Num 2c 1 else — — cerrcode := 1; 3c 1 Exit; 4c 1 cmaxfuncnode := Nodenum; 5c 1 cmaxfuncval := cqueue.Items[0].Funcval; 6c 1 cqueue.Delete(0); 7c 1 Delnode(Nodenum, adir); 1 )( 223 knkkO  if cqueue.Count <> 0 then 8c 1 Nodenum := cqueue.Items[0].Num 9c 1 else — — cerrcode := 1; 10c 1 Exit; 11c 1 cmaxfuncval := cqueue.Items[0].Funcval; 12c 1 cmaxfuncnode := Nodenum; 13c 1 Addnode(Nodenum, adir, true); 1 )( 234 nkkkkO  cmaxfuncval := cqueue.Items[0].Funcval; 14c 1 cmaxfuncnode := Nodenum; 15c 1 Согласно табл. 3 вычислим сложность алгоритма:  )(1 151413121110987654321 cccccccccccccccT )()( 234223 nkkkkOknkkO  или ).()()1( 234223 nkkkkOknkkOOT  Упростив выражение, окончательно получим ).( 24 nkkOT  С учетом количества итераций вычисли- тельная сложность алгоритма будет равна: ).()( 2424 KnkKkOnkkKOT  Заметим, что оценка дана в предположении, что параметр maxtime достаточ- но большой. Заключение Предложен приближенный метод анализа графа перестановочного много- гранника для условных линейных задач комбинаторной оптимизации на переста- новках. Теоретический анализ сложности предложенного алгоритма показал его полиномиальность относительно параметров K, k и n. Метод дает решение с за- данной точностью по функционалу. Как направление дальнейших исследований целесообразно осуществить про- граммную реализацию и численные эксперименты по методу анализа графа. О.О. Ємець, Є.М. Ємець, Д.М. Ольховський МЕТОД АНАЛІЗУ ГРАФА ПЕРЕСТАВНОГО БАГАТОГРАННИКА ДЛЯ ЛІНІЙНИХ УМОВНИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ З РЕАЛІЗАЦІЄЮ ДЛЯ БАГАТОПРОЦЕСОРНОЇ СИСТЕМИ Описано метод аналізу вершин графа переставного багатогранника для розв’я- зування лінійних умовних оптимізаційних задач на перестановках. Запропоно- вано його програмну реалізацію для багатопроцесорної системи. Теоретично досліджено складність даного алгоритму. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 3 55 O.A. Iemets, E.M. Yemets, D.N. Olhovskiy METHOD OF ANALYSIS OF THE PERMUTABLE POLYTOPE GRAPH FOR LINEAR CONDITIONAL OPTIMIZATION PROBLEMS WITH THE IMPLEMENTATION FOR A MULTIPROCESSOR SYSTEM A method of analysis of vertices of a permutable polyhedron graph for solving linear conditional optimization problems on the permutations is suggested. Its implementa- tion for a multiprocessor system is proposed. The complexity of the algorithm is the- oretically investigated. 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за- дач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения и исследования. — Киев : Наук. думка, 2003. — 260 с. 3. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. — Киев : Наук. думка, 1986. — 266 с. 4. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Оптимізація на полірозміщеннях: теорія та методи. — Полтава : РВЦ ПУСКУ, 2005. — 103 с. 5. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — Київ: Ін- ститут систем. досліджень освіти, 1993. — 188 с. 6. Емец О.А. Об одном методе отсечений для задач комбинаторной оптимизации // Экономи- ка и мат. методы. — 1997. — 33, вып. 4. — С. 120–129. 7. Ємець О.О., Ємець Є.М. Відсікання в лінійних частково комбінаторних задач евклідової комбінаторної оптимізації // Доп. НАН України. — 2000. — № 9. — С. 105–109. 8. Емец О.А., Емец Е.М. Отсечения в линейных частично комбинаторных задачах оптимиза- ции на перестановках // Экономика и мат. методы. — 2001. — 37, № 1. — С. 118–121. 9. Емец О.А., Емец Е.М. Модификация метода комбинаторного отсечения в задачах оптими- зации на вершинно расположенных множествах // Кибернетика и системный анализ. — 2009. — № 5. — С. 129–136. 10. Ємець О.О., Чілікіна Т.В. Нелінійні задачі комбінаторної оптимізації на вершинно розта- шованих множинах та їх розв’язування // Динамические системы. — 2004. — Вып. 18. — С. 160–165. 11. Емец О.А., Емец Е.М., Чиликина Т.В. Комбинаторное отсечение при решении оптимизаци- онных нелинейных условных задач на вершинно расположенных множествах // Междуна- родный научно-технический журнал «Проблемы управления и информатики». — 2010. — № 3. — С. 86–93. 12. Донец Г.А., Колечкина Л.Н. Метод упорядочения значений линейной функции на множе- стве перестановок // Кибернетика и системный анализ. — 2009. — № 2. — С. 50–61. 13. Донец Г.А., Колечкина Л.Н. Об одном подходе к решению комбинаторной задачи оптими- зации на графах // Упр. системы и машины. — 2009. — № 4. — С. 35–41. 14. Емец О.А. Евклидовы комбинаторные множества и оптимизация на них. Новое в матема- тическом программировании : Учебн. пособие. — К. : УМК ВО, 1992. — 92 с. 15. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комби- наторная теория многогранников). — М. : Наука, 1981. — 342 с. 16. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: 2-е изд. — М. : Вильямс, 2005 . — 1296 с. Получено 20.09 2011

Метод анализа графа перестановочного многогранника для линейных условных оптимизационных задач с реализацией для многопроцессорной системы

Institution

Ähnliche Einträge