1   2   3   4   5   6   7   8   9   ...   25
Ім'я файлу: Завдання до лабораторних робіт.docx
Розширення: docx
Розмір: 3648кб.
Дата: 19.02.2022
скачати

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Національний університет “Львівська політехніка”



МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Методичні вказівки до виконання циклу лабораторних робіт для студентів спеціальності 122 «Комп'ютерні науки», денної та заочної форм навчання

Львів – 2021

Математичні методи дослідження операцій: Методичні вказівки до виконання циклу лабораторних робіт для студентів спеціальності 122 «Комп'ютерні науки», денної та заочної форм навчання / Укл. Марікуца У.Б. – Львів.: НУ «Львівська політехніка», 2021. – 119 c.

Затверджено на засіданні кафедри Систем автоматизованого проектування.

Протокол № _1_ від _27.09.2021 р.

Укладачі:

Марікуца Уляна Богданівна, канд. техн. наук


Відповідальний редактор:

П.В. Тимощук


Рецензент:

Т.І. Мандзак, к.ф.-м.н., доц.

ЗМІСТ

ВСТУП 3

ЛАБОРАТОРНА РОБОТА № 1. Багатокритеріальний вибір. Визначення оптимальних альтернатив за Парето та Слейтером 5

ЛАБОРАТОРНА РОБОТА № 2. РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ СИМПЛЕКС-МЕТОДОМ 16

ЛАБОРАТОРНА РОБОТА № 3. Прийняття рішень в умовах повної інформації. Задача про упакування в контейнери 44

ЛАБОРАТОРНА РОБОТА № 4. Прийняття рішень в умовах ризику 57

ЛАБОРАТОРНА РОБОТА № 5. Прийняття рішень в задачах розпізнавання образів 68

ЛАБОРАТОРНА РОБОТА № 6. Теорія статистичних рішень «ігри з природою». 96

ДОДАТОК А 112

ДОДАТОК Б 117

ДОДАТОК В 119

ПЕРЕЛІК ПОСИЛАНЬ 120

ВСТУП


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

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

Завдання вивчення дисципліни полягає у формуванні системи наступних знань та умінь:

Знання:

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

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

Уміння:

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

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


Лабораторні роботи орієнтовані на студентів-бакалаврів, що навчаються за спеціальністю 122 «Комп'ютерні науки». Роботи мають дослідницький характер. Для полегшення підготування студентів до лабораторних робіт у методичних вказівках наведено необхідні довідникові дані і матеріали. Бажано також, щоб лабораторні роботи стимулювали подальше поглиблене вивчення студентами теоретичного матеріалу [2-4;7-10] та сприяли оволодінню українською науково-технічною термінологією [3;7;9;10].

ЛАБОРАТОРНА РОБОТА № 1.
Багатокритеріальний вибір. Визначення оптимальних альтернатив за Парето та Слейтером

1 Мета роботи


Ознайомитись з поняттями оптимальності за Парето та за Слейтером при багатокритеріальному виборі [1-3;6;7].

2 Короткі теоретичні відомості


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

Постановка задачі багатокритеріального вибору включає:

1) множину можливих рішень Х;

2) векторний критерій f;

3) відношення переваги .

В загальному випадку векторний критерій має вигляд:
(1.1)


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

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

1) – ОПР віддає перевагу першому рішенню ( );

2) – ОПР віддає перевагу другому рішенню ( );

3) не виконується ані , ані – ОПР не може надати переваги жодному рішенню.

Варіант, коли виконуються обидва випадки: та , не можливий внаслідок асиметричності відношення переваги .

Для першого випадку говорять, що рішення домінує рішення по відношенню , або що рішення доміноване . Для другого випадку говорять, що рішення домінує рішення по відношенню , або що рішення доміноване . Для третього випадку кажуть, що рішення та непорівнянні по відношенню .

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




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


Аксіома 1. (Аксіома виключення рішень, що домінуються)

Для будь-якої пари допустимих рішень , для яких має місце відношення , виконується .


Незважаючи на очевидну «розумність» цієї аксіоми, не слід вважати, що вона виконується у будь-якому випадку при виборі рішень.

Розглянемо, наприклад, таку задачу вибору з трьох претендентів на два робочих місця за умови, що обидва робочі місця обов’язково повинні бути заповнені. Нехай в процесі порівняння претендентів з’ясувалося, що перший переважає другого та третього, а другий переважає третього. Вочевидь, що обрані будуть перший ( ) та другий ( ) претенденти, хоча і виконується умова [1].

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

Якщо задано декілька критеріїв оптимальності, то для кожного з них необхідно визначити напрямок зацікавленості ОПР. Тут і надалі будемо вважати, що ОПР зацікавлений в отриманні максимальних значень всіх компонентів векторного критерію f. Таким чином, сформулюємо «Аксіому Парето»:


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

Запис означає виконання покомпонентних нерівностей для всіх j=1(1)m, причому . Це означає, що компоненти першого вектора не менші за відповідні компоненти другого вектора , і принаймні одна компонента першого вектора суворо більша за відповідну компоненту другого.


Визначення 1. Рішення називається оптимальним за Парето (парето-оптимальним), якщо не існує такого можливого вирішення , для якого має місце нерівність . Всі парето-оптимальні рішення утворюють множину Парето, що позначається .


У відповідності до «Визначення 1»:


не існує такого , що .




Тобто, парето-оптимальне рішення – це таке можливе рішення, яке не може бути покращене (збільшене) по жодному з наявних критеріїв без погіршення (зменшення) по будь-якому хоча б одному іншому критерію. Рішення, що входять до множини Парето, також називають парето-ефективними.


Принцип Еджворта-Парето. Якщо ОПР веде себе «розумно» (тобто виконуються умови «Аксіоми 1» та «Аксіоми Парето»), то рішення, що їм обираються, обов’язково повинні бути парето-оптимальними .


Домінування рішення над за Парето позначається як , або , або .

В багатьох випадках пошук парето-оптимальних рішень є вкрай трудомісткою задачею. Тому введемо поняття «слабкого» парето-оптимального рішення або рішення, оптимального за Слейтером.


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


Запис означає виконання покомпонентних нерівностей для всіх j=1(1)m, причому . Це означає, що компоненти першого вектора суворо більші за відповідні компоненти другого вектора .

Домінування рішення над за Слейтером позначається як , або , або .

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

Як при пошуку парето-оптимальних рішень, так і при пошуку рішень, оптимальних за Слейтером, необхідно враховувати узгодженість побажань ОПР. Тобто, ОПР зацікавлений в отриманні максимальних значень всіх компонентів векторного критерію f.

Геометрична інтерпретація принципу Еджворта-Парето наведена на рис. 1.1.



Рисунок 1.1 – Відношення між множинами допустимих, оптимальних за Слейтером, парето-оптимальних та обираємих рішень


  1   2   3   4   5   6   7   8   9   ...   25

скачати

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