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

од

Національна академія наук'України L rt «inn \нс

, Інститут кібернетики Імені В. М. Глушкова

9 0 глип і.^.!ї

На правах рукопису ПАНАСЕНКО Андрій Вікторович

РОЗРОБКА ТА ЗАСТОСУВАННЯ МЕТОДІВ ПАРАМЕТРИЧНОГО ПРОГРАМУВАННЯ І ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ ДЛЯ РОЗВ’ЯЗУВАННЯ ДЕЯКИХ КЛАСІВ ЗАДАЧ ОПТИМІЗАЦІЇ

05.13.16 — застосування обчислювальної техніки, математичного моделювання і математичних методів у наукових дослідженнях

Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

Київ 1994

Дисертацією е-рукопис:'* ^...............

Роботу виконано в Інституті програмних систем.НАН України.

Науковий керівник: академік НАН України, доктор фізико-математичних наук СЕРГІЄНКО Іван Васильович.

Офіційні опоненти: доктор фізико-математичних наук

ПЕРЕПЕЛИЦЯ Віталій Опанасович,

кандидат фізико-математичних наук ГУЛЕНКО Володимир Петрович.

Провідна організація: Інститут математики НАН України.

2М Об А Г Н

Захист відбудеться «---------» ------------- 199“ р. ----------1—

год. на засіданні спеціалізованої вченої ради Д 016.45.01 при Інституті кібернетики імені В. М. Глушкова НАН України за адресою:

252650 Київ МСД 22, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись у науково-технічному архіві інституту.

Автореферат розісланий «-------» -----------— 199 7 р.

Учении секретар ■спеціалізованої вченої ради

СИНЯВСЬКИИ Е. Ф.

Актуальність теми досліджень. Сьогодні діяльність, ще пов'язано з плануванням, підтримкою і прийняттям рішень, не уявляється без застосування обчислювальної техніки. У той же час програмні засоби, що здійснюють розв'язування задач оптимізації в традиційних постановках, не завжди задовольняють зростаючі вимоги тих предметних областей, де вони застосовуються. Одна з причин цього міститься у невизначеності даних, яка часто притаманна реальним задачам планування і управління, та обумовлена як похибкою обчислень, так і фактором довготермінового планування. Окрім цього, в багатьох практичних задачах початкові дані змінюються у деякий систематичний заздалегідь заданий спосіС-

В залежності від характеру невизначеності при постановці і розв'язуванні задач застосовуються різні підходи, значне місце серед яких займають аналіз стійкості, постоптимальний аналіз і методи параметричного програмування. Ці методи застосовуються до сімейств задач оптимізації однакової структури, які відрізняються лите значеннями деяких коефіцієнтів. В економічній інтерпретації це є моделювання ситуацій, коли виробничі показники змінюються у часі і в залежності від різних умов. Інша інтерпретація постоптимального аналізу і моделей параметричного програмування міститься в економічному аналізі виробничих структур з точки зору порівняння різноманітних технологічних і організаційних рішень, що пов’язано з необхідністю розв'язувапня великої кількості однотипних задач оптимізації.

Питанням стійкості розв'язків, постоптимального аналізу та параметричного програмування присвячені численні дослідження, що розглядають як неперервні задачі, так і задачі дискретного програмування. Дискретне програмування в цьому аспекті відрізняєтея тим, що за невеликих змін початкових даних моделі цілочисельного програмування поводять себе, як правило, нестійко і неп редбачено. Окрім цього, алгоритми розв'язування задач дискретного програмування часто мають характер неявного перебору всіх можливих розв'язків, і, отож, вони можуть "перебирати" і розв'язки при всіх можливих значеннях параметрів . '

На сьогодні досить добре розвинена теорія однопараметричних задач дискретної оптимізації. Здійснювалися також дослідження для випадків дискретного лінійного скалярного параметра, задач частково цілочисєльного лінійного програмування (ЧЦЛГГ) , нелінійного цілочи-

сельного програмування. Існує відносно небагато публікацій стосовно задач з векторними параметрами.

Великий внесок у розвиток цього напряку зробили Астаф'єв М.М., Ашманов С.А., Банк Б., Бєлоусов Є.Г., Блейр К.Е., Глушков В.М., Гольштейн Є.Г., Гордеєв Е.М., Джерослоу Р.Г., Джеффріон А.М., Єрьо-мін І.І., Золтнерс А.А., Клейн Д., Ковальов М.М., Козерацька Л.М., Лебедева Т.Т., Леонтьев В.К., Михалевич B.C., Наусс Р., Пайпер К.Дж., Перепелиця В.О., Рудман Г.М., Сергієнко І.В., Сотсков Ю.Н., Уолсі Л., Холм С. та ІН.

Алгоритми розв'язування задач оптимізації, як правило, мають дуже велику обчислювальна складність. У зв'язку з цим сьогодні гостро стоїть питання підвищення ефективності та швидкодії програмних засобів оптимізації. Існують дві сторони розв'язування цієї проблеми. Перша полягає в створенні надійних висрвопродуктивних ЕОМ, друга - в розробці ефективних методів розв'язування задач на таких ЕОМ.

Проблемам створення високопродуктивних ЕОМ присвячена численна література. Як основний елемент підвищення продуктивності обчислювальних засобів виділяється розпаралелювання обчислень. Зараз постійно зростає інтерес до чисельних алгоритмів, що ефективно розв'язують задачі на ЕОМ з паралельною організацією обчислень.

Паралельні алгоритми розробляються і застосовуються перш за все в лінійній алгебрі, при розв'язуванні систем нелінійних рівнянь, диференціальних рівнянь. В цих областях теорія і практика паралельних обчислень в певній мірі розвинена. Паралельні алгоритми для розв'я1 зуЕання задач оптимізації останнім часом активно розробляються, зокрема це стосується проблем розв'язування задач многокритеріальної оптимізації, лінійного і дискретного програмування.

Основні цілі дисертаційної роботи!

- дослідити природу взаємозв'язку двох класів задач параметрич-

ного програмування з параметрами у цільовій функції і правій частині обмежень; ■ •

. - розробити алгоритми розв'язування задач булевого лінійного

програмування (БЛП) із скалярним параметром у цільовій функції;

- розробити алгоритми розв'язування задач БЛП з багатовимірними параметрами у цільовій функції та в правій частині обмежень;

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

- застосувати розроблені методи для побудування декомпозиційно-гс і:сто,ту наближеного розв'язування задач БЯП великої розмірності та

для генерації тестових прикладів для різних задач математичного програмування; •

- розробити паралельні алгоритми для розв'язування задач лінійного програмування (ЛП) , БЛП спеціальної структури та лінійних дво-етапних задач стохастичного програмування (ЛДЗСП);

- створити на основі розроблених паралельних методів комплекс програм для розв'язування на МОК (макроконвейєрному обчислювальному комплексі) задач ЛП, БЛП та ЛДЗСП;

- провести експерименти по дослідженню ефективності створеного програмного засобу, їх аналіз і порівняння з теоретичними оцінками.

Наукова новизна дисертаційної роботи полягає у такому:

- дослідження маловивчєних сімейств задач з багатовимірним параметром ;

- установлення зв'язку між класами параметричних задач з пара-іетрами в правій частині обмежень і в цільовій функції, та використання цього зв'язку для розробки алгоритмів та генерації тестових прикладів;

- розробка, реалізація та експериментальне дослідження паралельних версій послідовних алгоритмів, що добре себе зарекомендували, для розв'язування задач ЛП і БЛП спеціальної структури;

- створення програмного засобу розв'язування задач оптимізації на принципово новій архітектурі ЕОМ з паралельною організацією обчислень.

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

Практична цінність дисертаційної робс •|и полягає з створенні програмного засобу для розв'язування на макроконвейєрному обчислювальному комплексі (МОК) ЕС 1766 задач ЛП, БЛП та ЛДЗСП, об'єднаних у комплекс програм ПАРОМ. Розроблений комплекс програм включений до Державного фонду алгоритмів та програм України. '

Апробація роботи. Основні результати дисертаційної роботи доповідалися та обговорювалися на Республіканському семінарі з дискретної оптимізації (Ужгород, 1989 р.), II Республіканській школі-семі-нарі молодих учених з кібернетики, інформатики та обчислювальної техніки (Київ, 1986 р.). Республіканській школі-семінарі з паралель-

них обчислень (Київ, 1988 р.), на засіданнях семінарів Наукової ради ЛН Ук; аїни з проблеми "Кібернетика" (Київ, 1984-1992 рр.).

убпікааії. За результатами проведених досліджень опубліковано й робіт, у яких відображено основний зміст дисертації.

Структура та обсяг дисертації. Робота складається із вступу, чотирьох глав, висновків, списку літератури і додатку. Загальний обсяг роботи - 140 сторінок, вона містить 5 малюнків, 3 таблиці. Бібліографія налічує 184 назви.

. ЗМІСТ РОБОТИ

V* вступі визначається актуальність та важливість досліджень, які проведені у дисертації. Подано стислий огляд результатів у досліджуваних областях, викладені основні цілі та результати роботи, схарактеризована її структура.

Перша глава присвячена загальним питанням проблематики параметричної оптимізації і паралельних обчислень.

В розділі 1.1 увага акцентується на специфічних властивостях і загальних підходах до розв'язування задач оптимізації з недетерміно-ван;ш даними. В розділі також обговорюється стан проблем розробки і застосування методів параметричного програмування стосовно головним чином дискретної оптимізації.

Метод параметричного і постоптимального аналізу задач цілочи-сельного програмування, як правило, базується на найбільш придатному методі для розв'язування детермінованих задач відповідної структури. Класифікацію алгоритмів і підходів, розглянутих у науковій літературі, можна здійснити за методами та за класами задач, до досліджуються. Виділяються чотири напрямки таких методів. Переважна більшість розглянутих у розділі задач мають лінійний скалярний параметр. Як приклади застосування наведені параметричні методи розв'язування задач ЧЦЛП та загальний підхід параметричної декомпозиції для задач оптимізації.

Розділ 1.2 є оглядом обчислювальних систем з паралельною організацією обчислень. Виділені чотири типи таких систем. Більш детально у цьому, розділі описана структура МОК ЕС 1766, який було створено в Інституті кібернетики ім. В. М. Глушкова АН України. .

. Огляду етану' справ у розробці і програмній реалізації > паралельних алгоритмів розв'язування задач оптимізації присвячений розділ . З . Виділено три хляси ^аралельніїх алгоритмів на основі принци-

пів їх розробки. Зроблено огляд придатності тих чи інших типів пара лельних ЕОМ до розв'язування різних класів задач.

Друга глава присвячена розробці та застосуванню алгоритмів розв'язування деяких параметричних задач, головним чином булевого прог-

рамування. Порушуються також питання оцінок кількості оптимальних розв'язків параметричних сімейств.

В розділі 2.1 доводиться така теорема про взаємозв'язок дпе;і сімейств задач параметричного програмування.

Теорема 2.1. Нехай х - вектор розмірністю П, функція Дх, G) та вектор-функція g(X, 0) = (gi(x, 0), ..., gm(x, 0)) визначені на X х 0, де Хс с R", 0 є RP - деякі множини, D: 0 ~+ R" - деяке рестрикційие відображення. Нехай також \|/(0, ті) - оптимальне відображення для параметричного сімейства задач

sup |Дх, 9) I gj(x, 9) = тії, і є Іо, gj(x, 9) > Vi, 1 є Іь х є D(9)},

ІО^Іі ~ •••* m}, Іо ^ її = 0

з параметрами 0 є 0 та ц = (rjj. ..., r|m) є Rm, а я(0, X) - оптимальне від

ображення для параметричного сімейства sup {/(х,в) + Xg(x,0)| з пара-

xtD(e)

метрами 0 є 0 та X = (Xj, ..., Xm) є Rm. Тоді .

В дисертації часто використовується частковий випадок теореми

вигляді теореми 2.2. , '

Теопема 2.2. Нехай X - вектор розмірність П; Дх) - деяка функція, g(x) - вектор-функція; П = (пі-. —. Пт) та X = (Х(, ..., Хщ) - вектори параметрів в Rm^ Ю - деяка множина в Нехай також »|/(л) - опти-

мальне відображення для параметричного сімейства задач

sup \Л*) І 8і(х) = Лі. 1 е І0> 8і(х) £ Пі, і є її, X є D), (1)

І0и Ij = {І, ..., т}, Іопї]=0, .

а п(Х) - оптимальне відображення для параметричного сімейства

и я(0,Х)с LMe.n)-

ОєеЄ XeRm Xі2:0, Іе1|

2.1, у якому відсутній параметр 0. Цей результат сформульований у

П)

Тоді U л(х)с (Jy(n)-XeR1" neRm

Теорема 2.2 дозволяє, як показано у наступних розділах, використовувати розв’язки одних параметричних сімейств задач при розв’язуванні ,ших. У цьому ж розділі формулюється ряд наслідків теореми стосовно параметричного опуклого програмування, коли вона випливає з достатніх умов оптимальності теореми Куна-Таккера.

З необхідності та достатності умов оптимальності теореми Куна-Таккера можна вивести таку теорему про множини оптимальних розв'язків параметричних сімейств задач опуклого програмування.

Теорема 2.3. Якщо у сімействах (1) - (2Л Ід = 0, функції Я;, і = 1, ..., Ш, є опуклими, І> - опукла замкнута множина і Н є множиною таких т| є Кт, при яких задовольняються умови Слейтера для обмежень

в(х)>ть то и^Чп) £ и — иЧ'(п)-

*ігН ХіО цєіі1"

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

Теорема 2.4. Якщо пара параметричних сімейств задач (1) - (2) задовольняє умови теореми 2.3 і, до того ж, Н =■ Нт, то

ич/(іі) - илМ- -

Г)єН АіО

Теорема 2.5. Хай в параметричних сімействах <1) , (2) -Дх) е

опуклою функцією, О - опукла замкнута множина, в(х) ** А, де А - ГО*І1-

матриця. Тоді Уч'(г))= и*(*•)• ■ .

т)сІ<т ХеЯ”

ХійО, Ієіі

Застосування теорем 2.4 і 2.5 ілюструється на прикладі параметричних сімейств задач опуклого квадратичного програмування.

У розділі 2.2 розглядається параметрична сімейство задач БЛП з скалярним лінійним параметром у цільовій функції '

тіп { (с + 9Ь)хІ Ах £ Ь, х є { 0, 1 )п ). (Р°>

де с, її, х - п-вимірні вектори, А - Шхп-иатриця, Ь - т-вимірний

ьектср, 020 ~ параметр. ■ ■ .

Це параметричне сімейство складає з сімейством

шіп { схі Ах ^ Ь, Ьх £ ц, х є { 0, 1 }п }, (Рч)

дч т| є (-оо,+со) - параметр, пару у розумінні теореми 2.2. Якщо у теоремі покласти Б = { х : Ах 5 Ь, X є {0, 1 }п }, то виходить, що всі опти-

мальні розв'язки сімейства. (

р0>

є оптимальними розв'язками сімейства

Запропонований ;_етод розв'язування (Р^) базується на методі ві~ ток та границь (МВГ) . Його відміна від МВГ для звичайних задач БЯП полягає в тому, що як задачі-кандидати розглядаються параметричні задачі, лінійними релаксаціями (ЛП-релаксаціями)' служать параметричні задачі ЛП, а верхніми та нижніми границями - кусково-лінійні функції верхніх та нижніх границь. Для побудови алгоритму розроблені метод розв'язування . відповідної ЛП-релаксації, а також евристика, що прискорює обчислення.

Побудувавши множину оптимальних розв’язків сімейства (РІ() , треба виключити з неї "зриві* розв'язки. У розділі запропонований по-кроковий алгоритм такого вилучення, який будує оптимальне відображення і функцію екстремуму та збігається не повільніше ніж за К кроків, де К - кількість оптимальних розв'язків сімейства () .

Розділ 2.3 присвячений розробці алгоритмів розв'язування параметричних сімейств задач БЛП з лінійними багатовимірними параметрами. Спочатку описується алгоритм розв'язування параметричного сімейства з багатовимірним параметром у правій частині обмежень. Сіиейст-во ^

шіп{сх| Ахі ч, х є { 0, І }п }, (РМЛ)

де А, С, X та. такі я, як у розділі 2.2, її є І1т - вектор незалежних параметрів, пов'язано з сімейством.

шах {(с - ХА)хІ х є { 0, 1 }п }, (РМХ)

де Х20 - вектор незалежних параметрів, у розумінні теореми 2.2, якщо покласти О = {0, НП• На основі цього факту і будується алгоритм, наближений у тому розумінні, що замість множини оптимальних.розв'язків сімейства (РМЧ): шукається його деяка підмножина і покроково будується відповідне точково-множинне відображення. Алгоритм є неявно-переборним і полягає у переборі 2П.систем лінійних нерівностей типу {(с - ХА)Я(О), X г 0(, у процесі якого вони перевіряються на сумісність симплекс-алгоритмом. Тут 3? = (9Ї|, ..., 9?п) - набір знаків і та 2, причому якщо якась система гакого типу є сумісною, то існує наближений розв'язок X параметричної задачі (РМЧ) з такими компонентами, що

знаку £ відповідає нуль, а знаку 'г - одиниця. По закінченні ітеративної переборної процедури отримаємо множину оптимальних розв'язків та наближення оптимального відображення. Наведений також спосіб отримання апостеріорного розходження за цільовою функцією для будь-якого т), в якому, загалом кажучи, треба розв'язати задачу ЛП у просторі параметрів X. Доведений ряд властивостей цієї оцінки, які дозволяють обчислювати оцінку без розв'язування задачі ЛП або використовувати

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

/нелогічний підхід використовується для розв'язування сімейства задач, в якому багатовимірні параметри присутні водночас у цільовій функції і правій частині обмежень. Це сімейство має такий вигляд:

шах {(с+ цН)хІ Ах£іі. х є { 0, 1}п}, (РМ^>

де А, с, х такі я, як у сімействі (РМ^) , Н = мВ, ц є Р -

- вектори незалежних параметрів вимірності, відповідно, р та І», О є є Лр - опукла многогранна множина, що може бути задана системою лінійних рівнянь і/або нерівностей, Р = { ц: £ Пі - Рі> І = Ь •••> ш } є Лт -

паралелепіпед, причому деякі (або всі) величини су, Рі можуть бути нескінченними. < ■

Сімейство (РМ*1) складає з сімейством Л

гаах {(с + йН - ХА)х І х є { 0, 1 )п} (РМ(иА))

пару у розумінні теореми 2.1. Метод пошуку сумісних систем є аналогічним попередньому алгоритму, а для покрокового перетворення наближення оптимального відображення пропонується дещо ускладнена процедура. Аіюстеріорні оцінки розходження за цільовою функцією, що застосовувались для сімейства (РМ^) , придатні і для сімейства (РМ^) .

Розділ 2.4 порушує питання, пов'язані з кількістю оптимальних розв'язків в параметричних сімействах задач булевого програмування, як лінійного, так і нелінійного, з багатовимірним лінійним параметром у цільовій функції. Спочатку розглядається задача (РМ^) , верхня оцінка кількості оптимальних розв'язків якої <рш(п) шукається за умов певної невиродженості, тобто для таких (А, с), що або П > Ш ї будь-які їй + 1 рядків матриці (А^, с) лінійно незалежні, або п 5 Ш. Доведено, що у цьому випадку для будь-яких т 2 2, П 2 1 функція <рт(п) є поліномом від П степеня т. Введення обмежень у параметричну задачу може істотно змінити поведінку 4>т(п), вона може стати експоненціальною навіть за згадуваних умов невиродженості, що й доводиться наведеним прикладом, коли введення лінійного обмеження до задачі (РМ*-)

дає фт(п) £ 0(—2П ).

уп - т

Розділи 2.5 та 2.6 присвячені застосуванню методів і підходів параметричного програмування на прикладі декомпозиції задач великої розмірності та генерації тестових прикладів.

В розділі 2.5 наводиться декомпозиційний алгоритм наближеного розв'язування задачі БЛП на основі підходу з розділу 2.3. Розглядається задача, у якій всі змінні розбиті на групи:

L L

max { Y,с1*11 Л aV < b , х' є(0,1}"', /= 1.... L}, (З)

/=1 Ы

де Ь - вектор розмірністю ПІ; та X* - вектори розмірністю Л/; А* -тхП/- матриці.

Нехай v/чО - множина оптимальних розв'язків задачі Ш&Х j сУ I

AVs ц1, x1 є{0,1}П/ }, де є Rm - вектор незалежних параметрів. Тоді,

очевидно, оптимальний розв’язок задачі

L L

max { ]TcV I £ aV ^ b , х'єА/, 1=1,..., h), (4)

/=1 /=!

де Д/ — Uw(V). буде оптимальним розв'язком задачі (3). n'^R"*

Через складність побудуви Л,- замість цих множин розглядаються множини О/5 Д/оптимальних розв’язків параметричних сімейств max {(с^ -

- )./А/)х,|х/ є (0,1}"'}, де Xі - невід’ємний вектор незалежних параметрів.

L

Сформулювавши задачу max V max{ сУІ AV < У, Xі є (її І, що ви-

rfc.b'-btt

ходить з (4) шляхом звуження допустимої області, у термінах елементів множин О/ та замінивши в ній умови булевості на умови невід’ємності, отримаємо замість задач вибору одного розв'язку з кожного її/ сукупність задач пошуку оптимальних опуклих комбінацій з елементів цих множин, причому двоїсті задачі до цих задач ЛП з урахуванням деяких замін і перетворень записуються у вигляді

F/(b#) = min[ max (с; - к'А^х1 + xk1] ,1=1,L - 1, x'so х'єІО,!)"'

- її, Ь~1 ,

Fi,(b....b ) = min( птах (cL - XLAL)xL + ХЦЬ - Ті/)].

я1- го х' е(0,і)"і- /Т)

' Запропонований алгоритм полягає у максимізації функції

L-1

F(b‘, bL-')= 5^F/(b/) + F^b1, bL-*) від. (L-l)m зміннич з подань-

/=І

шим визначенням підмножин СІ/ с О/, таких, що Я/ - { х' с Qf І к1 =

*вг

= arg max (с1 - kW)*1 }, I = 1, L, де Xі = arg min(p/(X^), -

x'tKO.i)"' 0

= max (if - л/А/)х/ + X/b^, I - I, L, (b1, bL_1) = argmaxF(bl, bL~*),

x'c(0,l|"'

L-l_, bL = b - £b' ■

/=1

Наближеним розв'язком задачі вважається розв'язок (fcl., хМ

таких зада" дискретного програмування: ,

шах { cVI А1*1 <, Ь1, х* є О/ }, і' = І, L. (5)

Сформульовані і доведені властивості задачі maxF(bl, ЬИ)і об-

ласть скінчєнності D Функції F є опуклим многогранником; куркова лінійність та угнутість функції F на D; кускова лінійність та опуклість функцій <р/(Х0 на множинах X* > 0. На підставі цих властивостей обраний метод розв'язування цієї задачі - градієнтний спуск з розтягуванням простору у напрямку різниці двох послідовних субградієнтів при оптимізації F та

Далі покроково викладаються алгоритми оптимізації функцій ? та (р/, наводиться верхня апостеріорна оцінка розходження за цільовою Функцією між оптимальним розв’язком задачі (3) та розв'язком сукупності задач (5) та наводяться обмеження на вимірність задачі (3)', які стосуються перш за все L та Ш, бо обмежень на кількість змінних П практично немає. . .

Розділ 2.6 є викладом методу генерації тестови* прикладів, тобто задач із заздалегідь відомим розв'язком, для деяких класів задач оптимізації, до необхідно для проведення випробувань і визначення швидкісних та інших характеристик існуючих програмних засобів та тих, що розробляються. Ідея методу базується на співвідношенні мі* двома класами задач параметричного програмування, яке встановлюється теоремою 2.2 при 1) = 0 (тобто мають місце тільки обмеження-рівно-сті). . . ,

Використовуючи відносну простоту розв'язування задачі (2), можна отримати серію оптимальних розв'язків та відповідних їм правих частин для конкретних реалізацій задачі (1).' Таким чином, виходить серія тестових задач з відомим оптимальним розв'язком, причому ці задачі відрізняються лише правими частинами обмежень, рівними g(x®), що с дуже зручним з точки зору переходу від однієї тестової задачі до іншої. Таку методику зручно застосовувати до задач БЛП та нелінійного програмування, частково блочних задач. Обмеження на розмір-

ність задач, що генеруються, визначаються лише складністю розв'язування задач типу (2) .

Розглядаються конкретні випадки для задач БЛП, булевого квадратичного програмування з лінійними та нелінійними обмеженнями, ЛП та БЛП з матрицею обмежень частково квазідіагонального вигляду.

Методика для останніх двох випадків була використана при гене рації тестових прикладів при створенні Комплексу програмних засобі в ПАРОМ. ^ -

Третя глава присвячена розробці паралельних алгоритмів розв'язування найбільш типових і поширених в економічних застосуваннях оп тимізаційних задач. Ці алгоритми призначені переважно для задач великої розмірності і створені на основі існуючих відомих послідовних методів, до добре зарекомендували себе - методу віток та границь, с! мплекс-методу, методу множників Лагранжа і методу узагальненого градієнтного спуску. Розробка алгоритмів проводилася стосовно до МОК ЕС 1766.

' , 0 розділі 3.1 описаний паралельний алгоритм розв'язування зада-

чі ЛП з матрицею обмежень частково квазідіагонального вигляду, яка має зв'язуючі обмеження:

т мі . .

№ах (6)

. >н=і т N1

Ї!!Еаихі5:Ь}« м, !7)

]-И-1 :■

N1

к“ *' Кі' •»“ 1....................................Т'

і«1

(8)

(9)

.-х{ а к « 1, ..., 1......Т.

Використовуючи метод множників Лагранжа, здійснюємо л-композицію за обмеженнями, яка призводить до необхідності мінпізації на

^ = {и1 в (и|, ..., и^): и1 і 0 } функції Лагранжа ф(и!), що дає и1* - ту

частину оптимального розв'язку двоїстої до (б) - (9) задачі, яка

відповідає.обмеженням (7), Маючи и1*, для отримання розв'язку задачі (61 (9) треба розв'язати Т незалежних задач ЛП, після чого вико-

нується деяка процедура отримання остаточного оптимального розв'язку задачі (6) - (9) , яка базується На симплег.с-мотоді.

Задача мінімізації <р(и*) на зводиться до задачі безумовної

мінімізації заміною змінних і розв'язується застосуванням методом узагальненого градієнтного спуску.

Паралельний алгоритм розв'язування задачі (6) - (9) є алгоритмом для паралельних обчислень за умов обмежених ресурсів. Для програмного виконання потрібно не більш як Т + 1 арифметичних процесорів (компонент). В одну арифметичну компоненту (координуючу) завантажується програма реалізації Г-алгоритму узагальненого градієнтного спуску та алгоритму отримання остаточного оптимального розв’язку задачі (6) - (9). Якшо в наявності є Р арифметичних компонент, то у

ШІп(Р - 1, Т) компонент завантажується програма, що реалізує обчислення елементів (доданків) значень функції <р та субградієнту, включаючи розв'язування симплекс-методом Т задач ЛП, про які йшлося раніше. Якщо Р>Т, то між зовнішньою пам'яттю та арифметичною компонентою здійснюється мінімальний обсяг обмінів. До координуючої компоненти пересилаються доданки значень функції та субградієнту. В решті компонент знаходяться копії програми, яка ці значення обчислює для кожного 3 = 1, ..., Т; у ці компоненти пересилається знов обчислене значення абсолютних величин вектора и*. У випадку Р <, Т необхідною є підкачка інформації із зовнішньої пам'яті, що, природно, уповільнює процес розв'язування задачі (6) - (9).

Далі покроково подаються паралельний алгоритм розв'язування задачі (6) - (9) та умови його зупинення, обмеження на пам'ять прог^

рамної реалізації алгоритму.

Паралельний алгоритм розв'язування задачі тієї г. структури, але з булевими обмеженнями, представлений в розділі 3.2. У розглянутій задачі замість обмежень (9) присутні обмеження .

х] е{0,1), к = 1, К,, 3=1....Т. (Ю)

Якщо їх замінити на обмеження

0 5х|<1, к= 1, ..., К^, 1.....Т, (11)

то задача (б) - (8), (11) буде ЛП-релаксацією вихідної задачі. Для

подальших обчислень необхідно спочатку розв'язати задачу, двоїсту до

.. . . , т. М ... . . ..

неї, мінімізацією на кусково-лінійної опуклої функції Лагранжа

з подальшим розв'язуванням задач ЛП з обмеженнями та X) + змінними кожна.

При розв'язуванні вихідної задачі (6) - (8), (10) паралельним

МВГ використовується Р арифметичних компонент, я яких містяться од-

накові програми зондування задач-кандидатів. Ще одна компонент* використовується для роботи програми, що координує процес обчислень.

Для отримання верхньої оцінки у будь-якій вершині дерева галуження треба розв'язувати ЛП-релаксац.ію, оптимальне значення якої позначимо через 2.

Стратегія галуження вибрана такою, що фіксація змінник робиться послідовно у бік зменшення індексів І та j (спочатку зміноється і, потім j! . Така стратегія істотно спрощує отримання Z. Дійсно, за кої стратегії величина z може бути представлена у вигляді z =

Т ,

- ^Zj + u^b1, де Zj дають складові Z по різких групах змінних, и1* -І=‘ ' .

озв'язок задачі мінімізації tp. Нехаіі остання зафіксована змінна у

вершині є xljj . Частина величин, що складають Z, зберігаються у

структурі, яка описує задачу-кандидата, a. Zj для j < ід були обчистені при розв’язуванні задачі, двоїстої до релаксації початкової задачі. Для визначення верхньої оцінки досить розв’язати задачу ЛП з Kjc І + ід - 1 змінними та - і обмеженнями (при ід = 1 задачу розв ’ язу вати не треба). Невелика розмірність дозволяє розв'язувати цю задачу швидко в одній арифметичній компоненті.

Таким чином, при виконуванні паралельного алгоритму водночас і незалежно можуть зондуватися Р задач-кандидатів.

Далі у розділі викладається паралельний алгоритм розв'язування задачі (6) - (8), (10) у вигляді Покрокового процесу. Наводяться обмеження щодо пам'яті.

В результаті реалізації алгоритму на МОК EC 1766 були проведені обчислювальні експерименти при різкій загальній кількості процесорі, для задачі (6) - (8) , (10) з Т = М = 4, Nj = 2, Kj = 4, j -- 1, 4, та

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

В розділі 3.3 описаний паралельний алгоритм розв'язування ЛДЗСП, яка полягає у обчисленні 11-міркого плана-вектора X за умови 'дискретної випадкової величини Ш:

шах{ сх - M[q(o)y((o)l | А(и)х + В(ш)у(ш) = Ь(ю), х £ 0, у(ш) і. 0 ), (12)

де С - вектор розмірністю П; q(co) - k-мірний стохдстччіїі-й ьектоо штрафів; А(п) - технологічна стохастична матриця розміриі с тю !Т1>П; В(со) - випадкова матриця корекції розмірністю Г) Ч; b('j} - т -н ~ рлі,й

вектор стохастичних ресурсів; у(ю) - к-мірний вектор корекції, М --имвол математичного сподівання.

Припустимо', що ми маємо можливість проводити статистичні випробуванні випадкової вепичнми ш. Нехай в результаті статистичних випробувань маємо Г вибіркових значень цієї величини (станів природи) СО], .... Шг З вибірковими Імовірностями Р), рг. При цьому для всіх І = = 1, г позначимо ч’ = £|(со|>, А1 = А(ш;), В* = В(о>,), Ь1 — Ь(и^. Позначимо також у* відповідний вектор корекції. Задачу (12) можна звести до такої задачі ЛП:

г

шах{ сх - ^ РіЧ'у* І х > 0, А!х + В'у* — Ь', у* > 0, і = І, г }. (13)

і=і

Відповідність постановок (12) та (13) є справедливое у той мірі, у якій є справедливою статистична гіпотеза.

Матриця обмежень двоїстої до (13) задачі має, аналогічно (6) -

- (9), зв'язуючі обмеження. Тому аналогічно розділу 3.1 визначається

функція Лагранжа <р(х), мінімізація якої на множині Х>0 проводиться узагальненим градієнтним спуском, а мінімум х* вважається оптимальним розв'язком задачі (12). •

Викладений у розділі паралельний алгоритм такої мінімізації є аналогічним розробленому у розділі 3.1. Оскільки природа задач (6) -

- (9) та (13) є схожою, обмеження щодо пам'яті є аналогічними.

Алгоритми третьої глави були реалізовані в Комплексі програмних засобів ПАРОМ для розв'язування ка МОК ЕС 1766 задач БЛП, ЛП та ЛДЗСП, описаному в четвертій главі, яка відображає результати практичної реалізації запропонованих паралельних алгоритмів.

Комплекс ПАРОМ є частиною програмного забезпечення МОК ЕС 1766 та призначений для розв'язування на цій обчислювальній системі задач поточного та перспективного планування у моделях третьої глави. Його було здано до Державного фонду алгоритмів та програм України.

В розділі 4.1 описано функціонування комплексу ПАРОМ. Воно в загальному випадку уявляється як таке, що складається а трьох послідовних етапів: активізація комплексу, розв'язування задач та завершення роботи, описані кожен з етапів функціонування Та типи повідомлень, що їх формує комплекс у процесі роботи.

В розділі 4.2 наданий опис логічної структури комплексу - структура і склад програм та зв'язок між і::іми .

Коиппекс ПАРОМ має складну модульну багатопроцесну структуру. Обсяг вихідних програм складає 7700 операторів, обсяг об'єктних про-грзи 2П0 Кбайт. У складі програмного забезпечення комплексу виділя-

ються дві основні компоненти: системне програмне забезпечення (СПЗ). що керує роботою комплексу та функціонує у периферійному процесорі ЕС 1066, та прикладне програмне забезпечення (ППЗ), що реалізує алгоритми обчислення оптимізаційких моделей і функціонує як сукупність мультімодульних програм (ММП) у арифметичних процесорах МОК. Наведений детальний опис функцій всіх програм.

Аби уникнути втрат при збої обладнання, у програмах ППЗ використовуються контрольні точки через певну кількість ітерацій.

Розділ 4.3 присвячений організації і способу підготовки даних, розробці систем перетворення вхідних та вихідних даних у комплексі ПАРОМ.

Оскільки комплекс ПАРОМ поєднує в собі програми, що функціонують у різних середовищах, на ЕОМ з різною архітектурою, то організація подання та перетворення даних постає неабиякою проблемою.

Ехідними та вихідними даними в комплексі в цілому є файли у стандартному МРБ-форматі, а також вхідні й вихідні дані (параметри) діалогової процедури запуску ММГТ-програм, - що входить до системного забезпечення МОК. Для ПДЗСП окрім вхідного МРБ-файлу додатково використовується ЗТОСНАБТІС-файл (файл стохастичних даних). Проміжні дані комплексу містяться у файлах ОС та зовнішніх масивах - спеціальних структурах даних.

У зв'язку з спеціальною структурою задач ПП та БЛП постає пи тання про структуризацію матриці обмежень, бо від користувача, загалом кажучи, т-з вимагається надання даних у МРЗ-файлі у структурова-ному вигляді (мається на увазі послідовність рядків та стовпців). Це питання вирішується розробкою та реалізацією простого евристичного алгоритму структуризації розріджених матриць. Алгоритм має обчислювальну складність, у найгіршому випадку пропорційну пАі/2, де ПІ та П - розмірності матриці по рядках та стовпцях.

Наприкінці наведена детальна схема інформаційних зв'язків комплексу ПАРОМ.

У висновках підсумовуються основні результати роботи.

У додатку міститься документ, що підтверджує упровадження дисертаційної роботи.

, •. ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ

1. Сформульовані та доведені теорема про взаємозв’язок дво.с класів задач параметри його прогр*мування, та її наслідки для пара-

метричних сімейств задач опуклого програмування, зокрема задач квадратичного опуклого програмування та ЛГЇ.

2. З використанням зазначеної теореми розроблені алгоритми роз-ч'язуЕання параметричних сімейств задач БЛП з скалярним параметром у цільовій функції та багатовимірним параметром у цільовій функції та правій частині обмежень (наближений алгоритм). У останньому випадку наведена апостеріорна оцінка розходження по цільовій функції в залежності від значення векторного параметра.

3. Отримані оцінки кількості оптимальних розв'язків сікейсте задач булеиого програмування з багатовимірним параметром у лінійній цільовій функції.

4. Здійснено застосування теореми про взаємозв'язок двох класіг задач параметричного програмування для розробки та програмної реалізації декомпозиційного методу розв'язування задач БЛП великої розмірності з отриманням апостеріорної оцінки розходження за цільовою Функцією.

5. Використані дослідяені властивості параметричних задач опти-міза ції для розробки методу генерації тестових прикладів для різних класів задач оптимізації.

6. Розроблені та реалізовані паралельні алгоритми розв‘язування

задач ЛП та БЛП з матрицею обмежень частково квазідіагональної структури. '

7. Здійснено застосування даних алгоритмів для розробки паралельного алгоритму розв'язування ЛДЗС1І.

8. На основі розроблених методів створений комплекс програм для розв'язування на КОК ЕС 17 66 задач ЛП, БШІ та ЛДЗСП (Програмний комплекс ПАРОМ).

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

Основні положення дисертації опубліковані у таких роботах.

]. Платон Е.В., Панасенко А.В., Тесанюк ЮЛІ. Парплельные алгоритмы решения задач линейного и линейного булевого программирования // Математическое обеспечение высокопроизводительных ЭВМ.- Киев: Ин-т кибернетики им. В. ". Глушкоза УССР, 1986.- С.47 51.

■ 2. Панасенко А.В. Приближенное решение задачи ЕЦЛП с многомерном параметром в правой части // Кибернетиха.- 1983,- !-і 5,- С.124-

- 12 п .

3. Панасет-тко А. С. ДскоулогтцгонгыЯ алгоритм приближенного решения задач БЦЛП // Инструментальные средства построения баз данных и знаний на персональных ЭВМ. — Киев : Ин-т кибернетики им. В. М. Глушкова АН УССР, 1989. — С. 63—72.

4. Панасенко А. В. Метод генерации тестовых примеров для некоторых классов задач булевого программирования // Республиканский семинар по дискретной оптимизации, Ужгород, 20—22 нояб.‘1989 г.: Тез. докл.

— Киев : Ин-т кибернетики им. В. М. Глушкова АН УССР, 1990. — С. 58.

5. Панасенко А. В. Параллельный алгоритм решения задачи булевого линейного программирования с матрицей ограничений частично квазиди-агонального вида // Численные методы и технология разработки пакетов прикладных программ. — Киев : Ин-т кибернетики им. В. М. Глушкова АН УССР, 1990.,— С. 77—82.

6. Комплекс программных средств для решения на многопроцессорном

вычислительном комплексе ЕС 2701 задач текущего и перспективного планирования методами линейного, булевого и двухэтапного стохастического программирования (ПАРОМ) /А. И. Кукса, А. И. Жежеря, А. В. Панасенко, Т. Б. Неверова. Государственный фонд алгоритмов и программ. Per. №50910000024. — 1991. •

Підп. до друку 06.05.94. Формат 00x84/16. Папір друк. № 2., Офс. друк, Ум. друк. арк. 1,05. Ум. фарбо-відб. 1,27. Обл.-вид. арк. 1,1. Тираж 100. Зам. 551.

Редакційно-видавничий відділ з поліграфічною дільницею Інституту кібернетики імені В. М. Глушкова АН України 252650 Київ МСД 22, проспект Академіка Глушкова, 40.