183950 (629983), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

У стохастичних моделях невідомі фактори – це випадкові величини, для яких відомі функції розподілу й різні статистичні характеристики (математичне очікування, дисперсія, середньоквадратичне відхилення й т.д.). Серед стохастичних можна виділити:

• моделі стохастичного програмування, у яких в цільову функцію (1.2) входять випадкові величини;

• моделі теорії випадкових процесів, призначені для вивчення процесів, стан яких у кожен момент часу є випадковою величиною;

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

Рисунок 1.4 – Класифікація математичних моделей

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

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

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

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

У динамічних моделях на відміну від статичних лінійних і нелінійних моделей враховується фактор часу. Критерій оптимальності в динамічних моделях може бути самого загального виду (і навіть взагалі не бути функцією), однак для нього повинні виконуватися певні властивості. Розрахунок динамічних моделей складний, і для кожної конкретної задачі необхідно розробляти спеціальний алгоритм рішення [4].

Графічні моделі використаються тоді, коли завдання зручно представити у вигляді графічної структури.

2. ТЕОРЕТИЧНІ АСПЕКТИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

2.1 Постановка задачі динамічного програмування. Основні умови й область застосування

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

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

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

Нехай – кількість етапів. На будь-якому і-му етапі процес може бути в різних станах { } , кожний з яких характеризується скінченою множиною параметрів. Множину параметрів доцільно розглядати як компоненти деякого вектора , де – кількість параметрів, обраних для характеристики стану. На будь-якому з досліджуваних етапів система може бути в кількох станах.

Перебіг процесу визначається певною послідовністю переходів з одного стану в інший. Якщо процес на і-му етапі перебував у деякому стані , то наступний стан на (і+1)-му кроці визначається не лише попереднім станом, а й вибором певного управління при досягненні ( ; ). У загальному випадку будь-яке управління на будь-якому етапі доцільно розглядати як -мірний вектор . Числові значення компонент вектора управління будуть залежати як від вихідного стану на і-му кроці, так і від наступного стану на (і+1)-му кроці , тобто вектор визначається чотирма індексами і має бути вибраний з певної множини допустимих управлінь.

Для спрощення записів вектори можливих поточного стану та управління будемо позначати лише одним індексом, спів ставляючи їх певному кроку (етапу), тобто щодо стану , мається на увазі один із можливих станів множини { } , а щодо вектора – один із можливих векторів множини { } , ( ).

Рисунок 1.5 – Можливі стани системи на кожному етапі

На рисунку 1.5 схематично кругами зображені можливі стани на кожному етапі, лініями – можливі переходи від одного стану до іншого за вибору певного управління. Таким чином, стан процесу на і-му етапі визначається певною функціональною залежністю від стану на попередньому кроці та значеннями параметрів управління на початку чергового кроку, тобто . Процес управління моделюється як вибір за кожного можливого j-го стану на і-му етапі певного k-мірного вектора з деяких допустимих множин векторів { } . Для спрощення він позначається . Множина послідовності управлінь позначається – , які переводять систему зі стану у стан , схематично це представлено на рисунку 1.6.

Рисунок 1.6 – Перехід системи із стану у стан

Будь-яку послідовність , що переводить систему зі стану у стан , називається стратегією, а вектори – її складовими.

Ефективність вибору послідовності управлінь (стратегії) оцінюється за вибраним критерієм певною цільовою функцією :

. (2.1)

Модель динамічного програмування можна використовувати в тих випадках, коли є підстави прийняти такі допущення стосовно досліджуваної системи:

– Стан системи в кінці і-го кроку визначається лише попереднім станом та управлінням на і-му кроці і не залежить від попередніх станів та управлінь. Формула (2.2) – рівняння стану.

, . (2.2)

– Цільова функція (2.1) є адитивною стосовно кожного етапу і залежить від того, яким був стан системи на початку етапу та яке було обране управління. Нехай – показник ефективності і-го кроку.

, . (2.3)

Тоді цільова функція (2.1) буде представлена формулою (2.4)

. (2.4)

Метод динамічного програмування також можна використовувати при розв’язанні задач з так званою “мультиплікативною” цільовою функцією, тобто:

. (2.5)

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

. (2.6)

Дана стратегія переводить систему зі стану у стан і за якої цільова функція (2.4) досягає екстремального значення.

Нехай розглядається задача, що розпадається на m кроків або етапів, наприклад планування діяльності підприємства на кілька років, поетапне планування інвестицій, керування виробничими потужностями протягом тривалого строку. Показник ефективності задачі в цілому позначиться через W, а показники ефективності на окремих кроках – через , . Якщо W має властивість адитивності, тобто:

, (2.7)

то можна знайти оптимальне рішення задачі методом динамічного програмування.

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

Змінна від якої залежать виграш на і-м кроці й, отже, виграш у цілому, називається кроковим керуванням, .

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

Оптимальне управління – це значення управління , при якому значення є максимальним (або мінімальним, якщо потрібно зменшити програш):

, , (2.8)

де – область припустимих управлінь.

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

. (2.9)

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

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

Характеристики

Список файлов курсовой работы