Зміна стану системи
Алгоритм вирішення задачі динамічного програмування, в якій стан системи характеризується двома параметрами. Умови переміщення для початкової та кінцевої точки. Визначення стратегії переведення системи із одного стану в інший з мінімальними витратами.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | практическая работа |
| Язык | украинский |
| Дата добавления | 02.04.2015 |
| Размер файла | 737,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Практична робота № 9. Зміна стану системи
Мета роботи: вирішення задачі динамічного програмування, в якій стан системи характеризується двома параметрами.
Теоретичні відомості
Задачі зміни поточного стану системи на заданий стан полягають у визначенні такого шляху в багатовимірному просторі станів системи, який відповідав би оптимальному значенню функції мети, тобто досягти бажаного стану потрібно з найменшими витратами.
Задачі динамічного програмування, в яких стан системи характеризується двома параметрами, можуть розв'язуватися на спрямованих графах, в яких дуги відповідають покроковим змінам стану системи і мають ваги, що дорівнюють приросту функції мети (витрат) між сусідніми станами, а вузли відповідають станам системи. Параметри, які характеризують стан системи, змінюються дискретно, тому зовнішній вигляд графа нагадує координатну сітку. Вхідними даними для даної задачі є координати поточного і бажаного станів в просторі станів системи, обрані дискрети параметрів, що характеризують стан системи, а також дані щодо приросту функції мети (витрат) між сусідніми станами.
Розглянемо рішення цього типу задач на наступному прикладі. Літак у точці 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”.
Висновок
В ході даної практичної роботи я здобула практичні навички рішення задачі динамічного програмування, в якій стан системи характеризується двома параметрами, тобто навчилася вирішувати задачі зміни стану системи. Задачі зміни поточного стану системи на заданий стан полягають у визначенні такого шляху в багатовимірному просторі станів системи, який відповідав би оптимальному значенню функції мети, тобто досягти бажаного стану потрібно з найменшими витратами.
Размещено на Allbest.ru
...Подобные документы
Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Розповсюдження об'єкно-орієнтованих мов програмування. Моделювання предметної області. Постановка задачі. Інформаційне забезпечення. Алгоритм розв'вязання задачі. Пограмне забезпечення. Основні задачі при моделюванні предметної області. Стан сутностей.
курсовая работа [772,8 K], добавлен 03.10.2008Задачі системного управління структурою і властивостями складних об'єктів. Аналіз вимог до точності та стійкості слідкувальної системи. Розробка алгоритмів визначення стійкості та якості перехідних процесів системи. Програмний комплекс системи.
курсовая работа [2,0 M], добавлен 28.02.2011Загальні відомості, методи та постановка задачі динамічного програмування. Практичне застосування методу динамічного програмування на прикладі розподілення вантажів між 4-ма торговими суднами. Рекурентна природа обчислень в динамічному програмуванні.
курсовая работа [1,1 M], добавлен 22.05.2015Методи алгоритмiчного описаня задач, програмування на основi стандартних мовних засобiв. Переклад з однієї системи числення в іншу при програмуванні. Системи числення. Двійкові системи числення. Числа з фіксованою і плаваючою комою. Програмна реалізація.
курсовая работа [164,1 K], добавлен 07.12.2008Дослідження проблеми пошуку автомобілів та постановка задачі створення автокаталогу з використанням мови програмування PHP і JаvаScrіpt. Дослідження моделей прецедентів системи та їх класової архітектури. Моделювання розподіленої конфігурації систем.
курсовая работа [3,7 M], добавлен 11.10.2010Побудова моделі процесів системи. Відображення користувачів і їхніх функцій, підметів автоматизації в прив'язці до структури системи. Відображення структури інформаційних та фізичних об'єктів системи та їх взаємозв’язків. Побудова моделі станів системи.
курсовая работа [125,2 K], добавлен 03.10.2008Поняття плоскої рами як стержневої системи. Умова задачі для розрахунку напружено-деформованого стану плоскої рами. Постановка задачі для розрахунку напружено-деформованого стану розпорів, комбінованих систем. Огляд епюр за допомогою документатора.
курсовая работа [777,6 K], добавлен 23.08.2014Стан комп`ютерізації підприємства ТОВ "Люксофт-Україна". Середа розробки Eclipse. Ознайомлення з мовою програмування С++. Розробка клієнту навігаційної системи для відображення місцеперебування користувача у реальному часі з використанням онлайн мап.
курсовая работа [2,1 M], добавлен 12.09.2012Аналіз навігаційних технологій у сучасних AVL системах. Структура системи і вимоги до апаратного забезпечення, розробка алгоритмів функціонування окремих програмних модулів. Вибір мови програмування і СУБД. Тестовий варіант програмного забезпечення.
дипломная работа [1,8 M], добавлен 17.12.2015Характеристика середовища програмування Microsoft Visual C++ та бібліотеки класів MFC. Знаходження коефіцієнтів при невідомих за допомогою методу найменших квадратів. Створення програми для вирішення задачі обраним методом, її алгоритм та інтерфейс.
курсовая работа [434,8 K], добавлен 20.01.2014Життєвий цикл інформаційної системи як упорядкована сукупність змін його стану між початковим і кінцевим станами. Умови забезпечення адаптивного характеру розвитку ІС. Технологія проектування інформаційної системи, технологічна мережа проектування.
реферат [252,2 K], добавлен 20.06.2010Програма на мові програмування С++. Аналіз стану технологій програмування та обґрунтування теми. Розробка програми виконання завдання, методу вирішення задачі. Робота з файлами, обробка числової інформації і робота з графікою. Розробка програми меню.
курсовая работа [41,0 K], добавлен 17.02.2009Аналіз системних вимог та обґрунтування методу проектування системи. Алгоритм розв'язання задачі. Інформаційне, технічне, програмне та організаційне забезпечення. Вибір методу проектування архітектури та моделі функціонування системи "клієнт-банк".
дипломная работа [3,1 M], добавлен 12.05.2017Критерії (вимоги) до створення автоматичного робочого місця оператора реєстратури. Обґрунтування вибору середовища програмування та засобів збереження даних. Алгоритм програми. Опис інтерфейсу проекту системи. Програмні модулі та керівництво користувача.
дипломная работа [1017,0 K], добавлен 31.10.2014Поняття експертної системи, приклади сфер її використання. Класифікація та задачі експертних систем. Означення продукційної експертної системи, приклад її дії та опис програми. Побудова бази знань із чіткою логікою, що вирішує завдання класифікації.
лабораторная работа [712,5 K], добавлен 19.03.2011Аспекти вирішення методологічної та теоретичної проблеми проектування інтелектуальних систем керування. Базовий алгоритм навчання СПР за методом функціонально-статистичних випробувань. Критерій оптимізації та алгоритм екзамену системи за цим методом.
курсовая работа [1,6 M], добавлен 22.09.2011Основні мови програмування для системи сенсорного терміналу для відображення інформації про розклад студентам. Аналіз баз даних для системи відображення інформації. Рекомендації по використанню програмного забезпечення адміністратору та користувачеві.
дипломная работа [1,0 M], добавлен 02.09.2014Створення гнучкої клієнт-серверної системи інформаційної підтримки підвищення кваліфікації персоналу ДП № 9 з застосуванням мови програмування PHP, системи керування базами даних MySQL. Розробка алгоритмів, програмна реалізація основних процедур системи.
дипломная работа [1,8 M], добавлен 26.10.2012Аналіз математичного підґрунтя двійкової та двійкової позиційної систем числення. Переведення числа з двійкової системи числення в десяткову та навпаки. Арифметичні дії в двійковій системі. Системи числення з довільною основою. Мішані системи числення.
курсовая работа [149,5 K], добавлен 20.06.2010
