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

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

Граф 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 подано платіжну матрицю гри, де і — стратегії керівника; і — стратегії, що віддзеркалюють характер розв’язуваних на ЕОМ задач. Необхідно знайти оптимальну змішану стратегію керівника.