НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ

ІМЕНІ А. М. ПІДГОРНОГО

Колєчкіна Людмила Миколаївна

УДК 519.85

ВЛАСТИВОСТІ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

З ДРОБОВО-ЛІНІЙНИМИ ЦІЛЬОВИМИ ФУНКЦІЯМИ.

МЕТОДИ ТА АЛГОРИТМИ ЇХ РОЗВЯЗАННЯ

01.05.02 математичне моделювання та обчислювальні методи

Автореферат дисертації

на здобуття наукового ступеня

кандидата фізико-математичних наук

Харків-2002

Дисертацією є рукопис.

Робота виконана в Полтавському національному технічному університеті імені Юрія Кондратюка МОН України

Науковий керівник: доктор фізико-математичних наук, професор

Ємець Олег Олексійович,

Полтавський національний технічний університет

імені Юрія Кондратюка, завідувач кафедри прикладної математики,

інформатики та математичного моделювання

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

Ляшенко Ігор Миколайович,

Національний університет імені Тараса Шевченка

(м. Київ), завідувач кафедри математичних методів

еколого-економічних досліджень;

кандидат фізико-математичних наук, доцент

Гребеннік Ігор Валерійович,

Харківський національний університет радіоелектроніки,

доцент кафедри системотехніки.

Провідна організація: Дніпропетровський національний університет

МОН України, кафедра обчислювальної математики та математичної кібернетики, м.Дніпропетровськ

Захист відбудеться “14” листопада 2002 р. о 14 годині на засіданні спеціалізованої вченої ради Д64.180.01 в Інституті проблем машинобудування ім. А.М.Підгорного НАН України за адресою:

61046, м. Харків, вул. Дм. Пожарського, 2/10

З дисертацією можна ознайомитися у бібліотеці Інституту проблем машинобудування ім. А.М.Підгорного НАН України за адресою: 61046, м. Харків, вул. Дм. Пожарського, 2/10

Автореферат розісланий “_11_” жовтня 2002 р.

Вчений секретар

спеціалізованої вченої ради, к.т.н. Б. П. Зайцев

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

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

Різним аспектам розвязання проблем, повязаних з дослідженням задач дискретної оптимізації, створенням адекватних математичних моделей, а також розробці на цій основі методів оптимізації, присвячені роботи багатьох вчених, в першу чергу В.О. Ємелічева, О.О. Ємця, М.М. Ковальова, Л.М. Козерацької, І. М. Ляшенка, В. С. Михалєвича, О.А. Павлова, В.О. Перепелиці, І. В. Сергієнка, Ю. Г. Стояна, Н. З. Шора, С. В. Яковлєва та інших. Підходи до розвязання дискретних оптимізаційних задач, що базуються на зануренні комбінаторних множин в арифметичний евклідів простір, розробляються зокрема в Харкові та Полтаві.

В останній час з’являється багато праць, що присвячені задачам з дробово-

лінійними функціями. В роботах Н. З. Шора та Д.І. Соломона, Ю.Г. Чернового та Е.Г.Ланге, I. M. Stancu-Minasian та інших досліджуються такі задачі. Але деякі моделі не завжди в повній мірі адекватно відображають властивості відповідних задач або їх змістовну суть. Можна навести ряд прикладів, де множини – області допустимих розвязків таких задач – мають і інші (зокрема переставні) властивості. Тому виникає потреба дослідити та розвязати задачі комбінаторної оптимізації з дробово-лінійною функцією цілі на так званій загальній множині переставлень та інших комбінаторних множинах, що раніше не розглядалися.

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

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

Звязок роботи з науковими планами. Дисертаційна робота виконана в період з 1995 по 2002р. в Полтавському національному технічному університеті ім. Юрія Кондратюка на кафедрі прикладної математики, інформатики та математичного моделювання у відповідності з планами науково-дослідної роботи університету та індивідуальним планом аспірантської підготовки.

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

Для цього в роботі були поставлені основні задачі:

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

2)одержання властивостей комбінаторного многогранника в задачі комбінаторної оптимізації з дробово-лінійною функцією цілі;

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

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

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

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

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

1)вперше запропонована постановка евклідових комбінаторних задач з дробово-лінійними функціями цілі на загальній множині переставлень, сформульовані і доведені властивості многогранника – області допустимих розвязків задачі з лінійною функцією цілі, до якої зводиться задача з дробово-лінійною функцією цілі на переставленнях (встановлені теореми про грані многогранника, суміжність граней, критерій вершини, одержано незвідну систему лінійних обмежень такого комбінаторного многогранника);

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

3)вперше побудовані математичні моделі прикладних задач з дробово-лінійною функцією цілі на переставленнях як задач евклідової комбінаторної оптимізації.

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

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

Результати дисертаційної роботи використовуються у наукових дослідженнях Полтавського національного технічного університету імені Юрія Кондратюка, а також впроваджені в навчальний процес університету при викладанні дисципліни "Елементи комбінаторної оптимізації".

Особистий внесок здобувача. Результати дисертаційної роботи, які подані до захисту, одержані особисто дисертантом. Роботи [7, 8, 14] опубліковані без співавторів. У роботах, написаних у співавторстві дисертанту належить: [1]– встановлення властивостей многогранника в задачі з дробово-лінійною функцією цілі, формулювання та доведення теорем про грані цього многогранника, про суміжність граней цього многоранника, критерій його вершини; [2] – формулювання та доведення властивостей многоранника – області допустимих розвязків задачі; [3] – формулювання та доведення теореми про незвідну систему обмежень комбінаторного многогранника в задачі з дробово-лінійною функцією цілі; [4; 11] –програмна реалізація алгоритму на ПЕОМ та проведення і аналіз числових експериментів; [5] – постановка задач та побудова їх моделей; [6] – формулювання та доведення твердження про відображення точок; [9] – формулювання та доведення теореми про незвідну систему обмежень многогранника; [10] – формулювання та доведення властивостей області допустимих розв’язків задачі; [12] – нове доведення теореми про грані переставного многогранника; [13] – формулювання та доведення теореми.

Апробація результатів дисертації. Основні положення роботи доповідались і обговорювались та отримали схвалення на:

- 6, 7, 8, 9 -й Міжнародних наукових конференціях ім. академіка М. Кравчука (м. Київ, 1997, 1998, 2000, 2002 р.);

- Семінарах наукової ради НАН України “Математичні методи геометричного проектування”, (м. Харків, Інститут проблем машинобудування імені А.М. Підгорного НАН України, 1998 р., 2002р.);

- Міжнародній науковій конференції “Розробка та застосування математичних методів у науково-технічних дослідженнях” (м. Львів, жовтень, 1998р.);

- 49-52 наукових конференціях професорів, викладачів, наукових працівників, аспірантів та студентів Полтавського національного технічного університету імені Юрія Кондратюка. (м. Полтава, 1997- 2000, 2002 р.р.).

Публікації. Результати дисертаційної роботи опубліковані в 14 друкованих працях: брошурі – [1], в 3-х статтях у фахових наукових журналах [2-4], в 2-х статтях у фахових збірниках [5, 6], в 3-х статтях у збірниках наукових праць [7-9], 2-х депонованих рукописах [10, 11], в матеріалах конференцій [12–14].

Структура та обсяг дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел з 149 найменувань (на 15 сторінках), а також містить 3 додатки (на 25 сторінках). Загальний обсяг роботи – 170 сторінок.

ОСНОВНИЙ ЗМІСТ

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

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

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

Нехай Jk={1, ..., k} – множина перших k натуральних чисел, = Jk{0}, J0=, dimL вимірність множини LRn, convM опукла оболонка множини M, vertП множина вершин многогранника П. Під мультимножиною G={g1,..., g} розуміють сукупність елементів, серед яких можуть бути й однакові. Мультимножина, всі елементи якої різні, є множиною. Будь-яку мультимножину G можна задати її основою S (G), тобто множиною всіх її різних елементів, і кратністю – числом повторень кожного елемента основи цієї мультимножини. Упорядкований список кратностей елементів основи мультимножини називають її первинною специфікацією і позначають через [G] =(r1, ..., rn). Тоді G={g1, ..., g} =, де eiR1 iJn, r1+...+ rn=.

Нехай kJ. Упорядкованою k-вибіркою з мультимножини G називається набір

, (1)

де gi jG ijJk , jJk , is it , якщо st sJk , tJk .

Множина E, елементи якої є k-вибірки вигляду (1) з G, називається евклідовою комбінаторною множиною, якщо для довільних елементів e=(a1, ..., ak), e =(b1, ..., bk) цієї множини виконується умова: (e e) ( jJk : aj bj ).

Множина переставлень без повторень з k різних дійсних чисел позначається Pk (G). Множина переставлень із повтореннями з k дійсних чисел, серед яких n різних називається загальною множиною переставлень та позначається Pk n (G).

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

Нехай E евклідова комбінаторна множина, а e, в зображенні (1), елемент E. Відображення

називається зануренням множини E в арифметичний евклідів простір, якщо f

ставить множину E у взаємно однозначну відповідність множині Ef R k за

правилом: для

маємо xj = gi j jJk .

Множина Ef називається спеціальною комбінаторною множиною, або c-комбінаторною множиною; c-множина є також e-множиною.

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

Задача 1. Дано k ділянок з заданими площами g1, g2, ...,gk, на яких засіваються m культур. Визначено мінімальну та максимально допустиму площу для кожної ділянки, зайнятої однією культурою. Відомі необхідні витрати ресурсів кожного виду при вирощуванні однієї культури на 1га площі ділянки. Відома врожайність культури та прибуток з 1га ділянки. Заданий мінімально потрібний обсяг продукції j-ї культури та витрати на зрошення 1 га ділянки, засіяної цією культурою. Необхідно визначити, як засівати ділянки, щоб забезпечити максимальну рентабельність виробництва.

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

Позначено: s=km – добуток кількості ділянок на кількість культур. Розглянуто (s-k) фіктивних ділянок, що мають площі gk+1=0, gk+2=0, ..., gs=0. Тоді мультимножина площ ділянок разом з фіктивними: G ={g1, g2, ..., gk, 0, …,0}, s - кількість її елементів, з яких n - число різних, а Esn(G) – загальна множина переставлень з елементів G.

Позначено: xij – площа i-ї ділянки, засіяної j-ю культурою; Sjmin, Sjmax - мінімально допустима та максимально можлива відповідно площі ділянок засіяних j-ю культурою; r - кількість видів виробничих ресурсів; pij - затрати ресурсів р-го виду на 1га і-ї ділянки, засіяної j-ю культурою; bp - наявність виробничих ресурсів р-го виду; ij - урожайність j-ї культури на і-й ділянці; cij - прибуток, одержуваний з 1га зрошуваної і-ї ділянки, зайнятої j-ю культурою; Qj - мінімально потрібний обсяг продукції, одержаний з ділянок, засіяних j-ю культурою; dij - затрати на зрошення 1га і-ї ділянки, засіяної j-ю культурою.

Задача набуває вигляду: знайти впорядковану пару <F(x*), x*>,

за умови та додаткових лінійних обмеженнях: на використання ресурсів; на посівні площі ; на обсяг одержуваної продукції.

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

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

В підрозділі 3.1. сформульована постановка безумовної задачі оптимізації та підхід до її розв’язування.

Задача: знайти впорядковану пару , таку що

при умові ci, di - задані дійсні числа , а Ekn(G)- загальна множина переставлень.

Для розвязування задачі (2), (3) зроблено перехід до зaдaчі з лінійною функцією цілі за допомогою співвідношень:

Співвідношення (4) задають відображення ()=Е.

Ввaжaється, що >0, 0, i , і : , а (х)=y.

В підрозділі 3.2. досліджується структура опуклої оболонки множини Е в задачі (5), (6).

Нехай елементи мультимножини та її основи впорядковані так g1 ... gk, e1>... >en , тоді із (4) та системи обмежень Пk n (G), де Пk n (G)=conv Ek n (G), маємо:

де jJk, jt, jJi , tJi , iJk , y0 >0, yi 0, i Jk .

Множину, що зaдaнa системою (7)-(9) познaчемо: .

Системa, обмежень (7), (8), визнaчaє опуклий многогрaнний конус з вершиною в точці О(0,...,0), a (9) - гіперплощину, якa перерізає конус і не проходить через його вершину. Тоді - основа пірaміди.

Теоремa 1. 1) Якщо F - m-грaнь многогранника , що визначається системою (7)-(9), то існують множини , де для яких нерівності в (7) перетворюються нa рівності уF. F - множинa розв'язків системи, одержaної з (7)-(9) зaміною нерівностей в (7) рівностями для , де J k - m-1.

2)Якщо для множин нерівності в (7) зaмінити рівностями, то множинa F розв'язків системи, яка складається з цих рівнянь, та рівнянь (8), (9) є m-грaнь многогранника , де

m = dim F = k - {+( - -1)}. (10)

Cумa в (10) знаходиться за всіма , для кожного з яких знaйдеться j, що

(0=0).

Познaчимо множину вершин основи пірaміди .

Нaслідок 1. Якщо , то спрaведливі умови

І нaвпaки, якщо виконуються умови (11)-(13), то yVk .

Твердження 1. Відобрaження , що визнaчaється (4) задає взаємооднозначну відповідність між точками та точками .

З твердження та рівності ()=Евипливає, що Vk =Е = vert .

Теоремa 2. Вершинaми , суміжними з вершиною є усякі вершини, які одержaні з перестaвленням в компонент

, ( p, q Jk ) рівних , і тільки вони.

Якщо елементи мультимножини G та її основи упорядкувати так: g1 ... gk, e1< ... <en , то з (4) та системи обмежень, що описує Пk n (G) отримуємо опис для :

де y0 >0, yj 0, jJk, , .

Означeння 1. Сукупність нeрівностeй (16), які мають однаковe значeння вeличини і, називають і-ю спілкою систeми (15)-(17), а нeрівність (15) цієї систeми - нeрівністю нульової спілки.

Тeорема 3. В системі (15)-(17), яка описує многогранник , надлишковими обмeжeннями є: при r1>1 - всі нeрівності спілок 2, 3, ..., r1; при rn >1- всі нeрівності спілок k-rn , k-rn+1, ..., k-2, і тільки вони.

Якщо k(e1)=r1>1, або k(en)=rn>1, де e1, enS(G), то вилучення з систeми (15)-(17) нeрівностей вказаних спілок згідно теореми 3, як надлишкових, дає систему обмежень, яка є нeзвідною.

Сформульовані та доведені властивості використовуються при побудові алгоритмів по методу комбінаторного відсікання для розв’язування задачі (5), (6).

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

В підрозділі 4.1. формулюється постановка задачі та досліджуються її властивості: визначити пару <F()>

при умові

та додаткових лінійних обмеженнях

, хj= tj j, де jJk. Тут m, k, r - задані натуральні числа, , bi, cj, dj - задані дійсні числа j, jJm, i Jr,

Застосовується відображення :

таке що , ()=Е , zj=yj j, де j. Ввaжaтимемо, що z0 >0, zj 0, j, j, таке що . Задача (20)-(22) набуває вигляду: знайти впорядковану пару < Ф (z*), z*>:

при умові

(22)

та додаткових лінійних обмеженнях

(23)

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

З твердження 1 випливає, що для множини в задачі (24)-(26) виконується властивість: = vert, де є опуклою оболонкою множини , що описується як розв’язок системи лінійних обмежень:

y0 >0, yj 0, jJk, , .

Властивості многогранника аналогічні властивостям . Вони використовуються при розв’язуванні задачі (24)-(26) методом комбінаторного відсікання. В методі комбінаторного відсікання для розвязування задач з дробово-лінійними цільовими функціями на загальній множині переставлень використовується метод відкидання неактивних обмежень в комбінації з методом послідовного підєднання обмежень (МППО).

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

1)здійснюємо перехід від задачі (20)-(22) з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі (24)-(26) за допомогою перетворень (23);

2)здійснюємо релаксацію задачі (24)-(26): умову (25) замінюємо умовою

; (27)

3)задачу (24), (26), (30) згідно МППО записуємо в вигляді: визначити пару

, (28)

при =0, де , де , cj, c0 - задані дійсні числа jJm, де область визначається системою S, в яку входять обмеження, що складаються з (26), (27)-(29);

згідно МППО на першому етапі при =1: формуємо систему S1 лінійних обмежень, що визначає область D1: D1D0 (S1S), де в систему S1 входять обмеження (26), та обмеження (27) нульової спілки, першої, (k–1) та k спілок з (27)-(29) та (29);

4) розвязує мо задачу лінійного програмування (ЗЛП) (31) на області D при поточному значенні (1) модифікованим (або двоїстим) симплекс-методом;

5) за точкою , визначаємо точку , де , та перевіряємо виконання всіх обмежень системи (27)-(29) в ній, тобто ; якщо ця умова виконується, то перехід на пункт 8; інакше – на пункт 6;

6)формуємо систему S+1, залучивши до системи обмежень S нерівність з (28), яка в точці не виконується, тоді область D, що описується системою S замінюється на область D+1, яка задається системою обмежень S+1, D D+1;

7) збільшуємо на одиницю і переходимо до пункту 4;

8)перевіряємо, чи задовольняє розвязок умову (25), якщо умова виконується, то перехід на пункт 9, інакше – на пункт 10;

9)здійснюємо перехід від задачі (24)-(26) до задачі (20)-(22) за формулами , tj=xj , отримуємо розвязок задачі (20)-(22); зупинка.

10)знаходимо суміжні до вершини многогранника, який описується системою S;

11)визначаємо півпростір, межа якого проходить через ці суміжні до вершини, а точка не належить йому, тобто будуємо відсікання, якому знайдена точка не задовольняє, в вигляді

;

12)формуємо систему S+1, яка описує область D+1: відсікання (34) підєднуємо до системи S , область D замінюємо на область D+1 (D D+1);

13) збільшуємо на одиницю;

14)визначаємо ті неактивні обмеження в системі S, які можливо та необхідно відкинути.;

15)формуємо систему S+1, в якій неактивні обмеження відсутні, тоді область D, що описується системою S замінюється на область D+1, яка задається системою обмежень S+1;

16) збільшуємо на одиницю; здійснюємо перехід на пункт 4.

Для ефективної перевірки умови в пункті 5 методу комбінаторного відсікання сформульована та доведена наступна теорема.

Теорема 4. Нехай , , , j. Тоді з виконання обмеження , що належить спілці нерівностей за номером і системи (27)-(29), випливає виконання і всіх інших обмежень і-ї спілки цієї системи, де іJk-1, в точці .

По даному методу комбінаторного відсікання для задач з дробово-лінійною цільовою функцією побудовані та реалізовані алгоритми на мові Pascal в середовищі Delphi. Були проведені числові експерименти.

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

В таблиці використовуються позначення: k – кількість елементів G; n – кількість різних елементів; b – інтервал, з якого вибираються елементи G; r – кількість додаткових обмежень; q – кількість підєднаних обмежень; p – кількість відкинутих обмежень; s – кількість відсікань; T – час рахунку; – параметр, з допомогою якого визначається обмеження, що треба відкинути.

На основі аналізу даних числових експериментів можна зробити висновок, що алгоритми, побудовані на основі методу відсікання для задач з дробово-лінійною функцією цілі, є ефективними для практичних розрахунків в даній програмній реалізації для задач розглянутого класу при параметрах задачі в межах: k 20, b = [1;100], = {0,01; 0,001}. В частковому випадку, коли знаменник в (20) рівний одиниці, алгоритм може використовуватися для розв’язування лінійних задач на переставленнях.

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

Висновки

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

Дисертаційна робота присвячена побудові та аналізу математичних моделей класу задач з дробово-лінійними цільовими функціями на переставних множинах. Результати дисертаційної роботи одержані на основі застосування теорії та підходів, розвинутих раніше в рамках евклідової комбінаторної оптимізації, можуть бути використані для дослідження та розв’язування нових задач комбінаторної оптимізації.

Серед основних результатів роботи слід зазначити такі:

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

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

3)розвинуто метод комбінаторного відсікання для розв’язування нового класу задач евклідової комбінаторної оптимізації з дробово-лінійними функціями цілі та додатковими лінійними обмеженнями на переставних множинах; вперше побудовано та обгрунтовано скінченний алгоритм цього методу відсікання для розглянутого класу задач. Проведені числові експерименти, які показали практичну ефективність запропонованого методу відсікання для розв’язування такого класу задач. Метод може бути застосований для розвязування практичних задач, які мають математичну модель у вигляді евклідових комбінаторних задач оптимізації з дробово-лінійними функціями цілі на переставній множині.

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

1. Ємець О.О., Колєчкіна Л.М., Недобачій С.І. Дослідження областей визначення задач евклідової комбінаторної оптимізації на переставних множинах. – Полтава: ПДТУ, Легат.- 1999. - 64с.

2. Ємець О.О., Колєчкіна Л.М. Задача оптимізації на переставленнях з дробово-лінійною цільовою функцією: властивості множини допустимих розвязків // Український математичний журнал. – 2000. – Т. 52, №12. – С. 1630-1640.

3. Емец О.А., Недобачий С.И., Колечкина Л.Н. Неприводимая система ограничений комбинаторного многогранника в дробно-линейной задаче оптимизации на перестановках // Дискретная математика. – 2001. – Т.13, №1. – С.110-118.

4. Емец О.А., Емец Е.М., Колечкина Л.Н. Использование метода отсечений при раскрое // Радиоэлектроника и информатика. – 1998, №3, С.114 –117.

5. Ємець О.О., Колєчкіна Л.М. Моделювання деяких прикладних задач оптимізаційними задачами з дробово-лінійною функцією цілі на переставленнях // Волинський математичний вісник. – 2000. – № 7 - С.116-119.

6. Ємець О.О., Колєчкіна Л.М. Розвязування оптимізаційних задач з дробово-лінійною цільовою функцією на загальній множині переставлень // Вісник державного університету “Львівська політехніка” – 1998. – № 337 – С.317-320.

7. Колєчкіна Л.М. Про одну задачу оптимізації з дробово-лінійною функцією цілі // Збірник наукових праць Полтавського державного пед. ін.-ту ім. В.Г.Короленка. – 1998 – Випуск 3. – С.32-35.

8. Колєчкіна Л.М. Задачі з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями на загальній множині переставлень // Проблеми праці, економіки та моделювання: Збірник наук. праць – 1998. – С.116-117.

9. Колєчкіна Л. М., Недобачій С. І. Дослідження області визначення задачі комбінаторної оптимізації з дробово-лінійною функцією цілі на переставленнях // Збірник наукових праць Полтавського державного пед. ін.-ту ім. В.Г.Короленка – 1998. – Випуск 3 – С.18-24.

10. Ємець О.О., Колєчкіна Л.М. Дробово-лінійна задача оптимізації на загальній множині переставлень, та властивості області її допустимих розвязків. / Полт. тех. ун-т. – Полтава, 1997. – 25с. – Деп. в УкрІНТЕІ 30.12.97, №575 - Уі 97.

11. Емец О.А., Емец Е.М., Колечкина Л.Н. Отсечения при решении задачи раскроя как оптимизации на перестановках. Полт. гос. тех. универ. – Полтава, 1998 – 22с., Деп. в ГНТБ 10.09.98, №409 – Ук98.

12. Ємець О. О., Колєчкіна Л. М. Про нове доведення теореми про грані загального переставного многогранника. // В кн.: Матеріали конференції. Шоста Міжнародна конференція імені академіка М. Кравчука ( 15-17 травня 1997р.). – Київ. – 1997. – С.160.

13. Ємець О.О., Колєчкіна Л.М., Недобачий С.І. Незвідна система обмежень многогранника допустимих розвязків дробово-лінійної задачі оптимізації на переставленнях // В кн.: Матеріали конференції. VIII Міжнародна наукова конференція імені академіка М.Кравчука ( 11-14 травня 2000р.). – Київ. – 2000. – С. 300-301.

14. Колєчкіна Л.М. Властивості задач комбінаторної оптимізації з дробово-лінійнимицільовими функціями. Методи і алгоритми їх розв’язання.// В кн.: Матеріали конференції. Дев’ята Міжнародна наукова конференція імені академіка М.Кравчука ( 16-19 травня 2002р.). – Київ. – 2002. – С. 431-432.

АНОТАЦІЯ

Колєчкіна Л. М. Властивості задач комбінаторної оптимізації з дробово-лінійними цільовими функціями. Методи і алгоритми їх розвязання. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут проблем машинобудування імені А. М. Підгорного, Харків, 2002.

В дисертації викладено дослідження властивостей задач евклідової комбінаторної оптимізації з дробово-лінійними цільовими функціями на переставних множинах. Розвинуто метод комбінаторного відсікання та вперше побудовані алгоритми розв’язування таких задач. Зроблено перехід від задачі з дробово-лінійною функцією цілі до задачі з лінійною функцією цілі. Для останньої сформульовані та доведені властивості області допустимих розв’язків задачі, опукла оболонка якої представляє собою многогранник: теорема про грані многогранника, критерій вершини, критерій суміжності граней. Встановлено незвідну систему лінійних обмежень цього многогранника. Алгоритми, побудовані по методу комбінаторного відсікання, програмно реалізовані на ПЕОМ. Зроблено аналіз алгоритмів на основі числових експериментів. Побудовано моделі прикладних задач з дробово-лінійною цільовою функцією на переставних множинах.

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

SUMMARY

Kolyechkina L. N. The properties of tasks of the combinatorial optimization with the fraction-linear aim function. Methods and algorithms for its decisions. – Manuscript.

This dissertation, which is submitted to obtain a scientific degree of a candidate of physics-mathematics sciences on the 01.05.02 speciality mathematical modelling and numerical methods. – A. M. Pidgorny’s Institute for problems in machinery, National Academy of Sciences of Ukraine, Kharkiv, 2002.

In the dissertation the research of properties of tasks Euclidean combinatorial optimization with linear-fractional criterion functions on permutation sets is stated. The method combinatorial of cutting off is advanced and for the first time algorithms of the decision of such tasks are constructed. The transition from tasks with linear-fractional function of the purpose to a task with linear criterion function is made. For last task and the properties of a range of definition are formulated they are proved, which convex hull represents combinatorial polyhedron: the theorem of edges of a polyhedron, criterion of top, criterion of a contiguity of sides. The nonreducible system of linear restrictions of this polyhedron is obtained. The approach and methods of a solution of a problem with linear-fractional function of the purpose on permutations is stated and program algorithm of a solution on PC is realized. The analysis of algorithms is made.

The models of applied tasks with linear-fractional criterion functions on permutation sets are constructed.

Key words: combinatorial optimization, combinatorial set, permutation sets, linear-fractional functions, nonreducible system, convex environment, method combinatorial of cutting off.

АННОТАЦИЯ

Колечкина Л. Н. Свойства задач комбинаторной оптимизации с дробно-линейными целевыми функциями. Методы и алгоритмы их решения. – Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Институт проблем машиностроения имени А. Н. Подгорного НАН Украины, Харьков, 2002.

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

Сформулированы постановки задач евклидовой комбинаторной оптимизации с дробно-линейными функциями цели на перестановках: а) как безусловной задачи оптимизации; б) как полностью комбинаторной задачи оптимизации с дополнительными линейными ограничениями; в) как частично комбинаторной задачи оптимизации с дополнительными линейными ограничениями.

Сделан переход от задачи с дробно-линейной целевой функцией к линейной. Для линейной задачи сформулированы и доказаны свойства области допустимых решений – комбинаторного многогранника, в частности: теорема о гранях многогранника, критерий вершины, критерий смежности граней. Установлено количество смежных с произвольной вершиной вершин многогранника. Получена неприводимая система линейных ограничений такого комбинаторного многогранника. Определены уравнения гиперграней, выраженные через неизбыточные ограничения, установлено их количество.

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

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

Изложены подходы и развит метод комбинаторного отсечения решения задач комбинаторного типа с дробно-линейными функциями цели на перестановках при дополнительных линейных ограничениях. Разработаны и программно реализованы на ПК Pentium-233 алгоритмы решения таких задач. Сделан анализ представленных алгоритмов на основании проведенных числовых экспериментов.

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