Ім'я файлу: теорія складності екстремальних задач теорія (1) (1).docx
Розширення: docx
Розмір: 111кб.
Дата: 20.11.2023
скачати

Основний матеріал лекцій знаходиться у навчальному посібнику:

Панішев, А. В. Вступ до теорії складності дискретних задач : Монографія. – Ж. : ЖДТУ, 2004. – 236с.

Додаткові теоретичні матеріали

Лекція № 1

Основні поняття. Множини. Комбінаторні комбінації.

Одним з  основних понять, які використовують у математиці, є поняття множини. Для нього не дають означення. Можна пояснити, що множиною називають довільну сукупність об’єктів, а самі об’єкти — елементами даної множини. Так, можна говорити про множину учнів у класі (елементи — учні), множину днів тижня (елементи — дні тижня), множину натуральних дільників числа 6 (елементи — числа 1, 2, 3, 6) тощо.

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

Як правило, множини позначають великими літерами латинського алфавіту. Наприклад, якщо множина М складається із чисел 1; 2; 3, то її позначають так: М = {1; 2; 3}. Той факт, що число 2 входить до цієї множини (є елементом даної множини М), записують за допомогою спеціального значка ∈ так: 2 ∈ М; а те, що число 5 не входить до цієї множини (не є елементом даної множини), записують так: 5 ∉ М.

Можна розглядати також множину, яка не містить жодного елемента, — порожню множину.

Наприклад, множина простих дільників числа 1 — порожня множина.

Позначення множин

Для деяких множин існують спеціальні позначення:

  • порожню множину позначають символом ∅;

  • множину всіх натуральних чисел — літерою  N;

  • множину всіх цілих чисел — літерою  Z;

  • множину всіх раціональних чисел — літерою  Q;

  • множину всіх дійсних чисел — літерою  R.

Множини бувають  скінченні і  нескінченні залежно від того, яку кількість елементів вони містять. Так, множини А = {7}; M = {1; 2; 3} — скінченні, бо містять скінченне число елементів, а множини N, Z, Q, R — нескінченні.

Множини задають або за допомогою переліку їх елементів (це можна зробити лише для скінченних множин), або за допомогою опису, коли задається правило — характеристична властивість, яке дозволяє визначити, належить чи ні даний об’єкт розглядуваній множині. Наприклад, множина А = {–1; 0; 1} задана переліком елементів, а множина B парних цілих чисел — характеристичною властивістю елементів множини. Останню множину інколи записують так:  B = {b  |  b — парне ціле число} або так: B = {b | b = 2m, де m ∈ Z} — тут після вертикальної риски записана характеристична властивість. (запис  m ∈ Z означає, що m приймає будь-яке ціле значення, що також можна записувати так:  m = 0; ±1; ±2; …)

У загальному вигляді запис множини за допомогою характеристичної властивості можна подати так: A = {x | P (x)}, де P (x) — характеристична властивість.

Наприклад, {x  |  x2 – 1 = 0} = {–1, 1}, {x| x ∈ R і  x2 + 1 = 0} = ∅.

I. Перестановки

Нехай є множина М, яка складається із n елементів: а1, a2, а3,…, аn. Якщо переставляти ці елементи можливими способами, залишаючи незмінним їх загальне число, одержуємо декілька послідовностей: а1, а2, а3,…,аn,…,аn-1,аn-2,…, а1 і т. д. Кожна з таких послідовностей є перестановкою із даних n елементів.

Перестановкою (the permutation) із n елементів називається будь-яка скінченна послідовність (progression), яка одержується в результаті упорядкування деякої скінченної множини, складеної з n елементів. Число всіх перестановок із n елементів позначається Рn. Це число дорівнює добутку всіх цілих чисел від 1 до n. Позначають:

.

Добуток n перших натуральних чисел прийнято позначати символом n!



Символ n! читають "eн факторіал". Це слово походить від латинського factor, що означає “множник”. При n=1 у виразі залишається одне число 1. Тому приймається (як визначення), що 1!=1. При n=0 вираз немає змісту, з числа 0 існує одне переміщення, тому приймається, що 0!=1. Значить, Рn=n! правильна формула .

II Сполучення (комбінації)

Нехай є множина М, яка складається з n різних елементів. Будь-яка підмножина множини М, яка містить k елементів (k=0, 1, 2, ..., n), називається сполученням (combination) або комбінацієюз даних n елементів по k елементів, якщо ці підмножини відрізняються хоча б одним елементом. Число різних сполучень із n елементів по k позначається (combination від combinare лат. ‑ сполучати). Іноді замість пишуть ( ).

Число всіх сполучень із n елементів по k, де ,дорівнює добутку k послідовних натуральних чисел, з яких найбільше є n, діленому на добуток всіх натуральних чисел від 1 до k.

.

Формулу для можна записати в іншому вигляді. Помноживши чисельник i знаменник дробу в правій частині на добуток , одержуємо:

.

Зауваження. Із n елементів можна скласти тільки одне сполучення, що містить всі n елементів, тому прийнято:

.

Властивості сполучень:

а) ;

б) .

III Розміщення

Кожна впорядкована підмножина, яка містить k елементів даної множини з n елементів, називається розміщенням (accommodation) із n по k елементів. Таким чином, два різних розміщення із даних n елементів по k відрізняються один від одного або складом елементів, або порядком їх розміщення.

Число розміщень із n елементів по k позначається символом (аrrangement (франц.) ‑ розміщення). Число всіх можливих розміщень із n елементів по k дорівнює добутку k послідовних чисел, з яких найбільшим є n, тобто:

, або .

Лекція №2

Теорія NP-повних задач.

Теорія алгоритмів розподіляє всі проблеми, що потребують вирішення, на дві широкі категорії : алгоритмічно розв’язні та нерозв’язні. Останні проблеми будуть розглянуті дещо пізніше. Зупинимося на перших.

Бурхливий розвиток комп’ютерної індустрії підсвідомо наводить на думку, що вже не так важливо, які алгоритми застосовувати для розв’язної проблеми, - сучасний комп'ютер може все. Однак, наприклад, алгоритм «грубої сили» для розв’язування задачки на триста-п'ятсот змінних може зажадати такої кількості операцій, що набагато більше, ніж у Всесвіті елементарних частинок. Наприклад, якщо розв’язання задачі на найсучасніших комп'ютерах займе 1010 років, то очевидно, такий алгоритм для нас не має сенсу.

У попередньому розділі ми ввели поняття «складність алгоритму». Зрозумілим є бажання аналогічно визначити і складність завдання ̶ наприклад, як складність найефективнішого алгоритму, що розв’язує цю задачу (для даних розміру n). На жаль, це бажання нездійсненне. Доведено, що є завдання, для яких не існує найшвидшого алгоритму, тому що будь-який алгоритм для такого завдання можна «прискорити», побудувавши більш швидкий алгоритм, що розв’язує цю задачу. Це твердження називають теоремою Блюма про прискорення. Якщо відволіктися від технічних деталей, то спрощений варіант теореми Блюма можна сформулювати таким чином.

Теорема. ( теорема Блюма про прискорення). Існує така алгоритмічно розв’язна проблема Z, що будь-який алгоритм A, що вирішує цю проблему, можна прискорити таким чином: існує інший алгоритм А1, що також вирішує Z і такий, що T А1 (n) ≤ log TA (n) для майже всіх n.

Зауважимо, що теорема Блюма не стверджує, що прискорення можливе для будь-якої задачі. Більше того, для деяких задач існує оптимальний (найшвидший) алгоритм. Однак твердження теореми Блюма про існування «незручних» задач не дозволяє визначити універсальне (застосовне до всіх задач) поняття «оптимального алгоритму».

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

Означення. Нехай f (n) - деяка функція, що відображає N в N. Клас складності C (f (n)) - це множина всіх задач, для яких існує хоча б один алгоритм, складність якого не перевищує O (f (n)).

Це визначення в певному сенсі умовне - позначення C(f (n)) ніколи не застосовують. Чому? Тому що для завдання реального класу задач необхідно ще уточнити:

• що ми розуміємо під «алгоритмом»;

• яка складність (тимчасова, ємнісна чи ще якась) нас цікавить.

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

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

  • У теорії складності під «алгоритмом» зазвичай розуміють той чи інший різновид машини Тюрінга. Винайдення нових різновидів приводить до появи й нових класів складності. Наприклад, окрім уже відомих класів P, NP, NPC, з’явилися класи: EXPTIME (іноді має назву EXP) - задачі, які розв’язуються детермінованою машиною Тюрінга за O (2p(n) ) часу, де р(n) є поліномом функції n; EXPSPACE - задачі, для розв’язання яких детермінованій машині Тюрінга потрібно O(2p(n)) ємнісного простору, де р(n) є поліномом функції n; BPP – проблеми, розв'язні за допомогою ймовірнісної машини Тюрінга в поліноміальний час із похибкою ймовірністю не більше 1/3 та інші. Є й екзотичні класи, наприклад, PNP- клас задач, що розв’язуються за поліноміальний час детермінованою машиною Тюрінга з оракулом для NP-завдання.

  • Для формальних визначень класів складності зазвичай розглядають не довільні алгоритми, а алгоритми для так званих задач розв’язання (decision problem), у яких потрібно визначити, належить чи ні певний елемент деякій множині. Враховуючи необхідність кодування даних, що подаються на вхід машині Тюрінга, ці задачі абсолютно еквівалентні задачам розпізнавання мов, коли на деякому алфавіті ∑ розглядається підмножина слів L

  • У сучасній теорії складності обчислень поняття поліноміального алгоритму є адекватним математичним уточненням інтуїтивного поняття «ефективний алгоритм», а клас P становить «клас ефективно розв'язуваних задач». Тобто, прості задачі (розв'язувані) - це задачі, які розв’язування за поліноміальний час. Важкорозв’язні задачі - це задачі, які не розвязуються за поліноміальний час, або алгоритм розв'язання за поліноміальний час не знайдений.

  • Побудовано ієрархічне співвідношення класів складності : P⊆NP⊆ BPP⊆ PH⊆ EXPSPACE⊆ EXPTIME, тобто одні містять у собі інші (більшість включень не доведено). Однак, зважаючи на потужності сучасних засобів обчислювальної техніки, задачі інших класів складності розглядаються поки що тільки в теорії, а однією з найбільш відомих відкритих проблем залишається питання про рівність класів P та NP.

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

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

Поняття алгоритмічного зведення було уточнено А. Тюрінгом: якщо, деяка машина Тюрінга переробляє послідовність закодованих значень функції g у послідовність закодованих значень функції f, то функція f зводиться до функції g. Якщо f зводиться до g за Тюрінгом, f ≤ T g, a g зводиться до f, g ≤ T f, то кажуть, що f і g мають один і той степінь нерозв'язності, або f ≡ T g.

Означення. Зведення задачі R1до задачі R2 за Куком – це поліноміальний за часом алгоритм (іншими словами, машина Тюрінга з поліноміальним часом роботи), що розв’язує задачу R1 за умови, що функція, що знаходить розв’язок задачі R2, йому дана як оракул, тобто звернення до неї займає один крок.

Якщо такий алгоритм існує, кажуть, що R1 зводима за Куком до R2 і пишуть R1 ≤ CR2.

Поява деяких нових класів складності пов’язана із залученням до процесу їх вивчення так званої «пророчої машини» - машини Тюрінга з оракулом. Пророк, у цьому розрізі, розглядається як сутність, здатна відповідати на набір питань і зазвичай представлена як деяка підмножина натуральних чисел. Тоді, інтуїтивно, пророча машина може виконувати всі звичайні дії машини Тюрінга і також може запитати у пророка: «Чи x належить A?».

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

Клас складності задач, розв’язуваних алгоритмом з класу А з оракулом для задачі класу B, позначають AB. Наприклад, клас задач, розв’язуваних за поліноміальний час детермінованою машиною Тюрінга з оракулом для NP-завдання, позначають PNP.

Повернемося до одного з основних питань - яке ж практичне значення має вивчення теорії складності й класифікація завдань з точки зору NP-повноти (NPC)? Відповідь очевидна - часто набагато розумніше та ефективніше знайти доказ того, що розглянута задача належить до класу NPC, й відповідно до цього зайнятися пошуком досить точних наближених алгоритмів, ніж безрезультатно витрачати час на відшукання поліноміальних алгоритмів її розв’язання. Зрозуміло, що саме NPC-задачі відіграють тут центральну роль - справа в тому, що поліноміальний час є, хоча й першим, але досить гарним наближенням поняття «практичної можливості розв'язання задачі».

Нагадаємо, що задачі класу NPC відповідають двом умовам: по-перше, вони обов’язково належать класу NP; по-друге, будь-яка довільна задача з класу NP зводиться до цих задач. Якщо опустити першу умову, то одержимо клас задач NPH(non-deterministic polynomial-time hard) - клас задач, які "принаймні так складні, як найбільш важкі задачі в NP". Клас NPH містить у собі NPC (див. рис. 15.1), але виходить із меж класу NP( за гіпотези P ≠ NP). Серед задач NPC виділяють також задачі NPCS – NP- повні в сильному сенсі, як ті, що належать класу NP, є NP-повними та мають максимальне значення величин, що зустрічаються в цій задачі, обмежені зверху поліномом від довжини входу.



Рисунок 1 – Співвідношення між класами P, NP, NPC, NPH

 

Приклади NP-повних задач

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

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

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

Наприклад, Річард Карп у своїй праці «Зводимість між комбінаторними задачами» опублікував цілий список, що складається з формулювання та доведення NP-повноти 21 задачі. Перелічемо деякі з них.

  1. Задача розбиття

Задана множина додатних цілих чисел x1, x2, ..., xn. Чи можна розбити її на дві підмножини так, щоб суми чисел в обох підмножинах були однаковими?

  1. Задача ізоморфізму підграфа

Нехай є два графи G1 і G2. Множину вершин першого графа позначимо V1, а другого  V2. Нехай | V1 |> | V2 |. Потрібно відповісти на запитання: чи знайдеться в графі G1 підграф Н, ізоморфний графу G2?

  1. Задача виконуваності булевих формул (SAT).

Задача виконуваності булевих формул (SAT) важлива для теорії обчислювальної складності. Об'єктом задачі SAT є булева формула, що складається тільки з імен змінних, дужок та операцій (І), (АБО) і (HІ). Задача полягає в такому: чи можна призначити всім змінним, що зустрічаються у формулі, значення «ІСТИННІСТЬ» і «ХИБНІСТЬ» так, щоб формула набула значення «ІСТИННІСТЬ»?

  1. Задача про кліку.

Маємо граф G з m вершинами і ціле додатне число n. Граф називається клікою, якщо кожна вершина в ньому зв'язана ребром з кожною. Кількість вершин у кліці назвемо її потужністю. Чи правда, що в даному графі G є кліка потужності не менше ніж n?

  1. Задача про гамільтонів цикл.

Маємо граф G з n вершинами. Чи існує у графі простий цикл, що проходить через усі вершини графа? Простим називається цикл, у якому вершини не повторюються. Таким чином, гамільтонів цикл  це послідовність вершин і ребер (дуг) графа, що містить усі вершини графа G по одному разу, але щодо ребер обмежень не встановлено, то може бути, що містить не всі дуги.

  1. Задача комівояжера.

Нехай є граф G з n вершинами. Кожному ребру графа приписано додатне ціле число di, що задає довжину ребра. Крім цього, задано деяке додатне ціле число L. Потрібно відповісти на запитання: чи знайдеться у графі G маршрут, що проходить через усі вершини графа G такий, що його довжина не перевищує L?

Алгоритмічно нерозв’язні проблеми

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

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

Алгоритмічна нерозв'язність не є проблемою теорії алгоритмів або невдачею, вона є науковим фактом. Популярність досліджень алгоритмічної нерозв'язності не поступається будь-яким іншим дослідженням у теорії алгоритмів і потребує іноді значних зусиль. Наприклад, доведення алгоритмічної нерозв'язності 10-ї проблеми Гільберта, одержане Ю. В. Матіясевичем, відносять до видатних наукових досягнень XX століття.

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

Означення. Алгоритмічною проблемою називається проблема побудови алгоритму, що володіє тими чи іншими властивостями.

Ми отримаємо вирішення алгоритмічної проблеми, якщо або знайдемо шуканий алгоритм (тобто подано його опис), або доведем, що такого алгоритму не існує.

Однією з найбільш загальних теорем теорії алгоритмів, що пояснює природу багатьох проблем у теорії алгоритмів, є теорема Райса.

Означення. Характеристичною функцією множини А будемо називати функцію

                                                                                                                                      Множина А називається рекурсивною, якщо її характеристична функція рекурсивна.

Означення. Нехай Q – деяка властивість одномісних частково-рекурсивних функцій. Властивість Q називається нетривіальною, якщо існують функції, що володіють цією властивістю, так і функції, що не володіють.

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

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

Відповідно до тез Черча і Тюрінга задача є алгоритмічно розв’язуваною тоді і тільки тоді, коли існує деяка машина Тюрінга М, що розв’язує цю задачу. За поставленим завданням необхідно визначити, чи характерна функції fм(х), що реалізується машиною М, властивість Q. Функцію fм(х) будемо розуміти як функцію, що відповідає програмі з номером Геделя x.

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

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

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

Першою фундаментальною теоретичною працею, пов'язаною з доведенням алгоритмічної нерозв'язності, була робота Курта Геделя  його відома теорема про неповноту символічних логік. Це була строго сформульована математична проблема, для якої не існує розв’язного її алгоритму. Зусиллями різних дослідників список алгоритмічно нерозв'язних проблем був значно розширений. Сьогодні прийнято під час доведення алгоритмічної нерозв'язності деякої проблеми зводити її до класичної задачі  «задачі зупину».

Теорема. Не існує алгоритму (машини Тюрінга), що дозволяє за описом довільного алгоритму і його вихідних даних (і алгоритм, і дані задані символами на рядку машини Тюрінга) визначити, зупиняється цей алгоритм на цих даних чи працює нескінченно.

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

Лекція №3

Задачі оптимізації. Задача побудови розкладів.

Задача оптимізації — задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції.

Формальне визначення


Нехай задано деяку множину X із n-вимірного евклідового простору і функцію f(x), визначену на X. Необхідно знайти точки мінімуму значень функції f(x) на X. Або:

f(x) → min, x ∈ X.

тут f(x) — цільова функція, X — допустима множина, кожна точка x цієї множини — допустима точка задачі.

Також, задачу оптимізації можна сформулювати як пошук максимуму (максимумів) цільової функції:

f(x) → max, x ∈ X.

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

Розв'язки задачі


Розв'язки задачі можна розділити на дві множини:

    • глобальні

(глобального мінімуму), це такі допустимі точки x* в яких цільова функція має найменше значення на всій допустимій області:

f(x*) ≤ f(x), ∀ x ∈ X;

    • локальні

(локального мінімуму), це такі допустимі точки x* в яких цільова функція приймає найменше значення в деякому околі:

f(x*) ≤ f(x), ∀ x ∈ X ∩ Uε(x*),

Де Uε(x*) = {x ∈ Rn | ‖x — x*‖ ≤ ε} — куля радіусу ε в центрі x*.

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

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

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

Існує певна різниця між термінами “впорядкування” та “складання розкладів”. Впорядкування – це формування черги операцій, що виконує одна машина, а складання розкладів означає завдання послідовності дій для декількох машин.

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

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

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

Задача теорії розкладів вважається заданою, якщо визначені

  1. Роботи та операції, що мають бути виконані;

  2. Кількість та типи машин, які виконують операцію

  3. Порядок проходження робіт

  4. Критерій оцінки розкладу

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

Лекція №4

Задача про рюкзак. Задача комівояжера. Задача трьох верстатів

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

Задачу пакування рюкзака використовують для моделювання різних проблем, зокрема:

  • У системах підтримки управління портфелем для балансування та диверсифікації вибраних капіталовкладень із метою пошуку найкращого балансу між ризиками та ефективністю вкладів у різні фінансові активи;

  • При завантаженні човна або літака: вибір багажів для оптимального завантаження транспортного засобу;

  • У кроєнні різних матеріалів (тканини, сталеві листи тощо): вибір оптимальної схеми розкрою матеріалів з метою зменшення кількості відходів.

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

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

Задача комівояжера (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.

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

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

Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера — евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок.

Задача комівояжера — NP-повна. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору.

Лекція №5-6

Точні алгоритми розв’язання NP-трудних задач.


Точні

    • прямий перебір,

    • метод «гілок і меж» ,

    • лінійне цілочисельне програмування (ЛЦП) ,

    • динамічне програмування ,

    • метод декомпозиції .

Повний перебір (або метод «грубої сили», англ. Brute force) - метод вирішення математичних задач. Відноситься до класу методів пошуку рішення вичерпання всіляких варіантів. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже велике, то повний перебір може не дати результатів протягом декількох років або навіть століть.
Будь-яке завдання з класу NP може бути вирішена повним перебором. При цьому, навіть якщо обчислення цільової функції від кожного конкретного можливого рішення задачі може бути здійснено за поліноміальний час, в залежності від кількості всіх можливих рішень повний перебір може зажадати експоненціального часу роботи.

Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.

Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм.

Алгоритм


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

  1. Рекордна множина розбивається на підмножини;

  2. Знайти оцінки згори та знизу для нових підмножин;

  3. Визначити максимальну оцінку знизу серед усіх підмножин;

  4. Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;

  5. Знайти максимальну оцінку згори серед усіх підмножин та вважати її рекордною;

  6. Якщо не досягнуто дискрентості, або необхідної точності перейти по пункту 1;

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

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

Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) — метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі чиї вимоги представлені через лінійні відношення. Лінійне програмування є особливим випадком математичного програмування (математичної оптимізації).

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

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

Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність. Наприклад, алгоритми Гоморі.

Динамічне програмування — розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління.

У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «прийняття рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.

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

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

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

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

Якщо підзадачі можуть бути вкладеними рекурсивно всередині більших задач, так що методи динамічного програмування можуть бути застосовні, то існує залежність між розв'язком загальної задачі, і розв'язком підзадач .[4] В методах оптимізації це відношення виражається рівнянням Беллмана.

Динамічне програмування в методах оптимізації


З точки зору математичної оптимізації, динамічне програмування полягає в спрощенні знаходження загального оптимального розв’язку, шляхом пошуку розв’язків в підзадачах, отриманих розбиттям задачі на послідовні проміжки часу. Це виражається в визначенні послідовності значень функцій V1, V2, ..., Vn, з аргументом y, котрий позначає стан системи в моменти часу i від 1 до n. Визначенням Vn(y) є значення, отримане в стані y в кінцевий момент часу n. Значення Vi в попередні моменти часу i = n −1, n − 2, ..., 2, 1 можуть бути знайдені рухаючись назад, використовуючи рекурсивну залежність, названу рівняння Беллмана.

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

Лекція №7-8

Наближеніі алгоритми розв’язання NP-трудних задач.

Наближені:

    • метод Монте-Карло,

    • метод часткового перебору,

    • метод спрямованого перебору,

    • спрощений метод «гілок і меж» та ін.).

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

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

Метод Монте-Карло широко використовується у всіх випадках симуляції на ЕОМ.

Не існує єдиного методу Монте-Карло, цей термін описує великий і широко використовуваний клас підходів. Проте ці підходи використовують в своїй основі єдиний шаблон:

  1. Визначити область можливих вхідних даних.

  2. Випадковим чином згенерувати вхідні дані із визначеної вище області за допомогою деякого заданого розподілу ймовірностей.

  3. Виконати детерміновані обчислення над вхідними даними.

  4. Проміжні результати окремих розрахунків звести у кінцевий результат.

При вирішенні інтелектуальних завданнях знайшов широке застосування метод часткового (неявного) перебору. У цьому методі (рис.1) в вузлах крім перевірки допустимості (відповідності обмеженням) вважається і перевіряється значення обраного критерію. Якщо значення цього критерію (при мінімізації цільової функції) в деякому вузлі J більше, ніж значення, отримане в іншому підсумковому вузлі I (представляє припустиме рішення задачі), то подальший пошук з вузла J не ведеться (тому що значення критерію не стане краще ).

Рис.1. Обхід дерева при пошуку рішення методом неявного перебору
(Кп - значення критерію в проміжному вузлі; Кі - значення критерію в вузлі, відповідному повного набору обмежень)

Оптимальним рішення в розглянутому прикладі є рішення в вузлі 5. Пошук рішення з вузла 7 не виконувався, тому що рішення у вузлах 8 і 9 дадуть свідомо гірше рішення в порівнянні з вузлом 5.
Обмеженням використання цього методу є як монотонність висновків, так і монотонність критерію (цільової функції). Тобто значення критерію в вузлі, з якого ведеться пошук, не може бути більше значення критерію в нижчих вузлах. У випадках, коли треба максимізувати цільову функцію, вважають величину зворотну критерієм 1 / К.

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

© Усі права захищені
написати до нас