Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач

На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
1. Verfasser:	Тимофієва, Н.К.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Schriftenreihe:	Управляющие системы и машины
Schlagworte:	Фундаментальные и прикладные проблемы информатики и информационных технологий
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/113324
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:	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-113324
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1133242025-02-09T09:42:17Z Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешаемых задач The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems Тимофієва, Н.К. Фундаментальные и прикладные проблемы информатики и информационных технологий На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається до нуля, а збіжність методу найближчого сусіда та «жадібного» алгоритму залежить від структури вхідних даних. На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных методом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего соседа и «жадного» алгоритма зависит от структуры входных данных. The proof of the approximate solutions convergence sequence to a global solution of the combinatorial optimization problem, which is based on a particular algorithm, is rather complicated problem. This is due to the fact that some classes of problems are unsolvable because of their computational complexity. A lot of researches are devoted to the problem of the methods and algorithms convergence within the mathematical programming. They enter the formal level features required and sufficient conditions for their convergence. The original way to prove some convergence combinatorial optimization methods, based on recognition of the structure of input data (structure-alphabetical search method nearest neighbor method, “greedy” algorithm) is presented. For this purpose, the subclasses of the traveling salesman problems is used. A sequence of the convergence solutions that are built specifically is proved. To assess the methods accuracy, which are decided on a set of permutations, the input data of combinatorial optimization problems defines the functions of the natural argument, one of which is combinatorial. This allows to define a set of values of the objective function for basic problem and to establish some error of interpretation algorithm. An solvable case for the traveling salesman problem is shown, in which the input data requires the linear combinatorial function for which analytically the global minimum and maximum are found. Using this case proves that the convergence of a solutions sequence built by the structural alphabet search for the traveling salesman problem is close to zero. The optimal solution for subclasses coincides with the global. The speed of the described method is polynomial of computational complexity. The convergence of the nearest neighbor method and of the “greedy” algorithm depends on the structure of input data. For some, the solution structures coincides with the global, while others may be far from optimal. 2016 Article Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113324 519.816 uk Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Фундаментальные и прикладные проблемы информатики и информационных технологий Фундаментальные и прикладные проблемы информатики и информационных технологий
spellingShingle	Фундаментальные и прикладные проблемы информатики и информационных технологий Фундаментальные и прикладные проблемы информатики и информационных технологий Тимофієва, Н.К. Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач Управляющие системы и машины
description	На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається до нуля, а збіжність методу найближчого сусіда та «жадібного» алгоритму залежить від структури вхідних даних.
format	Article
author	Тимофієва, Н.К.
author_facet	Тимофієва, Н.К.
author_sort	Тимофієва, Н.К.
title	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
title_short	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
title_full	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
title_fullStr	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
title_full_unstemmed	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
title_sort	доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2016
topic_facet	Фундаментальные и прикладные проблемы информатики и информационных технологий
url	https://nasplib.isofts.kiev.ua/handle/123456789/113324
citation_txt	Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр.
series	Управляющие системы и машины
work_keys_str_mv	AT timofíêvank dovedennâzbížnostíalgoritmívkombínatornoíoptimízacíízvikoristannâmpídklasívrozvâznihzadač AT timofíêvank dokazatelʹstvoshodimostialgoritmovkombinatornojoptimizaciisispolʹzovaniempodklassovrazrešaemyhzadač AT timofíêvank theproofofthealgorithmsconvergenceforcombinatorialoptimizationwiththeusingsubclassesofthesolvedproblems
first_indexed	2025-11-25T10:01:28Z
last_indexed	2025-11-25T10:01:28Z
_version_	1849756114989613056
fulltext	УСиМ, 2016, № 2 5 Фундаментальные и прикладные проблемы информатики и информационных технологий УДК 519.816 Н.К. Тимофієва Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных ме- тодом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего со- седа и «жадного» алгоритма зависит от структуры входных данных. Ключевые слова: комбинаторная оптимизация, комбинаторная конфигурация, целевая функция, задача коммивояжера, метод структурно-алфавитного поиска, метод ближайшего соседа, «жадный» алгоритм На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структур- но-алфавітного пошуку для задачі комівояжера наближається до нуля, а збіжність методу найближчого сусіда та «жадібного» алгоритму залежить від структури вхідних даних. Ключові слова: комбінаторна оптимізація, комбінаторна конфігурація, цільова функція, задача комівояжера, метод структур- но-алфавітного пошуку, метод найближчого сусіда, «жадібний» алгоритм Вступ. Доведення збіжності послідовності на- ближених розв’язків до глобального розв’язку задачі комбінаторної оптимізації, яка будуєть- ся певним алгоритмом, досить складна про- блема. Це пов’язано з тим, що деякі класи та- ких задач є нерозв’язними з причини їхньої обчислювальної складності. Для класів задач з чіткою (точно заданою) структурою вхідних даних та таких, які розв’язуються на множині перестановок, їхні математичні моделі розроб- лено досить ґрунтовно, а тому за змодельова- ною цільовою функцією теоретично можна ви- значити глобальне розв'язання цих задач по- вним перебором, який збігається з метою до- слідження. В задачах з нечіткими вхідними да- ними (задача розпізнавання, задача кластери- зації), крім кількості при обчисленні операцій, витрачених на пошук глобального розв'язання, необхідно враховувати і міри подібності, які тут відіграють основну роль та від вибору яких значною мірою залежить власне розв'язок. До того ж через ситуацію невизначеності, яка спо- стерігається в більшості задач комбінаторної оптимізації, одержаний за змодельованою ці- льовою функцією глобальний результат у них не завжди збігається з метою дослідження. При розв’язанні задач обчислювального (шту- чного) інтелекту досить часто використову- ються методи, які класифікують як евристичні. В них пошук оптимального розв’язку, який за- довольняв би мету дослідження, проводиться за тими ж правилами, яких дотримується лю- дина на інтуїтивному рівні. Ці методи ефекти- вні за швидкодією, але досить часто результат, одержаний таким шляхом, далекий від глоба- льного оптимуму. Постає проблема доведення ефективності за точністю та швидкодією таких алгоритмів. Проблемі збіжності методів та алгоритмів математичного програмування присвячено ба- гато робіт, наприклад [1–5]. В цих роботах на формальному рівні вводяться необхідні ознаки та достатні умови їхньої збіжності. В нейрон- них мережах досліджують збіжність алгорит- мів самонавчання. Для доведення збіжності використовують теорію рядів, функції Ляпу- нова тощо. Цю проблему ще зводять до задачі збіжності наближеного розв’язку операторних рівнянь. Їх використання для певного алгорит- му досить складне. В роботі [5] на прикладі 6 УСиМ, 2016, № 2 задач, які розв’язуються на графах, проводить- ся зведення NP-повної задачі до задачі P. З ці- єю метою розробленими процедурами знахо- диться нижня границя, наближена до глобаль- ного розв’язку. У комбінаторній оптимізації, як правило, розглядають обчислювальну склад- ність розв’язання задач оптимізації та точність алгоритму. Далі подано спосіб доведення збіжності де- яких методів комбінаторної оптимізації, які ґрунтуються на розпізнаванні структури вхідної інформації (метод структурно-алфавітного по- шуку, метод найближчого сусіда, «жадібний» алгоритм). З цією метою використано підкласи розв’язних задач із класу задачі комівояжера. Доводиться збіжність послідовності розв’язків, які будуються оговореними алгоритмами, та встановлюється швидкість цієї збіжності. Методи, що використовуються для роз- в’язання оптимізаційних задач Для розв'язання задач із класів задач комбі- наторної оптимізації виділимо такі основні ме- тоди та алгоритми [6]:  ітераційні методи та алгоритми, що ґрун- туються на частковому переборі варіантів;  методи та алгоритми, що ґрунтуються на розпізнаванні структури вхідної інформації, які ще називають евристичними, такими, в яких моделюються правила вибору оптималь- ного рішення в ручному режимі [7]. До ітераційних методів та алгоритмів нале- жать як універсальні методи та алгоритми ма- тематичного програмування, так і спеціальні, які враховують специфіку даної проблеми (точ- ні та наближені). Це – методи лінійного, ціло- числового, динамічного, нелінійного, квадратич- ного, стохастичного програмування, серед них градієнтні методи, методи гілок і меж, послі- довний аналіз варіантів, методи локального по- шуку, метод відпалу та алгоритми: генетичні, гібридні тощо. Останні десятиліття зусилля вче- них спрямоване на розроблення нових загаль- них схем розв'язання задач комбінаторної оп- тимізації, в основу яких покладено згадані ме- тоди та алгоритми, зокрема евристичні. Під евристичними алгоритмами, як правило, розу- міють способи прийняття рішень, подібні до того, як це робить людина, та побудовані на інтуїтивних міркуваннях, що спираються на попередній досвід [8]. Використання евристи- чних алгоритмів поширене в різних класах за- дач розпізнавання образів різної природи. Во- ни також спостерігаються і в комбінаторній оптимізації. Для багатьох практичних проблем ці алгоритми є чи не єдино можливим шляхом для отримання задовільного рішення в реаль- ному часі. До них відносять підходи, які скла- дно формалізувати та неможливо довести їхню точність. Іноді такий алгоритм може бути ефе- ктивним, тобто за його використання знахо- диться дійсно найкраще рішення, але його на- зивають евристичним через неможливість до- ведення їхньої збіжності. «Жадібний» алгоритм, наприклад, відносять до евристичних методів. Він працює так: із за- даної вхідної інформації за розробленими пра- вилами, що характерні для певного класу за- дач, вибираються найбільші величини з пода- льшим знаходженням максимального значення цільової функції. Методом найближчого сусіда із заданої вхідної інформації вибираються най- менші величини з подальшим пошуком міні- мального значення цільової функції [9]. Аналіз евристичних алгоритмів показує, що пошук оптимального значення проводиться шляхом розпізнавання змінних (найбільших чи найменших величин), тобто розпізнається вхідна інформація. Отже, евристичні алгоритми стосу- ються розв’язання задач комбінаторної оптимі- зації, які ґрунтуються на розпізнаванні вхідної інформації. Якщо класифікацію методів оптимі- зації проводити за можливістю чи неможливістю доведення їхньої збіжності, то до евристичних підходів за цією ознакою можна віднести значну частину перебірних методів, які використову- ються в оптимізації та які достатньо формалізо- вані. Це пов’язано з тим, що при оцінці точності розв’язання задач цими методами виникають різні види невизначеності. Загальна математична постановка задачі комбінаторної оптимізації Наведемо загальну постановку задачі ком- бінаторної оптимізації та сформулюємо її, як у роботі [6]. Задачі цього класу, як правило, за- УСиМ, 2016, № 2 7 даються однією або кількома множинами, на- приклад A та B, елементи яких мають будь-яку природу. Назвемо ці множини базовими. Наявні два типи задач. В першому типі кожну з цих множин подамо у вигляді графа, вершинами якого є її елементи, а кожному ребру поставлено у відповідність число Rclt  , яке називають вагою ребра (R – множина дійсних чисел), {1,..., }l n , {1,..., },t n  n – кількість елементів множини A, n~ – кількість елементів множини B. Приймемо, що nn ~ . Між елементами цих множин існують зв'язки, числове значення яких назвемо вагами. Величини ltc назвемо вхідни- ми даними та задамо їх матрицями. В другому типі задач між елементами заданої множини зв'язків не існує, а вагами є числа Rv j  , },...,1{ nj  , яким у відповідність поставлено деякі властивості цих елементів, числові зна- чення яких задаються скінченними послідов- ностями, що також є вхідними даними. Ці ве- личини визначають значення цільової функції. Для обох типів задач із елементів однієї або кількох із заданих множин, наприклад Aal  , },...,1{ nl , утворюється комбінаторна множи- на W – сукупність комбінаторних конфігурацій певного типу (перестановки, вибірки різних типів, розбиття тощо). На елементах w ком- бінаторної множини W вводиться цільова фун- кція F(w). Необхідно знайти елемент множини W, для якого F(w) набуває оптимального зна- чення при виконанні заданих обмежень. Змоделюємо вхідні дані функцією натураль- ного аргументу. Подамо елементи h наддіагона- лей симетричної комбінаторної матриці ( )kQ w комбінаторною функцією mkwjf 1\|),)(( , а елементи h наддіагоналей симетричної матриці C – функцією натурального аргументу 1( ) \| ( (1), ..., ( ))mj m    , де 2 )1(   nnm – кількість елементів h наддіагоналей матриць C та )( kwQ , 1,1  nh . Верхній індекс k ( },...,1{ qk  ) у kw позначає порядковий но- мер kw у W , q – кількість kw у W . Якщо матриці )( kwQ та C – несиметричні, то mkwjf 1\|),)(( та mj 1\|)( містять усі їхні елементи, а 2m n (або nnm ~ ). Для задач, які розв'язуються на перестановках, цільова функція набуває вигляду    m j k j k jwjfwF 1 )()),(()( . (1) Уведемо 1( ( ), )\|k mf j w = 1( ( (1), ) , ...,kf w ( ( ) , ))k m f m w H  – комбінаторну функцію, аргументом якої є комбінаторна конфігурація Wwk  , утворена з елементів базової множини },...,{ 1 nn aaA  та ' 1 ' \|),)(( Hwjf mi  – комбінаторну функцію, аргументом якої є ком- бінаторна конфігурація '' Ww i  , утворена з елементів базової множини }~,...,~{~ 1 mm aaA  , H та 'H відповідно – системи цих функцій. Якщо mm wjfwjf 1 1' 1 1 \|),)((\|),)((  , а 1,w '1w – комбінаторні конфігурації одного типу і Hwjf m  1 1 \|),)(( , ' 1 1' \|),)(( Hwjf m  , то 'HH  і 'WW  . Задачу комбінаторної оптимізації, вхідні дані в якій задано функціями mkwjf 1\|),)(( та mj 1\|)( , назвемо базовою. Задачу, вхідні дані в якій задано функціями miwjf 1 ' \|),)((  (або ' 1( ( ) , )\| )t mf j w  , де ' '( ( ), ) ( ( 1), )i if j w f j w      (або ),)1((),)(( '' tt wjfwjf   ), та mj 1\|)( (або mj 1\|)( ), де )1()(  jj  (або )1()(  jj  ), утворених із 1( ( ), )\|k mf j w та mj 1\|)( , назвемо упорядкованою. Оцінка точності методів, які використо- вуються для розв’язання задач на множині перестановок Розглянемо задачі комбінаторної оптимізації, аргументом цільової функції в яких є перестано- вка. Для оцінки точності використаємо підкласи розв’язних задач та спосіб визначення множини значень цільової функції [10]. Оскільки згадана упорядкована задача – відомий розв’язний випа- 8 УСиМ, 2016, № 2 док [11], то для базової задачі нескладно знайти область визначення цільової функції. Для систе- ми 'H знаходять перестановки, для яких вираз (1) набуває найбільшого або найменшого гло- бального значення. Якщо елементи комбінатор- ної функції із системи 'H впорядковані від більшого елемента до меншого, а елементи фун- кції натурального аргументу упорядковані від меншого елемента до більшого, то значення (1) є глобальним мінімумом. Якщо елементи обох таких функцій упорядковані від меншого еле- мента до більшого, то значення (1) є глобаль- ним максимумом. Цей розв'язний випадок не належить жодному класу із класів задач комбі- наторної оптимізації. Наведемо теорему [10]. Теорема 1. Значення цільової функції ( )kF w для задач комбінаторної оптимізації, аргумен- том якої є перестановка, знаходиться в межах ' ''t ' 't ' w max ( ) ( ) min ( ), i k i w WW F w F w F w    ' ' ', ,t iw w W Wwk  . У разі мінімізації значення цільової функції знаходиться в межах   )(min ' ' i Ww wF i )( FwF k  . У разі максимізації – в межах ' * '( ) max ( ), t k t w W F F w F w    де   )(min '* ' i Ww wFF i  )(min)(max '' '' i Ww t Ww wFwF it    , а  – коефіцієнт зменшення області пошуку оптимального роз- в'язання, який уточнюється в процесі роботи алгоритму, 't ' ' ' 't ' w max ( ), min ( ) i i W w W F w F w   – обчисле- ні глобальні максимум та мінімум упорядкова- ної задачі. Доведення – в [10]. Оцінку точності розв'язання задачі при ві- домому глобальному мінімумі обчислюємо за виразом %100 )( 1))(,( * min* min        k k wF FwFF (або %100)(1))(,( max * * max        F wFwFF i i у разі максимізації), де minF – глобальний мінімум задачі, Fmax – відповідно глобальний її макси- мум, )( kwF , )( iwF – одержані мінімальний або максимальний розв'язок цієї задачі певним алгоритмом. Експеримент показує, що чим бі- льша розмірність задачі, тим менша похибка (у відсотках) одержаного результату відносно гло- бального оптимуму. Вважатимемо, що алгоритм (метод) збіжний, якщо послідовність побудованих розв’язків на- ближається до нуля, тобто 0))(,( min  kwFF (або 0))(,( max  iwFF ). Серед одержаних розв’язків може бути такий, для якого 0))(,( * min  kwFF (або * max( , ( )) 0)iF F w  . При цьому швидкість збіжності – поліноміальна за обчислювальною складністю. Наведемо підклас розв’язних задач із класу задачі комівояжера. Якщо для них min( ,F ( )) 0kF w  , то оптимальний результат, отрима- ний певним алгоритмом, збігається з глобаль- ним. Задача комівояжера полягає в наступному: задано деяку кількість міст, відстань між яки- ми відома. Необхідно знайти найкоротший шлях, який є гамільтоновим циклом. Під гамі- льтоновим циклом розуміємо шлях в графі, який починається в заданій вершині, прохо- дить через усі вершини один раз та поверта- ється в початкову. Цей цикл в задачі комівоя- жера назвемо маршрутом. Позначимо маршрут 1 1( , )\| ( ( ,1),...,k n ku w l u w ( , ))k nu w n , де )(),)((),( jwjflwu k j k l  , якщо 0)(  j , },...,1{ mj , а uH – їхня множина. За певними правилами розділимо uH на підмножини 221 ,...,, nHHH . Відпові- дно на підмножини 221 ,...,, nKKK розділя- ється і множина перестановок. Покладемо {2, 4, ..., 2 }Z j , 1 {1,3,...,2 1}Z j  . Теорема 2 (дійсна для 4n ) [6, 12]. Якщо в задачі комівояжера комбінаторна функція ),...,1(\|),)(( 1 1 mwjf m  , то цільова функція (1) найбільшого значення набуває для переста- новки )2,4,6,8,...,7,5,3,1( iw , (2) УСиМ, 2016, № 2 9 для якої 1 * Kw i  , а найменшого значення – для перестановки 1 2 3 4 5 6 7 4 3 2 1 1 1 2 3 4 5 6 2 * 1 2 2 2 2 ((1) , ( 1) , (3) , ( 3) , (5) , ( 5) , (7) ,... ..., ( 4) , (4) , ( 2) , (2) , ( ) ), якщо , (( ) , (2) , ( 2) , (4) , ( 3) , (6) ,..., , 2 1 , 1 , 2 2 3 2 n n n n n n k n n n n n n n n n n Z nn n n n nw n                                         3 4 2 3 2 1 , 3 , ... 2 ( 3) , (3) , ( 1) , (1) ), якщо , n n n n n n n n n Z                           (3) для якої 2 *  n k Kw , де 1 0, якщо , 2 2, якщо . 2 n Z n Z        Найбільше значення цільової функції дорів- нює 3 6)83()( 2 *   nnnwF i , а найменше – відповідно 24 )45()( 2 *   nnwF k , якщо Zn , та 24 12)75()( 2 *   nnwF k , якщо 1Zn . Доведення. Якщо 4n , то найменше і найбільше значення цільової функції збігають- ся, тому цей варіант не розглядаємо. Спочатку доведемо, що )()( ** ki wFwF  . Для iw запишемо маршрут 1( , )\|i nu w l  1 1 2 3 4( , 1, 1, 1, 1,...v v v v v     2 11, )n nv v  , де 1 2 )2()1(    jnjv j – номер елемента в j-му рядку гамільтонової діагоналі. Сума членів цієї послідовності    21)( 1 1 * nvwF n j j i 1 1 ( 1) (2 ) 1 1 2 n j j n j n              2( 3 5) 1 1 3 n n n n       3 6)83( 2  nnn . Для kw запишемо маршрут 1 1 1 2 2 ( , )\| ( ( 3), ( 2), ( 5), ( 3), k nu w l v n v n v n v n           3 3 4 4 5 ( 7), ( 5), ( 9), ( 7), ( 11) ,... v n v n v n v n v n            (4) 1 1..., 1, 3, , 1)v v v v      , якщо Zn , * 1 1 1 2 2 ( , )\| ( ( 3), ( 2), ( 5), ( 3), k nu w j v n v n v n v n           3 3 4 4 5 ( 7), ( 5), ( 9), ( 7), ( 11) ,... v n v n v n v n v n           (5) 2 2 1 1..., ( 2), ( 4), ,v n n v n n v v          2, )v , якщо 1Zn , де       2 1n . Знайдемо суми членів послідовностей (4), (5). Якщо Zn , то    2 1 * 2)( n j j k vwF 2 1 2 ( 2) ( 1) (2 )2 1 2 2 ( 2) (5 12 28) ( 2) 2 24 2 n j n n j n j n n n n n n n                     24 )45( 2 nn . Якщо 1Zn , то ( )kF w  1 2 1 2 ( 1) (2 )2 1 2 ( 1) (3 1) 2 11 8 2 n j j n j n n n n                    2 2 3 (5 21 43) 27 ( 1) (3 1) 24 8 2 1 5 7 121 . 2 24 n n n n n n n n n                Для nZ доведемо, що 2( 3 8) 6 3 n n n    2(5 4) 24 n n   . Після нескладних перетворень одержимо 0 8 16208 23   nnn . (6) Для n = 6, для якого ( ) 50iF w  , ( ) 46kF w  , нерівність (6) набуде вигляду 04  . Отже, для будь-якого 4n ліва частина нерівнос- 10 УСиМ, 2016, № 2 ті (6) завжди додатна. Для 1Zn запишемо нерівність 24 1275 3 6)83( 32    nnnnn . Після нескладних перетворень одержимо 0 8 12198 23   nnn . Відзначимо, що для будь-якого 4n ліва частина цієї нерівності також завжди додатна. Доведемо, що для будь-якої перестановки tw порівнянно з iw значення цільової функ- ції не збільшується, а порівнянно з kw – не зменшується. Візьмемо перестановку, при ут- воренні маршруту якої з кожного рядка h над- діагоналей матриці C вибрано найменший елемент. Запишемо її як tw (1, 2, 3,..., )n (тур Майстра). Відповідно для неї запишемо марш- рут 1 1 2 2 1( , )\| ( , , ..., , , 1),t n n nu w l v v v v n   а зна- чення 1 1 ( ) 1 n t j j F w v n      = 2( 3 8) 6 3 n n n   , тобто )()( it wFwF  . Отже, для туру Майст- ра, маршрут для якого утворено вибиранням по одному найменшому елементу з кожного t- го рядка матриці )( 1wQ , 1,2  nt , цільова функція в порівнянні з kw не зменшується, а дорівнює )( iwF . У перестановці kw для Zn проведемо транспозицію елементів 3)2( n та 1)1(  nn . Для перестановки w t  Kn–3 у маршруті nt lwu 1\|),( два елементи збільшилися на оди- ницю та два елементи зменшилися на одини- цю, а ).()( kt wFwF  У kw проведемо тран- спозицію елементів 3)2( n та 1)(n . Одержа- на перестановка w t також знаходиться в під- множині (n – 3), а у відповідному маршруті два елементи збільшилися на два і два елементи зменшилися на два, а )()( kt wFwF  . Якщо в kw провести транспозицію елементів 2 n та n, то одержана перестановка w t буде у підмно- жині 1 2  n , а у відповідному маршруті два елементи зменшаться на 2 n . Елемент 2 nv по- міняється місцем з елементом 2 2  nvn , а 1 2 nv – з елементом 2 1031 2   nvn . Цільова функція в цьому випадку збільшиться на 2 143 n , а )()( kt wFwF  . Отже, якщо при утворенні маршруту елеме- нти вибираються по два з перших      2 1n ря- дків матриці C , то цільова функція зменшу- ється. Якщо маршрут утворено вибиранням елементів з рядків за номерами, більшими, ніж      2 1n , то цільова функція збільшується. Так, найбільшого значення цільова функція набу- ває для перестановки (2) і ,1 * Kw i  якщо 1 1( ( ) , )\| (1, ..., )mf j w m  , а найменшого – для перестановки (3) і 2 *  n k Kw , що і дово- дить теорему 2 для Zn . Аналогічно теорема 2 доводиться для 1Zn . Теорему доведено. Наслідок 1. Якщо значення комбінаторної функції 1 0( ( ) , )f j w k j b   або ( ( ) ,f j 1) 2 jw  , mj ,1 , 0,0 bk – цілі довільні чи- сла, то найбільшого значення цільова функція набуває для перестановки (2), відповідний ма- ршрут якої * 1 1( , )\|i nu w l H і 1 * Kw i  , а най- меншого значення – для перестановки (3), відпо- відний маршрут для якої 21 * \|),(  n nk Hjwu і 2 *  n k Kw . Теорема 3 (дійсна для 4n ). Якщо комбі- наторна функція )1,...,(\|),)(( 1 1 mwjf m  (матриці Демиденка, Кальмансона), то най- більшого значення цільова функція набуває для перестановки (3), відповідний маршрут якої 21 * \|),(  n ni Hlwu , а найменшого – для перестановки (2), відповідний маршрут якої УСиМ, 2016, № 2 11 11 * \|),( Hlwu nk  . Найменше значення цільової функції дорівнює 3 2 * 3 10 12( ) 6 k n n nF w     , а найбільше – відповідно )( iwF 24 20127 23 nnn   , якщо Zn , та ( )iF w  3 27 12 17 12 24 n n n    , якщо 1Zn . Доведення теореми 3 аналогічне доведенню теореми 2. Доведення збіжності методів та алгоритмів, які ґрунтуються на розпізнаванні структури вхідної інформації. Доведемо збіжність методу структурно-алфавітного пошуку[13], «жадібно- го» алгоритму та методу найближчого сусіда з використанням наведених раніше підкласів роз- в'язних задач для задачі комівояжера. Теорема 4. Метод структурно-алфавітного пошуку збіжний, якщо для підкласів розв'яз- них задач побудовою не більш як 2 2n пере- становок він забезпечує пошук упорядкова- ної послідовності локальних екстремумів ))(,...,)(),(( 21 kwFwFwFF  таких, що 0))(,( * min  kwFF , серед яких існує такий, для якого ,0))(,( * min  kwFF де ,k k 2{1,..., 2}n . Для доведення теореми 4 сформулюємо такі леми. Лема 1. Якщо для упорядкованої задачі ко- мівояжера перші n значень ),)(( 'twjf  (або ),)(( 'iwjf  ), mj ,1 , утворюють мар- шрут (гамільтоновий цикл), то ' 1( ( ), ) \|t mf j w   1( ( ) , ) \|k mf j w  ( або ' 1( ( ) , ) \|i mf j w   * 1( ( ), ) \| )k mf j w  ), а Wwk * є глобальним розв’язком базової задачі; ' 1( ( ), ) \| ,t mf j w  ' ' 1( ( ), ) \|i mf j w H   , * 1( ( ), ) \|k mf j w H  , 'H H . Доведення очевидне. Лема 2. Якщо базова задача комівояжера задана функцією натурального аргументу mwjf 1 1 \|),)(( , яка змінюється як монотонна (неспадна або незростаюча), то для знахо- дження за упорядкованою задачею глобально- го розв'язку методом структурно-алфавітного пошуку необхідно побудувати не більш як 2 2n перестановок. Доведення. Розглянемо задачу комівояже- ра, у якій комбінаторна функція змінюється як монотонно неспадна. Приймемо, що )...,,1(\|),)(( 1 1 mwjf m  – лінійна функція. Цю задачу зведемо до упорядкованої. Запишемо ' 1( ( ), ) \| (1, ..., ),t mf j w m   а 1 1 2( ) \| ((1) , (1)mj    1..., (1) , (0) ,..., (0) )n n m . Для неї побудуємо по- слідовність локальних екстремумів. Як випли- ває з теореми 2, для задачі комівояжера, вхідні дані в якій задано функцією 1 1( ( ), ) \|mf j w  (1, ..., ),m найбільшого значення цільова функ- ція набуває для перестановки (2) у підмножині 1K , а найменшого – для перестановки (3) у підмножині 2nK . Щоб отримати перестанов- ку з підмножини 2nK , необхідно зафіксувати в ній елементи у такому порядку (, n–1, ,...,1 n ) або за комбінаторною функцією ' 1( ( ), ) \| (1, ..., )t mf j w m   послідовно побудува- ти 2n перестановки, починаючи зі значення '( (1), ) 1,tf w   '( (2), ) 2tf w   та закінчуючи ( ( 2),f n   ' ) 2tw n  . Тобто, із 1n елемен- тів наддіагонального рядка матриці вибрати два елементи, які в комбінації з елементами інших рядків утворюють маршрут (відповід- но утворюється і перестановка), для якої зна- чення цільової функції – найменше. Для '( (1), ) 1tf w   одержана перестановка нале- жить до підмножини K1, для '( (2), ) 2tf w   вона належить до K2, а для '( ( 2), )tf n w    2 n – відповідно до 2nK . Для заданої структури вхідних даних серед маршрутів, які з першого рядка матриці містять елементи 2n та 1n , є найкоротші. Комбінацією елементів з другого рядка мат- риці у підмножині 2nK знайдемо меншу під- 12 УСиМ, 2016, № 2 множину, яка містить глобальний мінімум. Для цього зафіксуємо значення '( ( 2), )tf n w    2n  та 1),)1(( '  nwnf t  , пропустимо nwnf t  ),)(( '  (для нього перестановку уже побудовано) і, починаючи з '( ( 1), )tf n w    1n  , потім з 2),)2(( '  nwnf t  буду- ємо наступні перестановки. Для перестановки, де цільова функція – найменша, маршрут із другого рядка матриці містить елементи '( (2 5), ) 2 5tf n w n     та ( (2 3),f n   ' )tw  2 3n  . Кількість побудованих перестановок дорівнює 3n  . Аналогічно, комбінацією еле- ментів з кожного рядка вибираємо по два еле- менти так, щоб одержаний маршрут був най- коротший. Кількість побудованих перестано- вок для кожного рядка дорівнює )1(  sn , де s – номер рядка матриці. Вважаємо, що їхня кількість дорівнює n . Маршрут, якому відпо- відає перестановка * ((1, 1,3, 3,5,kw n n   ),2,2,4,4,...,7,5 nnnn  , містить по два елементи з      2 1n наддіагональних рядків матриці )( kwQ та є глобальним мінімумом (вираз (3)). Отже, щоб знайти глобальний мі- німум для задачі комівояжера, вхідні дані в якій задано )...,,1(\|),)(( 1 ' mwjf mt   , будуєть- ся послідовність розв’язків не більш як 2 2n перестановок, що і доводить лему 2 для ліній- ної функції. Для задачі комівояжера, вхідні дані в якій задаються комбінаторними функціями, що змінюються як монотонні (неспадні або незро- стаючі), лема 2 доводиться аналогічно. Лему 2 доведено. Лема 3. Якщо базова задача комівояжера задана функцією натурального аргумента, яка містить не менш як 4 15 n найменших одна- кових значень і вони утворюють маршрут (га- мільтонів цикл), то метод структурно-алфа- вітного пошуку збіжний, якщо для підкласів розв'язних задач з побудовою не більш як 2 2n перестановок він забезпечує знаходження упо- рядкованої послідовності локальних екстре- мумів ))(,...,)(),(( 21 kwFwFwFF  таких, що 0))(,( * min  kwFF , серед яких існує такий, для якого 0))(,( * min  kwFF , де ,k k  2 1,..., 2 n      . Доведення. Лему 3 доводимо методом ма- тематичної індукції. Розглянемо задачу, вхідні дані в якій задано комбінаторною функцією ),,...,,,,(\|),)(( '' 11 1 mm m bcbcbcwjf  , де ' 1 , якщо , , якщо , c m Z c b m Z     1' , якщо , , якщо , c m Z b b m Z     bc  , }2,...,4,2{ jZ  , }12...,,3,1{1  jZ . Зведемо її до упорядкованої. Запишемо ))0(,...,)0(,)1(,...,)1(,)1((\|)( 1211 mnn mj   , а ))(,)(,...,)(,)((\|),)(( 1211 ' mm mt bbccwjf   . Кіль- кість найменших значень c у mtwjf 1 ' \|),)((  більша ніж 4 15 n і для них виконуються умови існування гамільтонова циклу [14]. Як доведено в [15], найменше значення цільової функції для }6,5{n , дорівнює bcn  )1( , тому ці варіанти не розглядаємо. Оскільки зна- чення цільової функції залежить від парних та непарних n , 2 n , 2 3n і перестановки для них – різні [15], то лему 2 доводимо для }10,9,8,7{n . Проведемо пошук перестанов- ки (гамільтонова циклу), для якого цільова фу- нкція дорівнює cnwF k )( . Значення c у 1 1( ( ), )\|mf j w перебувають у позиціях з непар- ними номерами, тому глобальний мінімум шу- каємо в підмножинах sK , де 1s Z . Покладемо n = 7. Починаючи з '( (1), )tf w   = c та cwf t  ),)2(( '  , побудуємо переста- новку УСиМ, 2016, № 2 13  )6,7,5,3,2,1,4(1 w . Для неї значення цільової функції дорівнює 1( )F w ( 1)n c b   . Пропустимо cwf t  ),)2(( '  та, починаючи з cwf t  ),)1(( '  та ( (3),f  ' )tw c , побу- дуємо наступну перестановку  w2 (6,1, 2, 3, 5, 7, 4) , для якої 2( )F w  ( 2) 2n c b   . Оскільки значення цільової функції збільшилося, повернемося до попере- дніх cwf t  ),)1(( '  та cwf t  ),)2(( '  , а в другому рядку матриці проведемо перебір елементів c, тобто пропустимо ( (3),f  ' )tw  = c, урахуємо cwf t  ),)4(( '  та одержимо перестановку  )6,7,3,5,2,1,4(3 w , для якої cnwF )( 3 . Отже, глобальний мінімум для n = 7, якщо 1Zn , 12)3( Zn  , знайдено у K1 побудо- вою трьох перестановок. Покладемо n = 8. Аналогічно попередньому варіанту методом структурно-алфавітного по- шуку побудуємо перестановки:  w1 = (7, 3, 5, 4, 1, 2, 6, 8), для якої 1( )F w  = (n – 1)c + b;  )8,7,3,5,4,2,1,6(2 w , для якої 2( )F w  ( 1)n c b   ;  )5,3,7,6,8,2,1,4(3 w , для якої 3( )F w  ( 1)n c b   ;  w4 = (4, 1, 2, 6, 8, 5, 3, 7), для якої .)( 4 cnwF  Глобальний мінімум для n = 8, якщо n  Z, Zn  2 , у підмножині K1 знайдено побудовою чотирьох перестановок. Покладемо n = 9. Побудуємо перестановки:  )8,5,3,2,1,4,6,7,9(1 w , для якої F(w1) = = (n – 1)c + b;  )4,8,7,9,5,3,2,1,6(2 w , для якої )( 2wF bcn 2)2(  ;  w3 ( 4,1, 2, 5, 3, 7, 8, 9, 6) , для якої 3( )F w  ( 2) 2n c b   ;  )6,5,8,9,7,3,2,1,4(4 w , для якої )( 4wF = (n – 1)c + b;  w5 = ( 4,1, 2, 3, 7, 9, 6, 5, 8) , для якої )( 5wF = n c. Глобальний мінімум для n = 9, якщо 1Zn , Zn  2)3( , знайдено у K1 побудовою п'яти перестановок. Покладемо n = 10. Використовуючи описані правила, побудуємо перестановки:  w1 (4,1, 2, 6, 8,10, 9, 7, 3, 5) , для якої F(w1) = ( 1)n c b   ;  w2 (6,1, 2, 4,5, 3, 7, 9,10,8) , для якої )( 2wF bcn  )1( ;  3 (4,1,2,8,6,10,9,7,3,5)w  , для якої )( 3wF cn . Глобальний мінімум для 10n , якщо n  Z, n /2  Z1, знайдено у K1 побудовою трьох перестановок. За індукцією, якщо для задачі з довільним n матриця містить однакові елементи, з яких утворюється маршрут, то для знаходження глобального мінімуму в цьому випадку необ- хідно провести послідовний перебір елементів для кожного рядка окремо. Оскільки в кожно- му з них для періодичної функції зі значеннями },{ bc може бути     2 n елементів c , то для знаходження гамільтонова циклу необхідно по- будувати не більш як 22 2nnn  перестановок, що і доводить лему 3, коли вхідні дані задано періодичною функцією натурального аргументу, або іншою функцією, яка містить не менш як 4 15 n найменших однакових значень і вони утворюють маршрут (гамільтонів цикл). Справедливість теореми 4 для задачі комі- вояжера випливає з лем 1 і 2. Теорему 4 доведено. Наслідок 2. Якщо в задачі комівояжера ком- бінаторна функція 1 1( ( ), ) \| (1, ..., )mf j w m  , то за правилами методу найближчого сусіда у пошуку мінімального значення цільової функ- ції наведеного розв’язного випадку знайдено перестановку )2,4,6,8,...,7,5,3,1( iw , яка для нього є глобальним максимумом, тобто збіжність методу 1))(,( * min  kwFF . 14 УСиМ, 2016, № 2 Якщо в задачі комівояжера комбінаторна функція )...,,1(\|),)(( 1 1 mwjf m  , то за пра- вилами «жадібного» алгоритму при пошуку глобального максимуму одержуємо глобаль- ний максимум, тобто збіжність алгоритму до- рівнює 0))(,( * min  kwFF . Для обох випадків швидкість збіжності до- рівнює одній ітерації. Наслідок 3. Якщо в задачі комівояжера ком- бінаторна функція )1,...,(\|),)(( 1 1 mwjf m  , то за правилами методу найближчого сусіда при пошуку мінімального значення цільової функції наведеного розв’язного випадку знай- дено перестановку (3), яка є для нього глоба- льним мінімумом, тобто збіжність методу до- рівнює 0))(,( * min  kwFF . Якщо в задачі комівояжера комбінаторна функція )1,...,(\|),)(( 1 1 mwjf m  , то за пра- вилами «жадібного» алгоритму при пошуку глобального максимуму одержуємо глобаль- ний мінімум, тобто збіжність алгоритму дорів- нює 1))(,( * min  kwFF . Для обох випадків швидкість збіжності до- рівнює одній ітерації. Викладений у наслідках 2 та 3 результат по- яснюється тим, що в цих методах не прово- диться аналіз щодо виявлення факторів, які впливають на значення цільової функції в за- лежності від комбінації елементів вхідних да- них. Висновок. Отже, збіжність методів, які ґрун- туються на розпізнаванні структури вхідної інформації, можна довести з використанням підкласів розв’язних задач. Так, збіжність по- слідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі ко- мівояжера наближається до нуля, тобто 0))(,( min  kwFF , а для підкласів розв’язних задач 0))(,( min  kwFF . Її швидкість – полі- номіальна за обчислювальною складністю. Збіжність методу найближчого сусіда та «жа- дібного» алгоритму залежить від структури вхідних даних. Для одних структур розв’язок дорівнює 0))(,( * min  kwFF , а для інших мо- же бути 1))(,( * min  kwFF . Цей розв’язок, як правило, досягається за одну ітерацію. 1. Карманов В.Г. Математическое программирова- ние. – М.: Наука, 1986. – 286 с. 2. Лившиц Е.Д. Сходимость жадных алгоритмов: Ав- тореф. дис. ... д-ра. физ.-мат. наук / Рос. ун-т дружбы народов. – М., 2011. – 34 с. 3. Поляк Б.Г. Сходимость и скорость сходимости ин- теративных стохастических алгоритмов // Автома- тика и телемеханика. 1976. – Т. 1, № 12. – С. 83–94. 4. Про збіжність спектрального алгоритму навчання нейронних елементів / Ф. Гече, В. Коцовський, С. Ковальов та ін. // Вісн. Нац. ун-ту «Львів. полі- техніка». – 2007. – № 604. – С. 187–194. 5. Ivanov Viktor. A short proof that NP is not P // Int. J. of Pure and Applied Mathematics. – 2014. – 94, N 1. – P. 81–88. 6. Тимофієва Н.К. Теоретико-числові методи розв'я- зання задач комбінаторної оптимізації: Автореф. дис. ... д-ра. техн. наук / Ін-т кібернетики ім. В.М. Глушкова НАН України, К., 2007. – 32 с. 7. Тимофієва Н.К. Про методи комбінаторної оптимі- зації, що ґрунтуються на розпізнаванні вхідної ін- формації, евристичні алгоритми та обчислювальний інтелект // Вісн. Вінницьк. політехнічн. ін-ту. – 2015. – № 2. – С. 106–111. 8. Ивахненко А.Г. Системы эвристической самоорга- низации в технической кибернетике. – Киев: Техні- ка, 1971. – 392 с. 9. Пападимитриу Х., Стайглиц К. Комбинаторная оп- тимизация. Алгоритмы и сложность – М.: Мир, 1985. – 510 с. 10. Тимофеева Н.К. Определение множества значений целевой функции в задачах дискретной оптимиза- ции // КВТ. Сложные системы управления: Сб. на- уч. тр. – 1998. – 120. – С. 37–43. 11. Харди Г.Г., Литтльвуд Дж.Е., Полиа Г. Неравен- ства. – М.: Гос. изд-во иностр. лит., 1948. – 456 с. 12. Тимофієва Н.К. Використання структурного пере- творення вхідних даних для зведення нерозв'язних задач комбінаторної оптимізації до розв'язних // Ком- бінаторні конфігурації та їх застосування: Матеріали десятого Міжвуз. наук.-практ. сем. (17–18 квітня 2015 р.). – Кіровоград: Кіровогр. техн. ун-т. – 2015. – С. 94–99. 13. Тимофієва Н.К. Метод структурно-алфавітного пошуку та підкласи розв’язних задач із класу зада- чі комівояжера // УСиМ. – 2008. – № 4 – С. 20–36. 14. Оре О. Теория графов / Пер. с англ. – М.: Наука, 1980. – 336 с. 15. Тимофеева Н.К. Нахождение оптимального реше- ния в задаче коммивояжера // Программно-алго- ритмическое обеспечение решения задач приклад- УСиМ, 2016, № 2 15 ной математики. – К.: Ин-т кибернетики им. В.М. Глушкова АН Украины, 1993. – С. 21–26. Поступила 15.03.2016 Тел. для справок: +38 044 502-6365 (Киев) © Н.К. Тимофеева, 2016 Н.К. Тимофеева Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешимых задач Введение. Доказательство сходимости последователь- ности приближенных решений к глобальному решению задачи комбинаторной оптимизации, которая строится определенным алгоритмом, достаточно сложная про- блема. Это связано с тем, что некоторые множества та- ких задач неразрешимы с точки зрения вычислительной сложности. Для классов задач с четкой (точно заданной) структурой входных данных и таких, которые решаются на множестве перестановок, их математические модели разработаны достаточно основательно, и поэтому по смоделированной целевой функции теоретически можно определить глобальное решение этих задач полным пе- ребором, совпадающим с целью исследования. В зада- чах с нечеткими входными данными (задача распозна- вания, задача кластеризации), кроме количества при вычислении операций, затраченных на поиск глобально- го решения, необходимо учитывать и меры подобия, что играет основную роль и от выбора которых в значитель- ной степени зависит собственно решение. К тому же из- за ситуации неопределенности, наблюдаемой в боль- шинстве задач комбинаторной оптимизации, получен- ное по смоделированной целевой функции глобальное решение в таких задачах не всегда совпадает с целью исследования. При решении задач вычислительного (ис- кусственного) интеллекта достаточно часто использу- ются методы, классифицируемые как эвристические. В них поиск оптимального решения, которое удовлетво- ряло бы цель исследования, проводится по тем же пра- вилам, что и на интуитивном уровне. Эти методы эф- фективны по быстродействию, но часто результат далек от глобального оптимума. Возникает проблема доказа- тельства эффективности по точности и быстродействию таких алгоритмов. Проблеме сходимости методов и алгоритмов мате- матического программирования посвящено много работ, например [1–5]. В этих работах на формальном уровне вводятся необходимые признаки и достаточные условия их сходимости. В нейронных сетях исследуют сходи- мость алгоритмов самообучения. Для доказательства сходимости используют теорию рядов, функции Ляпу- нова и пр. Эту проблему сводят еще к задаче сходимо- сти приближенного решения операторных уравнений. Их использование для определенного алгоритма доста- точно сложно. В работе [5] на примере задач, решаемых на графах, проводится сведение NР-полной задачи к задаче P. С этой целью разработанными процедурами находится нижняя граница, приближенная к глобально- му решению. В комбинаторной оптимизации, как пра- вило, рассматривают вычислительную сложность реше- ния задач оптимизации и точность алгоритма. Далее приведен способ доказательства сходимости некоторых методов комбинаторной оптимизации, осно- ванных на распознавании структуры входной информа- ции (метод структурно-алфавитного поиска, метод бли- жайшего соседа, «жадный» алгоритм). С этой целью использованы подклассы разрешимых задач из класса задачи коммивояжера. Доказывается сходимость после- довательности решений, которые строятся оговоренны- ми алгоритмами, и устанавливается ее скорость. Методы, используемые для решения оптимизаци- онных задач Для решения задач из классов задач комбинаторной оптимизации выделим такие основные подходы [6]:  итерационные методы и алгоритмы, основанные на частичном переборе вариантов;  методы и алгоритмы, основанные на распознавании структуры входной информации. Их еще называют эв- ристическими, такими, в которых моделируются прави- ла выбора оптимального решения в ручном режиме [7]. К итерационным методам и алгоритмам относятся как универсальные методы математического програм- мирования, так и специальные, учитывающие специфи- ку данной проблемы (точные и приближенные). Это – методы линейного, целочисленного, динамического, нелинейного, квадратичного, стохастического програм- мирования, градиентные методы, методы ветвей и гра- ниц, последовательный анализ вариантов, методы ло- кального поиска, метод отжига и алгоритмы: генетиче- ские, гибридные и др. Последние десятилетия усилия ученых направлены на разработку новых общих схем решения задач комбинаторной оптимизации, в основу которых положены упомянутые методы и алгоритмы. Под эвристическими алгоритмами, как правило, подра- зумевают способы принятия решений, подобные тому, что делает человек, и построенные на интуитивных рас- суждениях, которые опираются на предыдущий опыт [8]. Эвристические алгоритмы широко используются в задачах распознавания разной природы и в комбинатор- ной оптимизации. Для многих практических проблем эти алгоритмы – единственно возможный способ полу- чения удовлетворительного решения в реальном време- ни. К ним относят подходы, которые сложно формали- зовать и невозможно доказать их точность. Иногда та- кой алгоритм может быть точным, т.е. при его примене- 16 УСиМ, 2016, № 2 нии находят действительно лучшее решение, но назы- вают его эвристическим из-за невозможности доказа- тельства их сходимости. «Жадный» алгоритм относят к эвристическим мето- дам. Он работает так: из заданной входной информации по разработанным правилам, характерным для опреде- ленного класса задач, выбираются самые большие величи- ны с последующим нахождением максимального значе- ния целевой функции. Методом ближайшего соседа из заданной входной информации выбираются наимень- шие величины с последующим поиском минимального значения целевой функции [9]. Анализ этих алгоритмов показывает, что поиск оп- тимального значения проводится путем распознавания переменных (наибольших или наименьших их величин), т.е. распознается входная информация. Следовательно, эвристические алгоритмы относятся к решению задач комбинаторной оптимизации, основанным на распозна- вании входной информации. Если классификацию мето- дов оптимизации проводить по возможности или невоз- можности доказательства их сходимости, то к эвристи- ческим подходам по этому признаку можно отнести значительную часть переборных методов, используемых в оптимизации и достаточно формализованных. Это свя- зано с тем, что при оценке точности решения задач эти- ми методами возникают различные виды неопределен- ности. Общая математическая постановка задачи ком- бинаторной оптимизации Приведем общую постановку задачи комбинаторной оптимизации и сформулируем ее, как в работе [6]. Зада- чи этого класса, как правило, задаются одним или не- сколькими множествами, например A и B, элементы ко- торых имеют любую природу. Назовем эти множества базовыми. Имеется два типа задач. В первом типе каж- дое из этих множеств приведем в виде графа, вершины которого – его элементы, а каждому ребру поставлено в соответствие число, называемое весом ребра (R – мно- жество вещественных чисел), {1,..., },l n {1 ,..., },t n  n – количество элементов множества A, n – количество элементов множества B. Положим, что n n  . Между элементами этих множеств существуют связи, числовое значение которых назовем весами. Величины clt назовем входными данными и зададим их матрицами. Во втором типе задач между элементами заданного множества свя- зей не существует, а весами будут числа vj  R, j  {1,,n}, которым в соответствие поставлены неко- торые свойства этих элементов, числовые значения ко- торых задаются конечными последовательностями, ко- торые также являются входными данными. Эти величи- ны определяют значение целевой функции. Для обоих типов задач из элементов одной или не- скольких из заданных множеств, например al  A, {1,..., }l n , образуется комбинаторное множество W – совокупность комбинаторных конфигураций опреде- ленного типа (перестановки, выборки разных типов, разбиения и др.). На элементах w комбинаторного мно- жества W вводится целевая функция ( )F w . Необходи- мо найти элемент множества, для которого ( )F w при- нимает оптимальное значение при выполнении задан- ных ограничений. Смоделируем входные данные функцией натураль- ного аргумента. Представим элементы h наддиагоналей симметричной комбинаторной матрицы ( )kQ w ком- бинаторной функцией 1( ( ) , )\|k mf j w , а элементы h наддиагоналей симметричной матрицы C – функцией натурального аргумента 1( ) \| ( (1), ..., ( )),mj m    где ( 1) 2 n nm   – количество элементов h наддиа- гоналей матриц C и ( )kQ w , 1, 1h n  . Верхний ин- декс k ( {1,..., }k q ) в kw означает порядковый номер kw в W, q – количество kw в W. Если матрицы ( )kQ w и C – несимметричны, то 1( ( ) , )\|k mf j w и 1( ) \|mj содержат все их элементы, а 2m n (или m n n  ). Для задач, решаемых на перестановках, це- левая функция примет вид 1 ( ) ( ( ), ) ( )mk k jj F w f j w j     . (1) Введем 1 1( ( ), )\| ( ( (1), ) , ..., ( ( ) ,k m k mf j w f w f m    ))kw H – комбинаторную функцию, аргументом ко- торой является комбинаторная конфигурация kw W , образованная из элементов базового множества 1{ ,..., }n nA a a и ' ' 1( ( ) , )\|i mf j w H  – комбинатор- ную функцию, аргументом которой будет комбинатор- ная конфигурация ' 'iw W , образованная из элементов базового множества 1{ ,..., }m mA a a   , H и 'H соответ- ственно – системы этих функций. Если ( ( ) ,f j 1 ' 1 1 1)\| ( ( ) , )\| ,m mw f 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 , назовем упорядоченной. Оценка точности методов, используемых при ре- шении задач на множестве перестановок УСиМ, 2016, № 2 17 Рассмотрим задачи комбинаторной оптимизации, ар- гумент целевой функции в которых – перестановка. Для оценки их точности используем подклассы разрешимых задач и способ определения множества значений целе- вой функции [10]. Поскольку упомянутая упорядочен- ная задача – известный разрешимый случай [11], то для базовой задачи несложно найти область определения целе- вой функции. Для системы 'H известны перестановки, для которых выражение (1) принимает глобальное наи- большее или наименьшее значение. Если элементы комби- наторной функции из системы 'H упорядочены от боль- шего элемента к меньшему, а элементы функции нату- рального аргумента упорядочены от меньшего элемента к большему, то значение (1) есть глобальным минимумом. Если элементы обеих таких функций упорядочены от меньшего элемента к большему, то значение (1) – глобаль- ный максимум. Этот разрешимый случай не принадлежит ни одному классу из классов задач комбинаторной опти- мизации. Приведем теорему [10]. Теорема 1. Значение целевой функции ( )kF w для задач комбинаторной оптимизации, аргумент которой – перестановка, находится в пределах: 't ' 't w max ( ) W F w   ' ' '( ) min ( ), i k i w W F w F w    ' ' i ', ,tw w W kw W . В случае минимизации значение целевой функции находится в пределах ' ' min ( ) ( ) i i k w W F w F w F    . В случае максими- зации – в пределах ' '( ) max ( ) t k t w W F F w F w    , где '' ' ' ' * ' max ( ) min ( ) min ( ) it i t i w Ww Wi w W F w F w F F w       , а  – коэф- фициент уменьшения области поиска оптимального ре- шения, которое уточняется в процессе работы алгорит- ма, ' ''t ' 't ' w max ( ) , min ( ) i i w WW F w F w  – вычисленные глобальные максимум и минимум упорядоченной задачи. Доказательство в [10]. Оценку точности решения задачи при известном глобальном минимуме вычисляем по выражению k* min min ( , ( )) 1 100% ( )k FF F w F w         (или max( , ( ))iF F w  * max ( )1 100% iF w F        в случае максимизации), где minF – глобальный минимум задачи, maxF – соответственно глобальный ее максимум, ( )kF w , ( )iF w – получен- ное максимальное или минимальное решение этой зада- чи определенным алгоритмом. Эксперимент показывает, что чем больше размерность задачи, тем меньше погре- шность (в процентах) полученного результата по отно- шению к глобальному оптимуму. Положим, что алгоритм (метод) сходимый, если после- довательность построенных решений приближается к ну- лю, т.е. k* min( , ( )) 0F F w  (или * max( , ( )) 0).iF F w  Среди полученных решений может быть такое, для ко- торого * min( , ( )) 0kF F w  (или * max( , ( )) 0).iF F w  При этом скорость сходимости – полиномиальна по вы- числительной сложности. Приведем подкласс разрешимых задач из класса за- дачи коммивояжера. Если для них * min( , ( )) 0kF F w  , то оптимальное решение, полученное определенным алгоритмом, совпадает с глобальным решением. Задача коммивояжера заключается в следующем: за- дано некоторое количество городов, расстояние между которыми известно. Необходимо найти кратчайший путь, который будет гамильтоновым циклом. Под гами- льтоновым циклом подразумеваем путь в графе, кото- рый начинается в заданной вершине, проходит через все вершины один раз и возвращается в начальную. Этот цикл в задаче коммивояжера назовем маршрутом. Обозначим маршрут 1 1( , )\| ( ( ,1),..., ( , ))k n k k nu w l u w u w n , где ( , ) ( ( ) , ) ( )k k l ju w l f j w j  , если ( ) 0j  , {1,..., }j m , а uH – их множество. По определенным правилам разобъем uH на подмножества 1 2, ,...,H H 2nH  . Соответственно на подмножества 1 2 2, ,..., nK K K  разбивается и множество перестановок. Положим {2, 4, ..., 2 }Z j , 1 {1, 3, ..., 2 1}Z j  . Теорема 2 (действительна для 4n  ) [6, 12]. Если в задаче коммивояжера комбинаторная функция 1 1( ( ), )\| (1,..., )mf j w m  , то наибольшее значение целе- вая функция (1) принимает для перестановки * (1, 3, 5, 7 ,..., 8, 6, 4, 2)iw  , (2) для которой * 1 iw K , а наименьшее значение – для пе- рестановки 1 2 3 4 5 6 7 4 3 2 1 1 1 2 3 4 5 6 2 * 1 2 2 2 2 ((1) , ( 1) , (3) , ( 3) , (5) , ( 5) , (7) , ... ...( 4) , (4) , ( 2) , (2) , ( ) ), если , (( ) , (2) , ( 2) , (4) , ( 3) , (6) ,..., , 2 1 , 1 , 2 2 3 2 n n n n n n k n n n n n n n n n n Z nn n n n nw n                                        3 4 2 3 2 1 , 3 , ... , 2 ( 3) , (3) , ( 1) , (1) ), если , n n n n n n n n n Z                          (3) для которой 2 *  n k Kw , где 1 0, если , 2 2, если . 2 n Z n Z        18 УСиМ, 2016, № 2 Наибольшее значение целевой функции равняется 3 6)83()( 2 *   nnnwF i , а нименьшее – соответст- венно 2 * (5 4)( ) 24 k n nF w   , если n Z , и ( )kF w  2(5 7) 12 24 n n    , если 1n Z . Доказательство. Если 4n  , то наименьшее и наи- большее значения целевой функции совпадают, поэтому этот вариант не рассматриваем. Сначала докажем, что ( ) ( )i kF w F w . Для iw запишем маршрут * 1 1 1( , )\| ( ,i nu w l v v  2 3 4 2 11, 1, 1, 1,..., 1, ),n nv v v v v      где jv  ( 1) (2 ) 1 2 j n j    – номер элемента в j-й строке гами- льтоновой диагонали. Сумма членов этой последователь- ности 1 * 1 ( ) 1 2 n i j j F w v n        1 1 ( 1) (2 ) 1 2 n j j n j          2( 3 5)1 1 1 3 n n nn n        = 2( 3 8) 6 3 n n n   . Для kw запишем маршрут 1 1 1 2 2( , )\| ( ( 3), ( 2), ( 5), ( 3),k nu w l v n v n v n v n         3 3 4 4 5 1 1 ( 7), ( 5), ( 9), ( 7), ( 11) ,..., 1, v n v n v n v n v n v v               (4) 3, , 1)v v   , если n Z , * 1 1 1 2 2( , ) \| ( ( 3), ( 2), ( 5), ( 3),k nu w j v n v n v n v n         3 3 4 4 5( 7), ( 5), ( 9), ( 7), ( 11),...v n v n v n v n v n          (5) 2 2 1 1..., ( 2), ( 4), , 2, ),v n n v n n v v v           если 1n Z , где 1 2 n       . Найдем суммы членов последовательностей (4), (5). Если n Z , то 2 * 1 ( ) 2 n k j j F w v    2 1 2 2 ( 2) ( 1) (2 ) ( 2)2 1 2 2 2 (5 12 28) ( 2) (5 4) . 24 2 24 n j n n j n j n n n n n n n n n                      Если 1n Z , то 1 2 * 1 ( 1) (2 )( ) 2 1 2 n k j j n jF w            2 2( 1)(3 1) 2 1 (5 21 43) 271 8 2 24 n n n n n n n            2 3( 1)(3 1) 2 1 5 7 121 8 2 24 n n n n n n          . Для n Z докажем, что 2( 3 8) 6 3 n n n    > 2(5 4) . 24 n n  После несложных преобразований получим 3 28 20 16 0 8 n n n    . (6) Для 6n  , для которого ( ) 50iF w  , ( ) 46kF w  , неравенство (6) примет вид: 4 0 . Следовательно, для любого n > 4 левая часть неравенства (6) всегда положительна. Для 1n Z запишем неравенство 2 3( 3 8) 6 5 7 12 3 24 n n n n n      . После несложных пре- образований получим 3 28 19 12 0 8 n n n    . Очевид- но, что для любого n > 4 левая часть этого неравенства также всегда положительна. Докажем, что для любой перестановки w t в сравне- нии с iw значение целевой функции не увеличивается, а в сравнении с kw – не уменьшается. Возьмем пере- становку, при образовании маршрута которой из каждой строки h наддиагоналей матрицы C выбран наименьший элемент. Запишем ее как (1, 2, 3,..., )tw n (тур Масте- ра). Соответственно для нее запишем маршрут 1 1 2 2 1( , ) \| ( , ,..., , , 1),t n n nu w l v v v v n   а значение ( )tF w  1 1 n j j v    1n   2( 3 8) 6 3 n n n   , т.е. ( ) ( )t iF w F w . Итак, для тура Мастера, маршрут для которого образован вы- боркой по одному наименьшему элементу из каждой t-й строки матрицы 1( )Q w , 2, 1t n  , целевая функция в сравнении с kw не уменьшается и равна ( )iF w . В перестановке kw для n Z проведем транспози- цию элементов 3( 2)n  и 1( 1)nn  . Для перестановки 3 t nw K  в маршруте 1( , )\|t nu w l два элемента увели- чились на единицу и два элемента уменьшились на еди- ницу, а ( ) ( )t kF w F w . В kw проведем транспозицию элементов 3( 2)n  и 1( )n . Полученная перестановка w t также находится в подмножестве ( 3)n  , а в соответ- ствующем маршруте два элемента увеличились на два и два элемента уменьшились на два, а ( )tF w ( )kF w . Если в kw провести транспозицию элементов 2 n и n, то полученная перестановка w t будет находиться в по- дмножестве 1 2 n  , а в соответствующем маршруте два элемента уменьшатся на 2 n . Элемент 2 nv поменяется УСиМ, 2016, № 2 19 местами с элементом 2 2nv n  , а 2 1nv  – с элементом 2 3 101 2n nv    . Целевая функция в этом случае увели- чится на 3 14 2 n  , а ( ) ( )t kF w F w . Итак, если при образовании маршрута элементы вы- бираются по два из первых 1 2 n      строк матрицы C, то целевая функция уменьшается. Если маршрут обра- зован выборкой элементов из строк по номерам больше, чем 1 2 n      , то целевая функция увеличивается. Таким образом, наибольшее значение целевая функция прини- мает для перестановки (2) и 1 iw K , при ( ( ) ,f j 1 1)\| (1, ..., )mw m , а наименьшее – для перестановки (3) и * 2 k nw K  , что и доказывает теорему 2 для n  Z. Аналогично теорема 2 доказывается для n  Z1. Теорема доказана. Следствие 1. Если значение комбинаторной функции 1 0( ( ), )f j w k j b   или 1( ( ), ) 2 jf j w  , 1,j m , k0, b > 0 – целые произвольные числа, то наибольшее значение целевая функция принимает для перестано- вки (2), соответствующий маршрут которой * 1 1( , ) \|i nu w l H и * 1 iw K , а наименьшее значение – для перестановки (3), соответствующий маршрут для которой * 1 2( , ) \|k n nu w j H  и * 2 k nw K  . Теорема 3. (действительна для n > 4). Если комби- наторная функция 1 1( ( ) , )\| ( ,..., 1)mf j w m  (матрицы Демиденко, Кальмансон), то наибольшее значение це- левая функция принимает для перестановки (3), соот- ветствующий маршрут которой * 1 2( , )\|i n nu w l H  , а наименьшее значение – для перестановки (2), соответ- ствующий маршрут которой * 1 1( , ) \|k nu w l H . Наиме- ньшее значение целевой функции равно k( )F w  3 23 10 12 6 n n n    , а наибольшее – соответственно ( )iF w  3 27 12 20 24 n n n  , если n Z , и (w )iF  3 27 12 17 12 24 n n n    , при n  Z1. Доказательство теоремы 3 аналогично доказатель- ству теоремы 2. Доказательство сходимости методов и алгорит- мов, основанных на распознавании структуры вход- ной информации. Докажем сходимость метода струк- турно-алфавитного поиска [13], «жадного» алгоритма и метода ближайшего соседа с использованием приведен- ных подклассов разрешимых задач для задачи коммиво- яжера. Теорема 4. Метод структурно-алфавитного поиска сходится, если для подклассов разрешимых задач пост- роением не более чем 2 2 n перестановок он обеспечива- ет поиск упорядоченной последовательности локальных экстремумов 1 2( (w ), ( ) ,..., ( ))kF F F w F w таких, что min( , ( )) 0kF F w  , среди которых существует такой, для которого * min( , ( )) 0kF F w  , при * 2, {1,..., 2}k k n . Для доказательства теоремы 4 сформулируем такие леммы. Лемма 1. Если для упорядоченной задачи коммивояже- ра первые n значений '( ( ), w )tf j  (или '( ( ), )if j w  ), 1,j m , образуют маршрут (гамильтонов цикл), то ' * 1 1( ( ) , ) \| ( ( ) , ) \|t m k mf j w f j w    (или ' 1( ( ), ) \|i mf j w   * 1( ( ) , )\|k mf j w  ), а Wwk * есть глобальное реше- ние базовой задачи; ' 1( ( ) , )\|t mf j w  , ( ( ) ,f j  ' ' 1) \|i mw H , * 1( ( ) , ) \|k mf j w H  , 'H H . Доказательство очевидно. Лемма 2. Если базовая задача коммивояжера задана функцией натурального аргумента 1 1( ( ), w ) \|mf j , кото- рая изменяется как монотонная (неубывающая или не- возрастающая), то для нахождения по упорядоченной задаче глобального решения методом структурно-алфа- витного поиска необходимо построить не более чем 2 2 n перестановок. Доказательство. Рассмотрим задачу коммивояжера, в которой комбинаторная функция меняется как монотонно неубывающая. Положим, что 1 1( ( ), ) \| (1, ..., )mf j w m  – линейная функция. Эту задачу сведем к упорядоченной. Запишем ' 1( ( ), ) \| (1, ... )t mf j w m   , а 1 1 2( ) \| ((1) , (1) ,...mj   , 1(1) , (0) ,..., (0) ).n n m Построим для нее последователь- ность локальных экстремумов. Как следует из теоремы 2, для задачи коммивояжера, входные данные в которой заданы функцией 1 1( ( ) , ) \| (1, ..., )mf j w m  , наиболь- шее значение целевая функция принимает для переста- новки (2) в подмножестве 1K , а наименьшее – для пере- становки (3) в подмножестве 2nK  . Чтобы получить пе- рестановку в подмножестве 2nK  , необходимо зафикси- ровать в ней элементы в таком порядке ( ..., 1, 1, ,...n n ) или по комбинаторной функции ' 1( ( ), ) \| (1, ..,. )t mf j w m   последовательно построить n – 2 перестановки, начиная со значения '( (1), ) 1tf w   , '( (2), ) 2tf w   и закан- 20 УСиМ, 2016, № 2 чивая '( ( 2), ) 2tf n w n     , т.е. из 1n  элементов наддиагональной строки матрицы выбрать два элемента, которые в сочетании с элементами других строк обра- зуют маршрут (соответственно образуется и перестанов- ка), для которой значение целевой функции – наимень- ше. Для '( (1) , ) 1tf w   полученная перестановка при- надлежит подмножеству 1K , для '( ( 2 ) , ) 2tf w   она принадлежит 2K , а для '( ( 2 ) , ) 2tf n w n     – соо- тветственно к 2nK  . Для заданной структуры входных данных среди маршрутов, которые с первой строки мат- рицы содержат элементы 2n  и 1n  , – кратчайшие. Комбинацией элементов со второй строки матрицы в подмножестве 2nK  найдем меньшее подмножество, содержащее глобальный минимум. Для этого зафикси- руем значения '( ( 2 ) , ) 2tf n w n     и ( ( 1) ,f n   ' ) 1tw n  , пропустим '( ( ), )tf n w n   (для него пере- становка уже построена) и, начиная с ( ( 1) ,f n   ' ) 1tw n  , затем с '( ( 2), ) 2tf n w n     строим сле- дующие перестановки. Для перестановки, где целевая функция – наименьшая, маршрут со второй строки мат- рицы содержит элементы '( ( 2 5) , ) 2 5tf n w n     и '( ( 2 3) , ) 2 3tf n w n     . Количество построенных пе- рестановок равно 3n  . Аналогично, комбинацией эле- ментов из каждой строки выберем по два элемента так, чтобы полученный маршрут был самым коротким. Ко- личество построенных перестановок для каждой строки равно ( 1)n s  , где s – номер строки матрицы. Поло- жим, что их количество равно n. Маршрут, которому соо- тветствует перестановка * ((1, 1, 3, 3, 5, 5,kw n n n    7 ,..., 4, 4, 2, 2, )n n n  , содержит по два элемента из 1 2 n      наддиагональних строк матрицы ( )kQ w и яв- ляется глобальным минимумом (выражение (3)). Итак, чтобы найти глобальный минимум для задачи коммиво- яжера, входные данные в которой заданы ' 1( ( ) , ) \| (1, ..., )t mf j w m   , строится последовательность решений не более чем 2 2 n перестановок, что и доказы- вает лемму 2 для линейной функции. Для задачи коммивояжера, входные данные в кото- рой задаются комбинаторными функциями, которые меняются как монотонные (неубывающие или невозрас- тающие), лемма 2 доказывается аналогично. Лемма 2 доказана. Лемма 3. Если базовая задача коммивояжера задана функцией натурального аргумента, содержащей не ме- нее 5 1 4 n  наименьших одинаковых значений и они образуют маршрут (гамильтонов цикл), то метод структур- но-алфавитного поиска сходится, если для подклассов разрешимых задач с построением не более 2 2 n переста- новок он обеспечивает нахождение упорядоченной после- довательности локальных экстремумов 1( (w ),F F 2( ) ,..., ( ))kF w F w таких, что * min( , ( )) 0kF F w  , среди которых существует такой, для которого min( ,F ( )) 0kF w  , где 2 , {1,..., } 2 nk k  . Доказательство. Лемму 3 доказываем методом ма- тематической индукции. Рассмотрим задачу, входные данные в которой заданы комбинаторной функцией 1 ' ' 1 1( ( ) , ) \| ( , , , ,..., , )m m mf j w c b c b c b  , где ' 1 , если , , если , c m Z c b m Z     1' , если , , если , c m Z b b m Z     c b , {2, 4,..., 2 }Z j , 1 {1, 3, ..., 2 1}Z j  . Сведем ее к упоря- доченной. Запишем 1 1 2 1( ) \| ((1) ,(1) ,..., (1) ,(0) ,..., (0) ),m n n mj    а ' 1 1 2 1( ( ), ) \| (( ) , ( ) ,..., ( ) , ( ) )t m m mf j w c c b b   . Количество наименьших значений c в ' 1( ( ) , w )\|t mf j  больше чем 5 1 4 n  и для них выполняются условия существования гамильтонова цикла [14]. Как доказано в [15], наимень- шее значение целевой функции для {5, 6}n  , равно ( 1)n c b  , поэтому эти варианты не рассматриваем. Поскольку значение целевой функции зависит от пар- ных и непарных n, 2 n , 3 2 n  и перестановки для них – разные [15], то лемму 2 доказываем для {7, 8, 9, 10}n  . Проведем поиск перестановки (гамильтонова цикла), для которого целевая функция равна ( )kF w nc . Зна- чение c в 1 1( ( ) , )\|mf j w пребывают в позициях с не- четными номерами, поэтому глобальный минимум ищем в подмножествах sK , где 1s Z . Положим 7n  . Начиная с '( (1) , )tf w c   и '( (2 ) , )tf w c   , построим перестановку  1w  (4, 1, 2, 3, 5, 7, 6) . Для нее значение целевой функции равно 1( ) ( 1) .F w n c b   Пропустим ( (2),f  ' )tw c и, начиная с '( (1), )tf w c   и '( (3) , )tf w   c , построим следующую перестановку  2 (6, 1, 2, 3, 5, 7, 4),w  для которой 2( )F w  ( 2) 2 .n c b   Поскольку значение целевой функции уве- личилось, возвратимся к предыдущим '( (1) , )tf w c   и '( (2) , )tf w c   , а во второй строке матрицы проведем УСиМ, 2016, № 2 21 перебор элементов c, т.е. пропустим '( (3), )tf w c   , учтем '( (4), )tf w c   и получим перестановку  )6,7,3,5,2,1,4(3 w , для которой 3( )F w n c . Итак, глобальный минимум для 7n  , если 1n Z , 1( 3) 2n Z  , найден в 1K построением трех переста- новок. Положим 8n  . Аналогично предыдущему вариан- ту методом структурно-алфавитного поиска построим перестановки:  1 (7, 3, 5, 4,1, 2, 6, 8)w  , для которой 1( ) ( 1)F w n c b   ;  2 ( 6,1, 2, 4, 5, 3, 7, 8)w  , для которой 2( ) ( 1)F w n c b   ;  3 (4,1, 2, 8, 6, 7, 3, 5)w  , для которой 3( ) ( 1)F w n c b   ;  4 (4, 1, 2, 6, 8, 5,w  3, 7) , для которой 4( )F w n c . Глобальный минимум для 8n  , если n Z , 2 n Z , в подмножестве 1K найден построением четырех пере- становок. Положим 9n  . Построим перестановки:  1w (9, 7, 6, 4, 1, 2, 3, 5, 8) , для которой 1( )F w  ( 1)n c b   ;  2 (6, 1, 2, 3, 5, 9, 7, 8, 4)w  , для которой 2( )F w  ( 2) 2n c b   ;  3 (4, 1, 2, 5, 3, 7, 8, 9, 6)w  , для которой 3( )F w  ( 2) 2n c b   ;  4 (4, 1, 2, 3, 7, 9, 8, 5, 6)w  , для которой 4( )F w  ( 1)n c b   ;  5 (4,1, 2, 3, 7, 9,w  6, 5, 8) , для которой 5( )F w n c . Глобальный минимум для n – 9, если n  Z1, (n + 3) /2   Z, найден в K1 построением пяти перестановок. Положим n – 10. Используя описанные правила, по- строим перестановки:  1 (4, 1, 2, 6, 8, 10, 9, 7, 3, 5)w  , для которой 1( )F w  ( 1)n c b   ;  2 (6, 1, 2, 4, 5, 3,w  7, 9,10, 8) , для которой 2( )F w  ( 1)n c b   ;  3 (4,1, 2, 8, 6,10, 9, 7, 3, 5)w  , для которой 3( )F w n c . Глобальный минимум для n – 10, если n  Z, n /2 Z1, найден в K1 построением трех перестановок. По индукции, если для задачи с произвольным n матрица содержит одинаковые элементы, из которых образуется маршрут, то для нахождения глобального минимума в этом случае необходимо провести последо- вательный перебор элементов для каждой строки отде- льно. Поскольку в каждой строке для периодической функции со значениями { , }c b может быть 2 n     эле- ментов c, то для нахождения гамильтонова цикла необ- ходимо построить не более 2 2 2 n nn  перестановок, что и доказывает лемму 3, когда входные данные заданы периодической функцией натурального аргумента, или другой функцией, содержащей не менее 5 1 4 n  наимень- ших одинаковых значений и они образуют маршрут (га- мильтонов цикл). Справедливость теоремы 4 для задачи коммивояжера следует из лемм 1 и 2. Теорема 4 доказана. Следствие 2. Если в задаче коммивояжера комбина- торная функция 1 1( ( ), ) \| (1, ..., )mf j w m  , то по прави- лам метода ближайшего соседа при поиске минималь- ного значения целевой функции приведенного разреши- мого случая найдена перестановка * (1, 3, 5, 7 ,...iw  , 8, 6, 4, 2) , которая служит для него глобальным мак- симумом, т.е. сходимостью метода * min( , ( )) 1kF F w  . Если в задаче коммивояжера комбинаторная функ- ция 1 1( ( ), ) \| (1, ..., )mf j w m  , то по правилам «жадного» алгоритма при поиске глобального максимума получим глобальный минимум, т.е. сходимость алгоритма равна * min( , ( )) 0kF F w  . Для обоих случаев скорость сходимости равна одной итерации. Следствие 3. Если в задаче коммивояжера комбина- торная функция 1 1( ( ), )\| ( ,..., 1)mf j w m  , то по прави- лам метода ближайшего соседа при поиске минималь- ного значения целевой функции приведенного разре- шимого случая найдена перестановка (3), которая есть для него глобальным минимумом, т.е. сходимость мето- да равна * min( , ( )) 0kF F w  . Если в задаче коммивояжера комбинаторная функ- ция 1 1( ( ), )\| ( ,..., 1)mf j w m  , то по правилам «жадного» алгоритма при поиске глобального максимума получаем глобальный минимум, т.е. сходимость алгоритма равна * min( , ( )) 1kF F w  . Для обоих случаев скорость сходимости равна одной итерации. Изложенный в следствиях 2 и 3 результат объясняет- ся тем, что в этих методах не проводится анализ по выя- влению факторов, влияющих на значение целевой фун- кции в зависимости от комбинации элементов входных данных. Заключение. Итак, сходимость методов, основанных на распознавании структуры входной информации, можно доказать с использованием подклассов разрешимых задач. Окончание на стр. 27 УСиМ, 2016, № 2 27 Окончание статьи Н.К. Тимофеевой Так, сходимость последовательности решений, постро- енных методом структурно-алфавитного поиска для за- дачи коммивояжера приближается к нулю, т.е. k* min( , ( )) 0F F w  , а для подклассов разрешимых задач * min( , ( )) 0kF F w  . Ее скорость – полиномиальна по вычислительной сложности. Сходимость метода бли- жайшего соседа и «жадного» алгоритма зависит от структуры входных данных. Для одних структур реше- ние равно * min( , ( )) 0kF F w  , а для других может быть * min( , ( )) 1kF F w  . Это решение, как правило, достига- ется за одну итерацию. UDC УДК 519.816 N.К. Tymofijeva The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems Keywords: combinatorial optimization, combinatorial configuration, objective function, traveling salesman problem, structure-alphabetical search method, nearest neighbor method, «greedy» algorithm. The proof of the approximate solutions convergence sequence to a global solution of the combinatorial optimization problem, which is based on a particular algorithm, is rather complicated problem. This is due to the fact that some classes of problems are unsolvable because of their computational complexity. A lot of researches are devoted to the problem of the methods and algorithms convergence within the mathematical programming. They enter the formal level features required and sufficient conditions for their convergence. The original way to prove some convergence combinatorial optimization methods, based on recognition of the structure of input data (structure-alphabetical search method nearest neighbor method, “greedy” algorithm) is presented. For this purpose, the subclasses of the traveling salesman problems is used. A sequence of the convergence solutions that are built specifically is proved. To assess the methods accuracy, which are decided on a set of permutations, the input data of combinatorial optimization problems defines the functions of the natural argument, one of which is combinatorial. This allows to define a set of values of the objective function for basic problem and to establish some error of interpretation algorithm. An solvable case for the traveling salesman problem is shown, in which the input data requires the linear combinatorial function for which analytically the global minimum and maximum are found. Using this case proves that the convergence of a solutions sequence built by the structural alphabet search for the traveling salesman problem is close to zero. The optimal solution for subclasses coincides with the global. The speed of the described method is polynomial of computational complexity. The convergence of the nearest neighbor method and of the “greedy” algorithm depends on the structure of input data. For some, the solution structures coincides with the global, while others may be far from optimal.  << /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