Графи та їхнє застосування

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

Граф G = G(V, E) – це сукупність множини V вершин (точок) і множини ребер E (зв’язків), що з’єднують деякі (або ж усі) вершини.

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

Хід роботи

1. Ознайомитись з теоретичними відомостями.

2. Створити робочу книгу МS Exсel під назвою Ваше прізвище_ Exсel_6 у відповідній папці своєї групи на диску D:. Усі завдання виконуються у цій робочій книзі але на окремих її «Листах».

3. Виконати практичні завдання, які наведені нижче.

4. Задача 6.1. Цілочисельне лінійне програмування. На підприємство, розміщене в пункті А, потрібно доставляти на автобусах 72 працівників, що мешкають поза межами пункту А. З них 42 працівники доставляються з пункту С, 20 — з пункту В, 6 — з пунктів, розташованих між С і В, і 4 — з пунктів, розміщених між В і А. Транспортне агентство, що обслуговує перевезення, має у своєму розпорядженні автобуси двох типів на 35 і 50 місць. На проїзні квитки агентство встановило ціни (табл. 6.1).

Таблиця 6.1

ВИХІДНІ ДАНІ

Тип автобуса	Ціни на білети, грн
ВА	СА	СВ
35 місць	39,0	54,0	45,0
50 місць	50,5	68,0	75,5

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

Розв’язання

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

Таблиця 6.2

ПОЗНАЧЕННЯ ЗМІННИХ

Тип автобуса	Ділянка шляху
ВА	СА	СВ
35 місць
50 місць

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

Тут співвідношенням із табл. 6.1 визначається цільова функція, що виражає сумарні витрати, які потрібно мінімізувати; б) виражаються обмеження, що випливають із необхідності обслу­говувати транспортними засобами 48 працівників (42 — з пункту С і В та 6 — з пунктів між С і В); в) обмеження на кіль­­кість автобусів, які мають забезпечити доставку всіх 72 працівників у пункт А.

Розв’язуючи цю задачу з використанням надбудови Excel Пошук рішень, одержимо, що цільова функція матиме мінімальне значення за

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

Таблиця 6.3

ПЛАТІЖНА МАТРИЦЯ

	B1	B2	a1
A1	0,3	0,8	0,3
A2	0,7	0,4	0,4
	0,7	0,8

Розв’язання

Запишемо умови в прийнятних індексах:

а₁₁ = 0,3; а₁₂ = 0,8; а₂₁ = 0,7; а₂₂ = 0,4.

Визначимо верхню й нижню ціни гри:

Як бачимо, одержано гру без сідлової точки, тому що

0,4 ¹ 0,7; b ¹ a.

Висновок: Оскільки сідлової точки немає, застосування чистих стратегій не приводить до оптимального результату.

Його можливо знайти шляхом використання змішаних стратегій.

5. Зберегти результати виконаних завдань.

6. Підготувати звіт про виконання практичної роботи.

7. Ознайомитися з питаннями для перевірки знань та тестами.

8. Захистити роботу викладачу.

Завдання для перевірки знань

1. Як відбувається класифікація методів системного аналізу?

2. Чому поділ методів системного аналізу на кількісні та якісні є умовним?

3. Які етапи системного аналізу охоплюють кількісні методи?

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

5. Які підходи чи методи називають кількісними? У яких випадках їх доцільно

6. Розкрийте суть економіко-математичного методу.

7. Назвіть приклади застосування математичного програмування.

8. Розкрийте суть методу лінійного і нелінійного програмування.

9. Назвіть основні етапи дискретного програмування.

10. Розкрийте суть статистичних методів у дослідженні систем.

11. У чому полягає відмінність між строго- і чітко вираженою ієрархічною структурою?

12. У яких випадках застосовують терміни: дерево функцій, дерево рішень, дерево напрямів прогнозування?