Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Управляющие системы и машины
Datum:	2014
Hauptverfasser:	Тимофієва, Н.К., Гриценко, В.І.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2014
Schlagworte:	Фундаментальные и прикладные проблемы Computer Science
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/83279
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:	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2014. — № 1. — С. 8-25. — Бібліогр.: 32 назв. — укр., рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-83279
record_format	dspace
spelling	Тимофієва, Н.К. Гриценко, В.І. 2015-06-17T19:41:50Z 2015-06-17T19:41:50Z 2014 Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2014. — № 1. — С. 8-25. — Бібліогр.: 32 назв. — укр., рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/83279 519.14+519.168 С использованием теории комбинаторной оптимизации сформулированы математические постановки таких прикладных задач геораспределенных динамических систем, как распределение сервисных объектов на определенной территории, и задача сохранения окружающей среды. Для них смоделирована целевая функция и определен ее аргумент. Среди рассматриваемых классов задач выделены подклассы, решаемые методом структурно-алфавитного поиска. Using the theory of combinatorial optimization the mathematical formulation of such applications of the geodistribution dynamical systems as distribution of objects service in a territory definite and the problem of environment are formulated. The objective function is modeled, its argument is determined. Among the considered classes of problems the subclasses solved by a structure-alphabetical search method are identified. З використанням теорії комбінаторної оптмізації сформульовано математичні постановки таких прикладних задач георозподілених динамічних систем, як розподілення сервісних об’єктів на певній території, та задача збереження довкілля. Для них змодельовано цільову функцію та визначено її аргумент. Із розглянутих класів задач виділено підкласи, які розв’язуються методом структурно-алфавітного пошуку. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы Computer Science Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах Modeling and Solving an Application Problems of Combinatorial Optimization Arised in Intelligent Geodistribution Dynamical Systems Моделирование и решение прикладных задач комбинаторной оптимизации, возникающих в интеллектуальных геораспределенных динамических системах Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
spellingShingle	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах Тимофієва, Н.К. Гриценко, В.І. Фундаментальные и прикладные проблемы Computer Science
title_short	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
title_full	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
title_fullStr	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
title_full_unstemmed	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
title_sort	моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах
author	Тимофієва, Н.К. Гриценко, В.І.
author_facet	Тимофієва, Н.К. Гриценко, В.І.
topic	Фундаментальные и прикладные проблемы Computer Science
topic_facet	Фундаментальные и прикладные проблемы Computer Science
publishDate	2014
language	Ukrainian
container_title	Управляющие системы и машины
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
format	Article
title_alt	Modeling and Solving an Application Problems of Combinatorial Optimization Arised in Intelligent Geodistribution Dynamical Systems Моделирование и решение прикладных задач комбинаторной оптимизации, возникающих в интеллектуальных геораспределенных динамических системах
description	С использованием теории комбинаторной оптимизации сформулированы математические постановки таких прикладных задач геораспределенных динамических систем, как распределение сервисных объектов на определенной территории, и задача сохранения окружающей среды. Для них смоделирована целевая функция и определен ее аргумент. Среди рассматриваемых классов задач выделены подклассы, решаемые методом структурно-алфавитного поиска. Using the theory of combinatorial optimization the mathematical formulation of such applications of the geodistribution dynamical systems as distribution of objects service in a territory definite and the problem of environment are formulated. The objective function is modeled, its argument is determined. Among the considered classes of problems the subclasses solved by a structure-alphabetical search method are identified. З використанням теорії комбінаторної оптмізації сформульовано математичні постановки таких прикладних задач георозподілених динамічних систем, як розподілення сервісних об’єктів на певній території, та задача збереження довкілля. Для них змодельовано цільову функцію та визначено її аргумент. Із розглянутих класів задач виділено підкласи, які розв’язуються методом структурно-алфавітного пошуку.
issn	0130-5395
url	https://nasplib.isofts.kiev.ua/handle/123456789/83279
citation_txt	Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2014. — № 1. — С. 8-25. — Бібліогр.: 32 назв. — укр., рос.
work_keys_str_mv	AT timofíêvank modelûvannâtarozvâzannâprikladnihzadačkombínatornoíoptimízacííâkívinikaûtʹvíntelektualʹnihgeorozpodílenihdinamíčnihsistemah AT gricenkoví modelûvannâtarozvâzannâprikladnihzadačkombínatornoíoptimízacííâkívinikaûtʹvíntelektualʹnihgeorozpodílenihdinamíčnihsistemah AT timofíêvank modelingandsolvinganapplicationproblemsofcombinatorialoptimizationarisedinintelligentgeodistributiondynamicalsystems AT gricenkoví modelingandsolvinganapplicationproblemsofcombinatorialoptimizationarisedinintelligentgeodistributiondynamicalsystems AT timofíêvank modelirovanieirešenieprikladnyhzadačkombinatornoioptimizaciivoznikaûŝihvintellektualʹnyhgeoraspredelennyhdinamičeskihsistemah AT gricenkoví modelirovanieirešenieprikladnyhzadačkombinatornoioptimizaciivoznikaûŝihvintellektualʹnyhgeoraspredelennyhdinamičeskihsistemah
first_indexed	2025-11-24T05:53:42Z
last_indexed	2025-11-24T05:53:42Z
_version_	1850842922460643328
fulltext	8 УСиМ, 2014, № 1 Фундаментальные и прикладные проблемы Computer Science УДК 519.14+519.168 Н.К. Тимофієва, В.І. Гриценко Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах С использованием теории комбинаторной оптимизации сформулированы математические постановки таких прикладных задач гео- распределенных динамических систем, как распределение сервисных объектов на определенной территории, и задача сохранения окружающей среды. Для них смоделирована целевая функция и определен ее аргумент. Среди рассматриваемых классов задач вы- делены подклассы, решаемые методом структурно-алфавитного поиска. Using the theory of combinatorial optimization the mathematical formulation of such applications of the geodistribution dynamical sys- tems as distribution of objects service in a territory definite and the problem of environment are formulated. The objective function is modeled, its argument is determined. Among the considered classes of problems the subclasses solved by a structure-alphabetical search method are identified. З використанням теорії комбінаторної оптмізації сформульовано математичні постановки таких прикладних задач георозподі- лених динамічних систем, як розподілення сервісних об’єктів на певній території, та задача збереження довкілля. Для них змодельовано цільову функцію та визначено її аргумент. Із розглянутих класів задач виділено підкласи, які розв’язуються ме- тодом структурно-алфавітного пошуку. Вступ. Основними складовими сучасної еко- номіки з-поміж інших є такі промислові компле- кси, як транспортні та телекомунікаційні мере- жі, системи нафта- та газовидобутку, розподілені сервісні об’єкти на певній території, зрошуваль- ні системи тощо [1–20]. Вони потребують роз- роблення багаторівневих розподілених комп'ю- терних систем керування. Такі комплекси на- зивають георозподіленими виробничими сис- темами. В процесі їх проектування та експлуа- тації необхідно вирішувати багато проблем, по- в’язаних з наявністю земельного ресурсу для розташування технологічних об'єктів та інже- нерних споруд, з оптимальним розміщенням цих об’єктів на певній території, вирішувати еко- номічні проблеми; необхідно враховувати і еко- логічний стан довкілля, а також приймати оп- тимальне рішення за умов невизначеності різ- ної природи та прогнозувати поведінку системи в часі. Для вирішення ситуації невизначеності використовують різні підходи, зокрема і спо- соби, пов’язані з обчислювальним інтелектом. Оскільки георозподілені системи одержу- ють ресурси з навколишнього середовища, то вони є відкритою динамічною структурою. Як Ключові слова: георозподілені динамічні системи, комбі- наторна оптимізація, розміщення сервісних об’єктів, тран- спортна задача, метод структурно-алфавітного пошуку. правило, в них розглядаються динамічні зада- чі, що належать до управлінських проблем. До того ж, прикладні задачі оптимізації, які зво- дяться до задач комбінаторної оптимізації, мо- жуть бути як статичними, так і динамічними. Назвемо інтелектуальними георозподілени- ми динамічними системами виробничі або сер- вісні промислові комплекси, розподілені на пев- ній території, які мають координати та керу- ються як централізовано, так і в автономному режимі за допомогою розподілених комп’ю- терних систем керування і є відкритими дина- мічними структурами. Для розроблення та екс- плуатації вони потребують використання різ- них підходів, зокрема і способів, пов’язаних з обчислювальним інтелектом. При розміщенні нових виробничих комплексів можна викорис- товувати існуючі ресурси (транспортні мережі, телекомунікації тощо). Серед них виділимо такі:  магістральні виробничі комплекси (заліз- ниці, автомобільні дороги, нафто- та газовидо- буток);  сервісні об’єкти, розміщені на певній те- риторії, в яких використано існуючі транспортні та інші ресурси. Це – ремонтні майстерні, бан- ки, мережа аптек, магазинів тощо;  авіаперевезення, при яких використано як земельні ресурси, так і повітряний простір; УСиМ, 2014, № 1 9  телекомунікаційні мережі, які для переда- чі інформації потребують земельних ресурсів, прокладання каналів зв’язку під землею та під водою, використання повітряного простору та телекомунікаційних космічних систем;  зрошувальні системи, які займають певну територію та потребують розміщення на ній датчиків для збору поточної інформації про стан ґрунту. Розроблення та експлуатація інтелектуаль- них георозподілених динамічних систем по- требує вирішення проблем оптимізації, серед яких виділимо:  вирішення низки оптимізаційних задач, які зводяться до задач комбінаторної оптимізації;  оптимальне використання земельних ре- сурсів;  розроблення баз знань та інтелектуалізація систем керування для прийняття рішень в умо- вах невизначеності;  розроблення способів прогнозування ро- боти георозподілених динамічних систем;  оптимізація витрат на розробку та експлу- атацію георозподілених динамічних систем;  оптимальне вирішення екологічної про- блеми. Далі розглянемо задачі оптимізації, що ви- никають при розробці та експлуатації геороз- поділених динамічних систем і які зводяться до задач комбінаторної оптимізації. Різні класи за- дач потребують cпеціальних підходів до їх роз- в’язання. Побудова математичних моделей при- кладних задач у межах теорії комбінаторної оптимізації дозволяє виявити їхні характерні властивості, сформулювати для них адекватну математичну постановку, завдяки якій нескла- дно розробляти нові або використовувати ві- домі алгоритми для ефективного вирішення. Загальна характеристика задачі розподі- лення мережі сервісних об’єктів Проблему розміщення підприємств, до якої належить задача розподілення мережі сервісних об’єктів на певній території, досліджено досить ґрунтовно [2, 9–15, 18, 19]. Математичні моде- лі цих задач розроблялися і розробляються в межах цілочислового лінійного програмування. Побудовані моделі мають властивості, харак- терні для транспортної задачі та її узагальнен- ня, тому їх інколи зводять до цієї задачі. Деякі з них моделюються в межах теорії масового обслуговування [5, 21]. Для розв’язання задачі оптимального розміщення підприємств засто- совуються методи декомпозиції, універсальні та спеціальні методи математичного програму- вання як точні, так і наближені [2, 19]. Оскіль- ки в задачі розміщення підприємств спостері- гається перебір варіантів, то вона належить до задач комбінаторної оптимізації. У [18] описано спосіб розв’язання задачі розміщення складів, в якому використано апроксимаційно-комбіна- торний підхід. У [3, 9–11, 19] для моделювання задач розміщення підприємств використовують теорію графів, а в [4] – перелічувальну комбі- наторику, застосовуючи яку визначають кіль- кість варіантів їхнього розміщення. Але при розв’язанні прикладних задач цього класу ва- жливо не знайти кількість варіантів, а змоде- лювати цільову функцію та визначити її аргу- мент (комбінаторну конфігурацію), для якого вона набуває оптимального значення. Отже, задача розподілення мережі сервісних об’єктів на певній території полягає у пошуку такої їхньої оптимальної кількості, за якої усі потенційні замовники, що належить до цієї те- риторії, могли б скористатися послугами таких об’єктів за умови мінімальної віддалі між ними та мінімальними витратами на обслуговування, наприклад ремонт приладів. Для мінімізації ви- трат на перевезення та ремонт необхідно побу- дувати математичну модель «замовник–викона- вець», в якій основною умовою може бути змен- шення віддалі від замовника до виконавця, що впливає на зниження ціни на послуги. В задачі розподілення мережі сервісних об’єк- тів виділимо такі варіанти:  кількість замовників і кількість сервісних об’єктів відома;  кількість замовників і кількість сервісних об’єктів невідома;  кількість замовників відома, а кількість сервісних об’єктів необхідно визначити; 10 УСиМ, 2014, № 1  кількість замовників невідома, а кількість сервісних об’єктів відома. В літературі описано задачі розміщення під- приємств, кількість яких наперед задано і те- риторія для їх розташування відома [2, 18]. За умов конкуренції розміщення підприємств про- водиться в динамічному режимі. Поруч може бути розміщено кілька однотипних обслуго- вуючих центрів [10, 11]. У [15] задача розмі- щення центрів обслуговування розглядається як гра двох учасників. Наведемо загальну постановку задачі комбі- наторної оптимізації і сформулюємо її, як у роботі [22]. Задачі цього класу, як правило, за- даються однією або кількома множинами, на- приклад A і B, елементи яких мають будь-яку природу. Назвемо ці множини базовими. Наяв- ні два типи задач. В першому типі кожну з цих множин подамо у вигляді графа, вершинами якого є її елементи, а кожному ребру поставлено у відповідність число Rclt  , яке називають ва- гою ребра (R – множина дійсних чисел); {1,..., }l n , }~,...,1{ nt  , n – кількість елеме- нтів множини A, n~ – кількість елементів мно- жини B. Приймемо, що nn ~ . Між елемента- ми цих множин існують зв'язки, числове зна- чення яких назвемо вагами. Величини ltc на- звемо вхідними даними і задамо їх матрицями. В другому типі задач між елементами заданої мно- жини зв'язків не існує, а вагами є числа Rv j  , {1,..., }j n , яким у відповідність поставлено деякі властивості цих елементів, числові зна- чення яких задаються скінченними послідов- ностями, що також є вхідними даними. Ці ве- личини визначають значення цільової функції. Для обох типів задач з елементів однієї або кількох із заданих множин, наприклад Aal  , },...,1{ nl , утворюється комбінаторна множи- на W – сукупність комбінаторних конфігурацій певного типу (перестановки, вибірки різних ти- пів, розбиття тощо). На елементах w комбіна- торної множини W вводиться цільова функція )(wF . Необхідно знайти елемент w множини W, для якого )(wF набуває екстремального значення при виконанні заданих обмежень, тобто функціонал 0 ( ) glob extr ( ) w W W F w F w    , де extr {min, max} , 0W – підмножина, яка ви- значається обмеженнями задачі. За способом обчислення цільової функції виділимо задачі, в яких для певного варіанту розв'язку її значення обчислюється одночасно. Такі задачі назвемо статичними. Задачі, в яких в процесі розв'язання генерується поточна ін- формація, за якою оцінюється результат, а по- шук оптимального розв'язання проводиться по- етапно з обчисленням часткових сум цільової функції, назвемо динамічними. Змоделюємо вхідні дані задачі комбінатор- ної оптимізації першого типу скінченними по- слідовностями. Подамо елементи h наддіагона- лей симетричної комбінаторної матриці )( kwQ комбінаторною функцією 1( ( ) , )\|k mf j w   1 ( (1) , ) ,..., ( ( ) , )k k mf w f m w   , а елемен- ти h наддіагоналей симетричної матриці C – функцією натурального аргументу 1( ) \|mj  ( (1), ..., ( ))m   , де 2 )1(   nn m – кількість елементів h наддіагоналей матриць C і )( kwQ , 1,1  nh . Верхній індекс k ( {1,..., }k q ) в kw – порядковий номер kw в W . Якщо матри- ці )( kwQ і C – несиметричні, то ( ( ),f j 1) \|k mw і 1( ) \| mj містять усі їхні елементи, а 2m n (або nnm ~ ). Функція цілі )( kwF набуде вигляду )(),)(()( 1 jwjfwF k m j j k   . (1) Побудова математичних моделей задач ком- бінаторної оптимізації, як правило, проводить- ся з використанням задачі цілочислового лі- нійного програмування, яка формулюється в такому вигляді. Знайти екстремум функції   n l ll xc 1 ~ за умов    n l slsl bxa 1 ~~ , ps ,1 , 0lx , nl ,1 , lx – цілі для pl ,1 , np  , ssll bac ~ ,~,~ – задані цілі числа, lx – змінні. Виходячи з цієї УСиМ, 2014, № 1 11 моделі, вважають, що цільова функція в ком- бінаторній оптимізації залежить від багатьох змінних, а lx є елементами комбінаторної кон- фігурації ),...,( 1 nwww  і перемножуються на задані числа sll ac ~,~ . Але це неможливо, оскіль- ки lw можуть мати будь-яку природу. Змінні lx не є елементами w , а модель цілочислового лінійного програмування не відображає суті задач комбінаторної оптимізації. Цілочислове лінійне програмування розроблялося для еко- номічних задач, що належить до другого типу, для яких математична постановка формулю- ється так: задано одну множину A, елементи Aal  якої не мають між собою звя'зків. Нато- мість кожен елемент Aal  , {1,..., }l n , характе- ризується певною властивістю (вагою) lx . Ар- гументом цільової функції в них, як правило, є вибірки (сполучення, розміщення), а вхідні да- ні – послідовність значень ваг nxx ,...,1 елемен- тів la заданої множини A, кількість яких збіга- ється з кількістю елементів у w . Звідси твер- дження, що аргументом цільової функції в цих задачах є послідовність вхідних даних nxx ,...,1 , а не комбінаторна конфігурація w 1( ,..., )nw w . Відповідно вважають, що цільова функція в задачах комбінаторної оптимізації залежить від багатьох змінних. Послідовність nxx ,...,1 є вхідними даними певної задачі, а значення lx неявно залежить від комбінаторної конфігурації ),...,( 1 nwww  , тобто вираз   n l ll xc 1 ~ слід записати у такому ви- гляді:    n l ll wxcwF 1 )(~)( . Тоді постає проблема визначення цієї залежності в задачах комбі- наторної оптимізації. Для цього необхідно розробляти їхні математичні постановки з урахуванням комбінаторної природи. До того ж при використанні цільової функції ( )F w  1 ( ) n l l l c x w    на комбінаторних множинах, які складаються з підмножин ізоморфних комбі- наторних конфігурацій, виникає ситуація не- визначеності [23]. Для моделювання прикладних задач в межах теорії комбінаторної оптимізації необхідно:  визначити вид задачі (статична або динамі- чна) за способом обчислення цільової функції;  визначити базові множини, якими задаєть- ся певна задача;  визначити тип задачі за вхідними даними;  визначити аргумент цільової функції (ком- бінаторну конфігурацію);  змоделювати цільову функцію. Уточнимо такі поняття, як критерій і цільо- ва функція. Критерій – ознаки або властивості, які ха- рактеризують певний об’єкт або зв’язки між об’єктами, і є вхідними даними. Цільова функція – вираз, який формулюєть- ся на основі заданих критеріїв з урахуванням особливостей задачі, за яким обчислюється і оцінюється результат її розв’язку. Як правило, цільову функцію ототожнюють з критеріями, а за її аргумент приймають вхід- ні дані. Але для одних і тих же критеріїв ці- льову функцію можна змоделювати по-різ- ному, тобто оцінка проводиться за різними ви- разами і отримується різний результат. Її аргу- ментом є комбінаторні конфігурації різних ти- пів (перестановки, сполучення, розбиття n - елементної множини на підмножини та ін.). До того ж вона може залежати як від однієї змін- ної, так і від багатьох (комбінаторних конфігу- рацій). За цією ознакою задачі комбінаторної оптимізації розділяються на підзадачі. В цьому випадку для їхнього розв’язання необхідно розробляти гібридні алгоритми. Враховуючи сказане, змоделюємо задачу розподілення мережі сервісних об’єктів на певній території як задачу комбінаторної оп- тимізації. Побудова математичної моделі задачі роз- поділення мережі сервісних об’єктів з вико- ристанням теорії комбінаторної оптимізації Побудуємо математичну модель розподілен- ня мережі сервісних об’єктів за умови, що їхня 12 УСиМ, 2014, № 1 кількість наперед невідома, але відома кіль- кість замовників і їхнє місцезнаходження. Мо- дель має враховувати транспортні витрати та розподілення замовлень між сервісними об’єк- тами. Вважатимемо, що поставка матеріалу проводиться централізовано як з одного цент- ру, так і з розподілених пунктів постачання. Моделювання задачі розподілення сервіс- них об’єктів на певній території з використан- ням теорії комбінаторної оптимізації свідчить, що вона ділиться на кілька підзадач: задачу кластеризації, транспортну задачу і задачу з теорії масового обслуговування. Розглянемо ці підзадачі. Задача кластеризації. Для визначення кіль- кості сервісних об’єктів необхідно виходити з кількості усіх відомих замовників на певній те- риторії, які позначимо множиною 1{ ,..., }nA a a . В результаті розв’язання задачі кластериза- ції кількість сервісних об’єктів дорівнюватиме кількості одержаних кластерів. Сформулюємо математичну постановку цієї задачі, вхідними даними в якій є віддалі між замовниками. Ар- гументом цільової функції в ній є розбиття n- елементної множини на підмножини, яке по- значимо k  , де  – множина розбиттів. Задача кластеризації задається на одній мно- жині },...,{ 1 naaA  . Числові значення зв'язків між елементами Aaa tl , (вхідні дані), якими є віддалі між замовниками, подамо симетрич- ною матрицею l t n n C c   (або функцією 1( ) \|mj ). Для задання розподілення елементів множини },...,{ 1 naaA  між підмножинами (кластерами) k s фіксованого розбиття k  введемо симетричну комбінаторну (0,1)-матри- цю розподілення nn k lt k gQ   )()( (або функ- цію mkjf 1\|),)((  ). Якщо 1),)((  kjf (або 1)( k lsg ), то елементи Aaa tl , знахо- дяться в одному кластері. В іншому разі ( ( ) , ) 0kf j   . Задача кластеризації полягає у пошуку такого розбиття k  на неперетинні кластери, для якого цільова функція (1) набу- ває максимального значення. Оскільки пошук оптимального розв’язку про- водиться на усій множині розбиттів  , то при використанні для оцінки результату цільової функції (1) виникає ситуація невизначеності. Тобто, для певного впорядкування підмножин ізоморфних розбиттів закономірність зміни значень виразу (1) змінюється однаково неза- лежно від вхідних даних. Для виходу з цієї си- туації необхідно ввести додаткові цільові фун- кції, критерії або обмеження. Математична постановка транспортної за- дачі як задачі комбінаторної оптимізації. Для оптимізації перевезень необхідно розв’язати транспортну задачу як всередині утворених кластерів, так і між кластерами. Це – друга під- задача, аргументом цільової функції в якій є перестановка i  , де  – множина пере- становок. При цьому необхідно врахувати в за- лежності від віддалі вартість перевезень мате- ріалів від центрального постачальника матері- алів та приладів, що потребують ремонту, до цих об’єктів (наприклад, ремонтних майстерень). Транспортна задача була формалізована ще у 1781 р. [24]. Як проблему лінійного програ- мування її вперше розглянуто у роботі [25], тому цю задачу розглядають як задачу лінійно- го програмування спеціального виду, і вона є підмножиною задач лінійного програмування. Для розв’язання транспортної задачі викорис- товують симплекс-метод, метод одночасного розв’язання прямої та двоїстої задачі, метод потенціалів, угорський метод, динамічне про- грамування, метаеврістичні підходи [2, 26, 27]. Цю задачу ще зводять до задачі комівояжера або до задачі про ранець. Для пошуку початко- вого розв’язку використовують метод північ- но-західного кута, метод мінімальних тарифів, а для остаточної оптимізації – метод потенціа- лів. У [27] зазначено, що задача про призна- чення є частковим випадком класичної транс- портної задачі. Задача про призначенння полі- номіально розв’язується угорським алгоритмом. Сформулюємо однокритеріальну транспорт- ну задачу закритого виду, в якій оптимізується УСиМ, 2014, № 1 13 вартість перевезення, як задачу комбінаторної оптимізації. Вона задається двома множинами A і B , де елементи Aal  , відповідають про- дукції, яку необхідно перевезти, а Bbt  – про- дукцію, яка споживається заданим об’єктом. Між елементами цих множин визначено зв'яз- ки, Rclt  – їхнє числове значення (ваги). Ве- личини ltc (вхідні дані) задамо несиметричною матрицею. Із елементів однієї із заданих множин, на- приклад Aal  , },...,1{ nl , утворимо комбіна- торну множину  – сукупність комбінаторних конфігурацій певного типу (в даному випадку це – перестановки). На елементах  комбіна- торної множини  введемо цільову функцію )(F . Необхідно знайти елемент  множини  , для якого )(F набуває екстремального зна- чення за виконання заданих обмежень. Для розв’язання транспортної задачі мето- дом структурно-алфавітного пошуку [22] зве- демо її до задачі про призначення. Множину 1{ ,..., }nA a a подамо множиною 1 ' ' 1{ ,...A a , 1 * ' ' ' 1 ,..., ,..., } s s n na a a , де елемент ' l a визначає найменшу частину продукції від загальної Aal  , яка в будь-якій комбінації з іншими ' rl a повністю задовольняє попит будь-якого пунк- ту Bbt  , тобто умовно приймемо, що 1'  rl a , },...,{, 1 s llr , а n n n aaaa ss     * 1 ' 1 1 1 ' 1 ,..., , де  l – кількість елементів ' l a в Aal  . Анало- гічно, множину },...,{ ~1 nbbB  подамо упоряд- кованою множиною 1 1 ' ' ' ' ' 1 1{ ,..., ,..., ,..., } p pn nB b b b b   , де елемент ' t b , 1{ ,..., }ps s  , дорівнює одній одиниці продукції від загальної Bbt  , а 1 ' ' 1 11 1 ,...,p pn n nb b b b       , де ps – кількість елементів ' t b у Bbt  . Вартість перевезень в транспортній задачі задається несиметричною комбінаторною мат- рицею )( kQ  (комбінаторна функція  ( ) ,f j 1)\|k m , а для k-го варіанта розв'язання задачі введемо (0,1)-матрицю C (функція 1( ) \| mj ), де nnm ~ . Її елемент 1'  tlc , якщо з la вибира- ється одиниця продукції Aaa ll   ' і перево- зиться в пункт споживання, якому необхідно Bbb tt   ' одиниць. В іншому разі 0'  tlc . Тобто, одному елементу продукції з 'A від- повідає один пункт споживання з 'B . Роз- в’язання цієї задачі знаходиться на множині перестановок, причому виконується транспо- зиція або стовпців, або рядків матриці )( kwQ . Цільова функція зводиться до виразу  1 ( ) ( ), mk jj F f j      ( )k j  . Аналогічно фор- мулюється задача про призначення, яка також задається на двох множинах: 1{ ,..., }nA a a , де Aal відповідає l-му претенденту, і 1{ ,...B b ..., }nb , де Bbt  відповідає t-й посаді. Між елементами Aal і Bbt  визначено зв'язки. Таким чином транспортна задача зводиться до задачі про призначення. Задача з теорії масового обслуговування. Тре- тя підзадача, яку отримуємо після розбиття ос- новної задачі, належить до теорії масового об- слуговування і полягає у визначенні потужності сервісних об’єктів (ремонтних майстерень) в за- лежності від заявок, що надходять від замовни- ка. Позначимо підмножиною },...,{ 1 ttt tzzZ   за- явки, що надходять в t -у майстерню від t за- мовників, а 1{ ,..., }t t t t r r r z z z     – заявки від r-го за- мовника в t -у майстерню, де t rz  ~ – одна заявка, t ~ – кількість заявок, } ~ ,...,1{ t . Оскільки t ~ – величина випадкова, то виникає ситуація неви- значеності. Вважатимемо, що ' ' ' ' 1{ ,..., }t t t t r r r z z z    tZ – найбільша кількість заявок, яка може надійти в t -у майстерню від r -го замовника. Тоді необхідно визначити таке сполучення без повторень Μ  елементів t rz '  з множини tZ , коли потужність майстерні була б збалансова- 14 УСиМ, 2014, № 1 на, тобто 1 1 ( ) t t t r r             , де ( )t   – по- тужність t-ї майстерні, r – кількість заявок від r-го замовника, які надійшли в t -у майстерню, M – множина сполучень без повторень. Для роз- в’язання аналогічних задач в теорії масового обслуговування розроблено багато підходів [21]. Отже, задача розподілення мережі сервісних об’єктів полягає у визначенні такої їхньої кіль- кості на певній території (пошук такого k), за яких мінімізуються витрати на перевезення про- дукції і матеріалів (пошук перестановки i  ). При цьому необхідно визначити потужність майстерень, яку можна збалансувати з кількіс- тю ймовірних заявок. В результаті необхідно знайти такі k  , i  ,   , для яких * * ( , , )k iF     1 2min( ( , , ) ( , , ) ) k i k i k if f v v                     , де ),,(1  ikf – вартість перевезень матеріалів з центру до сервісних об’єктів, ),,(2  ikf – вартість перевезень приладів, які потребують ремонту, до сервісних об’єктів, vt – вартість матеріалу, çv – вартість витрат на зарплатню, енергію, технологічне устаткування тощо. Розв’язання задачі розподілення мережі сервісних об’єктів методом структурно-алфа- вітного пошуку Описані в літературі методи і алгоритми ґрунтуються на частковому переборі варіантів. Але існують підходи, які ґрунтуються на роз- пізнаванні структури вхідної інформації, на- приклад метод найближчого сусіда, «жадіб- ний» алгоритм тощо. До них належить і метод північно-західного кута. Ці методи і алгоритми ефективні за швидкодією, але розв’язок при цьому може бути далекий від оптимального. З цієї причини другому підходу в літературі до- статньої уваги не приділяють. Описаний далі метод структурно-алфавітного пошуку також ґрунтується на розпізнаванні структури вхідної інформації. Цей метод, з використанням знач- ної переваги за швидкодією, за структурою вхідних даних, дозволяє поліноміально знахо- дити аргумент, для якого цільова функція на- буває глобального або наближеного до нього розв’язання. Знаходження оптимального розв'язання в задачах комбінаторної оптимізації методом структурно-алфавітного пошуку проводиться за функціями натурального аргументу, упо- рядкованими за зростанням або спаданням значень. За розробленими правилами знахо- дять послідовність локальних екстремумів 1( ( ),F F w ..., ( ),..., ( ))k qF w F w таких, що ( ) glob extr ( ) k k k w W F w F w   , де extr {min, max} , Www kq , , * , , {1,..., !}k k q n , q – кіль- кість локальних екстремумів. Метод структурно-алфавітного пошуку ефек- тивний для задач, аргументом цільової функції в яких є перестановка, а також на підмножині ізоморфних комбінаторних конфігурацій, ос- кільки цільова функція на цих підмножинах змінюється так, як і на множині перестановок. В задачі розподілення мережі сервісних об’єк- тів цим методом знаходимо розв’язання на під- множині ізоморфних розбиттів n-елементної множини на підмножини для задачі кластери- зації і на перестановках в транспортній задачі. Оптимальне розв’язання для цієї задачі визна- чається на двох комбінаторних множинах: на множині розбиттів n -елементної множини на підмножини знаходять за однією обчислюва- льною схемою, а на множині перестановок – за іншою. Розглянемо 1 1( ( ) , )\| ( ( (1), ),k m kf j w f w    , ( ( ) , ))k m f m w H  – комбінаторну функ- цію, аргументом якої є комбінаторна конфігу- рація Wwk  , утворена з елементів базової множини },...,{ 1 nn aaA  , ' ' 1( ( ), ) \|i mf j w H  – комбінаторну функцію, аргументом якої є ком- бінаторна конфігурація '' Ww i  , утворена з елементів базової множини }~,...,~{ ~ 1 mm aaA  , H і 'H – відповідно системи цих функцій. Якщо 1 1( ( ), ) \| mf j w  '1 1( ( ), ) \| mf j w , а 1'1, ww – комбі- УСиМ, 2014, № 1 15 наторні конфігурації одного типу і 1 1( ( ), ) \| mf j w H  , '1 ' 1( ( ), ) \| mf j w H  , то 'HH і 'WW  . Задачу комбінаторної оптимізації, вхідні дані в якій задано функціями ( ( ),f j 1) \|k mw і 1( ) \| mj , назвемо базовою. Задачу, вхід- ні дані в якій задано функціями ' 1( ( ), ) \|i mf j w  (або ' 1( ( ), ) \|t mf j w  ), де '( ( ), ) ( ( 1),if j w f j     ' )iw ( або '( ( ), )tf j w   '( ( 1), )tf j w   ), та 1( ) \| mj  (або 1( ) \| mj  ), де )1()(  jj  (або )1()(  jj  ), утворених із 1( ( ), ) \|k mf j w і 1( ) \| mj , назвемо упорядкованою. Методом структурно-алфавітного пошуку за упорядкованими комбінаторною та числовою функціями за розробленими правилами, почи- наючи з найменших або найбільших значень з урахуванням структури вхідних даних і комбі- нації елементів у рядках і стовпцях заданої ма- триці, знаходимо локальний оптимум і для нього визначаємо підмножину комбінаторних конфігурацій, яка містить глобальне розв'язан- ня. Потім у знайденій підмножині за другим, третім і подальшими елементами варіанту роз- в'язання задачі знаходимо другий, третій і на- ступні локальні оптимуми, значення яких зме- ншуються або не змінюються. У кожній одер- жаній підмножині комбінаторних конфігурацій виділяються менші підмножини, які можуть містити глобальне розв'язання. Тим самим зву- жуються межі його пошуку. Пошук оптималь- ного розв'язання за цією схемою виконується так, як пошук слова у словнику. Доведення твердження, що за допомогою цього методу поліноміально знаходимо глобальний або бли- зький до глобального оптимум, проводиться з використанням підкласів розв'язних задач. Отже, методом структурно-алфавітного по- шуку розв’язуємо транспортну задачу на мно- жині перестановок і задачу кластеризації на підмножині ізоморфних розбиттів n-елемент- ної множини на підмножини. Оскільки на всій множині  з використанням функції (1) маємо ситуацію невизначеності, оптимальне розв’я- зання знаходимо самоналагоджувальним алго- ритмом [23]. Моделювання цільової функції в задачі збереження довкілля з використанням тео- рії комбінаторної оптимізації При моделюванні процесів, пов’язаних із збе- реженням довкілля розглядають наслідки впли- ву людської діяльності на природу. Цю задачу інколи відносять до антагоністичних ігор двох учасників з прямо протилежними інтересами і називають іграми проти природи [28]. Задача полягає в тому, що при переході від однієї си- туації до іншої з збільшенням (зменшенням) виграшу одного з гравців чисельно однаково зменшується (збільшується) виграш другого гравця. Їх ще називають іграми двох осіб з ну- льовою ставкою. Розумна поведінка гравців здійснюється на підставі принципу максиміну. Далі наведемо математичну постановку задачі збереження довкілля, розроблену з використан- ням теорії комбінаторної оптимізації [29]. Задачу збереження довкілля розглянемо як гру двох гравців:  мораль суспільства,  збагачення суспільства (зокрема збагачен- ня його правлячої верстви). Вважатимемо, що рівень моралі та спосіб збагачення суспільства – критерії, за якими оп- тимізується цільова функція. Під цією функці- єю розумітимемо таке її числове значення, яке визначає рівень здоров’я довкілля, людини і суспільства загалом. Задача полягає у знахо- дженні між цими критеріями такої рівноваги, щоб суспільство і природа співіснували ком- фортно. Як відомо, на певному етапі збагачен- ня суспільства його мораль починає знижува- тися. Наступає момент, коли заради збагачення нехтують законами природи, відповідно і за- конами моралі, що призводить до руйнації су- спільства загалом, втрачаються всі накопичені матеріальні цінності. В літературі аналогічну ситуацію названо «трагедией общин» [30, 31]. Введемо множини A = (a1, , an), кожен еле- мент aj, j  (1, , n) якої відповідає ознакам, які характеризують рівень моралі суспільства; },...,{ 1 nbbB  , кожен елемент jb якої визначає числову оцінку рівня моралі суспільства; 1( ,..., )nA a a   , кожен елемент la~ , ),...,1{ nl , від- 16 УСиМ, 2014, № 1 повідає ознакам, які характеризують способи збагачення суспільства; 1{ ,..., }nB b b   , кожен елемент якої lb ~ визначає числову оцінку спо- собу збагачення суспільства. Отже, задача збереження довкілля задається двома множинами A і A ~ , між елементами яких відсутні зв’язки. Вхідними даними є скінчен- ні послідовності },...,{ 1 nbbB  і 1{ ,..., }nB b b   . Ця задача належить до другого типу. Змоделюємо цільову функцію і визначимо її аргумент. Вважатимемо, що кожному елементу bj мно- жини B відповідає елемент jb ~ з множини B ~ і , { 1,...,0,...,1}j jb b   , jj bb ~ , – дійсні числа. Якщо добробут суспільства забезпечує гармо- нійний його розвиток і не шкодить природі, то ці величини додатні і jj bb ~ , , jj bb ~  , 0 – мінімальне значення, коли можлива розумна поведінка гравців. Якщо },...,~{ ~ , jj bb , де 0~  – найбільше значення, за якого не руй- нується природа, то маємо антагоністичну гру двох учасників з протилежними інтересами. Якщо  ~~ , jj bb , тоді руйнується мораль суспіль- ства, знищується природа, втрачаються всі на- копичені матеріальні цінності. Тобто, виникає ситуація, коли виграє один гравець (який зба- гачується), але в результаті програють обидва. В процесі розв’язання задачі з кожної мно- жини ),...,( 1 naaA  і 1( ,..., )nA a a   вибиранням певної кількості елементів утворюються сполу- чення без повторення, що є аргументом цільо- вої функції. З елементів множин ),...,( 1 naaA  і 1( ,..., )nA a a   утворимо дві комбінаторні мно- жини W і W ~ . На цих множинах уведемо ці- льову функцію )~,( wwF , де Ww і Ww ~~ – сполучення без повторень. Задача полягає в пошуку таких Ww * і * ,w W  для яких уве- дена цільова функція )~,( wwF набуває макси- мального значення за умови, що )~,( ** wwF , де  – мінімальна величина, за якої природа і суспільство існують комфортно, добробут сус- пільства використовується на його розвиток і не руйнується довкілля. Змоделюємо вхідні дані функціями нату- рального аргументу 1( ) \| nj , 1( ) \| nj та ком- бінаторними функціями 1( ( ), , ) \|k i nf j w w  і 1( f ( ) , , )\|k i nl w w   . Якщо з множини A вибрати елемент ja , то ( ( ) , , ) 1k i j f j w w  . В іншому разі ( ( ), , ) 0k i j f j w w  . Відповідно, якщо з множини A ~ вибрати елемент la~ , то ( ( ),l f l  , ) 1k iw w  . В іншому разі ( ( ) , ,k l f l w  ) 0iw  . Оскільки поставлена задача розв’язується на двох комбінаторних множинах, то функції 1( ( ), , ) \|k i nf j w w  і 1( ( ) , , )\|k i nf l w w   залежать від двох змінних: Ww і Ww ~~ . Цільова функція в цій задачі оптимізується за двома критеріями, які змоделюємо як серед- ню величину сумарного добутку значень фун- кції натурального аргументу та комбінаторної функції: ' n j ik j ik q jwwjf wwF     1)1( )()~,,)(( )~,( і '' 1)2( )(~)~,,)( ~ ( ~ )~,( q jwwjf wwF n j ik j ik     , а    2 1 )( )~,()~,( t iktik wwFwwF ; де 'q – кількість одиниць в nik wwjf 1\|)~,,)(( , ''q – кількість одиниць в 1( ( ), , ) \|k i nf l w w   . Множини W і W ~ складаються з підмножин ізоморфних сполучень без повторень. Оскільки пошук оптимального розв’язання проводиться на всіх їхніх елементах, то в процесі роз- в’язання задачі з використанням виразів )~,()1( ik wwF і )~,()2( ik wwF може виникнути си- туація невизначеності, пов’язана зі структурою аргументу цільової функції [32]. Тому задача полягає в знаходженні такої підмножини ізо- морфних сполучень без повторень, яка містить УСиМ, 2014, № 1 17 оптимальний розв’язок, що збігається з метою дослідження за умови )~,( ik wwF . Отже, якщо значення цільової функції дорі- внює двом або не менше за величину  , то природа і суспільство існують комфортно, до- бробут суспільства використовується на його розвиток. В іншому разі руйнується мораль суспільства, знищується природа. Цільова фу- нкція в задачі збереження довкілля залежить від двох змінних, якими є сполучення без по- вторень. На відміну від інших задач комбіна- торної оптимізації, які за цією ознакою розді- ляються на підзадачі з послідовним розв’язан- ням, розв’язання цієї задачі знайдемо одночас- но на двох комбінаторних множинах. Висновки. Cистемний аналіз прикладних за- дач з використанням теорії комбінаторної оп- тимізації дозволяє вивчати властивості геороз- поділених динамічних систем на загальному рівні, виявляти задачі оптимізації комбінатор- ного типу, будувати математичні моделі та на основі останніх розробляти ефективні алгори- тми для їх розв’язання. Так, задача розподілен- ня мережі сервісних об’єктів розділяється на три підзадачі: задачу кластеризації, аргумен- том цільової функції в якій є розбиття n-еле- ментної множини на підмножини; транспортну задачу, аргументом цільової функції в якій є перестановка, і задачу з теорії масового обслу- говування. Ця задача потребує для розв’язання розроблення гібридних алгоритмів. В процесі розв’язання підзадачі кластеризації та визна- чення потужності сервісних об’єктів виникає ситуація невизначеності. Для її вирішення не- обхідно розробляти самоналагоджувальні ал- горитми, що характерно для проектування сис- тем обчислювального інтелекту. 1. Размещение отраслей народного хозяйства СССР / Под ред. А.Д. Данилова, Г.И. Мухина – М.: Гос- планиздат, 1960 – 331 с. 2. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимиза- ционные задачи производственно-транспортного пла- нирования. – М.: Наука, 1986. – 264 с. 3. Геопространственные производственные системы. Ч. 1. Анализ, моделирование, проектирование / В.М. Ілюшко, О.Э. Федорович, О.Н. Замирец и др. – Харьков: ХАИ, 2011. – 249 с. 4. Греков Л.Д. Методологічні основи створення гео- розподілених виробничих систем: Автореф. дис. ... д-ра техн. наук. – Харків, 2012. – 37 с. 5. Гриценко В.И., Панченко А.А., Лапа А.П. Проблем- но-ориентированное моделирование производствен- но-транспортных систем. – Киев: Наук. думка, 1987. – 158 с. 6. Зайдельман Ф.Р. Мелиорация почв. – М.: Изд-во МГУ, 2003. – 448 с. 7. Поливода О.В., Рудакова А.В. Методы оперативно- го управления влагообеспечением в ирригацион- ных системах с прогнозирующей моделью // Sys- tem Analysis and Inform. Technol., 15-th Inter. Conf. SAIT 2013, Kyiv, Ukraine, May 27–31, 2013. Proc. Inst. for Applied System Analysis of National Techn. Univ. of Ukraine «KPI» – Kyiv, Ukraine. 2013. – P. 165. 8. Бардась О.О. Використання експертних систем при прогнозуванні прибуття поїздів на станцію // Матем. та прогр. забезпеч. інтел. систем (MPZIS–2012). X Ювілейна Міжнар. наук.-практ. конф. Тези доп. 21–23 лист. 2012 р. Дніпропетровськ. Дніпропет- ровськ. ун-т ім. Олеся Гончара. 2012. – С. 20–21. 9. Агеев А.А., Гимарди Э.Х., Курочкин А.А. Полино- миальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощ- ностями предприятий // Дискет. анализ и исслед. операций. – 2009. – Т. 16, № 5. – С. 3–16. 10. Береснев В.Л., Мельников А.А. Приближенные ал- горитмы для задачи конкурентного размещения пред- приятий // Там же. – 2010. – Т. 17, № 6. – С. 3–19. 11. Васильев И.Л., Климентова К.Б. Метод ветвей и от- сечений для задачи размещения с предпочтениями клиентов // Там же. – 2009. – Т. 16, № 2. – С. 21–41. 12. Горбачевская Л.Е. Полиномиально разрешимые и NP-трудные двухуровневые задачи стандартиза- ции: Автореф. дис. ... канд. физ.-мат. наук. – Новосибирск. – 2007. – 18 с. 13. Федорович О.Е., Греков Л.Д., Западня К.О. Опти- мизация размещения геораспределенной производ- ственной системы на земной поверхности // Радіо- електронні і комп’ютерні системи. – 2011. – № 2 (50). – C. 107–111. 14. Baumrucker B.T., Biegler L.T. MPEC strategies for cost optimization of pipeline operations / Comput. and Chem. Eng. – 2010. – 34, № 6. – Р. 900–913. 15. Godinho Pedro, Dias Joana. A two-player competitive discrete location model with simultaneous decisions / Eur. J. Oper. Res. – 2010.– 207, № 3. – Р. 1419–1432. 16. Атаян Н.Х. Макроэкономическая концептуальная оценка эффективного развития российского нефте- газового комплекса и моделирование синергетики межгосударственной и межрегиональной мэзоор- ганизации // Управление и высокие технологии – 2008. – № 3 – С. 19–26. 18 УСиМ, 2014, № 1 17. Оpешин А.Н., Тукелев А.В. Методика оптимизации организации контроля технического состояния об- ъектов телекоммуникаций // Телекоммуникации. – 2006. – № 8. – С. 2–5. 18. Занчева Ф.Н. Применение аппроксимационно-ком- бинаторного метода для решения задачи размеще- ния складов (с учетом потерь) с ограниченными объектами. // Оптимизация и моделирование слож- ных систем: Сб. науч. тр. – Алма-Ата, 1976. – С. 3–6. 19. Гимарди Э.Х., Курочкин А.А. Эффективный алго- ритм решения двухэтапной задачи размещения на древовидной сети // Дискретный анализ и исследо- вание операций. – 2012. – Т. 19, № 6. – С. 9–22. 20. Петров Э.Г., Писклакова В.П., Бескоровайный В.В. Территориально-распределенные системы обслу- живания. – К.: Техника, 1992. – 208 с. 21. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1987. – 336 с. 22. Тимофієва Н.К. Теоретико-числові методи розв'я- зання задач комбінаторної оптимізації: Автореф. дис... докт. техн. наук. – Київ. – 2007. – 32 с. 23. Тимофеева Н.К. О природе неопределенности и переменных критериях в задачах разбиения // Про- блемы управления и информатики. – 2009. – № 5. – С. 88–99. 24. Monge G. Mémoire sur la théorie des déblais et des remblais // Histoire de l'Académie Royale des Sciences, Année M. DCCLXXXI, avec les Mémoires de Mathé- matique et de Physique, pour la même Année, Tirés des Registres de cette Académie. – Paris, 1781. – P. 666–704. 25. Данциг Д.Б. Линейное программирование, его приме- нения и обобщения. – М.: Прогресс, 1966. – 600 с. 26. Канторович Л.В., Гавурин М.К. Применение мате- матических методов в вопросах анализа грузопо- токов // Проблемы повышения эффективности работы транспорта. – М.: Изд-во АН СССР, 1949. – С. 110–138. 27. Пападимитриу Х., Стайглиц К. Комбинаторная опти- мизация. Алгоритмы и сложность. – М.: Мир, 1985. – 510 с. 28. Воробьев Н.Н. Основы теории игр. Бескоалицион- ные игры. – М.: ФИЗМАТЛИТ, 1984. – 496 с. 29. Тимофієва Н.К. Моделювання цільової функції в задачі збереження навколишнього середовища з використанням теорії комбінаторної оптимізації // «Автоматика–2012»: Матеріали XIX міжнар. конф. з автоматичного управління, 26–28 верес. 2012 р. – Київ, Україна. – К.: НУХТ, 2012. – С. 65–66. 30. Hardin G. The Tragedy of the Commons // Science. – 1968. – 162, N 3859. – P. 1243-1248. 31. Рыжкова М.В., Иваненкова Е.Д. Эксперименталь- ная проверка «Трагедии общин» // Современ. пробл. науки и образов. – 2013. – № 2. – www.science- education.ru/108-8820 32. Тимофієва Н.К. Про розв’язання задач комбінатор- ної оптимізації в умовах невизначеності // Вісн. Вінницьк. політехн. ін-ту. 2012 – № 6. – С. 157–162. Поступила 25.11.2013 Тел. для справок: (044) 502-6365 (Киев) E-mail: tymnad@gmail.com © Н.К. Тимофеева, В.И. Гриценко, 2014  Н.К. Тимофеева, В.И. Гриценко Моделирование и решение прикладных задач комбинаторной оптимизации, возникающих в интеллектуальных геораспределенных динамических системах Введение. Одной из основных составляющих современ- ной экономики есть такие промышленные комплексы, как транспортные и телекоммуникационные сети, системы нефте- и газодобычи, распределенные сервисные объек- ты на определенной территории, оросительные системы и др. [1–20]. Им для работы необходимы разработки мно- гоуровневых распределенных компьютерных систем уп- равления. Такие комплексы называют геораспределен- ными производственными системами. В процессе их про- ектирования и эксплуатации необходимо решать много проблем, связанных с наличием земельного ресурса для расположения технологических объектов и инженерных сооружений, оптимальным размещением этих объектов на определенной территории, решать проблемы эконо- мического характера, необходимо учитывать и экологи- ческое состояние окружающей среды, а также прини- мать оптимальное решение в условиях неопределенно- сти разной природы и прогнозировать поведение систе- мы во времени. Для решения ситуации неопределенно- сти используют разные подходы, в частности и способы, связанные с вычислительным интеллектом. Поскольку геораспределенные системы получают ре- сурсы из окружающей среды, то они есть открытой ди- намической структурой. Как правило, в них рассматри- ваются динамические задачи, которые относятся к уп- равленческим проблемам. К тому же, прикладные за- дачи оптимизации, которые сводятся к задачам комби- наторной оптимизации, могут быть как статическими так и динамическими. Интеллектуальными геораспределенными динамиче- скими системами назовем производственные, или сер- висные промышленные комплексы, которые распределе- ны на определенной территории, имеют координаты и управляются как централизованно, так и в автономном режиме с помощью распределенных компьютерных сис- УСиМ, 2014, № 1 19 тем управления и есть открытыми динамическими струк- турами. Для разработки и эксплуатации они нуждаются в разнообразных подходах, в частности и способах, свя- занных с вычислительным интеллектом. При размеще- нии новых производственных комплексов можно ис- пользовать существующие ресурсы (транспортные сети, телекоммуникации и др.). Среди них выделим:  магистральные производственные комплексы (же- лезные и автомобильные дороги, нефте- и газодобычу);  сервисные объекты, размещенные на определенной территории и использующие существующие транспорт- ные и другие ресурсы. Это – ремонтные мастерские, банки, сеть аптек и магазинов и др.;  авиаперевозки, в которых используются как зе- мельные ресурсы, так и воздушное пространство;  телекоммуникационные сети, которым для переда- чи информации необходимы земельные ресурсоы, про- кладки каналов связи под землей и под водой, воздуш- ное пространство и телекоммуникационные космичес- кие системы;  оросительные системы, занимающие определенную территорию и требуют размещения на ней датчиков для сбора текущей информации о состоянии почвы. Разработка и эксплуатация интеллектуальных гео- распределенных динамических систем требует решения проблем оптимизации, среди которых выделим такие:  решение ряда оптимизационных задач, которые сводятся к задачам комбинаторной оптимизации;  оптимальное использование земельных ресурсов;  разработку баз знаний и интеллектуализацию сис- тем управления для принятия решений в условиях неоп- ределенности;  разработку способов прогнозирования работы гео- распределенных динамических систем;  оптимизацию затрат на разработку и эксплуатацию геораспределенных динамических систем;  оптимальное решение экологической проблемы. Далее рассмотрим задачи оптимизации, возникающие при разработке и эксплуатации геораспределенных дина- мических систем и сводимые к задачам комбинаторной оптимизации. Разные классы задач нуждаются в специ- альных подходах к решению. Построение математиче- ских моделей прикладных задач в рамках теории комби- наторной оптимизации позволяет выявить их характер- ные свойства, сформулировать для них адекватную ма- тематическую постановку, которая упростит разработку новых или использование известных алгоритмов для эф- фективного решения. Общая характеристика задачи распределения се- ти сервисных объектов Проблема размещения предприятий, к которой отно- сится задача распределения сети сервисных объектов на определенной территории, исследована достаточно осно- вательно [2, 9–15, 18, 19]. Математические модели этих задач разрабатывались и разрабатываются в рамках це- лочисленного линейного программирования. Построен- ные модели имеют свойства, характерные для транс- портной задачи и ее обобщения, поэтому их иногда сво- дят к этой задаче. Некоторые из них моделируются в рамках теории массового обслуживания [5, 21]. Для ре- шения задачи оптимального размещения предприятий используются методы декомпозиции, универсальные и специальные методы математического программирова- ния как точные, так и приближенные [2, 9–11, 19]. По- скольку в задаче размещения предприятий имеется пе- ребор вариантов, то она относится к задачам комбина- торной оптимизации. В [18] описан способ решения за- дачи размещения складов, в котором использован аппрок- симационно-комбинаторный подход. В [3, 19] для моде- лирования задачи размещения предприятий используют теорию графов, а в [4] – перечислительную комбинато- рику, при использовании которой определяют количе- ство вариантов их размещения. Но при решении прик- ладных задач этого класса необходимо найти не количе- ство вариантов, а смоделировать целевую функцию и оп- ределить ее аргумент (комбинаторную конфигурацию), для которого она принимает оптимальное значение. Следовательно, задача распределения сети сервис- ных объектов на определенной территории заключается в нахождении такого их оптимального количества, при котором все потенциальные заказчики, которые отно- сятся к этой территории, могли бы воспользоваться ус- лугами таких объектов при условии минимального рас- стояния между ними и минимальными затратами на об- служивание, например ремонт приборов. Для миними- зации затрат на перевозку и ремонт необходимо постро- ить математическую модель «заказчик–исполнитель», в которой основным условием может быть уменьшение расстояния от заказчика к исполнителю, что влияет на снижение цены на услуги. В задаче распределения сети сервисных объектов вы- делим такие варианты:  количество заказчиков и количество сервисных объ- ектов известно;  количество заказчиков и количество сервисных объ- ектов неизвестно;  количество заказчиков известно, а количество сер- висных объектов необходимо определить;  количество заказчиков неизвестно, а количество сервисных объектов известно. В литературе описаны задачи размещения предпри- ятий, в которых их количество заранее задано и извест- на территория для их расположения [2, 18]. В условиях конкуренции размещение предприятий проводится в динамическом режиме. Рядом может быть размещено несколько однотипных обслуживающих центров [10, 11]. В [15] задача размещения обслуживающих центров рассматривается как игра двух игроков. Приведем общую постановку задачи комбинаторной оптимизации и сформулируем ее [22]. Задачи этого клас- са, как правило, задаются одним или несколькими мно- 20 УСиМ, 2014, № 1 жествами, например А и В, элементы которых имеют любую природу. Назовем эти множества базовыми. Имеются два типа задач. В первом типе каждое из этих множеств можно подать в виде графа, вершинами кото- рого есть его элементы, а каждому ребру поставим в со- ответствие число ltc R , которое называют весом ребра (R – множество вещественных чисел); {1,..., }l n , {1 ,..., }t n  , n – количество элементов множества A, n – количество элементов множества B. Положим, что n n  . Между элементами этих множеств существуют связи, числовое значение которых назовем весами. Ве- личины ltc назовем входными данными и зададим их мат- рицами. Во втором типе задач между элементами за- данного множества связей не существует, а весами есть числа jv R , {1,..., }j n , которым в соответствие по- ставлены некоторые свойства этих элементов, числовые значения которых задаются конечными последователь- ностями, которые также – входные данные. Эти величи- ны определяют значение целевой функции. Для обоих типов задач из элементов одной или не- скольких заданных множеств, например la A , {1,...l ..., },n образуется комбинаторное множество W – сово- купность комбинаторных конфигураций определенного типа (перестановки, выборки разных типов, разбиния и пр.). На элементах w комбинаторного множества W вво- дится целевая функция F(w). Необходимо найти элемент w множества W, для которого F(w) принимает экстре- мальное значение при выполнении заданных ограниче- ний, т.е. функционал 0 ( ) glob extr ( ) w W W F w F w    , где extr {min, max} , 0W – подмножество, определяемое ограничениями задачи. Выделим задачи по способу вычисления целевой функ- ции, в которых для определенного варианта решения ее значение вычисляется одновременно. Такие задачи на- зовем статическими. Задачи, в которых в процессе ре- шения генерируется текущая информация, по которой оценивается результат, а поиск оптимального решения проводится поэтапно с вычислением частичных сумм целевой функции, назовем динамическими. Смоделируем входные данные задачи комбинаторной оптимизации первого типа конечными последовательно- стями. Представим элементы h наддиагоналей симметрич- ной комбинаторной матрицей ( )kQ w комбинаторной функцией 1 1( ( ), )\| ( ( (1), ),..., ( ( ), ))k m k k mf j w f w f m w    , а элементы h наддиагоналей симметричной матрицей c – функцией натурального аргумента 1( )\| ( (1), ..., ( ))mj m    , где ( 1) 2 n n m   – количество элементов h наддиаго- налей матриц C и ( )kQ w , 1, 1h n  . Верхний индекс k ( {1,..., }k q ) в kw – порядковый номер kw в W. Если матрицы ( )kQ w и C – несимметричные, то 1( ( ), )\|k mf j w и 1( )\|mj содержат все их элементы, а 2m n (или m n n  ). Функция цели ( )kF w примет вид 1 ( ) ( ( ) , ) ( ) m k k j j F w f j w j     . (1) Построение математических моделей задач комбина- торной оптимизации, как правило, проводится с исполь- зованием задачи целочисленного линейного программи- рования, которая формулируется в таком виде. Найти экстремум функции 1 n l l l c x    при условиях s 1 n sl l l a x b    , 1,s p , 0lx  , 1,l n , lx – целые для 1,l p , p n , , ,l sl sc a b  – заданные целые числа, lx – переменные. Ис- ходя из этой модели, считаем, что целевая функция в комбинаторной оптимизации зависит от многих пере- менных, а lx – элементы комбинаторной конфигурации 1( ,..., )nw w w и перемножаются на заданные числа ,l slc a  . Но это невозможно, поскольку wl могут иметь любую природу. Переменные lx не являются элемента- ми w, а модель целочисленного линейного программи- рования не отражает сути задач комбинаторной оптими- зации. Целочисленное линейное программирование раз- рабатывалось для экономических задач, относящихся ко второму типу, для которых математическая постановка формулируется так: задано одно множество A, элементы la A которого не имеют между собой связей. Зато каж- дый элемент la A , {1,..., }l n , характеризуется опре- деленным свойством (весом) lx . Аргументом целевой функции в них, как правило, есть выборки (сочетания, размещения), а входные данные – последовательность значений весов 1,..., nx x элементов la заданного множе- ства A, количество которых совпадает с количеством элементов w. Отсюда утверждение, что аргументом це- левой функции в этих задачах есть последовательность входных данных 1,..., nx x , а не комбинаторная конфигу- рация 1( ,..., )nw w w . Соответственно считают, что це- левая функция в задачах комбинаторной оптимизации зависит от многих переменных. Последовательность x1, , xn – входные данные опре- деленной задачи, а значение xl неявно зависит от комби- наторной конфигурации w, т.е. выражение 1 n l l l c x    необ- ходимо записать так: F(w) 1 ( ) n l l l c x w     . Тогда возникает проблема определения этой зависимости в задачах ком- бинаторной оптимизации, для чего необходимо разраба- тывать их математические постановки с учетом комби- наторной природы. К тому же при использовании целе- УСиМ, 2014, № 1 21 вой функции ( )F w 1 ( ) n l l l c x w     на комбинаторных мно- жествах, состоящих из подмножеств изоморфных ком- бинаторных конфигураций, возникает ситуация неопре- деленности [23]. Для моделирования прикладных задач в рамках тео- рии комбинаторной оптимизации необходимо:  по способу вычисления целевой функции опреде- лить вид задачи (статическая или динамическая);  определить базовые множества, которыми задается определенная задача;  по входным данным определить ее тип;  определить аргумент целевой функции (комбина- торную конфигурацию);  смоделировать целевую функцию. Уточним такие понятия, как критерий и целевая функция. Критерий – признаки или свойства, характеризую- щие определенный объект или связи между объектами и служат входными данными. Целевая функция – выражение, формулируемое на основе заданных критериев с учетом особенностей зада- чи, по которым вычисляется и оценивается результат ее решения. Как правило, целевую функцию отождествляют с критериями, а в качестве ее аргумента принимают вход- ные данные. Но для одних и тех же критериев целевую функцию можно смоделировать по-разному, т.е. оценка проводится по разным выражениям и дает разный ре- зультат. Ее аргументы – комбинаторные конфигурации разных типов (перестановки, сочетания, разбиение n- элементного множества на подмножества и др.). К тому же она может зависеть как от одной переменной, так и от многих (комбинаторных конфигураций). По этому признаку задачи комбинаторной оптимизации разделя- ются на подзадачи. Учитывая сказанное, смоделируем задачу распреде- ления сети сервисных объектов на определенной терри- тории как задачу комбинаторной оптимизации. Построение математической модели задачи рас- пределения сети сервисных объектов с использова- нием теории комбинаторной оптимизации Построим математическую модель распределения сети сервисных объектов при условии, что их количе- ство заранее неизвестно, зато известно количество за- казчиков и их местонахождение. Модель должна учиты- вать транспортные расходы и распределение заказов между сервисными объектами. Положим, что поставка материала проводится как централизованно из одного центра, так и из распределенных пунктов снабжения. Моделирование задачи распределения сервисных объ- ектов на определенной территории с использованием те- ории комбинаторной оптимизации показывает, что она разделяется на несколько подзадач: задачу кластериза- ции, транспортную задачу и задачу по теории массового обслуживания. Рассмотрим эти подзадачи. Задача кластеризации. Для определения количества сервисных объектов необходимо исходить из количе- ства всех известных заказчиков на определенной терри- тории, которые обозначим множеством 1{ ,..., }nA a a . В результате решения задачи кластеризации количе- ство сервисных объектов будет равно количеству полу- ченных кластеров. Сформулируем математическую по- становку этой задачи, входными данными в которой бу- дут расстояния между заказчиками. Аргументом целе- вой функции в ней есть разбиение n-элементного мно- жества на подмножество, которое обозначим k  , где  – множество разбиений. Эта задача задается одним множеством 1{ ,..., }nA a a . Числовые значения связей между элементами ,l ta a A (входные данные), которыми служат расстояния меж- ду заказчиками, представим симметричной матрицей l t n nC c  (или функцией 1( )\| mj ). Для задання рас- пределения элементов множества 1{ ,..., }nA a a между подмножествами (кластерами) k s фиксированного раз- биения k  введем симметричную комбинаторную (0,1)-матрицу распределения ( ) ( )k k lt n n Q g     (или функцию ( ( ) ,f j 1) \|k m ). Если ( ( ) , ) 1kf j   (или ( ) 1k lsg   ), то элементы t,la a A находятся в одном кластере. Иначе ( ( ) , ) 0kf j   . Задача кластеризации заключается в поиске такого разбиения k  на непе- ресекаемые кластеры, для которого целевая функция (1) принимает максимальное значение. Поскольку нахождение оптимального решения прово- дится на всем множестве разбиений, то при использовании для оценки результата целевой функции (1) возникает ситуация неопределенности, т.е. для определенного упо- рядочения подмножеств изоморфных разбиений зако- номерность изменения значений выражения (1) изменя- ется одинаково независимо от входных данных. Для выхода из этой ситуации необходимо ввести дополни- тельные целевые функции, критерии или ограничения. Математическая постановка транспортной задачи как задачи комбинаторной оптимизации. Для оптими- зации перевозок необходимо решить транспортную за- дачу как внутри образованных кластеров, так и между кластерами. Это – вторая подзадача, аргументом целе- вой функции в которой будет перестановка i  , где  – множество перестановок. При этом необходимо учитывать в зависимости от расстояния стоимость пере- возок материалов от центрального поставщика и прибо- ров, требующих ремонта, к этим объектам (например, ремонтных мастерских). 22 УСиМ, 2014, № 1 Транспортная задача формализирована еще в 1781 г. [24]. Как проблема линейного программирования она впервые рассмотрена в работе [25], поэтому эту задачу рассматривают как задачу линейного программирования специального вида и она есть подмножеством задач ли- нейного программирования. Для решения транспортной задачи используют симплекс-метод, метод одновремен- ного решения прямой и двойственной задачи, метод потенциалов, венгерский метод, динамическое про- граммирование, метаэвристические подходы [2, 26, 27]. Эту задачу сводят еще к задаче коммивояжера или к за- даче о ранце. Для поиска начального решения исполь- зуют метод северо-западного угла, метод минималь- ных тарифов, а для окончательной оптимизации – ме- тод потенциалов. Задача о назначениях – это частный случай классической транспортной задачи [27]. Зада- ча о назначениях полиномиально решается венгер- ским алгоритмом. Сформулируем однокритериальную транспортную задачу закрытого вида, в которой оптимизируется стои- мость перевозки, как задачу комбинаторной оптимиза- ции. Она задается двумя множествами A и B, где эле- менты la A , сооответствуют продукции, которую не- обходимо перевезти, а bt  B – продукцию, которая по- требляется заданным объектом. Между элементами этих множеств определены связи, ltc R – числовое их зна- чение (веса). Величины clt (входные данные) зададим несимметричной матрицей. Из элементов одного из заданных множеств, например la A , {1,..., }l n , образуем комбинаторное множество  – совокупность комбинаторных конфигураций опре- деленного типа (в данном случае это – перестановки). На элементах  комбинаторного множества  введем целевую функцию F (). Необходимо найти элемент  множества, для которого F () принимает экстремальное значение при выполнении заданных ограничений. Для решения транспортной задачи методом струк- турно-алфавитного поиска [22] сведем ее к задаче о на- значениях. Множество 1{ ,..., }nA a a представим мно- жеством 1 * 1 * ' ' ' ' ' 1 1{ ,..., ,..., ,..., } s s n nA a a a a , где элемент ' la  определяет наименьшую часть продукции от общей la A , которая в любой комбинации с другими ' rl a полностью удовлетворяет спросу любого пункта tb B , т.е. условно примем, что ' 1 rl a  , 1, { ,..., } s r l l  , а 1 ' ' 1 11 1 ,...,s s n n na a a a       , где l  – количество эле- ментов ' la  в la A . Аналогично множество B = {b1,  ..., }nb представим упорядоченным множеством 1 ' ' 1{ ,...B b 1 ' ' ' 1..., ,..., ,..., } p pn nb b b  , где элемент ' tb  , 1{ ,..., }ps s , равен одной единице продукции от общей tb B , а 1 ' ' 1 11 1 ,...,p pn n nb b b b       , где ps – количество эле- ментов ' tb  в tb B . Стоимость перевозок в транспортной задаче задается несимметричной комбинаторной матрицей ( )kQ  (ком- бинаторная функция 1( ( ) , ) \|k mf j  ), а для k -го вари- анта решения задачи введем (0,1)-матрицу C (функция 1( ) \|mj ). Ее элемент ' 1l tc    , если из la выбирается единица продукции ' l la a A    и перевозится в пункт потребления, которому необходимо ' t tb b B    единиц. В другом случае ' 0l tc    , т.е. одному элементу продук- ции из 'A соответствует один пункт потребления из 'B . Решение этой задачи находится на множестве переста- новок, причем проводится транспозиция или столбцов, или строк матрицы ( )kQ w . Целевая функция сводится к выражению 1 ( ) ( ( ), ) ( ) mk k jj F f j j       . Аналогич- но формулируется задача о назначениях, которая также задается на двух множествах: 1{ ,..., }nA a a , где la A отвечает l-му претенденту, и 1{ ,..., }nB b b  , где tb B соответствует t-й должности. Между элементами la A и tb B определены связи. Таким образом транспорт- ная задача сводится к задаче о назначениях. Задача по теории массового обслуживания. Третья подзадача основной задачи, относится к теории массового обслуживания и заключается в определении мощности сервисных объектов (ремонтных мастерских) в зависи- мости от заявок, поступающих от заказчика. Обозначим подмножеством 1{ ,..., }t t t tZ z z   заявки, поступающие в t-ю мастерскую от t заказчиков, а 1{ ,..., }t t t t r r r z z z     – за- явки от r-го заказчика в t-ю мастерскую, где t rz  – одна за- явка, t – их количество {1,..., }t   . Поскольку t – ве- личина случайная, то возникает ситуация неопределенно- сти. Положим, что ' ' ' ' 1{ ,..., }t t t t r r r z z z    tZ – наибольшее количество заявок, которое может поступить в t-ю мас- терскую от r-го заказчика. Тогда необходимо определить такое сочетание без повторений   элементов 't rz  из множества Zt, при котором мощность мастерской бы- ла бы сбалансирована, т.е. 1 1 ( ) t t t r r             , где ( )t   – мощность t-й мастерской, r – количество заявок от r-го заказчика, которые поступили в t-ю мастерскую, M – множество сочетаний без повторений. Для решения ана- логичных задач в теории массового обслуживания раз- работано много подходов [21]. Следовательно, задача распределения сети сервисных объектов заключается в определении такого их количе- УСиМ, 2014, № 1 23 ства на определенной территории (поиск такого k ), при которых минимизируются затраты на перевозку продук- ции и материалов (нахождение перестановки i  ). При этом необходимо определить мощность мастер- ских, которая может быть сбалансирована с количе- ством возможных заявок. В результате необходимо найти такие k  , i  ,   , для которых * * 1 2( , , ) min( ( , , ) ( , , ) ) k i k i k i k iF f f v v                         , где 1( , , )k if    – стоимость перевозок материалов из центра к сервисным объектам, 2 ( , , )k if    – стоимость перевозок приборов, требующих ремонта, к сервисным объектам, v – стоимость материала, v – стоимость за- трат на зарплату, энергию, технологическое оборудова- ние и пр. Решение задачи распределения сети сервисных объектов методом структурно-алфавитного поиска Описанные в литературе методы и алгоритмы осно- ваны на частичном переборе вариантов. Но существуют подходы, базирующиеся на распознавании структуры входной информации, например метод ближайшего со- седа, «жадный» алгоритм и др. К ним относится и метод северо-западного угла. Эти методы и алгоритмы эффек- тивны по быстродействию, но результат решения при этом может быть далек от оптимального. По этой при- чине второму подходу в литературе достаточного вни- мания не уделяют. Далее описан метод структурно-ал- фавитного поиска, который также базируется на распо- знавании структуры входной информации. Этот метод при использовании значительного преимущества по бы- стродействию по структуре входных данных позволяет полиномиально находить аргумент, для которого целе- вая функция принимает глобальное или приближенное к нему решение. Нахождение оптимального решения в задачах ком- бинаторной оптимизации методом структурно-алфавит- ного поиска проводится по функциям натурального ар- гумента, упорядоченным по возрастанию или убыванию их значений. По разработанным правилам находится по- следовательность локальных экстремумов 1( ( ),F F w  *..., ( ),..., ( ))k qF w F w таких, что ( ) glob extr ( ) k k k w W F w F w   , где extr {min, max} , * ,q kw w W , , , {1..., !}k k q n , q – количество локальных экстремумов. Метод структурно-алфавитного поиска эффективен для задач, аргументом целевой функции в которых есть перестановка, а также на подмножестве изоморфных ком- бинаторных конфигураций, поскольку целевая функция на этих подмножествах изменяется так же, как и на мно- жестве перестановок. В задаче распределения сети сер- висных объектов этим методом находим решение на подмножестве изоморфных разбиений n-элементного множества на подмножества для задачи кластеризации и на перестановках в транспортной задаче. Оптимальное решение для этой задачи определяется на двух комбина- торных множествах: на множестве разбиений n-элемент- ного множества на подмножества находимя по одной вычислительной схеме, а на множестве перестановок – по другой. Рассмотрим 1 1( ( ), )\| ( ( (1) , ), ..., ( ( ),k m k mf j w f w f m    ))kw H – комбинаторную функцию, аргумент которой – комбинаторная конфигурация kw W , образованная из элементов базового множества 1{ ,...nA a ..., }na , ' ' 1( ( ) , )\|i mf j w H  – комбинаторную функцию, аргу- ментом которой есть комбинаторная конфигурация ' 'iw W , образованная из элементов базового множества 1{ ,..., }m mA a a   , H и 'H – соответственно системе этих функций. Если 1 1( ( ), )\| mf j w ' 1 1( ( ) , )\| mf j w  , а 1 '1,w w – комбинаторные конфигурации одного типа и 1 1( ( ), )\|mf j w H  , '1 ' 1( ( ), )\|mf j w H  , то 'H H и ' .W W Задачу комбинаторной оптимизации, вход- ные данные в которой заданы функциями 1( ( ), )\|k mf j w и 1( ) \| mj , назовем базовой. Задачу, входные данные в которой заданы функциями ' 1( ( ), )\|i mf j w  (или ' 1( ( ), )\|t mf j w  ), где ' '( ( ), ) ( ( 1), )i if j w f j w      (или ' '( ( ), ) ( ( 1), )t tf j w f j w      ), и 1( ) \|mj  (или 1( ) \|mj  ), где ( ) ( 1)j j      (или ( ) ( 1)j j      ), образованных из 1( ( ), )\|k mf j w и 1( ) \|mj , назовем упорядоченной. Методом структурно-алфавитного поиска по упоря- доченным комбинаторной и числовой функциям по раз- работанным правилам, начиная с наименьших или наи- больших их значений с учетом структуры входных дан- ных и комбинации элементов в строках и столбцах за- данной матрицы, находится локальный оптимум и для него определяется подмножество комбинаторных кон- фигураций, которое содержит глобальное решение. За- тем в найденном подмножестве по второму, третьему и другим элементам варианта решения задачи находят второй, третий и последующие локальные оптимумы, значения которых уменьшаются или не изменяются. В каждом полученном подмножестве комбинаторных кон- фигураций выделяются меньшие подмножества, кото- рые могут содержать глобальное решение. Тем самым сужается область его поиска. Поиск оптимального ре- шения по этой схеме проводится так, как поиск слова в словаре. Доказательство утверждения, что этим методом полиномиально находят глобальный оптимум или близ- кий к таковому, проводится с использованием подклас- сов разрешимых задач. Следовательно, методом структурно-алфавитного поиска решаем транспортную задачу на множестве пе- 24 УСиМ, 2014, № 1 рестановок и задачу кластеризации на подмножестве изоморфных разбиений n-элементного множества на подмножества. Поскольку на всем множестве  с ис- пользованием функции (1) наблюдается ситуация неоп- ределенности, оптимальное решение находим самона- страивающимся алгоритмом [23]. Моделирование целевой функции в задаче сохра- нения окружающей среды с использованием теории комбинаторной оптимизации При моделировании процессов, связанных с сохра- нением окружающей среды рассматривают последствия влияния человеческой деятельности на природу. Эту задачу иногда относят к антагонистическим играм двух участников с противоположными интересами и называ- ют играми против природы [28]. Она заключается в том, что при переходе от одной ситуации к другой с увели- чением (уменьшением) выигрыша одного из игроков численно одинаково уменьшается (увеличивается) вы- игрыш второго. Их еще называют играми двух лиц с нулевой ставкой. Разумное поведение игроков осущест- вляется на основании принципа максимина. Приведем математическую постановку задачи сохранения окру- жающей среды, разработанную с использованием тео- рии комбинаторной оптимизации [29]. Задачу сохранения окружающей среды рассмотрим как игру двух игроков:  мораль общества,  обогащение общества (в частности обогащение его правящего слоя). Положим, что уровень морали и способ обогащения общества – критерии, по которым оптимизируется целе- вая функция. Под целевой функцией понимаем ее чи- словое значение, определяющее уровень здоровья окру- жающей среды, человека и общества в целом. Задача заключается в поиске между этими критериями такого равновесия, при котором общество и природа сосущест- вовали бы комфортно. Как известно, на определенном этапе обогащения общества его мораль начинает сни- жаться. Наступает момент, когда ради обогащения пре- небрегают законами природы, соответственно и закона- ми морали, что приводит к разрушению природы и об- щества в целом. В результате общество теряет все нако- пленные материальные ценности. В литературе описана аналогичная ситуация, которая названа «трагедия об- щин» [30, 31]. Введем множества: 1( ,..., )nA a a , каждый элемент aj, {1,..., )j n , которого соответствует признакам, характе- ризующим уровень морали общества; 1{ ,..., }nB b b , каж- дый элемент bj которого определяет числовую оценку уровня морали общества; 1( ,..., )nA a a   , каждый элемент la , {1,..., )l n , соответствует признакам, которые харак- теризуют способы обогащения общества; 1{ ,..., }nB b b   , каждый элемент которого lb определяет числовую оценку способа обогащения общества. Следовательно, задача сохранения окружающей сре- ды задается двумя множествами A и A , между элемен- тами которых отсутствуют связи. Входными данными выступают конечные последовательности 1{ ,..., }nB b b и 1{ ,..., }nB b b   . Эта задача относится ко второму типу. Смоделируем целевую функцию и определим ее ар- гумент. Положим, что каждому элементу jb множества B соот- ветствует элемент jb из множества B и , { 1,...j jb b   ...,0,...,1} , ,j jb b – вещественные числа. Если благосос- тояние общества обеспечивает его гармоническое развитие и не вредит природе, то эти величины положительные и ,j jb b   , j jb b  , 0  – минимальное значение, при котором возможно разумное поведение игроков. Если , { ,..., }j jb b     , где 0  – наибольшее значение, при котором не разрушается природа, то происходит антаго- нистическая игра двух участников с прямо противопо- ложными интересами. Если ,j jb b    , то разрушается мораль общества, уничтожается природа, теряются все накопленные материальные ценности, т.е. возникает ситуация, при которой выигрывает один игрок (который обогащается), но в результате проигрывают оба. В процессе решения задачи из каждого множества 1( ,..., )nA a a и 1( ,..., )nA a a   выбором определенного количества элементов образуются сочетания без повто- рений, которые есть аргументом целевой функции. Из элементов множеств 1( ,..., )nA a a и 1( ,..., )nA a a   обра- зуем два комбинаторные множества W и W . На этих мно- жествах введем целевую функцию ( , )F w w , где w W и w W  – сочетания без повторений. Задача состоит в поиске таких w W и w W  , для которых введенная целевая функция ( , )F w w принимает максимальное зна- чение при условии, что * *( , )F w w   , где  – мини- мальная величина, при которой природа и общество существует комфортно, благосостояние общества ис- пользуется на его развитие и не разрушается окружаю- щая среда. Смоделируем входные данные функциями натураль- ного аргумента 1( )\|nj , 1( )\|nj и комбинаторными функ- циями 1( ( ), , )\|k i nf j w w  и 1( ( ), , )\|k i nf l w w   . Если из мно- жества A выбирается элемент ja , то ( ( ), , ) 1k i j f j w w  . В противном случае ( ( ), , ) 0k i j f j w w  . Соответственно, если из множества A выбирается элемент la то ( ( ),l f l  УСиМ, 2014, № 1 25 , ) 1k iw w  . В противном случае ( ( ), , ) 0k i l f l w w   . Поскольку поставленная задача решается на двух ком- бинаторных множествах, то функции 1( ( ), , )\|k i nf j w w  и 1( ( ), , )\|k i nf l w w   зависят от двух переменных: w W и w W  . Целевая функция в этой задаче оптимизируется по двум критериям, которые смоделируем как среднюю величину суммарного произведения значений функции натурального аргумента и комбинаторной функции: 1(1) ' ( ( ), , ) ( ) ( , ) q n k i j jk i f j w w j F w w        и j 1(2) ' ' ( ( ) , , ) ( ) ( , ) n k i j k i f j w w j F w w q         , а 2 ( ) 1 ( , ) ( , )k i t k i t F w w F w w     ; где 'q – количество единиц в 1( ( ), , )\|k i nf j w w  , ' 'q – количество единиц в 1( ( ), , )\|k i nf l w w   . Множества W и W состоят из подмножеств изо- морфных сочетаний без повторений. Поскольку нахож- дение оптимального решения проводится на всех их элементах, то в процессе решения задачи с использова- нием выражений (1) ( , )k iF w w и (2) ( , )k iF w w может воз- никать ситуация неопределенности, связанная со струк- турой аргумента целевой функции [32]. Поэтому задача состоит в поиске такого подмножества изоморфных со- четаний без повторений, которое содержит оптимальное решение, совпадающее с целью исследования при усло- вии, что ( , )k iF w w   . Итак, если значение целевой функции равно двум или не меньше величины  , то природа и общество су- ществует комфортно, благосостояние общества исполь- зуется на его развитие. В противном случае разрушается мораль общества, уничтожается природа. Целевая функ- ция задачи сохранения окружающей среды зависит от двух переменных, которыми будут сочетания без повто- рений. В отличие от других задач комбинаторной опти- мизации, которые по этому признаку разделяются на подзадачи с последовательным их решением, решение этой задачи находится одновременно на двух комбина- торных множествах. Заключение. Системный анализ прикладных задач с использованием теории комбинаторной оптимизации позволяет изучать свойства интеллектуальных георас- пределенных динамических систем на общем уровне, выявлять задачи оптимизации комбинаторного типа, формулировать их математические модели и на основе последних разрабатывать эффективные алгоритмы ре- шения. Так, задача распределения сети сервисных объ- ектов разделяется на три подзадачи: задача кластериза- ции, аргументом целевой функции в которой есть раз- биение n-элементного множества на подмножества; транс- портная задача, аргумент целевой функции в которой – перестановка, и задача по теории массового обслужива- ния. Эта задача требует для решения разработки гиб- ридных алгоритмов. В процессе решения подзадачи кла- стеризации и определения мощности сервисных объек- тов возникает ситуация неопределенности. Для ее реше- ния необходимо разрабатывать самонастраивающиеся алгоритмы , что характерно для проектирования систем вычислительного интеллекта.  Внимание ! Оформление подписки для желающих опубликовать статьи в нашем журнале обязательно. В розничную продажу журнал не поступает. Подписной индекс 71008 << /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

Моделювання та розв’язання прикладних задач комбінаторної оптимізації, які виникають в інтелектуальних георозподілених динамічних системах

Institution

Ähnliche Einträge