Зміна стану системи
Вирішення задачі динамічного програмування, в якій стан системи характеризується двома параметрами. Умови переміщення для початкової та кінцевої точки у задачі про зміну стану системи. Оптимальна стратегія переведення системи із одного стану в інший.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | практическая работа |
| Язык | украинский |
| Дата добавления | 09.02.2015 |
| Размер файла | 739,1 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Поняття плоскої рами як стержневої системи. Умова задачі для розрахунку напружено-деформованого стану плоскої рами. Постановка задачі для розрахунку напружено-деформованого стану розпорів, комбінованих систем. Огляд епюр за допомогою документатора.
курсовая работа [777,6 K], добавлен 23.08.2014Розповсюдження об'єкно-орієнтованих мов програмування. Моделювання предметної області. Постановка задачі. Інформаційне забезпечення. Алгоритм розв'вязання задачі. Пограмне забезпечення. Основні задачі при моделюванні предметної області. Стан сутностей.
курсовая работа [772,8 K], добавлен 03.10.2008Дослідження проблеми пошуку автомобілів та постановка задачі створення автокаталогу з використанням мови програмування PHP і JаvаScrіpt. Дослідження моделей прецедентів системи та їх класової архітектури. Моделювання розподіленої конфігурації систем.
курсовая работа [3,7 M], добавлен 11.10.2010Поняття експертної системи, приклади сфер її використання. Класифікація та задачі експертних систем. Означення продукційної експертної системи, приклад її дії та опис програми. Побудова бази знань із чіткою логікою, що вирішує завдання класифікації.
лабораторная работа [712,5 K], добавлен 19.03.2011Побудова моделі процесів системи. Відображення користувачів і їхніх функцій, підметів автоматизації в прив'язці до структури системи. Відображення структури інформаційних та фізичних об'єктів системи та їх взаємозв’язків. Побудова моделі станів системи.
курсовая работа [125,2 K], добавлен 03.10.2008Життєвий цикл інформаційної системи як упорядкована сукупність змін його стану між початковим і кінцевим станами. Умови забезпечення адаптивного характеру розвитку ІС. Технологія проектування інформаційної системи, технологічна мережа проектування.
реферат [252,2 K], добавлен 20.06.2010Задачі системного управління структурою і властивостями складних об'єктів. Аналіз вимог до точності та стійкості слідкувальної системи. Розробка алгоритмів визначення стійкості та якості перехідних процесів системи. Програмний комплекс системи.
курсовая работа [2,0 M], добавлен 28.02.2011Методи алгоритмiчного описаня задач, програмування на основi стандартних мовних засобiв. Переклад з однієї системи числення в іншу при програмуванні. Системи числення. Двійкові системи числення. Числа з фіксованою і плаваючою комою. Програмна реалізація.
курсовая работа [164,1 K], добавлен 07.12.2008Вибір моделі задачі інформаційної підтримки сучасних автопаркінгів. Постановка задачі та вибір структур даних. Здійснення замовлень в системі. Перевірка замовлених місць на парковці. Специфікація системи інформаційного обслуговування автопаркінгу.
дипломная работа [2,5 M], добавлен 13.07.2014Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Загальні відомості, методи та постановка задачі динамічного програмування. Практичне застосування методу динамічного програмування на прикладі розподілення вантажів між 4-ма торговими суднами. Рекурентна природа обчислень в динамічному програмуванні.
курсовая работа [1,1 M], добавлен 22.05.2015Програма на мові програмування С++. Аналіз стану технологій програмування та обґрунтування теми. Розробка програми виконання завдання, методу вирішення задачі. Робота з файлами, обробка числової інформації і робота з графікою. Розробка програми меню.
курсовая работа [41,0 K], добавлен 17.02.2009Теорія обчислювальних систем. Режим обробки, що визначає порядок функціонування системи. Клас оброблюваних задач і порядок їхнього надходження в систему. Порядок ідентифікації обчислювальної системи. Математично задача синтезу обчислювальної системи.
реферат [33,7 K], добавлен 08.09.2011Поняття та функції операційної системи. Види операційних систем та їх характеристика. Напрямки розвитку операційних систем. Розробка алгоритму розв’язку економічної задачі розподілу продукції пекарні та реалізація його за допомогою Microsoft Excel.
курсовая работа [1,2 M], добавлен 15.06.2016Аналіз системних вимог та обґрунтування методу проектування системи. Алгоритм розв'язання задачі. Інформаційне, технічне, програмне та організаційне забезпечення. Вибір методу проектування архітектури та моделі функціонування системи "клієнт-банк".
дипломная работа [3,1 M], добавлен 12.05.2017Обґрунтований вибір засобів для проектування автоматизованої інформаційно-довідкової системи. Опис структури технологічного процесу обробки даних для розв’язання задачі. Комп'ютерна реалізація окремих об'єктів системи (таблиці, форми, звіти, запити).
курсовая работа [30,7 K], добавлен 14.05.2011Розробка програмного забезпечення для розв’язування задачі обчислювального характеру у середовищі Turbo Pascal 7.0. Розгляд систем числення. Практична реалізація задачі переводу чисел з однієї системи числення у іншу. Процедура зворотного переводу.
курсовая работа [112,2 K], добавлен 23.04.2010Побудова інформаційної системи, що буде слугувати для автоматизації процесу захисту персональних даних клієнтів банку. Вибір методу проектування архітектури та моделі функціонування системи. Перелік масивів, використовуваних під час розв’язання задачі.
дипломная работа [1,8 M], добавлен 02.06.2017Стан комп`ютерізації підприємства ТОВ "Люксофт-Україна". Середа розробки Eclipse. Ознайомлення з мовою програмування С++. Розробка клієнту навігаційної системи для відображення місцеперебування користувача у реальному часі з використанням онлайн мап.
курсовая работа [2,1 M], добавлен 12.09.2012
