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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М. ГЛУШКОВА

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

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

Транспортні задачі комбінаторного типу, їх властивості та розв'язування

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

Парфьонова ТЕТЯНА ОЛЕКСАНДРІВНА

Київ-2010

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

Робота виконана у ВНЗ Укоопспілки «Полтавський університет економіки і торгівлі»

Науковий керівник: доктор фізико-математичних наук, професор Ємець Олег Олексійович, ВНЗ Укоопспілки «Полтавський університет економіки і торгівлі», завідувач кафедри математичного моделювання та соціальної інформатики

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

старший науковий співробітник

Донець Георгій Панасович,

Інститут кібернетики імені

В.М. Глушкова НАН України, завідувач відділу економічної кібернетики

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

професор Ляшенко Ігор Миколайович, Київський національний університет ім. Тараса Шевченка, професор кафедри математичної інформатики

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

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

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

Серед науковців України, відомих своїми досягненнями в дослідженні задач дискретної та комбінаторної оптимізації, розробками методів їх розв'язування, в першу чергу треба назвати вчених: академіків І. В.Сергієнка, В.С.Михалевича, Н.З.Шора, член-кореспондентів А.М.Гупала, Ю.Г.Стояна, а також І.В.Гребенніка, Л.Ф.Гуляницького, Г.П.Донця, О.О.Ємця, І.М.Ляшенка, О.А.Павлова, А.В.Панішева, В.О.Перепелицю, Ю.Ю.Червака , В.П.Шила та багатьох інших. Відомий доробок у розвиток теорії та застосування нечітких множин для врахування невизначеності при аналізі складних об'єктів, систем, явищ та процесів вітчизняних вчених член-кореспондента І.М.Парасюка, а також І.Б.Сіроджи, О.Ю.Соколова та багатьох інших дослідників. Така велика увага відомих вчених до задач дискретної оптимізації, до врахування невизначеності при їх розв'язанні є ще одним свідченням актуальності теми дисертації.

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконувалася на кафедрі математичного моделювання та соціальної інформатики Полтавського університету економіки і торгівлі згідно з індивідуальним планом аспірантської підготовки та науково-дослідними темами кафедри: №275/08 „Розвиток теорії та методів комбінаторної оптимізації” (2009-2010 р.р.) №0109U007659 та теми №213/04 „Евклідова комбінаторна оптимізація” (2005-2008 р.р.).

Мета і завдання дослідження. Метою роботи є дослідження транспортних задач комбінаторного типу, розробка та дослідження методів розв'язування таких задач, розвиток апарату нечітких множин для застосування при розв'язуванні комбінаторних ТЗ (КТЗ). Мета конкретизується в задачах: 1)формалізація КТЗ та дослідження властивостей одержаних моделей; 2)розвиток підходів та створення точних та наближених методів розв'язування КТЗ; 3)введення та дослідження операцій та відношень з нечіткими числами з континуальним носієм для використання їх при розв'язуванні КТЗ; 4)розвиток підходів врахування стохастичної невизначеності в КТЗ.

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

Предмет дослідження - КТЗ, методи розв'язування таких задач як в умовах визначеності, так і з урахуванням невизначеності даних.

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

Наукова новизна одержаних результатів. Всі результати, що виносяться в дисертації на захист, є новими:

- вперше

1) введено до розгляду КТЗ на переставленнях (КТЗП) та досліджено її властивості, зокрема необхідні умови розв'язності та достатні умови нерозв'язності, що дозволяє використовувати такі задачі на практиці, а властивості при розробці методів розв'язування КТЗП;

2) запропоновано та обґрунтовано наближений метод розв'язування КТЗП, що дозволяє розв'язувати її з наперед заданою точністю;

3) розроблено та обґрунтовано алгоритм послідовного аналізу значень змінних для КТЗП, що розвиває методологію послідовного аналізу варіантів та дозволяє одержувати розв'язок;

4) розглянуто КТЗП з невизначеністю, що задається нечіткими числами з континуальним носієм або стохастичними параметрами, та запропоновано підходи до їх розв'язування, що дозволяє на практиці розв'язувати КТЗП з невизначеністю;

- розвинуто

1) апарат методу гілок та меж (МГМ): оцінками допустимих множин в КТЗП, властивостями цих оцінок, правилами галуження допустимих множин в КТЗП, що дозволяє застосовувати МГМ до КТЗП;

2) апарат нечітких чисел з континуальним носієм введенням нових операцій та відношень; доведено, що на відміну від інших, вони мають необхідні для розв'язування задач КО властивості.

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

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

Особистий внесок здобувача. Всі результати дисертації, що виносяться на захист, отримані особисто автором. Дисертанту належить: [1,7] - наближений метод розв'язування; [2] - оцінка допустимої множини в МГМ при розв'язуванні КТЗП та її властивості; [3] - операції (та їх властивості) для нечітких чисел з континуальним носієм, модель КТЗП в «нечіткій» постановці, підходи до її розв'язування; [4] - модель КТЗП; [5,6,11] - підходи до точного розв'язування КТЗ, економічні застосування КТЗП; [8] - підходи до моделювання та розв'язування КТЗП зі стохастичними параметрами; [9,10,17] - застосування методу комбінаторного відсікання до розв'язування КТЗП; [16] - різні постановки та методи для КТЗП.

Апробація результатів дисертації. Основні результати роботи доповідались та отримали схвалення на: X науковій конференції «Проблеми економічної кібернетики» (2005, Київ); 11-тій міжнародній науковій конференції ім. ак. М. Кравчука (2005, Київ), Міжнародній конференції «Сучасна стохастика: теорія і застосування» (2006, Київ), ІІІ-ій міжнародній школі-семінар «Теорія прийняття рішень» (2006, Ужгород), Міжнародному симпозіумі «Питання оптимізації обчислень» (2007, Кацивелі), 2-ій науковій конференції «Комп'ютерна математика в інженерії, науці та освіті» (2008, Полтава), Українському математичному конгресі (2009, Київ), Всеукраїнській науково-практичній конференції «Інформатика та системні науки» (2010, Полтава) та інших.

Публікації. Основні результати дисертації опубліковані в 18 наукових публікаціях автора: 4 статті (з них 3 у фахових виданнях за переліком ВАК України), 14 - у збірниках матеріалів та тез доповідей конференцій.

Структура та об'єм роботи. Дисертація складається зі вступу, основної частини з чотирьох розділів, висновків, списку використаних джерел з 167 найменувань. Загальний обсяг дисертації 165 сторінок, основного тексту 131 сторінок.

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

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

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

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

Мультимножина називається різницею мультимножини та її підмультимножини (позначимо , де ), якщо: (){()()}; і при цьому ()= ()().

Нехай з мультимножини , де , , утворена упорядкована -вибірка

, (1)

Якщо для деякого індексу виконується , то упорядковані -вибірки та вигляду (1) називають різними. Евклідовою комбінаторною множиною називається множина, елементи якої є різними впорядкованими -вибірками вигляду (1).

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

Нехай - евклідова комбінаторна множина та задано функціонал на . Під основною задачею евклідової КО розуміють задачу знаходження ; .

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

. (2)

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

Моделювання сучасних систем, явищ, об'єктів та процесів не може відбуватися без врахування в них невизначеності вхідних даних та параметрів. Врахування невизначеності може відбуватися різними шляхами. Актуальним вбачається дослідження КТЗ, в яких невизначеність задається (враховується) за допомогою апарату нечітких множин, зокрема з континуальним носієм, а також стохастичної невизначеності. Таким чином, актуальним вбачаються дослідження КТЗ, в яких дані (параметри) задаються звичайними дійсними числами („чітка” постановка) та і нечіткими числами („нечітка” постановка), а також зі стохастичною невизначеністю.

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

, (3)

, ; , ; (4)

, (5)

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

Теорема 2.1. За умови (2) для того, щоб задача (3)-(5) мала розв'язок необхідно, щоб елементи в задовольняли умову .

Наслідок з теореми 2.1. За умови (2) транспортна задача (3)-(5) еквівалентна транспортній задачі, що включає співвідношення (3), (5), а умови (4) замінюються в ній рівностями

, . (6)

Теорема 2.2. Для того, щоб КТЗП (3)-(5) за умови (2) мала розв'язок необхідно, щоб елементи в задовольняли умовам:

, ; , ; (7)

де ; ; , .

Якщо - мультимножина використаних як в (6) елементів , , то при цьому (6) набувають вигляду:

, , , . (8)

Нехай та - кількість змінних в лівій частині відповідної рівності (6), які не належать . Нехай , , , , .

Теорема 2.4. 1) Якщо , то (8) не виконується для жодного набору з елементів . 2) Якщо , то (8) не виконується для будь-якого набору з елементів .

Показана можливість моделювання КТЗП як задачі евклідової частково КО та введено поняття розв'язку КТЗ за несумісності обмежень.

У третьому розділі розглянуто методи розв'язування КТЗП.

Досліджено можливості застосування до КТЗП методу гілок та меж (МГМ). Для цього треба задати правила оцінювання допустимих множин та правила їх розбиття і відсікання. Дано означення оцінки допустимих множин в КТЗП (3), (5), (6). Нехай елементи , (), упорядковані по неспаданню: . Нехай деякі змінні задачі (3), (5), (6) фіксовані як елементи з :

(9)

Не обмежуючи загальності, упорядкуємо нумерацію цих змінних:

. (10)

З умов (9) та (10) маємо також

. (11)

Упорядкуємо по незростанню не визначені в умові (11) змінні КТЗП (3), (5), (6) (та позначимо їх , , ),

, (12)

та не використані в (9) елементи . Нехай - мультимножина використаних в (9) елементів , ,

. (13)

Позначимо коефіцієнти цільової функції (5) з тими ж індексами, що і змінні з (9), так: , де - коефіцієнт при з (9). Коефіцієнти , що стоять при невизначених змінних з (12), позначимо . Введемо нумерацію серед чисел та :

; (14)

. (15)

Теорема 3.1. Для множини допустимих розв'язків задачі (3), (5), (6), що задовольняють умову (9), в МГМ оцінкою може бути:

, (16)

де параметри задовольняють умови (11), (13)-(15).

Показано, що оцінка (16) має властивість, яка дозволяє в МГМ значно скоротити кількість вершин, що треба розгалужувати.

Нехай , де

(17)

Нехай , де - множина, що містить будь-який з векторів , для яких виконуються умови (13), (17), а - множина допустимих розв'язків КТЗП (3), (5), (6), що задовольняють умову (9). Доведено, що тоді між оцінками вигляду (16) для множин допустимих розв'язків та задачі (3), (5), (6) виконується співвідношення: .

Нехай , де

, (18)

Нехай за умов (12), (13), (15), (18) з множини сформуємо дві множини векторів та вигляду

,.

Зауважимо, що перші елементів в та однакові; елемент - це або відповідно. Оскільки , то в силу (18) , а з (15) маємо . Нехай - підмножина допустимих розв'язків, в якій координати допустимого розв'язку, що не є , визначені. Нехай ; .

Теорема 3.3. Для оцінок множин та має місце: .

Запропоновані та обґрунтовані правила відсікання та галуження.

Правило А. Якщо при галуженні в МГМ для КТЗП (3), (5), (6) допустима підмножина визначається заданням певної кількості змінних з , після чого з рівнянь (6) підстановкою визначених змінних отримано два рівняння вигляду

; (19)

, (20)

де , і якщо , то множина відсікається, як така, що не має допустимих розв'язків.

Правило В. Якщо за умов правила А - і , такий, що , то в (19) та (20): ; , і задавши так можна розгалузити.

Правило С. Якщо при утворенні допустимої підмножини з (6) утворилась система обмежень з невідомими, то, не проводячи подальших галужень, її розв'язують. Це дає одне з трьох: 1) система несумісна: - відсікаємо; 2) ранг матриці системи , система сумісна - отримуємо одноелементну підмножину - допустимий розв'язок; 3) матриця системи має ранг менший : можна галузити далі.

Запропоновано та обґрунтовано наближений метод розв'язування КТЗП, що дає бажану точність розв'язку. Використовуються перетворення методу комбінаторного відсікання і МГМ. Алгоритм: Крок 1. Здійснюється розрахунки за методом комбінаторного відсікання для КТЗП до отримання розв'язку поточної допоміжної задачі лінійного програмування. Крок 2. Здійснюється розрахунки за МГМ для для КТЗП до отримання наступного допустимого розв'язку . Крок 3. Перевірка , де - точність розв'язку за функціоналом. Якщо умова кроку 3 виконалась, то - є наближеним розв'язком КТЗП. Зупинка. Інакше точка відсікається за правилами методу комбінаторного відсікання, перехід на крок 1.

Теорема 3.6. Якщо виконується , то має місце: , де - мінімальне значення функціоналу.

Запропоновано та обґрунтовано алгоритм, що послідовно розглядає можливі варіанти множин допустимих розв'язків, відбраковуючи безперспективні. Цей алгоритм використовує методологію послідовного аналізу варіантів. Розглядається КТЗП (5)-(7). В алгоритмі використовуються теореми 2.1, 2.2 та 2.4.

Алгоритм:

Крок 1. Перевіряється виконання теореми 2.1. Якщо теорема 2.1 виконується, то замінюємо нерівності в (4) рівностями (6) і переходимо до кроку 2, якщо ні - зупинка: задача розв'язків не має.

Крок 2. Перевіряємо виконання теореми 2.2. Якщо теорема 2.2 виконується, то перехід до кроку 3, якщо ні - задача розв'язків не має.

Крок 3. Упорядкуємо числа , ; по не зростанню, позначивши їх , : , . Елементи упорядковуємо: . На етапі () вибираємо новий доданок з коефіцієнтом рівним , відповідне вважаємо рівним . Підставляємо в (3) та (6) і аналізуємо обмеження, використовуючи теорему 2.4. При необхідності вибираємо рівним наступному за збільшенням елементу , що залишилися не вибраними, і т.д. Якщо призначено останнє - зупинка, одержано розв'язок. Протиріччя в системі обмежень при підстановці чергової змінної озна-чає недопустимість множини точок з уже визначеними координатами. Тоді останнє призначене задається як наступний за збільшенням елемент , який не вибрано. Якщо всі елементи з вибрані, так же змінюється попередньо призначене . Якщо це - перше вибране , а в все вибрано, то задача не має розв'язку.

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

Означення 4.1. Нечітким числом (НЧ) з носієм, що має потужність континуум будемо називати , де ; ; ; ; ; ; на - зростаюча, а на - спадаюча функція. Функцію називають функцією належності, - називають носієм НЧ.

Дійсне число можна розглядати як граничний випадок НЧ, коли ; ; , .

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

Позначимо - характеристичний порівнювач - функцію НЧ , що відображає множину нечітких чисел в множину дійсних чисел . Необхідні властивості : 1) для лінійного порядку на множині НЧ має виконуватись: якщо , то , та якщо , то (або ); 2) для суми НЧ , що використовується в моделі, повинна виконуватись рівність: ; 3) для суми НЧ та лінійного порядку має виконуватись правило: якщо , то .

Далі в роботі введено суму НЧ, лінійний порядок на множині НЧ, характеристичний порівнювач, які мають названі властивості.

Означення 4.8. Характеристичним порівнювачем НЧ , , називається функція, яка НЧ ставить у відповідність число за правилом: , де - множина НЧ з носієм потужності континуум.

Означення 4.10. Два НЧ і назвемо упорядкованими за зростанням, якщо а) або ; б) або , але , де , , що при , а . Будемо говорити, що передує за зростанням. Позначка: .

Означення 4.11. Два НЧ та називаються рівними, якщо ; ; , . Позначка: .

Означення 4.12. Два НЧ і називаються впорядкованими за не спаданням (позначатимемо ), якщо: а) або ; б) або .

Теорема 4.1. Впорядкованість є лінійним порядком.

Означення 4.13. Нехай є НЧ , . Сумою назвемо НЧ (позначка: ), де , , , а утворюється множиною пар

;

, . Елементи з утворюють функцію двох змінних та : . Носій НЧ - це . Значення ж функції належності знаходяться за формулою: , де ; , а , .

Теорема 4.2. Якщо ; - довільні НЧ з X, то для характеристичного порівнювача , має місце властивість: .

Теорема 4.3. Для будь-яких трьох НЧ ; ; таких, що , , , має місце: якщо , то .

Теорема 4.4. Для введеного лінійного порядку упорядкованість виконується тоді і тільки тоді, коли .

Означення 4.14. Нехай на множині НЧ введено лінійний порядок (означення 4.10-4.12): . НЧ називається мінімумом, а НЧ - максимумом в множині НЧ .

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

Обсяги перевезень продукту від виробника до споживача позначимо та будемо вважати такими же числами як і числа з . Якщо - НЧ, то можна знаходити за принципом розширення Заде.

Означення 4.15. Нехай , а - НЧ з континуальним носієм, . Добутком назвемо число , де , , , .

Модель КТЗПНП можна записати у вигляді: знайти мінімум за умов , ; , ; , де мінімум, сума, добуток, лінійний порядок - означені вище, а - множина нечітких переставлень з мультимножини . Якщо - НЧ з континуальним носієм, то під множиною розуміють таке.

Означення 4.16. Нехай - множина НЧ з континуальним носієм, де , . Тоді кортеж , де називають переставленням з НЧ з континуальним носієм, а множину всіх таких переставлень називають множиною переставлень з НЧ з континуальним носієм та позначають .

Такі ТЗ можна розв'язувати МГМ з допустимою множиною . Оцінкою підмножини допустимої множини в МГМ, може виступати , де - множина клітин транспортної таблиці, що вже завантажена перевезенням (саме ці перевезення визначають множину ). Порівняння оцінок та значення цільової функції в МГМ може здійснюватися за характеристичним порівнювачем. Метод галуження може використовуватися довільний.

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

Користуючись введеними операціями (сума, мінімум), стохастичними аналогами детермінованих чисел, введеним лінійним порядком побудовано математичну модель КТЗП з випадковими даними, яку можна розв'язувати МГМ. Оцінки та галуження можна здійснювати, як це розглянуто в розділі 3, використовуючи введені операції та порядок. Запропоновано способи врахування ризику порушення умов задачі при конкретній реалізації випадкової величини.

ВИСНОВКИ

У дисертації наведено вирішення нового наукового завдання: дослідження комбінаторних транспортних задач на переставленнях (КТЗП), розробка методів, підходів до її розв'язування як в умовах визначеності даних, так і за „нечіткої” та стохастичної невизначеності.

У дисертації вперше:

- введено до розгляду КТЗП та досліджено її властивості, зокрема необхідні умови розв'язності та достатні умови нерозв'язності, що дозволяє використовувати такі задачі на практиці, а властивості - при розробці методів розв'язування КТЗП;

- запропоновано та обґрунтовано наближений метод розв'язування КТЗП, що дозволяє розв'язувати її з наперед заданою точністю;

- розроблено та обґрунтовано алгоритм послідовного аналізу значень змінних для розв'язування КТЗП;

- введено до розгляду КТЗП з невизначеністю, що задається нечіткими числами з континуальним носієм або стохастичними параметрами та запропоновано підходи до їх розв'язування, що дозволяє розв'язувати практичні КТЗП;

розвинуто:

- апарат методу гілок та меж: оцінками допустимих множин в КТЗП, властивостями цих оцінок, правилами галуження допустимих множин в КТЗП, що дозволяє застосовувати метод гілок та меж до КТЗП;

- апарат нечітких чисел з континуальним носієм введенням нових операцій та відношень; доведено, що на відміну від інших, вони мають необхідні для розв'язування задач КО властивості.

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

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

1. Ємець О.О. Наближений метод для розв'язування комбінаторних транспортних задач / О.О. Ємець, Т.О. Парфьонова // Радиоэлектроника и информатика. - 2006. -№2. - С. 39-41.

2. Ємець О.О. Оцінювання допустимих множин розв'язків комбінаторної транспортної задачі на переставленнях, що розв'язується методом гілок та меж / О.О. Ємець, Т.О. Парфьонова // Наукові вісті НТУУ «КПІ». - 2010 - №1. - С. 21-28.

3. Емец О.А. Операции над нечеткими числами с носителем мощности континуум для моделирования в комбинаторной оптимизации / О.А. Емец, Т.А. Парфенова // Проблемы управления и информатики. - 2010 - №2. - С. 86-101.

4. Ємець О.О. Транспортні задачі комбінаторного типу / О.О. Ємець, Т.О. Парфьонова // Вестник Харьк. нац. автомоб.-дорож. у-та. - 2005. - Вып. 29. - С. 162-164.

5. Ємець О.О. Про розв'язування транспортних задач комбінаторного типу / О.О. Ємець, Т.О. Парфьонова // Тези допов. Х наук.-метод. конф. „Проблеми економічної кібернетики” (17-15 вересня 2005 р., м Київ). - Донецьк: АПЕКС, 2005. - С. 107-109.

6. Ємець О.О. Комбінаторна транспортна задача в мікроекономічному прогнозуванні/О.О. Ємець, Т.О. Парфьонова // Тези допов. Всеукраїн. наук.-практ. конф. „Сучасні моделі і методи соціально-економічних процесів в Україні” (13-14 квітня 2006 р., Київ). - К.: КНУ, 2006. - С.56-58.

7. Ємець О.О. Наближене розв'язування комбінаторних транспортних задач / О.О. Ємець, Т.О. Парфьонова // ХІ міжн. наук. конф. ім. М. Кравчука (18-20 травня 2006, Київ): Матер. конф. - К.: Задруга, 2006. - С. 701.

8. Yemets` O. O. Transport Combinatorial Stochastic Tasks and Their Sol-ving / O.O. Yemets`, T.O. Parfonova // International Conf. “Modern Stochastic: Theory and Appl.: Conference materials (June 19-23, 2006). - P. 281-282.

9. Ємець О.О. Математична модель транспортної задачі на переставленнях та її розв'язування методом комбінаторного відсікання / О.О. Ємець, Т.О. Парфьонова // III-я міжн. шк.-семінар „Теорія прийняття рі-шень” (Ужгород, 2-7 жовтня). - Ужгород: УжНУ, 2006. - С. 53.

10. Ємець О.О. Комбінаторні транспортні задачі та їх розв'язування / О.О. Ємець, Т.О. Парфьонова // Тези допов. міжн. симп. «Питання оптимізації обчислень (ПОО-ХХХІІІ)» (23-28 вересня 2007 р., Кацивелі). - Київ: ІК НАН України , 2007. - С. 104.

11. Ємець О.О. Задача вибору плану обслуговування клієнтів фінансового ринку та її розв'язування / О.О. Ємець, Т.О. Парфьонова // Тези допов. міжн. наук.-прак. конф. «Фінансові ринки та інститути» 7-8 грудня 2007 р. У 2-х т. - Т.2. - Х.: ІНЖЕК, 2007. - С. 371-373.

12. Парфьонова Т.О. Комп'ютерні технології для транспортних задач комбінаторного типу / Т.О. Парфьонова // Тези допов. Всеукраїн. конф. „Структурні зміни в економіці та освіті під впливом інформаційно-комунікаційних технологій” 24-25 квітня 2008 р. - Полтава: РВВ ПУСКУ, 2008. - С. 112-113.

13. Парфьонова Т.О. Застосування методу гілок та меж до комбінаторних транспортних задач / Т.О. Парфьонова // Тези допов. IV міжн. наук. конф. „Методологія та практика менеджменту на порозі XXI століття” 15-16 травня 2008. - Полтава: РВВ ПУСКУ, 2008. - С. 352-353.

14. Парфьонова Т.О. Евклідова комбінаторна транспортна задача на переставленнях, її розв'язування методом гілок та меж / Т.О. Парфьонова // Матеріали друг. наук.-техн. конф. „Комп'ютерна математика в інженерії, науці та освіті”, Полтава, 29-31 жовт. 2008 - К: НАНУ, 2008. - С. 24.

15. Парфьонова Т.О. Моделювання та оптимізація витрат транспортних кооперативів / Т.О. Парфьонова // Міжн. Наук. конф. “Споживча кооперація ХХІ століття: уроки трансформаційних реформ і перспективи розвитку”, 20-21 лист. 2008. - Полтава: РВВ ПУСКУ, 2008. - С. 121-122.

16. Ємець О.О. Транспортна задача на переставленнях та її розв'язування: чітка та нечітка постановки / О.О. Ємець, Т.О. Парфьонова // Український матем. конгрес - 2009. (Київ 27-29 серпня, 2009). [Електронний ресурс] - 2 с. - Режим доступу до тез: http://www.imath.kiev.ua/ ~congress2009/Abstracts /Yemets.pdf . - Назва з титул. екрану.

17. Ольховский Д.М. Числові експерименти з застосуванням методу комбінаторного відсікання до транспортної задачі на переставленнях/ Д.М. Ольховский, Т.О. Парфьонова // Інформатика та системні науки (ІСН-2010): Матеріали Всеукраїн. наук.-прак. конф. (18-20 березня 2010, Полтава). - Полтава: РВВ ПУСКУ. - С. 149-151.

18. Парфьонова Т.О. Транспортні задачі комбінаторного типу, їх властивості та розв'язування / Т.О. Парфьонова // Інформатика та системні науки (ІСН-2010): Матеріали Всеукраїн. наук.-прак. конф. (18-20 березня 2010, Полтава). - Полтава:РВВ ПУСКУ. - С. 153-154.

АНОТАЦІЯ

Парфьонова Т.О. Транспортні задачі комбінаторного типу, їх властивості та розв'язування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2010.

Введено до розгляду та досліджено комбінаторну транспортну задачу на переставленнях (КТЗП), її властивості. Розвинуто апарат методу гілок та меж для розв'язування КТЗП, введено оцінки допустимих множин в КТЗП, одержано властивості цих оцінок, що дозволяють покращити відсікання допустимих множин; розроблено правила галуження допустимих множин в КТЗП. Запропоновано і обґрунтовано наближений метод розв'язування КТЗП, що дає її розв'язок з заданою по функціоналу точністю. Розроблено і обґрунтовано в рамках методології послідовного аналізу варіантів точний алгоритм послідовного аналізу значень змінних для розв'язування КТЗП. Розвинуто апарат нечітких множин з континуальним носієм введенням нових операцій і відношень. Цей апарат використано для моделювання і розв'язування КТЗП за умов „нечіткої” невизначеності. Побудовано моделі і підходи для їх розв'язування як КТЗП зі стохастичною невизначеністю даних. комбінаторний транспортний задача континуальний

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

Парфенова Т.О. Транспортные задачи комбинаторного типа, их свойства и решение. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2010.

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

В первом разделе рассмотрены необходимые теоретические сведения из теории евклидовой комбинаторной оптимизации, транспортных задач. Определены направления диссертационных исследований.

Во втором разделе рассмотрены следующие задачи: о перевозке однородного продукта с минимальными затратами заданным набором емкостей; задача выбора плана обслуживания клиентов финансового рынка; классическая транспортная задача с дополнительным условием, что перевозки являются перестановкой заданных объемов. Для них построены математические модели в виде задач комбинаторной оптимизации транспортного типа на перестановках или размещениях. Дальше диссертационные исследования сосредоточены на исследовании комбинаторных транспортных задач на перестановках (КТЗП). Исследованы свойства КТЗП, которые используются далее при построении методов и обосновании подходов ее решения.

В третьем разделе рассматриваются и обосновываются методы решения КТЗП. Как к любой оптимизационной задаче к КТЗП возможно применение универсального метода ветвей и границ, если определить эффективную оценку допустимых множеств. Обоснованы оценка и три правила ветвления. Показана применимость к решению КТЗП метода комбинаторного отсечения для задач на вершинно расположенных множеств. Предложен и обоснован приближенный метод решения КТЗП, объединяющий идеи метода ветвей и границ и метода комбинаторного отсечения. Показано, что метод дает решения с любой точностью по функционала. В рамках метода последовательного анализа вариантов разработан и обоснован алгоритм решения КТЗП.

В четвертом разделе КТЗП рассматриваются при условии нечеткой или стохастической неопределенности. При этом обоснована необходимость введения новых операций и отношений над нечеткими числами с континуальным носителем (суммы, линейного порядка, максимума, минимума) и так называемого характеристического сравнителя нечеткого числа, которые в совокупности обладают рядом необходимых в задачах оптимизации свойств. Такой аппарат нечетких чисел в четвертом разделе введен и доказано наличие у него свойств, обобщающих метрические свойства множеств действительных чисел с естественными операциями над ними. Это позволило получить модель транспортной задачи в условиях нечеткой неопределенности как КТЗП в нечетких числах с континуальным носителем. Даны подходы к решению таких задач. Для учета стохастической неопределенности использован аналогичный аппарат, где задействованы случайные величины. Построен спектр математических моделей для КТЗП с учетом стохастических параметров и даны подходы к решению таких задач.

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

Parfonova Т.О. Transport Problem of Combinatorial Type, Their Properties and Solving Methods. - Manuscript.

Thesis for the candidate degree in physics and mathematics sciences by speciality 01.05.01 - theoretical foundations of informatics and cybernetics. - V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2010.

The combinatorial transport problem on permutations (CTPP), its properties is taken into consideration and investigated. The apparatus the method of branches and limits for solving CTPP is developed, the estimations of admissible sets in CTPP are introduced, the properties of these estimations are received that allow to improve the cutting of admissible sets; the rules of admissible sets branching in CTPP are developed. The paper introduces and grounds the approximate method of solving CTPP, giving its solution with given according to functional accuracy. The exact sequential analysis algorithm of variables values for solving CTPP is developed and grounded in the methodology of sequential analysis of variants. The thesis develops the apparatus of fuzzy sets with continuous support of the introduction of new operations and relations. This apparatus is used to model and solve the CTPP under conditions of "fuzzy" uncertainty. It models the patterns and ways of their solving as CTPP with stochastic uncertainty data.

Key words: combinatorial optimization, transport problem, fuzzy numbers, fuzzy sets, the stochastic optimization, the method of branches and limits, the method of sequential analysis of variants.

Размещено на Allbest.ru

...