автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Парметрические задачи и стойкость при моделировании евклидовыми комбинаторными задачами оптимизаций

ДШПРОПЕТРОВСЬКИЙ ДЕРЖАВНЫЙ УН1ВЕРСИТЕТ

«6 ОД , 9 «*

РОСКЛАДКА АНДР1И АНАТОЛШОВИЧ

УДК 519. 85

ПАРАМЕТРИЧН1ЗАДАЧ1 ТА СТ1ЙК1СТЪ ПРИ МОДЕЛЮВАНН1 ЕВКЛЩОВИМИ КОМБ1НАТОРНИМИ ЗАДАЧАМИ ОПТИМ13А1Щ

«яг./з./*

01.05.01 - теоретичш основи шформатики та юбернетики

Автореферат дисертащ!' на здобугтя наукового ступени кандидата ф1зико-математичних наук

Дншропетровсыс - 2000

Дисертащею е рукопис.

Робота виконана в Полгавському державному техшчному ушверсите™ 1меш íOpifl Кондратюка Мшстерства освгги i науки УкраТни

Науковий кер1вник: доктор ф1зико-математичних наук, професор Смець Олег Олексшович,

Полтавський державний техшчний ушверситет ÍMeHi Юрш Кондратюка, завщувач кафедри прикладно'1 математики та математичного моделювання.

Офщшш опоненти: доктор фЬико-матемагичних наук, професор Ляшенко Ггор Миколайович, Нацюнальний ушверситет ¡мет Тараса Шевченка (м. Кшв), зав1дувач кафедри математичних метод!в еколого-екожтчних досшджень; кандидат ф!зико-математичних наук, доцент Рева Володимир Миколайович, Дншропетровський державний университет, доцент кафедри обчислювально\' математики та математично! габернетики.

Провщна установа: 1нститут мбернегики ím. В. М. Глушкова HAH Укра'ши, вщщл методов розв'язування складних задач оптишзацп, м. КиТв.

30

Захист вщбудеться " 09, 2000 р. о годиш на засщанш спещал!зовано1 вченоТ ради К 08.051.09 при Дшпропетровському державному ушверсите-п за адресою: 49044, м. Дншропетровськ, проспект Карла Маркса, 35, кори, 3, ауд. 42.

3 дисертащею можна ознайомитися у б1блштещ Дншропетровського державного ушверситету за адресою: 49050, м. Дшпропетровськ, вул. Козакова, 8.

Автореферат розкланий Л1Л-¥ШХ~ 2000р.

Вчений секретар спещал1зованоГ вчено! ради

Турчина В. А.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальность теми. В осташпй час значно розширилася область застосувашш метод1в дискретного програмування. Цьому сприяв той факт, що багато важливих задач проектування, планування, розмщення i управления добре описуються за допомогою моделей дискретного програмування. З'явилася велика кшьгасть публжацш, в яких пропонуються HOBi шдходи до розв'язку задач дискретно! опттшацп взагал1 i комбшаторноГ оптим1зацп зокрема, дослщжуеться ефективнють вщомих метод ¡в, описуються створеш програмш засоби, яга призначеш для реашзацп системного гпдходу до розв'язку цих оптим1зацшних задач на ЕОМ. Зусилля багатьох вчених та наукових колектив1в спрямоваш на розробку ше! проблематики. Серед вЬчизняних в першу чергу треба вщзначити колективи, яга працюють тд кер!вництвом академшв HAH УкраТни I. В. CepricHKa, Н. 3. Шора, член.-кор. HAH Украши 10. Г. Стояна.

Великого практичного значения при розв'язувант задач набувають питания CTifiKOCTi отртшаних розв'язюв та параметричний анаги'з задач. Под1бн1 дослщження для задач дискретного програмування в останш десятир!ччя склали нову область, яка ¡нтенсивно розвиваеться. Необхщшсть у проведенш параметричного аиал1зу виникае в зв'язку з тим, що в задачах оптим1зацп в бьтылосп випадюв в1дом1 ¡нтервали змши даних, а не i'x точш значения. Це обумовлено насамперед тим, що багатьом факторам, яы характеризують реальш процеси, властива невизначешсть. Насшльки ж великою може бути вказана похибка, щоб вона не впливала на змшу оптимального розв'язку задач!. Под1бш питания з'ясовуються при аналЫ ст1Йкост1 вщповщних оштпзацшних задач. Методами параметричного програмування можна ефективно розв'язувати економ1чш задач^ в яких початков! дан!, необхщш для i'x розв'язування (варттсть виробництва одинищ продукцп, кшьюсть запаав сировини, енергн, величина катталовкладень) змшюються в чаек

В останш десятир1ччя суттевий прогрес в теорп оптим^зацп прив!в до видшення з широкого класу задач дискретного програмування задач на комбшаторних множинах, а евклщова комбшаторна оптим1защя розглядаеться як важливий аспект комбшаторноУ оптим1зацй'. Роботи в цьому напрямку проводяться в наукових колективах, якими керують Ю.Г. Стоян, С. В. Яковлев, О. О. Смець. Парам етричш задач! евклщовоТ комбшаторноТ ornmmaniT е невивченими i тому i'x дослщження е актуальною задачею.

Робота присвячена дослщженню евклщових комбшаторних множин сполучень, а також розмвдень, з точки зору задач параметричноУ оптим1зацй на них, розробщ шдходгв та метод ¡в i'x розв'язування.

Зв'язок роботи з науковими програмами, планами, темами. Дисертацшна робота виконувалась на кафедр! прикладно!' математики та математичного моделювання Полтавського державного техшчного ушверситету ¡меш IOpifl Кондратюка згщно з ¡ндивщуальним планом acnipaHTCbKoi шдготовки та планами науково-дослщно'1 роботи ушверситету.

Мета i задач! дослвджсння. Метою роботи е дослщження параметричних задач на множинах сполучень i розмщень та розробка метод ¡в i алгоритм ¡в i'x розв'язування.

Основними задачами дослщження с:

- розробка метод! в та алгоритм!в розв'язування параметричних задач евюпдово!' комбшаторноТ оптилпзацп з лшшною цшьовою функщею на сполученнях та розмпценнях;

- алгорит.чшащя побудови опукло! оболонки загально!' множини сполучень i розробка метод1в пошуку вершин вщповвдного многогранника;

- застосування параметричних задач оптимдзацй' на комбшаторних множинах до побудови моделей практичних задач.

Наукова новизна одержаних результатов.

- посилен! оцшки екстремальних значень сильно опуклих функцш при оптим1зацп на сполученнях;

- запропонован! та обгрунтоваш методи та алгоритми розв'язування параметричних задач на евюидовш комбшаторнш множит сполучень з повторениями та загальшй множит розмщень;

- проанал!зоваш розроблеш алгоритми та доведена 'ix ефектившсть для множини сполучень;

- розроблено модифшований алгоритм пошуку аналитичного вигляду загального многогранника сполучень;

- отримано новий критерш г'-граш довшьного многогранника.

Практичие значения одержаних результате полягае:

- в створенш математичних моделей задач! про варткть перифершних пристрош та задач i про об'еднання електростанцш в енергосистему.

- в розробщ атгоритм1в розв'язування задач з параметрами в лшшнш цшьовш функцп та в систем! обмежень, що дозволяе знаходити оптимальш розв'язки для моделей, яю сформульован! у вигляд! таких параметричних комб!наторних задач на евюидових множинах.

Особистий внесок здобувача. Bei результата дисертацшноТ робота, що виносяться на. захист, отримаш особисто автором. У працях, написаних у cnißaBTopcTBi, дисертанту належать:

[1] - доведения теорем про нов1 посилен! оцшки м!н1мум!в сильно опуклих функцш при м1Н1м1зап,!У на множит сполучень з повторениями;

[2] - розробка та обгрунтування алгоршлйв розв'язування двох параметричних задач на множит сполучень з повторениями, проведения анашзу ефективност! дих алгоритм!в;

[3] - модифжащя алгоритму побудови опукло'! оболонки i його застосування до побудови аналогичного опису загального многогранника сполучень у вигляд! системи лшшних нер1вностей;

[4] - оптамзащя оцшок екстремальних значень диференцшованмх сильно опуклих функцш;

[5] - розгляд магематично!' модел! вибору оптимально!' шдмножини задач на ЕОМ як задач! евюпдово!' комбшаторно"! оптим!зац!!' на сполученнях;

[6] - обгрунтування алгоритму розв'язування загально!' параметрично!' задач! при оптим!зацп на сполученнях;

[7] - використання властивостей евюпдово!' множини сполучень для побудови математично!" модел! задач! мш!м!зацп вартост! перифер!йних пристрош.

Анробащя результате дисертаци. Основн! результата робота

доповщалися та обговорювалися на:

- VII мшнароднш науковш конференцй ímchí академжа М.Кравчука (Кшв, 1998 );

- Мгжнароднш науковш конференцй' «Розробка та застосування математичних метод1В у науково-техшчних доЫдженнях» (Льв1в, 1998);

- М1жнароднш школ1 з актуарноТ та фшансовоТ математики (Кшв, 1999);

- 49-52 наукових конференшях професор!в, викладач1в, наукових ствробшшшв, acnipairr'm i студенев Полтавського державного техшчного университету ¡меш Юр1я Кондратюка ( Полтава, 1997-2000);

науковому ccMinapi вщдшу математичного моделювання та геометричного проектування 1нституту проблем машинобудування HAH УкраГни (Харюв, 1998);

науковому ceMÍHapi кафедри обчислювально!" математики та математичноТ кибернетики Дшпропетровського державного ушверситету (Дншропетровськ, 1999).

Публ1кащТ. Результата дисертацшно1 робота опублковаш у 3 статтях у фахових наукових журналах [1-3], 3 статтях у фахових зб1рниках наукових праць [4-6], матер!алах конференцй [7].

Структура та обсяг дисертаци. Дисертац1я складаеться 3¡ вступу, п'яти роздшв, bhchobkíb, списку використаних джерел з 129 найменувань, 2 додатюв. Усього - 142 сторшки.

ОСНОВНИЙ 3MICT

• У встут обгрунтовано актуальшсть теми, сформульовано мету й задач! дослщження, вказано наукову новизну одержаних результата, Гх теоретичну цшшсть та практичне значения.

У першому роздЫ проведено огляд результатов з Teopií criñKOCTi оптим^зацшних задач та комбтаторнсн Teopií многогранштв. Зроблено висновки про актуальшсть дослщження задач евюпдово!' комбшаторноУ оптим1заци та евклщових комбшаторних множин.

Наведено означения i твердження, яю е необхщними при виклад1 наступних роздгав дисертаца.

Нехай J„- множина п перших натуральних чисел, тобто

7„ = {l,...,«},J° = /nu{o},/o=0. Пщ мультимножиною G= |g„ g2,--,gn)

розумшть сукупшсть елемент1в, серед яких можуть бути i однаковь Мультимножина, bcí елементи якоТ p¡3HÍ, е множиною. Будь-яку мультимножину А можна задати i'í основою S(A), тобто множиною bcíx i"í р1зних елеметпв, i кратн1'стю - числом повторень кожного елемента основи uic'í мультимножини. Список кратностей мультимножини називають i"í первинною специфжащею i позначають через [ Л].

Розглянемо упорядковану к -виб1рку з мультимножини G \

e=[girgi2,-,gik), (1)

де g¡_ gG, ij т± i, V ij,it e/,, Vj, t eJk,

Множину Е, елементами яко'1 е к -виб1рки з мультимножини б ё = е = (еи...,ек) вигляду (1), називають евюндовою

комбшаторною множиною, якщо з умови 3/ е Jk, ëJ * е^ випливае ё Ф е . Розглянемо означения необхвдних евклщових комбшаторних множин. Загальна множина ^-розмщень. Нехай 0 = ^], g2,■..,gц^, мультимножина з основою 5'(С) = |е[, е2е„} та первинною сиецифжащею [С] = {г)15 г\2>---,т\к}, Де Т1,<£ У/е^. Сукупшсть уах упорядкованих к -виб1рок вигляду (1) з мультимножини й називають загальною множиною к -розмщень 1 позначають Акп(й).

Множина &>сполучень з повторениями з п_ р1зних дтсних чисел. Нехай £ = &>--->£г|| — мультимножина з основою Б{С)~ [е\,е2,--,еп\ та

первинною специфкащею [(?] = , тобто мультимножина (7 м!стить по к екземпляр1в кожного з елеменпв е, основи Елементами евклщовоТ

множини к -спо лучен ь з необмеженими повторениями С* {О) е вс1 к -виб1рки вигляду (1) з мультимножини (7 при виконанш умови

(2)

Загальна множина ¿_-сполучень. Нехай = g2.---.gnj > — мультимножина з основою 5'(б;) = та первинною специфшацгею

[б]={г|], г)2,де г),-<£ V/ е^. Сукупшсть ус1х к -виб1рок вигляду (1) з мультимножини (7, для яких виконуетьея умова (2), називають загальною множиною сполучень О) .

1нтёрес до свюпдових комбшаторних множин пов'язаний з можливктю

розглядати IX як точки Кк, тобто з можливютю IX занурення в арифметичний

к

евклщовии простф К .

Нехай е — евклщова комбшаторна множина, а е в зображенш (1) -елемент Е. Тод1 вщображення

називають зануренням е в арифметичний евюпдовий простор, якщо / ставить множину е у взаемно однозначну вщповщшсть множит еу за таким правилом:

ДЛЯ

е),х = (х],х2,...,хк) еЕг

маемо х] = g¡J V/ е .

Позначимо е\п(С) = Г(А\п(С))\ 5к(0) =/(Ск(С)) ;

5к(а) = /(Скп(С)).

j.'

Симплексними точками множшш £^„((7) називають точки

yj = (yji.....y}k)eRkVje4.

yß=gi VieJb_j, yj(k-M) =2к-м gjzG.

Позначимо Q^n(G)— загальний многогранник сполучень - опуклу оболонку множини S*„(G).

Як вщомо, симплексш точки множини S^„(G) с вершинами многогранника (G).

1ндексом п{е) довшьного елемента e&S^n{G) вигляду (1.3) називаеться к- вишрний вектор

n(e) = (ix,i2-ix,...,ik-ik_{), Точка е називаеться регулярною, якщо в шдексп п(е) Bei неодиничш компоненти оточен! одиничними, а також у випадку, якщо ik - ? 1, а ik = n,.

Позначимо R^„(G)— множину регулярних точок множини (G). Як

вщомо, множина вершин многогранника Q*n(G) е шдмножиною множини

регулярних точок R^n(G).

Другий роздш присвячсний комбшатортй оштнзацп' на множит сполучень з повторениями.

У шдроздкш 2.1 обгрунтовано посилен! оцшки м]'шмум1в цшьових функцш, що можуть бути використаш при побудов! алгоритмв комбшаторноТ (в тому числ1 параметричноГ) оптим!зацп.

Як вщомо, функщю ч/(х), яка задана на деякш множит X, називають сильно опуклого, якщо ¡снуе стала р > 0 така, що Ух, у е X таких, що [*,}'] € X, i Vae[0,l] буде виконуватися HepiBHicTb

\у(ах + (\ - а)у) < а\\)(х) + (\- а )у(у) - а(\ - а^рЦх - yf. Доведено таю теореми.

Теорема 1. Якщо функция \\)(х) сильно опукла з параметром р > 0 i диферснщйована на опуклш замкненш множит Х~пЕ, Е - евклщова

комбшаторна множина, утворена з мультимножини G, то £

min^(y)^pilgli +max[v(x)-(v4>(x),x)+px2 + ytE /'=1 хеХ

+min (v4'fх), у) - щах (2рх- у)1

уеЕ уеЕ

де елементи ga. мультимножини G задовольняють умову

Теорема 2. Якщо функщя\|>Сх) сильно опукла з параметром р> О на опуклш замкненш множит X i диференцшована на X, евклщова комбинаторна множина Е с: X, то

~с 1 +max[ vW-J-||Vv|/(xj||27. y*E 11 11 xj 4P

де g = arg rn inlx - cf при c = x- Vyf/ (2p) .

xsE

Застосувавши розглянуп одшки для евклщовоТ комбшаторноТ множини Е до множини сполучень з повторениями S„(G) , отримано таю теореми.

Теорема 3. Якщо функщях^х) сильно опукла з параметром р> 0 i диференщйована на опуклш замкнешй множит X eRkG) cl, то minMу) ^ Pk82 + max ivW- *),*) + px2 +

.yeE xeX

s к

+en( SVvi/Cx,; -2px,)J,

1=1 i=J+l

де константа g = ming^, gi eG, константа s e визначаеться системою

t

-2pXs_j+l

>0 Vi e Je,

s

у=14

-2px

s+j

<0 VieJ

Ä-j'

де e\,e„- вщповщно найменший та найбшьший елементи основи мультимножини G.

Теорема 4. Якщо функщя^л^ сильно опукла з параметром р> 0 на

опуклш замкнешй множит X eRk,S„(G) cl, i диференщйована на X, то '.in v(y) +mcjxfMx)-^-\\^w(x)fj.

min

xeX

4p"

У пщроздЫ 2.2 здшенено постановки трьох параметричних задач на множит сполучень з повторениями: задач1 з параметром у лшшнш цшьов1Й функцп, задач1 з параметром у систем! обмежень [ загальноТ параметричноУ задач1 та розроблеш I обгрунтоваш алгоритми Тх розв'язування, доведена Тх ефектившеть.

Задача з параметром у цтъовш фунщй. Постановка задач к знайти пару

(с(х *) ,х * ^ таку, що

* * к

С(х )- тт х = argmin^*£J(c'j+tc"j)xj■, (3)

при умовах

де c'j,c'j eRl.

х eS*(G); t е[гн;гв]еД'

(4)

(5)

Як ведомо, розв'язком лшшноГ задач! без додаткових обмежень на множит сполучень з повторениями S,к(G) (тобто задач) (3) з t=0 при умоп'1 (4))

* * * и

еточка х =(Х| ел :

хд = е1 х*=еп VqeJk\Js, (6)

еие„ - Б1дпов1дно найменшийта найбшыпий елементи оенови мультимножини

G, а s eJk визначаеться системою: т т

5>s+w>0 VmeJs, *Zcs+j<0 VmeJk_s. (7)

]=l /=i Схема алгоритму Ai розв'язування задач1 (3)-(5): Крок 1. Для кожного значения i скласти систему нер1вностей: т т

2>;+w+?<+w>0 Vwe7s, ^c's+j^tcl+j<0 VmeJk_3. (8)

7=1 J=1

Крок 2. Знайти розв'язок кожноТ системи (8) вщносно t у вигляд! пром!жку Тп або показати вщсутшсть розв'язмв системи при даному s = i,

i.jl

Крок 3. Знайти перетин штервату з пром1жками Ts, як1 i будуть

визначати розв'язок задач! (3)-(5) у представленш (6) для s eJk.

Таким чином, [/,, ;(е ] розбиваеться на пром1жки, для кожного з яких знайдено число s, маючи яке по (6) записуемо розв'язок.

Теорема 5. Максимальна кшьюсть опсращй алгоритму А\ розв'язування задач1 (3)-(5) становигь величину порядку к?.

Ця теорема доводить ефективтсть алгоритму А).

Задача з параметром у cucmeMi обмежень к * к

С(х ) = min У\сх:; х = arg min "Тех:; (9)

xeRkp\ 1 x^J=] J

при умовах

xeSnk(G( 0); * (Ю)

ief^je*1. (11)

В (6) елементи основи e^t),e^(t),...,en^(t) повинш задовшьняти наступну систему иер1ВНОстей:

ei(t)<ep(t)<en(t) VpzJn_x\{\}. (12)

Розв'язок х* = (х\,...,х\) eRk зпдно (6)задаеться таким чином:

де 5 визначаеться з системи (7).

Таким чином, алгоритм А2 розв'язування задач1 (9-11) з параметром у систем! обмежень, мае таку схему:

Крок 1. Для кожноГ впорядкованоГ пари елемен'пв S(G(t)) скласти систему (12).

Крок 2. Знайти розв'язок системи (12) у виглад пром1Жка 7], i е Jn(n_\). Крок 3. Знайти перетин штервалу [?H/fe] з вдаовщними пром1жками 7}, який i буде визначати вигляд e^t), en(t) у (13).

Теорема 6. Загальна максимальна кшьюсть операцш за алгоритмом Аг для

•а

знаходження розв'язив задач1 (9) - (11) становить величину порядку п . Ця теорема св:дчить про ефектившсть алгоритму.

Загальна параметрична задача * к * к

С(х ) = min с'j + tc"j JXj; х = arg min Су + tc"j jxj; (14)

• xsRk xeR*

при умовах

X 6Sn\G(t)y, (15)

/е[гн;гв]ед', (16)

де c'j.c'j bR1 .

Множина розв'язюв Г,- , i eJ^ системи (8) розбивае числову Bicb на к+1 штервал. Множина розв'язк]в системи (12) розбивае числову вкь на ¡нтервали, ильгасть яких дор1внюе п-(п — \) .

Задача(14)- (16) мае розв'язок (13) при умов1 t eTv, n[fH;fB],

' " П г 1

де Tv = 7} (]Tj yieJkyj e Jn.(n-\) i не мае розв'язюв при / е L^h^bJ^U^v-

V

Схема алгоритму А3 пошуку розв'язку задач! (14) - (16) така: Крок 1. Для кожного значения s скласти систему (8).

I

Крок 2. Знайти розв'язки цих систем у вигляд! пром1жшв Г,- .

Крок 3. Для кожного переставлення елеменпв S(G(t)) скласти систему

(12).

I /

Крок 4. Знайти розв'язки цих систем у вигляд! пpoмiжкiв Tj .

* г tt

Крок 5. Знайти штервали Tv = 7} П 7} .

Крок 6. Знайти перергз ¡нтервалу [iH;iB] з вщповщними пром!жками Tv, що i визначатиме розв'язок (13) задач! (14) - (16).

Теорема 7. Максимальна кшьюсть операцш, яку необхщно здШснити для отримання розв'язку загально!' параметричноТ задач1 (14) - (16) за умови лшшно! залежност! вщ t цшьовоТ функци за алгоритмом А3 не перевищуе величину порядку к3 + п3.

Це св1дчить про ефектившсть запропонованого алгоритму. У третьому роздш1 розв'язуються задач1 комбшаторно'1 оптим1зацн з параметром у лшшшй щльовш функци, у систем! обмежень та загальна

параметрична задача на множит розмщень £*„(£?). Для кожно!' з розглянугих

задач розроблеш та обгрунтоваш алгоритми розв'язування. Уа алгоритми проанал!зоват на складшсть. Отримаш ошнки, що дозволяють ощнити максимальну складность розглянутих алгоритм!в.

Задача з параметром у цтьовш функци - це задача (3) при умов! (5) та

хеЕ*п(с). (17)

Як вщомо, розв'язком непараметр ичноУ лшшноУ задач! без додаткових

обмежень на загалынй множит розм!щень е точка

* у * * к

х =(х\ ,...,хк) еЯ :

*5,-=а = ,&т1-г+1 ^'е-Л-- (18)

Переставлення Р = ' константа «е^ задовольняють умову:

>0>ср5+1 >...>ср/,,де+ * = г,я

Переставлення |3 = дають можливкть упорядкувати

коефвденти су + /су цшьовоУ функцн к\ способами. Тому значения я е./® задае

не одну систему, а сукупшсть ¡з к\ систем, кожна з яких визначаеться одним переставленням Р = (р,

Обгрунтовано алгоритм В, розв'язування задач! (3),(5),(17), що мае таку схему:

Крок 1. Для кожного значения .г еУ'1 скласти сукупшсть систем нер!вностей, кожна з яких визначаеться одним переставленням р :

Ср1 (19> Крок 2. Знайти розв'язок кожноГ системи (19) ввдносно / у вигляд! пром1жка ГД або показати вщсутшсть розв'язк!в ц!еТ системи при

даному

Крок 3. Знайти об'еднання знайдених пром!жк!в для фксованого значения 5: Т* = и7/

Крок 4. Знайти перетин ¡нгервалу /в] з пром!жками Г5, яю1 будуть визначати розв'язок задач! (3), (5), (17) у представленш (18).

Таким чином, ^]розбиваеться на пром!жки,- для кожного з яких знайдено число 5, маючи яке по (18) записуемо розв'язок.

Загальна максимальна юльгасть операцш для знаходження розв'язк!в задач! (3), (5), (17) за алгоритмом В! е величиною порядка (к + 2)!.

Наведений анашз алгоритм1в дае змогу реально ошнити можливост! ЕОМ щодо розв'язування задач цього типу розглянутим алгоритмом.

Задача з параметром у систелп обмежень - це задача (9) при умовах (11)

та

. , хеЕ*(0(ф. (20)

Позначимо a¡(t) = ga}(t)..... аГ[(1) = де а,- е^ VizJr].

Оскшыш для знаходження оптимального розв'язку (18) нам необхщно знати точне розташування тшьки перших 5 1 остангах г елеменпв С(1), то елементи Сг(?) повишп задовольняти насгупну систему нер1Вностей:

^О) - ат(0 - ац-г+! (0. т 6^п-г ^ Л* * * к

Точках = (х\,...,хк) еЯ з розв'язку цю' задач! задаеться так: дгр. =а,-(/) Уге^; =«п-г+1(0 VI е^. (22)

Обгрунтовано алгоритм В2 розв'язування задач! (9), (11), (20), що мае таку схему:

Крок 1. За коефпиентами с,- визначити стали л г 1 записати структуру оптимального розв'язку.

Крок 2. Для кожного розмщення з к елеменпв мультимножини С(г)скласти систему (21).

Крок 3. Знайти розв'язок системи (21) у вигляд1 пром!жку Ц.

Крок 4. Знайти перетин ¡нгервалу з ввдповщними пром!жками Ц,

який 1 буде визначати вигляд а/1), 0 в (22).

Загальна максимальна юльмсть операцш для знаходження розв'язюв задач! з параметром у систем! обмежень становить порядку к -г\

Анализ алгоритму свщчить про те, що шдвищення складности обчислень суттево залежить в1д величини вширноеп простору к.

Загальна параметрична задача — це задача знаходження (3) при умовах (5) та (20).

Величини « 1 г не е фксованими. Отже, необхщно так упорядковувати елементи <?(/), щоб задовольнити будь-яку структуру оптимального розв'язку (22). Цього можна досягти шляхом упорядкування к перших I к останшх елеменпв мультимножини . Таким чином, щ елементи повинш задовшьняти наступну систему неровностей:

Кшыасть Ц7 систем вигляду (23) визначаеться як кшьмсть розмодень ¡з т] елеменпв по 2к , тобто }У - х\-(т\-\) ■... ■(ц-2к +1) .

Множина розв'язпв М-, г е/к ,, 5 , системи (19) розбивае числову В1сь на штервали, гальгасть яких дор!внюе (к + \)-к!. Множина розв'язгав Л^-, ) е 3\У системи (21) розбивае числову вюь на ¡нтервали, юльюсть яких дор1внюе IV . Серед цих ¡нтервал1в можуть бути порожш.

Задача (3), (5), (20) буде мати розв'язок (22) при умов1 / е 7" ^ 0, де Т = М/ П N у , 5 е е е .11Г.

Схема алгоритму В3 пошуку розв'язку задач1 (3), (5), (20) така:

Крок 1. Для кожного значения ¡е^ скласти сукупнють систем нер!Вностей вигляду (19), кожна з яких визначаеться одним переставленням

Р = (М2--Р*)-

Крок 2. Знайти розв'язок кожно1 системи (19) вщносно / у вигляд] пром1жка М ■, / або показати вщсутшсть розв'язив щеТ системи при даному г.

Крок 3. Знайти об'еднання знайдених пром!жк!в для фжсованого

к! п

значения .V: М = и Л/5 Уа-е-Л.

,=1 ' -

Крок 4. Для кожного розмшення елемент!в (7(г) скласти систему

(23).

Крок 5. Знайти розв'язок системи (23) у вигаяд! яром^жку Д'^, j е. Крок 6. Знайти штервали Г = Л/5 П Л^- ■

Крок 7. Знайти перер1з интервалу [/„;/„] з вщповщними пром1жками Г, що I визначатиме розв'язок (22) задач! (3), (5), (20).

Максимальна кшькють операций, необхщних для отримання оптимального розв'язку загально'! параметрично! задач! не перевищуе величину

порядку (к + 2)!+к2-г\2Ш.

Задач!, що розглядаються у четвертому роздал с необхщними для розв'язування параметричних задач, для яких невщом! опукл! оболонки комб'шаторннх множин. Знаходження загального многогранника сполучень, критерий його вершин с передумовами до розгляду параметричних задач на цш множин!.

В шдроздЫ 4.1. пропонуеться метод виокремлення, що дозволяе значно зменшити кшьюсть дослщжуваних точок, необхщних для побудови опукло"! оболонки загально')' множини сполучень.

В!домий алгоритм О. Л. Черних, який будуе опуклу оболонку множини

.г точок в Л", властивост! яких невщомь Для цього складають систему

^ . з

- А.; < 0, ! е - У/ =0,^ К] = 1 вщносно змшних

у=1 ;=1

у = (у\,■••,}>„) 1 еЯ.* !, виключивши з не\' змшш

А, 1,... ,х „+1, отримують систему неровностей

tcijXj + fJc)+syj<clieJn^ -Л.<0,2- = и+2,...,*, (24)

;=«+2 у=1

яка описуе опуклу оболонку п + 1 точки.

Подальший х!д алгоритму грунтуеться на використанн! методу скорочено'1 згортки. Кожн!й нер!вност! ставиться у вщповщшсть так званий !ндекс, що являе собою порядковий номер нер1вност1 в систем!. Надал! 1ндекс нер!вност1 буде складатися з певного набору натуратьних чисел, що формуеться за вщомими правилами. Постулово виключаючи з системи (24) змшш X п„2 , отримують опуклу оболонку задано! множини точок.

Введения в умову вектору змшних А у цьому алгоритм! пов'язано з тим, що процее створення опуклоТ оболонки ведеться безпосередньо. Для гонок же множини 5С) в1домий аналпичний опис симплекса, який е шдмножиною

загального многогранника сполучень. В цьому випадку, приеднання решти точок до кнуючоУ оболонки можна здшснити без застосування вектору змшних X. Таким чином, обертаються на нуль вс'1 доданки, що утворюють першу суму в нер1вностях системи (24), значно спрощуючи и вигляд. Цей запропонований в дисертацп алгоритм гз спрощеною структурою назвемо модифкованим алгоритмом побудови опуклоТ оболонки.

Запропоновано алгоритм побудови опукло'! оболонки точок загально! множини сполучень, що складаеться з трьох основних етатв:

1.1з множини в) видшяеться множина регулярних точок С).

2. 1з множини, що належать В.щ( й) виокремлюеться множина (С) точок, яю не лежать в симплекс!.

3. До множини С) застосовусться модифкований алгоритм побудови опукло!оболонки.

Таблиця 1

Результата числових експеримента побудови опукло'! оболонки за

Л п к кн Максимальна к-ть нер-тей при побудет Кшьюсть rineprpa-кей Час

4 4 2 6 6 1 4 4 1 сек

5 4 2 7 6 1 4 4 1 сек

5 4 3 10 9 2 6 5 1 сек

8 6 4 36 20 9 8 7 2 сек

8 6 '5 30 20 6 16 16 3 сек

8 6 6 17 14 4 15 " ГТ2 2 сек

10 8 4 113 53 _, 12 11 9 2 сек

10 8 6 113 65 19 19 13 4 сек

10 8 8 30 26 6 27 15 10 сек

12 12 10 66 58 9 29 23 12 сек

15 15 12 455 333 58 80 78 20 сек

15 15 13 105 94 12 52 32 ■ 14 сек

20 16 16 2153 1426 313 164 114 14 хв

20 16 17 606 487 86 261 157 1 хв

20 18 18 139 128 15 129 115 24 сек

22 22 20 231 213 19 97 62 29 сек

25 14 22 714 592 100 214 202 17 сек

25 15 22 470 367 72 287 119 7 хв

25 18 22 869 722 115 201 189 16 хв

25 22 22 1603 1304 178 521 362 24 хв

25 25 22 2300 1858 234 426 394 38 хв

25 22 23 234 218 20 231 207 18 сек

У шдроздин 4.2 сформульовано \ доведено критерш /-грат довшьного многогранника на основ! системи шдекс!в, що визначена в роздш4.1

Теорема 8. Точка у' еЯ*належить /-гран! Р^, / е ^^, якщо серед шдекав нер1вностей, що описують даний многогранник знайдеться ршно (к-]) таких, що не млстять числа г.

Наслщок. Точка V9 е е вершиною многогранника, якщо система, що його описуе мктить р1вно к неровностей, шдексияких не мютять числа q.

У роздш 5 побудовано математячш модел 1 задач! про вартють перифершних пристроУв та задач! про об'еднання електростанцш в енергосистему у вигляд! параметричних огатизащйних задач на сполученнях. Розглянут! модел! шдтверджують актуальшсть досл^дження та розробки методов \ алгоритмов евклидово'! комб!наторно1 отлтшацп для розв'язування параметричних задач на сполученнях.

У додатках розмоден! програма побудови опуклоУ оболонки для загальноУ множини сполучень 1 приклад реал1зацй' на ЕОМ щеУ програми.

ВИСНОВКИ

Параметричш задач! евювдово-! комбшаторно! оптим1зацп с новим перспективним аспектом дослщження в щй теори. Таю задач! були розглянуп рашше лише для загальноУ множини переставлень, досл^дження Ух на шших множинах е актуальними.

у дисертаци параметричш задач! евкшдовоУ комбшаторно!" оппмзаци на сполученнях ! розм'иценнях дослщжет на основ! метод)'в 1 тдход!в теори комбшаторно-! оптим1заци.

Практичне значения розроблених алгоритшв - в можливосп знаходження оптимальних розв'язив параметричних задач в залежносп В1д конкретного значения параметру, визначення штервал!в стшкост! оптимальних розв'язюв, оцшюванн! впливу похибок початкових даних на результат розв'язування задач на евклщових комбшаторних множинах.

В робот1 одержан! нов1 теоретичш та практичш результата в облает! параметричного анализу та стшкост! задач оптим!зацп на евкл!дових комб!наторних множинах.

1. Для множини сполучень з повторениями одержано посилен! оцшки мппмум!в сильно опуклих диференц!йованих функц!й. Це дозволяе покращити оцшювання екстремальних значеиь цшьових функшй, зокрема, при побудов! комбшаторних алгоритм!в, у тому числ! алгоритм!в параметрично'! комбшаторно"! оитим1задп. Для евклщових комбшаторних множин сполучень з повторениями та загальноУ множини розмвдень створен! алгоритми розв'язування задач з параметром у лшшних цшьових функщях, системах обмежень ! загальних параметричних задач з лшшними ц!льовими функцьямн на цих множинах. Проведено анал!з ! доведена ефективн1сть алгоритм!в. Результати досл!джень з параметрично'! оптим!зац11 можуть використовуватися для побудови моделей задач на вказаних множинах сполучень та розмщень, алгоритмов Ух розв'язування, а також для проведения аналопчних дослщжень на шших евклщових комб!наторних множинах.

2. Розроблено модифшащю алгоритму побудови onyiaio'i оболонки сиичепоТ МНОЖИНИ ТОНОК, ЩО ДОЗВОЛИЛО сутгево скоротити ЫЛЬШСТЬ ТОНОК, ЯК1 використовуються при побудов! загального многогранника сполучень. Доведено новий критерш /-граней довшьного многогранника. За допомогою розробленого модифкованого алгоритму можна будувати опукш оболонки тих множин (зокрема комбшаторних множин в задачах оптим1зацп з параметрами), для пщмножин яких вдама опукла оболонка.

3. Побудоваш математичш модел! задач1 про варткть перифершних пристроГв та задач! про об'еднання електростанцш в енергосистему як параметричних задач оптим1задй' на сполученнях. Розглянуи пщходи до моделювання можуть використовуватися для побудови моделей задач у р1зних галузях.

Достов]р!Псть результатов дисертацн випливае з коректноси математичних доведень теорем та тверджень, обгрунтованосп алгоритшв, як1 також протестовав в числових експериментах.

Результата, одержан! в дисертацшшй po6oTi можуть бути використаш в подальших досл1дженнях criüKocii та параметричного анализу задач комбшаторно! оппмзацй, зокрема з бшьш складними цшьовими функщями, обмеженнями, а також на шших комбшаторних множинах.

СПИСОК ОПУБЛ1КОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦП

1. Смедь О. О., Роскладка А. А. Про оцшки мш1мум1в цшьових функщй при оптилшацй' на сполученнях // Украшський математичний журнал. - 1999. -т. 51. - №8. - С. 1118 - 1121.

2. Емец О. А., Роскладка А. А. Алгоритмическое решение двух параметрических задач оптимизации на множестве сочетаний с повторениями // Кибернетика и системный анализ. - 1999. -№5. - С J&0' {€£.

3. Смець О. О., Роскладка А. А. Побудова опуклоТ оболонки загальноТ множини сполучень //Радиоэлектроника и информатика,-1998,-

4. Смець. О. О., Роскладка А. А. До опттпзацп оцшок екстремальних значень сильно опуклих функщй при оггтим1защУ на сполученнях //Шсник державного ушверситету "Льв1вська полп-ехшка". - 1998. -№ 363. - C.320-J22.

5. Емец О. А., Роскладка А. А. Модель выбора подмножества задач для ЭВМ с минимизацией количества периферийных устройств как задача комбинаторной оптимизации //Проблемы бионики. -1999. - № 51. - С.

6. Смець О. О., Роскладка А. А. Параметрична комбшаторна оптим1защя на сполученнях // Вкник державного ушверситету "Льв1вська полпехшка". -1.999. -№ 364. - С. 32-34.

7. Емец O.A., Роскладка A.A., Роскладка Е.В. Применение евклидовых поликомбинаторных множеств к построению моделей оптимизационных задач // Abstracts of second international school on actuarial and financial mathematics (June 8-12,1999, Kyiv, Ukraine). -C.20.

Роскладка А. А. Параметричщ задач1 та стшгасть при моделюванш евюндовими комбшаторними задачами оптим^зацп. - Рукопис.

Дисертащя на здобуття наукового ступеня кандидата ф!зико-математичних наук за спещальшстю 01.05.01 - теоретичн1 основи шформатики

i юбернетики. - Дншропетровський державний ушверситет, Дншропетровськ, 2000.

В дисертацп викладено дослщження параметричних задач евклщовоУ комбшаторноУ оптим1защ'У на сполученнях та розмпценнях. Для множини сполучень з повторениями одержано посилсгп оцшки мнимум1в сильно опуклих диференцшованих цшьових функщй. Для множил сполучень з повторениями та розмвдень створен1 алгоритми розв'язування задач з параметром у лишних цшьових функциях, системах обмежень, а також алгоритми розв'язування узагальнених параметричних задач на цих множинах. Для Bcix алгоритмов дослщжена складшсть обчислень. Для загалыгоУ множини сполучень розроблено модифжований алгоритм побудови опуклоУ оболонки. Встановлено новий критер1й /-граней довщьного многогранника. Побудовано парамстричш оштшацшш математичш модел1 задач на сполученнях.

Клгочов1 слова: параметрична оптим!защя, комбшаторна оптилпзащя оцшка складност1, комбшаторна множила, сполучсння, розмщення, опукла оболонка.

Roskladka A. A. The parametrical tasks and stability at modelling by the Euclidean combinatorial tasks of optimization. - Manuscript.

Thesis for a candidate's degree by speciality 01.05.01 - theoretical bases of informatics and cybernetics. - Dnepropetrovsk State University, Dnepropetrovsk, 2000.

In dissertation a research of the parametrical tasks of Euclidean combinatorial optimization on the combinations and arrangements is explained. For set of combinations with repetitions the amplified estimates of minimum of strongly convex differentiated objectives functions are received. For Euclidean combinatorial sets of combinations with repetitions and arrangements the algorithms of problem solving with a parameter in the linear objectives functions, in systems of restrictions, and also algorithms of a solution of the general parametrical tasks on these sets are created. For all algorithms the complexity of calculations is investigated. For general set of combinations the modified algorithm of a construction a convex environment is developed. New criterion of i-edges of any polyhedron is established. The parametrical optimization mathematical models tasks on combinations are constructed.

Key words: parameter optimization, combinatorial optimization, estimation of complexity, combinatorial set, combination, arrangement, convex environment.

Роскладка А. А. Параметрические задачи и устойчивость при моделировании евклидовыми комбинаторными задачами оптимизации. -Рукопись.

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

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

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

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

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

Анализ системы индексов неравенств при использовании модифицированного алгоритма построения выпуклой оболочки позволил установить новый критерий /-граней произвольного многогранника.

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

Ключевые слова: параметрическая оптимизация, комбинаторная оптимизация, оценка сложности, комбинаторное множество, сочетание, размещение, выпуклая оболочка.

Подписано до друку 11.07.2000. Формат 60x90.16. Hanip друкарськлй. Друк плоский. Гарштура Times New Romaa Суг. Умов. друк. арк I. Тираж 100

прим. Замовлення № 111._

Ротапринт ПДГУ шею Юр ¡я Кондратюка, 36601, м. Полтава, пр-т Першотравневий. 24._