Визначення стратегії оптимального розподілу об’єму пам’яті між комп’ютерами з використанням методу динамічного програмування

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

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

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

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

Рисунок 1.1 - Розділення ресурсів між агрегатами

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

Розділ 2. Теоретичні відомості

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

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

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

У вузькому сенсі прийняття рішень - це заключний акт аналізу варіантів, результат вибору.

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

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

Методи прийняття рішень

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

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

Матричний - це занесення до матриці усіх можливих наслідків реалізації рішення.

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

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

Аналітично-систематизаційний - це сукупність трьох складових: аналізу ситуації, аналізу проблем і аналізу рішень.

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

Груповий - це створення деякими організаціями груп для прийняття важливих рішень.

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

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

Успішне рішення має бути: науково обґрунтованим, цілеспрямованим, кількісно та якісно визначеним, правомірним, оптимальним, своєчасним, комплексним, гнучким, повністю оформленим [2].

Метод динамічного програмування

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

Нехай є деяка операція О, що розкладається на ряд послідовних "кроків" або "етапів", - наприклад, діяльність промислової галузі впродовж декількох років; або послідовність тестів, що застосовуються для контролю апаратури.

Розглянемо операцію О, що складається з m етапів. Нехай ефективність операції характеризується деяким показником W - виграшем. Припустимо, що виграш за всю операцію складається з виграшів на кожному з етапів:

де wi - виграш на i-му етапі.

Операція О є процесом, яким ми керуємо, обираючи значення різних параметрів. На кожному етапі обирається рішення, від якого залежить виграш на цьому етапі та за операцію в цілому, таке рішення - етапне управління. Сукупність всіх етапних управлінь є управлінням операцією в цілому і позначається літерою x, а етапні управління - літерами х 1, х 2,…xm:

Слід мати на увазі, що х 1, х 2,…xm в загальному випадку не числа, а можуть бути векторами, функціями, тощо.

Потрібно знайти таке управління х, за якого виграш W перетворюється на максимум:

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

Максимальний виграш, що досягається за цього управління позначимо W* [3]:

2.2 Алгоритм рішення задач динамічного програмування

Нехай в системі є певний запас ресурсу К, який треба розподілити між m агрегатами А 1, А 2, …, Аm. Кожен агрегат Аi за умови давання йому ресурсу в розмирі х приносить дохід, що можна знайти за функцією ц(хi). Всі функції ц(хi) (i=1,2,…m) задані та є неубутніми. Треба знайти такий розподіл засобів К між агрегатами, за якого вони приносять найбільший дохід.

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

,

де i=1,2,…m, j=1,2,…К.

Якщо 0<бi<1 виробнича функція моє вигляд S-образної кривої опуклої вгору (рис. 2.4.1), при бi>1 вона опукла донизу(рис. 2.4.2), а при бi=1 вона є лінійною (рис. 2.4.3).

Рисунок 2.4.1 - 0<бi<1

Рисунок 2.4.2 - бi>1

Рисунок 2.4.3 - бi=1

На першому етапі приймаємо вкладення засобів у перший агрегат А 1, на другому - в агрегат А 2 і так далі.

Система управління S в даному випадку - засоби або ресурси, які розподіляються. Стан системи S перед кожним кроком характеризується одним числом S - початковим запасом ще не вкладених засобів. В цій задачі етапним управлінням є засоби х 1, х 2,…xm, що виділяються агрегатам. Потрібно знайти оптимальне управління, тобто таку сукупність чисел х 1, х 2,…xm, за якої сумарних дохід буде максимальним:

.

Перший етап починаємо з оптимізації останнього m-го кроку. Нехай ми підійшли до цього кроку із залишком засобів S. Звичайно, треба вкласти всю суму S в агрегат Аm. Тому умовне оптимальне управління на m-ому кроці: віддати останньому агрегатові всі засоби S, тобто:

хm(S)=S,

а умовний оптимальний виграш

Wm(S)=цm(S).Задаючись цілою гамою значень S, для кожного значення S розраховуємо хm(S) та Wm(S). Таким чином останній крок оптимізовано.

На другому етапі переходимо до передостаннього (m-1)-го кроку. Припустимо ми підійшли до нього із запасом засобів S. Позначимо Wm-1(S) умовний оптимальний виграш на двох останніх кроках: (m-1)-м та m-м (який вже оптимізовано на першому етапі розв'язання). Якщо виділити (m-1)-му кроці (m-1)-му агрегату засоби у розмирі х, то на останній крок залишиться S-x. Тоді виграш на двох останніх кроках буде дорівнювати:

цm-1(х) + Wm(S-х),

треба знайти таке х, за якого виграш максимальний:

Wm-1(S)=max{цm-1(x)+Wm(S-x)}.

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

На наступних етапах оптимізуємо (m-2)-ий, (m-3)-ий і т.д. кроки. В загальному випадку, для будь-якого і-го кроку знаходимо умовний оптимальний виграш за всі кроки до цього та до кінця за формулою:

Wі(S)=max{ці(x)+Wі+1(S-x)}.

А відповідне йому умовне оптимальне управління хі(S) - те значення х, за якого цей максимум досягається.

На останньому етапі дійшли до першого агрегату А 1. На цьому кроці не треба перебирати значення S, оскільки точно відомо, що запас засобів перед першим кроком дорівнює К:

W*=W1(K)=max{ц1(x)+W2(K-x)}.

Таким чином максимальний виграш (дохід) від всіх агрегатів знайдений. Залишається лише "прочитати рекомендації". Те значення х, за якого досягається максимум, є оптимальне управління х 1* на першому кроці. Після того, як ці засоби вкладено у перший агрегат залишається К-х 1*. "Читаючи" рекомендацію для S=К-х 1*, другому агрегату надаємо оптимальну кількість засобів х 2*=х 2-(К-х 1*) і т.д. до кінця.

Розділ 3. Визначення оптимальної стратегії розподілу ресурсів

3.1 Моделювання системи

Вхідними даними для розрахунку даної системи є:

- m - кількість мережевих комп'ютерів, між якими слід ділити ресурси;

- K - об'єм ресурсів, який слід розділити між m комп'ютерами.

Також для кожного комп'ютера системний адміністратор повинен вказати коефіцієнти bi, di min, di max та бi (i=1,2,…m) для визначення ефективності певного агрегату.

Вихідні дані:

- максимальна ефективність системи;

- вектор-розподіл ресурсів між комп'ютерами.

Ефективність роботи агрегату при певній кількості ресурсів буде автоматично рахуватись в окремій процедурі.

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

Також слід урахувати можливі помилки при вводі даних.

3.2 Рішення програмних засобом

Для розрахунку даної системи у середовищі Visual Studio 2013 мовою C# була створений програмний засіб.

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

Розроблене програмне забезпечення підтримується на операційних системах Windows XP/Vista/7/8/8.1/10 і не потребує встановлення.

Програма відкривається подвійним натиском на піктограму.

Першим етапом роботи з програмою є введення початкових даних: кількості агрегатів і об'єму пам'яті (рис. 3.2.1), що треба розподілити, та відповідних коефіцієнтів bi, di min, di max та бi (рис. 3.2.2).

Рисунок 3.2.1 - Введення кількості агрегатів та ресурсів

Рисунок 3.2.2 - Введення коефіцієнтів для агрегатів

Слід зауважити, що потрібно обов'язково заповнювати всі поля, інакше система видає повідомлення про помилки (рис. 3.2.3 та рис. 3.2.4).

Рисунок 3.2.3 - Помилка при незаповненому полі ресурсів

Рисунок 3.2.4 - Помилка при невказаному коефіцієнті

Якщо ж усі початкові дані введені, то по натисканню на кнопку "Розрахувати" система видає повідомлення, що містить значення максимальної ефективності при заданих вхідних даних та їх параметрах, та інформацію про те, як краще ефективніше розділити ресурси між комп'ютерами (рис. 3.2.5).

Рисунок 3.2.5 - Вивід рішення задачі

При натисканні кнопки "Назад" можна повернутися до вводу початкових даних та корегувати їх.

При натисканні кнопки "Вихід" система уточнює, чи дійсно вийти з програми (рис. 3.2.6), та у випадку позитивної відповіді робота програми завершується.

Рисунок 3.2.6 - Вікно-попередження про вихід

При натисканні кнопки "Новий розв'яз" програма повертається до першого етапу введення даних (рис. 3.2.1).

Слід зазначити, що всі поля вводу обмежені на введення символів і приймають тільки числа, а поля для вводу бi ще сприймають кому. Тому програма буде нескладною у використання навіть для неуважного користувача.

Висновки