Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Програма «Технології штучного інтелекту»

Скачати 254.84 Kb.

Програма «Технології штучного інтелекту»




Скачати 254.84 Kb.
Сторінка3/5
Дата конвертації24.05.2017
Розмір254.84 Kb.
ТипПрограма
1   2   3   4   5

Блок дослідження операцій і теорія прийняття рішень

Основні поняття та методологія дослідження операцій


Історія розвитку та використання методів дослідження операцій.
Дослі́дження опера́цій (ДО) - це дисципліна, що займається розробкою й застосуванням методів знаходження оптимальних рішень на основі математичного моделювання у різних областях людської діяльності. ДО тісно пов'язане з системним аналізом, математичним програмуванням, теорією оптимальних рішень.
Класифікація моделей дослідження операцій. Області практичних застосувань методів дослідження операцій та мета його вивчення. Основні поняття дослідження операцій: операція, стратегія, стан, діючі фактори операції, критерії ефективності. Методологія проведення операційного дослідження: визначення мети; складання плану розробки; формулювання проблеми; побудова математичної моделі;
Математи́чна моде́ль - система математичних співвідношень, які описують досліджуваний процес або явище. Математична модель має важливе значення для таких наук, як: економіка, екологія, соціологія, фізика, хімія, механіка, інформатика, біологія та ін.
синтез та (або) обґрунтування математичного методу; опрацювання інформації; перевірка адекватності моделі; реалізація результатів. Пряма та обернена задачі дослідження операцій. Поняття про детерміновані та стохастичні моделі дослідження операцій і основні підходи до їх розв'язування. Проблема багатокритеріальності та її розв'язування; згортка критеріїв, переведення критеріїв в обмеження, методи послідовних поступок, діалогові методи.

Задачі лінійного програмування


Поняття про задачу математичного програмування. Загальна постановка та класифікація задач математичного програмування, поняття складності алгоритмів розв'язування задач математичного програмування. Побудова математичних моделей задач дослідження операцій. Канонічні рівняння. Лінійні моделі та зв'язані з ними спрощення дійсності: пропорційність і адитивність. Загальна канонічна форма задачі лінійного програмування.
Складність обчислювальних процесів - це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу) необхідних для виконання алгоритму.
Канонічна форма - така форма, що однозначно репрезентує об'єкт. Її часто плутають зі схожим поняттям нормальна форма. В булевій алгебрі деяка булева функція може бути виражена у канонічному вигляді з використанням мінтермів або макстермів.
Математи́чне програмува́ння - це прикладна математична дисципліна, яка досліджує екстремум функції (задачі пошуку максимуму або мінімуму) і розробляє методи їх розв'язання. Такі задачі ще називають оптимізаційними.
Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) - метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі чиї вимоги представлені через лінійні відношення.
Графічне розв'язування задач лінійного програмування. Поняття про основні задачі аналізу лінійних моделей на чутливість: статус та допустимі межі зміни ресурсів, цінність ресурсів, чутливість функції мети. Базисні розв'язки задачі лінійного програмування. Основні теореми лінійного програмування. Алгоритм симплекс-методу та його таблична форма. Метод штучного базису. Особливі випадки вирішення задач лінійного програмування. Умови оптимальності та допустимості. Особливі випадки симплекс-методу. Методи знаходження початкового базису. Двоїстість у задачах лінійного програмування. Поняття прямої та двоїстої задач лінійного програмування. Основні теореми двоїстості. Двоїстий симплекс-метод. Економічна інтерпретація двоїстості. Модель транспортної задачі лінійного програмування.
Транспортна задача (задача Монжа - Канторовича) - задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення.
Приклади транспортних задач. Методи побудови опорного плану транспортних задач: північно-західного кута, мінімального елементу, евристичний метод Фойгеля.
Опорний план - розв'язок системи лінійних обмежень в задачі лінійного програмування, який неможливо представити у вигляді лінійної комбінації будь яких інших розв'язків.
Методи знаходження оптимального плану (метод потенціалів і розподільчий). Теореми про потенціали. Задача про призначення. Угорський алгоритм.

Задачі на мережах


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

1   2   3   4   5


Скачати 254.84 Kb.

  • Задачі лінійного програмування
  • Задачі на мережах