Об одном подходе к решению комбинаторной задачи оптимизации на графах

Об одном подходе к решению комбинаторной задачи оптимизации на графах

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2009
Hauptverfasser: Донец, Г.А., Колечкина, Л.Н.
Format: Artikel
Sprache:Russian
Veröffentlicht: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2009
Schriftenreihe:Управляющие системы и машины
Schlagworte:
Новые методы в информатике
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/82742
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:Об одном подходе к решению комбинаторной задачи оптимизации на графах / Г.А. Донец, Л.Н. Колечкина // Управляющие системы и машины. — 2009. — № 4. — С. 34-42. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-82742
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-827422025-02-10T00:14:04Z Об одном подходе к решению комбинаторной задачи оптимизации на графах Донец, Г.А. Колечкина, Л.Н. Новые методы в информатике Рассмотрены задачи комбинаторной оптимизации на множестве перестановок с повторениями. На основании специфических свойств и структуры множества перестановок, а также теории графов описывается построение последовательности значений линейной целевой функции, разложение точек множества перестановок по гиперплоскостям и их зависимость с учетом повторения элементов. The problems of the combinatorial optimization on a set of transpositions with repetitions. are considered. On the basis of specific characteristics and structures of a set of transpositions as well as the graph theory, the building of a sequence of values of a linear target function, the decomposition of points of a set of transpositions on hyperplanes and their dependence with account of elements repetitions are described. Розглянуто задачі комбінаторної оптимізації на множині перестановок з повтореннями. На підставі специфічних властивостей та структури множини перестановок, а також теорії графів описано побудову послідовності значень лінійної цільової функції, розклад точок множини перестановок на гіперплощинах та їх залежність з урахуванням повторення елементів. 2009 Article Об одном подходе к решению комбинаторной задачи оптимизации на графах / Г.А. Донец, Л.Н. Колечкина // Управляющие системы и машины. — 2009. — № 4. — С. 34-42. — Бібліогр.: 12 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/82742 519.1 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 2009
topic_facet Новые методы в информатике
url https://nasplib.isofts.kiev.ua/handle/123456789/82742
citation_txt Об одном подходе к решению комбинаторной задачи оптимизации на графах / Г.А. Донец, Л.Н. Колечкина // Управляющие системы и машины. — 2009. — № 4. — С. 34-42. — Бібліогр.: 12 назв. — рос.
series Управляющие системы и машины
work_keys_str_mv AT donecga obodnompodhodekrešeniûkombinatornoizadačioptimizaciinagrafah
AT kolečkinaln obodnompodhodekrešeniûkombinatornoizadačioptimizaciinagrafah
first_indexed 2025-12-02T01:59:43Z
last_indexed 2025-12-02T01:59:43Z
_version_ 1850359978547740672
fulltext 34 УСиМ, 2009, № 4 УДК 519.1 Г.А. Донец, Л.Н. Колечкина Об одном подходе к решению комбинаторной задачи оптимизации на графах Рассмотрены задачи комбинаторной оптимизации на множестве перестановок с повторениями. На основании специфических свойств и структуры множества перестановок, а также теории графов описывается построение последовательности значений линейной целевой функции, разложение точек множества перестановок по гиперплоскостям и их зависимость с учетом повто- рения элементов. The problems of the combinatorial optimization on a set of transpositions with repetitions. are considered. On the basis of specific char- acteristics and structures of a set of transpositions as well as the graph theory, the building of a sequence of values of a linear target function, the decomposition of points of a set of transpositions on hyperplanes and their dependence with account of elements repeti- tions are described. Розглянуто задачі комбінаторної оптимізації на множині перестановок з повтореннями. На підставі специфічних властивостей та структури множини перестановок, а також теорії графів описано побудову послідовності значень лінійної цільової функції, розклад точок множини перестановок на гіперплощинах та їх залежність з урахуванням повторення елементів. Введение.∗ Комбинаторные оптимизационные задачи сложны с вычислительной точки зре- ния. Методы решения этих задач развиваются в двух основных направлениях: точные и при- ближенные. Такое разделение весьма условно в силу того, что каждый конкретный класс за- дач (даже отдельная задача) предъявляют свои требования к методу решения. В последние годы началось изучение свойств отдельных классов дискретных оптимизацион- ных задач и использование этих свойств при построении алгоритмов решения. Ряд обзор- ных публикаций охватывают определенные классы задач и методы их решения. В частно- сти, разработан ряд методов итерационного типа, достаточно универсальных и позволяю- щих вместе с тем учитывать конкретную спе- цифику задачи. В этом смысле представляют интерес задачи комбинаторного типа, описан- ные в работах [1–8]. Задачи на комбинаторных множествах ин- тересны тем, что область допустимых решений представляет собой некоторый комбинаторный многогранник, свойства которого изучены и ис- следованы, что дает возможность использовать их специфические свойства для построения но- вых и для совершенствования существующих методов решения комбинаторных оптимиза- ционных задач. ∗ Ключевые слова: комбинаторные множества, множест- во перестановок с повторениями, перестановочный многогран- ник, графы, гиперграни, гамильтонов путь. Широкий круг задач по своей математиче- ской постановке сводится к соответствующим классам задач комбинаторной оптимизации, в частности, в ряде задач оптимизируемый функ- ционал задается на комбинаторном множестве. Примерами комбинаторных множеств является множество перестановок, перестановок с по- вторениями, разбиений и др. В работах [4–6, 9] показано, что элементы множества перестано- вок можно интерпретировать как вершины не- которого выпуклого многогранника. Отметим, что особенности комбинаторных свойств много- гранников тесно связаны с задачами оптими- зации, важными для практических примене- ний. Многогранники тесно связаны с изучени- ем свойств графов. Графы многогранников об- ладают многими интересными свойствами. При их изучении и применении решается боль- шое число задач, представляющих интерес в экономике, транспорте, оптимальном календар- ном и многоэтапном планировании. Графы можно использовать, когда иссле- дуемая задача моделируется с помощью графа, вершины которого представляют вершины мно- гогранника. Использование свойств графов комбинатор- ных многогранников могут послужить повы- шению эффективности «традиционных» и раз- работке новых методов комбинаторной опти- мизации. Комбинаторные модели могут быть приме- нены для представления оптимизационных за- УСиМ, 2009, № 4 35 дач, возникающих при оптимальном размеще- нии на графах. Отметим, что ряд задач форму- лируется в терминах точек и связей между ни- ми, такие как составление расписания, проек- тирование электронных схем, анализ сетей в электротехнике и др. Поэтому эффективные алгоритмы решения задач теории графов име- ют большее практическое значение. В статье рассматривается комбинаторная за- дача нахождения вершины перестановочного многогранника, отвечающей значению задан- ной целевой функции. Предложен новый алгоритм решения опти- мизации задач на комбинаторном множестве перестановок с повторениями использования специальных свойств перестановочного мно- гогранника и его графов, что является продол- жением работ [9–12], в которых рассматрива- ются алгоритмы на графах. Задача оптимизации на комбинаторном множестве перестановок с повторениями Для дальнейшего изложения материала при- ведем основные понятия и определения. Рас- смотрим мультимножество 1 2{ , ,..., }qA a a a= , его основание { }1 2( ) , ,..., kS А e e e= , где l je R∈ для kNj∈∀ , и кратность элементов ,)( jj rek = kNj∈ , 1 2 ... kr r r q+ + + = согласно [4, 5]. Упорядоченной n-выборкой из мультимно- жества A называется набор ( )1 2, , , ,ni i ia a a a= … (1) где jia А∈ ,j ni N∀ ∈ nj N∀ ∈ , s ti i≠ , если s ≠ t ,ns N∀ ∈ nt N∀ ∈ . Определение 1. [4–6] Множество E(A), эле- ментами которого являются n-выборки вида (1) из мультимножества A, называется евкли- дово комбинаторное множество, если для про- извольных его элементов 1 2( , ,..., )na a a a′ ′ ′ ′= , a′′= 1 2( , ,..., )na a a′′ ′′ ′′= выполняются условия: ( )a a′ ′′≠ ⇔ ( : )n j jj N a a′ ′′⇔ ∃ ∈ ≠ , т.е. два элемента множе- ства E(A) отличны один от другого, если они не- зависимо от других отличий различаются по- рядком размещения символов, их образующих. Множество перестановок с повторениями из n действительных чисел, среди которых k раз- личны, называется общим множеством пере- становок и обозначается Pnk(A). Это множество упорядоченных n-выборок вида (1) из муль- тимножества А при условии n = q > k. Будем рассматривать элементы множества перестановок как точки арифметического евк- лидова пространства R n. В монографиях [9, 10] показано, что выпук- лой оболочкой множества перестановок явля- ется перестановочный многогранник П(А) = = conv Pnk(A), множество вершин которого равно множеству ( )nkP A перестановок: ( )vert M A = )(APnk= . Не теряя общности, упорядочим элементы мультимножества A по неубыванию: 1 2 ,na a a≤ ≤ ≤… (2) и элементы его основания – по возрастанию: 1 2 .ke e e< < <… Тогда выпуклой оболочкой об- щего множества перестановок Pnk(A) является общий перестановочный многогранник M(A) = = P(A), описываемый следующей системой ли- нейных неравенств: ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ∑∑ ∑∑ == α == )4(, )3(, 11 11 i j j i j n j j n j j ax ax j ,, tjnj N α≠α∈α ,, jtj ∀≠∀ ,,, ni NiNtj ∈∀∈∀ а ( )nkP A = vert П(А). Рассмотрим задачу евклидовой комбинатор- ной оптимизации вида: { }( ( ), ( )) : max ( ) ( )nk nkZ а P A а а P AΦ Φ ∈ , состоящей в максимизации функции Ф(а) на множестве перестановок ( )nkP A , где Ф(а) = 1 . n j j j с x = =∑ При отображении множества ( )nkP A в евкли- дово пространство Rn можно сформулировать задачу линейного программирования Z(F, X) максимизации критерия ( )F x на множестве X, 36 УСиМ, 2009, № 4 причем каждой точке a ∈ ( )nkP A будет соот- ветствовать точка ,Xx∈ такая что F(x) = Ф(a). { }( , ) : max ( ) |Z F X F x x X∈ , (5) где ∑ = = n j jj xcxF 1 )( , X – непустое множество в Rn, определяемое таким образом X = )(AvetrM , )(AconvPM nk= . Следует отметить, что иногда целесообраз- но решить задачу вида: )(maxarg )( xFx AMx∈ ∗ = , (6) для значения функции y* = F(x*). Имеет смысл рассматривать задачу, где значение целевой функции находится в интервале )()()( xFxFxF ≤≤ . Тогда задача (6) примет вид: )(maxarg )( xFx AMx∈ = при )(xFy = , )(maxarg )( xFx AMx∈ = при )(xFy = при условии minx x− → . Продолжая исследования и развивая резуль- таты работ [4–6], в статье предложен подход к решению задач, основанных на упорядочива- нии значений целевой линейной функции F(x) и построении гамильтонова пути для точек, в которых эти значения находятся. Далее под задачей понимаем задачу (6). Для построения метода, прежде всего, необ- ходимо определить начальную точку. Восполь- зуемся следующим утверждением. Утверждение 1. [8] Если для элементов муль- тимножества A и коэффициентов целевой функ- ции задачи 1 ( ) ( ) n j j j extr f x c x x vert M A = ⎧ ⎫ = ∈⎨ ⎬ ⎩ ⎭ ∑ выполняются соответственно условия (2) и niii c...cc ≤≤≤ 21 , (7) ,nn Ni ∈ то максимум функции f(x) на допусти- мом множестве достигается в точке x∗= 1 ( ,...ix∗ ..., ) ( ) ni x vertM A∗ ∈ , которая задается следующим образом: , ji j nx a j N∗ = ∀ ∈ а минимум соответственно в точке y = (y1, y2, … yn), где { } 1 1 0 . ji n j ny a j N + − −= ∀ ∈ ∪ Отметим, что общее число q линейных не- равенств, входящих в систему (3), (4), описы- вающую перестановочный многогранник M(A), равно 0 2 , n i n n i C = =∑ а это задача большей раз- мерности и очень сложна при решении тради- ционными методами линейного программиро- вания. Поэтому назрела необходимость в раз- работке новых методов, базирующихся на свой- ствах множества допустимых решений и целе- вых функций. Для рассматриваемой задачи (6) область до- пустимых решений определяется перестано- вочным многогранником, вершины которого – точки общего множества перестановок. Сфор- мулируем некоторые полезные свойства пере- становочного многогранника. Теорема 1. [4] Точки множества ( )nkP A ле- жат на семействе n -плоскостей вида ,01 21 =+−−− − − ++ − + − +− − s tnsn sn axx x sn sx sn sx sn s … … ( ) 1, 2, , , ! !s nt s n s = γ ≤ − … при этом s может принимать значения 1, 2, … …, 1n − . Теорема 2. [4] Вершины M(A), смежные с вершиной 1 2 ( , ,..., ) ni i ia a a a= , имеют вид β = )...,,( 21 njjj aaa= , где каждая из последователь- ностей 1 2( , ,..., )nj j j получена из 1 2( , ,..., )ni i i в результате перестановки таких индексов ri и ti , что 1, r tr t i ii i a a− = ≠ . Обе теоремы дают возможность рассматри- вать многогранник перестановок как некий граф, поскольку задача формулируется в тер- УСиМ, 2009, № 4 37 минах точек и связей между ними, т.е. в тер- минах графов. Большинство задач на графах касается определения компонент связности, поиска маршрутов, расстояния. Подход к решению задачи комбинаторной оптимизации Существует множество задач, постановка ко- торых укладывается в рамки задач комбина- торной оптимизации, в частности задач на мно- жестве перестановок с повторениями. Решение таких задач – сложный процесс. В данной статье рассматривается задача, в кото- рой необходимо определить точку экстремума – вершину перестановочного многогранника M(A) по известному значению целевой функции. Для этого вначале необходимо найти значения целевой функции в каждой точке, построить для этих значений цепочку (граф), отобража- ющую переходы от точки к точке, где точки соединяются дугами, и выяснить зависимость между ними. На основании утверждения 1 можно опре- делить точку максимума и минимума. Обозна- чим вершину x 0, определяющую точку мини- мума, началом сети, из которой дуги только выходят. Тогда вершина, определяющая точку максимума xn, – конец сети, в которую дуги входят. Воспользуемся теорией графов и рассмот- рим произвольную вершину многогранника. Произвольная вершина перестановочного мно- гогранника x и ребро u графа Г являются ин- цидентными, так как вершина x – один из кон- цов ребра u, т.е. входит в пару вершин, опре- деляющих ребро u. Как известно, степенью вершины называют число инцидентных ей ре- бер. Вершины первой степени называются кон- цевыми. Вершины нулевой степени очевидно не связаны ребрами с другими вершинами, и их называют изолированными. Учитывая, что каждое ребро перестановоч- ного многогранника инцидентно двум верши- нам графа, легко заметить, что сумма степеней всех вершин графа равна удвоенному числу его ребер. Пусть Г = CX , – некоторый граф, X = {1, 2, …, n}. Бинарная матрица ija такая, что 1, если вершины смежные, 0, если вершины несмежныеija ⎧ = ⎨ ⎩ определяет матрицу смежности графа переста- новочного многогранника. Смежность вершин многогранника перестановок определяется со- гласно теоремы 2. Отметим, что граф многогранника переста- новок – гамильтонов, т.е. должен содержать простой цикл, проходящий через каждую его вершину. Гамильтоновой цепью называют прос- тую цепь, содержащую все вершины графа. Знаменитая задача о коммивояжере – ком- бинаторная задача на множестве перестановок и связана с нахождением гамильтонова цикла кратчайшей суммарной длины. В этой задаче считается, что имеется n городов, которые не- пременно должен посетить коммивояжер, – все и по одному разу, проделав общий путь наи- меньшей суммарной протяженности. Если ме- жду городами есть дороги, то они интерпрети- руются как ребра графа порядка n с указанием длины. Вершины такого графа – вершины пе- рестановочного многогранника. Задача коммивояжера – пример комбина- торной задачи на графах, имеющий большое практическое и теоретическое значение. В си- лу своей вычислительной сложности она рав- носильна целому классу переборных задач и часто используется математиками для сравни- тельного анализа и изучения сложности алго- ритмов оптимизации в дискретной математике. Легко убедится, что в полном графе порядка n существует ровно (n – 1)! гамильтоновых цик- лов. Действительно, зафиксировав любую из n вершин полного графа, из нее (n – 1) способа- ми можно перейти в другую – следующую, по- лучая простую цепь из двух вершин. Далее вы- брать следующую вершину можно (n – 2) спо- собами и так далее, получая (n – 1) (n – 2) … … 2*1 = (n – 1)! гамильтоновых циклов. Поскольку ⎟ ⎠ ⎞ ⎜ ⎝ ⎛=≈ − e nnaenna!n nn при n →∞, можно предположить, что поиск га- мильтоновых циклов связан с огромным пере- бором вариантов. Но в данной статье предла- гается другой подход к решению таких задач, 38 УСиМ, 2009, № 4 без перебора вариантов, что делает алгоритм более эффективным и удобным. Рассмотрим пример перестановки с повто- рениями из множества A = {1, 2, 2, 4}. Последовательности перестановок можно интерпретировать как граф Gn, вершины кото- рого соответствуют всем точкам множества перестановок ( )nkP A . В графе две вершины, соответствующие пе- рестановкам f и g, соединены ребром тогда, ког- да g образуется из f однократной транспозици- ей соседних элементов (таким образом, каждая вершина имеет степень n – 1). Согласно теоре- ме 2, эти вершины являются смежными. Заметим, что последовательность переста- новок, образованная графом, соответствует га- мильтонову пути в Gn, т.е. пути, содержащему каждую вершину графа в точности один раз. Теорема 1 указывает на возможность разбие- ния множества ( )nkP A на подмножества, лежа- щие во взаимно параллельных плоскостях, так же согласно [4] исходное множество ( )nkP A можно разложить на множества меньшей раз- мерности, объединение которых порождает множество ( )nkP A : 1 ( ) ( ). k t nk nk t Р A Р A = =∪ В некоторых ситуациях важно, чтобы каж- дое последующее полученное подмножество на- именьшим образом отличалось от предыдущего. Последовательность таких подмножеств мож- но проиллюстрировать на графе, вершины ко- торого соответствуют бинарным последова- тельностям длины n и две вершины которого соединены ребром, если соответствующие по- следовательности отличаются только в одной позиции. В таком графе построенная последо- вательность соответствует гамильтонову пути. Рассмотрим примеры. Пример 1. Пусть дано множество A = {1, 2, 2, 4}, с помощью которого образуется множе- ство перестановок с повторениями ( )nkP A . Определена функция 44332211)( xcxcxcxcxF +++= , (8) коэффициенты которой упорядочены следую- щим образом 4321 cccc ≤≤≤ и принимают зна- чения {1, 2, 3, 4}, а y∗ = F(x∗) значение функ- ции в некоторой точке. Необходимо найти x∗ arg ( )extrF x= , где x∗ ∈ ∈ P(A). Решение: Как известно )()( AconvPAM nk= . Представим разложение графа перестановоч- ного многогранника M(A) по подграфам. Со- гласно утверждению 1 и условию упорядоче- ния коэффициентов, в начальной вершине гра- фа находится точка, в которой достигается максимальное значение целевой функции. На рис. 1 рассматривается подграф A , ко- торый задается уравнением x4 = 4, а остальные три цифры переставляются между собой. Стрел- ки указывают переход от точки к точке по убыванию значений целевых функций. 1 2 2 2 1 2 2 2 1 Рис. 1 Соответственно можно построить подграф B, на котором будут представлены точки при условии x4 = 2. Заметим, что такой подграф бу- дет содержать по шесть точек. Назовем эти ги- перплоскости 3-грани. Грани лежат на гипер- грани вида x1 + x2 +x3 +x4 = 1 + 2 + 2 + 4. Обо- значим ее символом A. Тогда A = A B C∪ ∪ , а на рис. 2 гиперплоскость A имеет вид. А. 1 2 2 4 2 1 2 4 2 2 1 4 В. 1 2 4 2 1 4 2 2 4 1 2 2 4 2 1 2 2 4 1 2 2 1 4 2 С. 2 2 4 1 2 4 2 1 4 2 2 1 Рис. 2 Таким образом, количество повторений в множестве перестановок ( )nkP A приводит к «склеиванию» гиперплоскостей в точках этих повторений. УСиМ, 2009, № 4 39 Определим значения целевой функции в каж- дой вершине многогранника. F(А1) = 1*1+2*2+3*2+4*4=1+4+6+16 = 27 F(А2) = 1*2+2*1+3*2+4*4=2+2+6+16 = 26 F(А3) = 1*2+2*2+3*1+4*4=2+4+3+16 = 25 F(А4) = 1*1+2*2+3*4+4*2=1+4+12+8 = 25 F(А5) = 1*1+2*4+3*2+4*2=1+8+6+8 = 23 F(А6) = 1*4+2*1+3*2+4*2=4+2+6+8 = 20 F(А7) = 1*4+2*2+3*1+4*2=4+4+3+8 = 19 F(А8) = 1*2+2*1+3*4+4*2=2+2+12+8 = 24 F(А9) = 1*2+2*4+3*1+4*2=2+8+3+8 = 21 F(А10) = 1*2+2*2+3*4+4*1=2+4+12+4 = 22 F(А11) = 1*2+2*4+3*2+4*1=2+8+6+4 = 20 F(А12) = 1*4+2*2+3*2+4*1=4+4+6+4 = 18 С учетом сказанного и рис. 1, 2 сформулиру- ем следующую лемму. Лемма 1. Точки множества перестановок с повторениями ( )nkP A можно разложить по па- раллельным гиперплоскостям в порядке убы- вания значений линейной целевой функции F(x) в этих точках. Справедливость леммы следует из теоремы 1 и утверждения 1 (рис. 3). А. 27 26 25 23 20 В. 25 19 24 21 С. 22 20 18 1 2 2 4 2 2 1 4 2 1 2 4 1 4 2 2 1 2 4 2 4 2 1 2 4 1 2 2 2 4 1 2 2 1 4 2 4 2 2 1 2 4 2 1 2 2 4 1 Рис. 3 На основании леммы 1 целесообразно сфор- мулировать утверждение, обеспечивающее по- строение иерархии точек. Лемма 2. Разложение точек комбинаторного множества перестановок с повторениями ( )nkP A при n ≥ 4 обеспечивает иерархическое распо- ложение этих точек по гиперплоскостям A, B, C (рис. 2) согласно значениям целевой функ- ции y∗ = F(x∗). Доказательство: Согласно теореме 1 раз- ложение по гиперплоскостям точек комбина- торного множества перестановок очевидно. А по утверждению 1 можно определить макси- мальное и минимальное значения функции F(x) на каждой из гиперплоскостей A, B, C, D. Стрел- ки указывают переход по значениям целевой функции от больших к меньшим. Для функции (8) при условии 4321 cccc ≤≤≤ введем следующие обозначения 1 2 1c cΔ = − ; 2 3 2c cΔ = − ; 3 4 3c cΔ = − . Для вышеопределенных обозначений уста- новим возможные соотношения: 1) 1 2 3Δ = Δ = Δ ; 1 2 32) ;Δ > Δ > Δ 2 1 33) ;Δ > Δ > Δ 2 3 14) .Δ > Δ > Δ Для построения гамильтонова пути необхо- димо установить соотношения на каждой из гиперплоскостей , ,A B C (рис. 3) между пара- ми точек. Для этого введем в рассмотрение понятия αi-вопросов. Определение 2. Назовем αi-опросами соот- ношения между точками множества переста- новок ( )nkP A на гиперплоскостях , ,A B C , ре- шаемых для определения гамильтонова пути отдельно на каждой гиперплоскости. По каждому из вышеопределенных случаев составим схему, отображающую расположение точек множества перестановок ( )nkP A по зна- чению целевой функции на гиперплоскостях , , ,A B C затем составим общее соотношение и укажем гамильтонов путь по всему перестано- вочному многограннику П(A). Рассмотрим гиперплоскость A (рис. 1) и точ- ки, между которыми необходимо установить связь. Поэтому вычислим соотношения: 1 2 2 4 2 1 2 4 1 1 0 − − + = 1 2 0Δ −Δ = , 2 1 2 4 2 2 1 4 0 1 1 − − + = 1 2 0−Δ + Δ = . Обозначим вопрос α1 = Δ1 – Δ2. 40 УСиМ, 2009, № 4 Тогда, размещение точек на гиперплоскости А по значению целевой функции соответствует рис. 1. Аналогичная ситуация и на гиперпло- скости С: С. 2 2 4 1 4 2 2 1 2 4 2 1 Рассмотрим гиперплоскость B (рис. 2), для точек которой составим соотношение для та- ких пар вершин: 1 4 2 2 2 1 4 2 1 3 2 − − + − = 1 2 22 0Δ − Δ = −Δ < , 4 1 2 2 2 4 1 2 2 3 1 − + − + = 1 2 12 0− Δ + Δ = −Δ < . На гиперплоскости B возникают вопросы 1 1 22α = Δ − Δ и 2 1 22α = − Δ + Δ . Поэтому га- мильтонов путь на B имеет вид: B . 1 2 4 2 2 1 4 2 1 4 2 2 2 4 1 2 4 1 2 2 4 2 1 2 При решении αi-вопросов также следует от- метить, что прослеживается зависимость меж- ду точками, которые находятся на разных ги- перплоскостях. Заметим, что на гиперплоскостях A и B имеются точки, для которых выполняется сле- дующее соотношение: 2 2 1 4 1 2 4 2 1 0 3 2 − + − + . С учетом вышесказанного точки на гиперп- лоскостях A и B можно разложить в следую- щую цепочку, в зависимости от значений це- левой функции: 27 26 25 25 24 23 21 20 19 4 2 1 2 4 1 2 2 2 4 1 2 1 4 2 2 2 1 4 2 1 2 4 2 2 2 1 4 2 1 2 4 1 2 2 4 Рассмотрим точки на гиперплоскости C , в частности (2 1 4 2), (1 4 2 2), так как 2 1 4 2 1 4 2 2 1 3 2 − + − = 1 2 12 0− Δ + Δ = −Δ < , то значение в (2 1 4 2) больше значения в точке (1 4 2 2). В данной ситуации рассматривается вопрос 2 1 22α = − Δ +Δ . Аналогично со значениями в точках (4 1 3 2) и (3 4 1 2) , так как 4 1 2 2 2 4 1 2 2 3 1 − + − + = 1 2 22 0−Δ + Δ = Δ > . Это вопрос 2 1 22α = −Δ + Δ . Если рассматривать отношение точек из разных гиперплоскостей, то значение в точке (1 2 4 2) из B равно значению в точке (1 4 2 2) из B , так как 1 2 4 2 1 4 2 2 2 2 0 − − = 2 3 0Δ −Δ = . В результате расчетов получим гамильтоно- ву цепь всего графа перестановочного много- гранника и упорядочение всех значений ли- нейной функции F(x) в порядке их убывания для точек гиперплоскостей , ,A B C (рис. 4): 27 26 25 25 24 23 21 21 20 20 19 18 4 2 2 1 4 2 1 2 2 4 2 1 4 1 2 2 2 4 1 2 2 2 4 1 1 4 2 2 2 1 4 2 1 2 4 2 2 2 1 4 2 1 2 4 1 2 2 4 Рис. 4 Пусть дано A1 = (1, 1, 3, 3,) = (12, 22), где k = 4, n = 2, r1 = 2, rn = r2 = 2. Система ограничений многогранника П (А) имеет вид: x1 ≥ 1; x2 ≥ 1; x3 ≥ 1; x4 ≥ 1; x1 + x2 + x3 ≥ 5; x1 + x2 + x4 ≥ 5; x1 + x3 + x4 ≥ 5; x2 + x3 + x4 ≥ 5; x1 + x2 + x3 + x4 = 8. Необходимо определить значение целевой функции 1 2 2 4( ) 1 2 3 4f x x x x x= + + + в верши- не многогранника П(А). Вершины многогранника размещены на ги- пергранях. Количество гиперграней этого мно- гогранника γ(Гk–2) = 2k = 8. Количество гипер- граней, проходящих через одну и ту же произ- вольную его вершину, равно γ(Г(ν))= r1 + r2 = 4. Многогранник изображен на рис. 5. Определим значение целевой функции в каж- дой вершине многогранника и построим гамиль- тонов путь по этим значениям. 1( ) 1 3 2 3 3 1 4 1 16f A = ∗ + ∗ + ∗ + ∗ = 2( ) 1 3 2 1 3 1 4 3 20f A = ∗ + ∗ + ∗ + ∗ = 3( ) 1 3 2 1 3 3 4 1 18f A = ∗ + ∗ + ∗ + ∗ = 4( ) 1 1 2 3 3 3 4 1 20f A = ∗ + ∗ + ∗ + ∗ = УСиМ, 2009, № 4 41 5( ) 1 1 2 3 3 1 4 3 20f A = ∗ + ∗ + ∗ + ∗ = 6( ) 1 1 2 1 3 3 4 3 24f A = ∗ + ∗ + ∗ + ∗ = 5A (1,3,1,3) 1A (3,3,1,1) 2A (3,1,1,3) 3A (3,1,3,1) 6A (1,1,3,3) 4A (1,3,3,1) Рис. 5 Пример 2. Пусть дано А2={1, 1, 2, 4,} = {12, 21 41}, где k = 4, n = 3, r1 = 2, r2 = r3 = 1. Система ограничений многогранника П(А) имеет вид x1 ≥ 1; x2 ≥ 1; x3 ≥ 1; x4 ≥ 1; x1 + x2 + x3 ≥ 4; x1 + x2 + x3 + x4 ≥ 4; x1 + x2 + x4 ≥ 4; x1 + x2 + x3 + x4 = 8; x1 + x3 + x4 ≥ 4. Найти значение целевой функции 1( ) 1f x x= + 2 2 42 3 4x x x+ + + в вершине многогранника П(А). Вершины многогранника размещены на ги- пергранях. Количество гиперграней этого мно- гогранника определено как ( ) 1 8 4 4 8.k C C−2γ Γ = + = Количество гиперграней, проходящих через од- ну и ту же произвольную его вершину ( ))νγ Γ = 1 1 2 1 2 1 3.C C= + = + = Многогранник П(А) изо- бражен на рис. 6. C (1,2,1,4) L (1,4,1,2) N (4,1,2,1) B (2,1,1,4) A(1,1,2,4) D(1,1,4,2) S (1,2,4,1) R (1,4,2,1) P (2,4,1,1) K (4,1,1,2) O (4,2,1 ,1) Рис. 6 На многораннике задано линейную целевую функцию вида 1 2 3 4( ) 1 2 3 4f x x x x x= + + + . Определим значение целевой функции в каждой вершине многогранника а) на гиперграни х4 = 4: (1;1;2;4) 1 1 2 1 3 2 4 4 25f * * * *= + + + = (2;1;1;4) 1 2 2 1 3 1 4 4 23f * * * *= + + + = (1;2;1;4) 1 1 2 2 3 1 4 4 24f * * * *= + + + = б) на гиперграни х4 =2: (1;1;4;2) 1 1 2 1 3 4 4 2 23f * * * *= + + + = (1;4;1;2) 1 1 2 4 3 1 4 2 20f * * * *= + + + = (4;1;1;2) 1 4 2 1 3 1 4 2 17f * * * *= + + + = в) на гиперграни х4 =1: (1;2;4;4) 1 1 2 2 3 4 4 1 21f * * * *= + + + = (1;4;2;4) 1 1 2 4 3 2 4 1 19f * * * *= + + + = (2;1;4;1) 1 2 2 1 3 4 4 1 22f * * * *= + + + = (4;1;2;1) 1 4 2 1 3 2 4 1 20f * * * *= + + + = (4;2;1;1) 1 4 2 2 3 1 4 1 16f * * * *= + + + = (2;4;1;1) 1 2 2 4 3 1 4 1 17f * * * *= + + + = Пример 3. Пусть А = {1, 2, 2, 2,} = {11, 22, 31}, где k = 4, n = 3, r1 = 1, rn = r3 = 1. Система огра- ничений многогранника П (А) имеет вид x1 ≥ 1; x2 ≥ 1; x3 ≥ 1; x4 ≥ 1; x1 + x2 ≥ 3; x1 + x3 ≥ 3; x1 + x4 ≥ 3; x2 + x3 ≥ 3; x2 + x4 ≥ 3; x3 + x4 ≥ 3; x1 + x2 + x3 ≥ 5; x1 + x2 + x4 ≥ 5; x1 + x3 + x4 ≥ 5; x2 + x3 + x4 ≥ 5; x1 + x2 + x3 + x4 = 8. Вершины многогранника размещены на ги- пергранях. Количество гиперграней этого мно- гогранника определено как ( ) 1 2 3 2 4 4 4k C C C−γ Γ = + + = = 14, а количество гиперграней, пересекающих- ся в одной вершине, ( ) 1 1 1 1 2 1 4C C Cν )γ Γ = + + = . Многогранник П (А) изображен на рисунке 7. 1 2 3 4( ) 1 2 3 4f x x x x x= + + + 2( ) 1 2 2 2 3 3 4 1 16f x * * * *= + + + = 3( ) 1 1 2 3 3 2 4 2 21f x * * * *= + + + = 4( ) 1 2 2 3 3 2 4 1 18f x * * * *= + + + = 5( ) 1 2 2 1 3 3 4 2 21f x * * * *= + + + = 6( ) 1 1 2 2 3 2 4 3 23f x * * * *= + + + = 7( ) 1 2 2 1 3 2 4 3 22f x * * * *= + + + = 8( ) 1 3 2 1 3 2 4 2 19f x * * * *= + + + = 9( ) 1 3 2 2 3 2 4 1 17f x * * * *= + + + = 42 УСиМ, 2009, № 4 10( ) 1 2 2 3 3 1 4 2 20f x * * * *= + + + = 11( ) 1 2 2 2 3 1 4 3 22f x * * * *= + + + = 12) 1 3 2 2 3 1 4 2 23f ( x * * * *= + + + = На многограннике задана линейная функция 1 2 3 4( ) 1 2 3 4f x x x x x= + + + . Построим граф многогранника П(А) (рис. 7). Как известно, граф перестановочного много- гранника П(А) – гамильтонов. Тогда толщина многогранника П(А) равна числу вершин мно- гогранника П(А). Теорема 3. Если П(А) – перестановочный многогранник, то граф многогранника П(А) – гамильтонов. Х8 (3,1,3,2) Х4 (2,3,2,1) Х7 (2,1,2,3) Х5 (2,1,3,2) Х3 (1,3,2,2) Х10 (2,3,1,2) Х12 (3,2,1,2) Х1 (1,2,3,2) Х11 (2,2,1,3) Х2 (2,2,3,1) Х6 (1,2,3,2) Х9 (3,2,2,1) Рис. 7 Заключение. Исследованы сложные ком- бинаторные задачи на множестве перестано- вок. Рассмотрены некоторые свойства допус- тимой области евклидовой комбинаторной за- дачи, имеющей специфические входные дан- ные. Построен и обоснован метод упорядоче- ния значений линейной функции на множестве перестановок. Дальнейшее развитие этой тематики, кото- рая не нашла полного отражения в статье, бу- дет направлено на реализацию и адаптацию сформулированного метода, а также на разра- ботку новых методов решения комбинаторных оптимизационных задач с учетом входных данных и других комбинаторных множеств. 1. Сергиенко И.В., Каспшицкая М.Ф. Модели и мето- ды решения на ЭВМ комбинаторных задач опти- мизации. – К.: – Наук. думка, 1981. – 287 с. 2. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Там же, 1988. – 472 с. 3. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. При- ближенные методы решения дискретных задач оп- тимизации. – Там же, 1980. – 276 с. 4. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического про- ектирования. – Там же, 1986. – 265 с. 5. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідо- вої комбінаторної оптимізації. – К.: Ін-т систем. до- сліджень освіти, 1993. – 188 с. 6. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функ- ціями. – К.: Наук. думка, 2005. – 118 с. 7. Баранов В.И., Стечкин Б.С. Экстремальные ком- бинаторные задачи и их приложения. – М.: ФИЗ- МАТЛИТ, 2004. – 240 с. 8. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Под- ход к решению векторных задач дискретной опти- мизации на комбинаторном множестве перестано- вок // Кибернетика и системный анализ. – 2008. – № 3. – С. 158–172. 9. Емеличев В.А., Ковалев М.М., Кравцов М.К. Много- гранники, графы, оптимизация. – М.: Наука, 1981. – 344 с. 10. Донец Г.А., Шулинок И.Э. О сложности алгоритмов поиска в глубину на модульных графах // Теорія оптимальних рішень. – 2002. – № 1. – С. 105–110. 11. Донец Г.А. Алгоритмы раскраски плоских графов // Там же. – 2006. – № 5. С. 134–143. 12. Донец Г.А., Самер И.М., Альшаламе Решение зада- чи о построении линейной мозаики // Там же. – 2005. – № 4. – С. 15–24. Поступила 19.11.2008 Тел. для справок:(044) 526-2188 (Киев) E–mail: ludapl@ukr.net © Г.А. Донец, Л.Н. Колечкина, 2009 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Ähnliche Einträge