Зміна стану системи

Зміна стану системи

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

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

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

Розглянемо рішення цього типу задач на наступному прикладі. Літак у точці S0 має швидкість v0 та висоту H0. Він повинен піднятися на висоту HK і отримати швидкість vK. Потрібно мінімізувати витрати палива, якщо відома витрата палива при збільшенні швидкості від vi до vi+1 при H = const та відома втрата палива при збільшенні висоти від Hi до Hi+1 при v = const. Для розв’язання задачі поділимо (HK — H0) та (vK — v0) відповідно на n1 та n2 однакових частин:

; .

Розрахунки проводимо за графом рис .1, в якому ваги горизонтальних дуг відповідають витратам палива при збільшенні швидкості від vi до vi+1 при H = const, а ваги вертикальних дуг — втратам палива при збільшенні висоти від Hi до Hi+1 при v = const .

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

Розглянемо більш детально алгоритм розрахунків:

• 1. У кінцевому прямокутнику записуємо витрати палива «0».
• 2. У прямокутниках B1 та B2 записуємо витрати палива відповідно «11» та «8», що витрачається для досягнення кінцевої точки SK. Можлива оптимальна траєкторія позначається стрілками, а заборонені шляхи не помічаються стрілками.
• 3. У точки B1, B2 можна попасти з точок C1, C2, C3. Із точки C2 на кінцеву точку можна йти шляхом на точку B1 (з витратами палива 7+11=18), або на точку B2 (з витратами палива 9+8=17). У прямокутнику C2 ми пишемо найменшу втрату палива «17» і показуємо лише однією стрілкою можливу оптимальну траєкторію на точку B2. Стрілка на точку B1 не показується, бо цей шлях збільшить витрати палива.

Таким чином ми заповнюємо цифрами втрат палива всі інші прямокутники, отримуючи ряд можливих траєкторій, позначених стрілками. Оптимальну потрібну кількість палива ми отримуємо у початковому (стартовому) прямокутнику S0 — цифру «37».

4. Оптимальний шлях відповідає ланцюгу незаборонених дуг, який починається в точці S0 і завершується в кінцевій точці SK (він показаний жирними стрілками). Оптимальна стратегія полягає втому, що з поточного стану на одну дискрету збільшують висоту, на висоті на три дискрети збільшують швидкість і при швидкості на дві дискети збільшують висоту.

Рисунок 1. Задача про зміну стану системи У даній задачі визначені всі умови переміщення для початкової та кінцевої точки. Тому процес отримання оптимальної траєкторії можна було б почати з початку — точки S0, позначаючи у прямокутниках мінімальну витрату палива при такому переміщенні. Кінцевий результат (кількість витраченого палива та оптимальна траєкторія) при цьому не змінюється. Але ми почали розрахунок з кінця, бо це — найбільш розповсюджений напрямок розрахунків у задачах динамічного програмування.

Розрахунок на графі дозволяє наочно побачити всі результати розрахунків і всі можливі шляхи, у тому числі і зайві. На перший погляд ми отримали рішення методом перебору всіх можливих варіантів, але насправді заборона неперспективних шляхів дозволяє скоротити розрахунки у 5 — 10 разів.

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

Рисунок 2. Рішення задачі зміни стану системи На рис. 2. оптимальна стратегія переведення системи із стану S0 в стан SК показана жирними стрілками. Мінімальні витрати ми отримуємо у початковому (стартовому) прямокутнику S0 — цифру «1».

Висновок

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