183951 (629984), страница 2

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

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

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

Будемо вважати, що стан розглянутої системи S на K-м кроці (k=1, n) визначається сукупністю чисел X^(k) =(x₁^(k), x₂^(k),…, x_n^(k)), які отримані в результаті реалізації керування uk, що забезпечило перехід системи S зі стану X^(k-1) у стан X^(k). При цьому будемо припускати, що стан X^(k), у яке перейшла система S, залежить від даного стану X^(k-1) і обраного керування u_k і не залежить від того, яким образом система S прийшла в стан X^(k-1).

Далі із уважати, що якщо в результаті реалізації k-го кроку забезпечені певний доход або виграш, що також залежить від вихідного стану системи X^(k-1) і обраного керування u_k і рівний W_k^{(X(k-1), uk)}, те загальний доход або виграш за n кроків становить

n

F=∑ W_k(X^(k-1), u_k) (1.1)

k=1

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

Виконання для завдання динамічного програмування першої умови дозволяє сформулювати для неї принцип оптимальності Беллмана. Перш ніж зробити це, треба дати визначення оптимальної стратегії керування. Під такою стратегією розуміється сукупність керувань U^*=(u₁*, u₂*,…, u_n*), у результаті реалізації яких система S за n кроків переходить із початкового стану X⁽⁰⁾ у кінцеве X^(k) і при цьому функція (1.1) приймає найбільше значення.

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

Звідси треба, що оптимальну стратегію керування можна одержати, якщо спочатку знайти оптимальну стратегію керування на n-м кроці, потім на двох останніх кроках, потім на трьох останніх кроках і т.д., аж до першого кроку. Таким чином, рішення розглянутого завдання динамічного програмування доцільно починати з визначення оптимального рішення на останньому, n-м кроці. Для того щоб знайти це рішення, мабуть, потрібно зробити різні припущення про те, як міг скінчитися передостанній крок, і з обліком цього вибрати керування un0, що забезпечує максимальне значення функції W_n(X^(n-1), u_n). Таке керування un0 обране при певних припущеннях про те, як скінчиться попередній крок, називається умовно оптимальним керуванням. Отже, принцип оптимальності вимагає знаходити на кожному кроці умовно оптимальне керування для кожного з можливих варіантів попереднього кроку.

Щоб це можна було здійснити практично, необхідно дати математичне формулювання принципу оптимальності. Для цього введемо деякі додаткові позначення. Позначимо через F_n(X⁰) максимальний доход, одержуваний за n кроків при переході системи S з початкового стану X⁽⁰⁾ у кінцевий стан X^(k) при реалізації оптимальної стратегії керування U=(u₁, u₂,…, u_n), а через F_n-k(X^(k)) – максимальний доход, одержуваний при переході з будь-якого стану X(k) у кінцевий стан X⁽ⁿ⁾ при оптимальній стратегії керування на що залишилися n-k кроках. Тоді:

F_n(X⁰)=max[W₁(X⁽⁰⁾, u₁)+ … + W_n(X^(n-1), u_n)] (1.2)

U_k+j

F_n-k(X^(k))=max[W_k+1(X^(k), u_k+1)+F_n-k-1(X^k+1))] (k=0, n-1) (1.3)

U_k+1

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

Думаючи k=n-1 у рекуррентном співвідношенні (1.3), одержимо наступне функціональне рівняння:

F₁(X^(n-1)=max[W_n(X^(n-1), u_n)+F₀(X⁽ⁿ⁾)] (1.4)

u_n

У цьому рівнянні F₀(X⁽ⁿ⁾) будемо вважати відомим. Використовуючи тепер рівняння (1.4) і розглядаючи всілякі припустимі із системи S на (n-1) – м кроці X₁^(n-1), X₂^(n-1),…, X_m^(n-1),…, знаходимо умовні оптимальні рішення u_n⁰(x₁^(n-1)), u_n⁰(x₂^(n-1)),…, u_n⁰(x_m^(n-1)),…

і відповідні значення функції (1.4)

F₁⁰ (X₁^(n-1)), F₁⁰ (X₂^(n-1)), …, F₁⁰ (X_m^(n-1)),…

Таким чином, на n-м кроці знаходимо умовно оптимальне керування при будь-якому припустимому стані системи S після (n-1) – го кроку. Тобто, у якому би стані система не виявилася після (n-1) – го кроку, буде відомо, яке варто прийняти рішення на n-м кроці. Відомо також і відповідне значення функції (2.4). Розглянемо функціональне рівняння при k=n-2:

F₂(X^(n-1))=max[W_n-1(X^(n-2), u_n-1)+F₁(X^(n-1))] (1.5)

U_n-1

Для того щоб знайти значення F₂ для всіх припустимих значень X^(n-2), необхідно знати W_n-1(X^(n-2), u_n-1) і F₁(X^(n-1)). Що стосується значень F₁(X^(n-1)), те вони вже визначені. Тому потрібно зробити обчислення для W_n-1(X^(n-2), u_n-1) при деякому відборі припустимих значень X^(n-2) і відповідних керувань u_n-1. Ці обчислення дозволять визначити умовно оптимальне керування u0n-1 для кожного X^(n-2). Кожне з таких керувань разом із уже обраним керуванням на останньому кроці забезпечує максимальне значення доходу на двох останніх кроках.

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

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

Щоб знайти оптимальну стратегію керування, тобто визначити шукане рішення завдання, потрібно тепер пройти всю послідовність кроків, тільки цього разу від початку до кінця. А саме: на першому кроці як оптимальне керування u₁* візьмемо знайдене умовно оптимальне керування u₁⁰. На другому кроці знайдемо стан X₁*, у яке переводить систему керування u₁*. Цей стан визначає знайдене умовно оптимальне u₂⁰, що тепер уважається оптимальним. Знаючи u₂*, знаходимо X₂*, а виходить, визначаємо u₃* і т.д. У результаті цього найдеться рішення завдання, тобто максимально можливий доход й оптимальну стратегію керування U*, що включає оптимальні керування на окремих кроках: U*= (u₁*, u₂*,…, u_n*).

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

Динамічне завдання по заміні встаткування можливо також вирішити й графічним методом. На осі Х відкладають номер кроку (к). на осі В – вік устаткування (t). Крапка (до-1; t) на площині відповідає початку К-ого кроку по експлуатації встаткування у віці t років.

Б удь-яка траєкторія переводящая крапку S (k-1; t) зі стану S0 S. Складається з відрізків, тобто із кроків відповідним рокам експлуатації. Потрібно вибрати таку траєкторію при якій витрати на експлуатацію будуть мінімальні. Якщо відомі залежність продуктивності встановленого на підприємстві встаткування від часу його використання R(t) і залежність витрат на ремонт устаткування при різному часі його використання S(t) і витрати пов'язані із придбанням нового обладнання, то показником ефективності в цьому випадку є прибуток яка максимізується.

2. Застосування динамічного програмування в економічних дослідженнях

програмування економічний дослідження динамічний

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

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

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

1) балансовий метод;

2) метод математичного моделювання;

3) векторно-матричний метод;

4) метод економіко-математичних множників (оптимальних суспільних оцінок);

5) метод послідовного наближення.

У той же час академік Канторович виділяв математичні методи в чотири групи:

– макроекономічні моделі, куди відносив балансовий метод і моделі попиту;

– моделі взаємодії економічних підрозділів (на основі теорії ігор);

– лінійне моделювання, включаючи ряд завдань, що небагато відрізняються від класичного лінійного програмування;

– моделі оптимізації, що виходять за межі лінійного моделювання (динамічне, нелінійне, ціле і стохастичне програмування).

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

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

Із цього погляду безсумнівним лідером є метод лінійної оптимізації, що був розроблений академіком Канторовичем в 30-і роки ХХ-го століття. Найчастіше завдання лінійного програмування застосовується при моделюванні організації виробництва. От як по Канторовичу виглядає математична модель організації виробництва:

У виробництві беруть участь M різних виробничих факторів (інгредієнтів) – робоча сила, сировина, матеріали, устаткування, кінцеві й проміжні продукти й ін. Виробництво використає S технологічних способів виробництва, причому для кожного з них задані обсяги вироблених інгредієнтів, розраховані на реалізацію цього способу з одиничною ефективністю, тобто заданий вектор a_k = (a_1k, a_2k,…, a_mk), k = 1,2…, S, у якому кожна з компонентів a_іk указує обсяг виробництва, що відповідає (і-го) інгредієнта, якщо вона позитивна; і обсяг його витрати, якщо вона негативна (у способі k).

Вибір плану означає вказівка інтенсивності використання різних технологічних способів, тобто план визначається вектором x = (x1, x2,…, x) з невід’ємними компонентами.

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

a _ikx_k > b_i; i=1,2,…, m. (2.1)

Якщо і > 0, то нерівність означає, що з потреба в інгредієнті в розмірі й, якщо і < 0, то нерівність означає, що є ресурс даного інгредієнтів розмірі – і =| і |. Далі передбачається, що використання кожного способу, пов'язаного з витратами одного з перерахованих інгредієнтів або особливо виділеного інгредієнта в кількості Ck при одиничній інтенсивності способу k. Як цільова функція приймається сумарна витрата цього інгредієнта в плані.

f(x) = c_kx_k. (2.2)

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

На основі об'єктивно обумовлених оцінок американським математиком Дж. Данцигом – був розроблений симплекс-метод рішення завдань оптимального програмування. Цей метод досить широко застосовується. Алгоритм його досить детально пророблений, і навіть розроблені прикладні пакети програм, які застосовуються в багатьох галузях планування.

Метод лінійної оптимізації з того моменту, як він був розроблений Канторовичем, не залишався без змін, він розвивався й продовжує розвиватися. Наприклад, формула (2.2) у сучасній інтерпретації виглядає в такий спосіб.

a_ij x_j < b_i (i I) (2.3)

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

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

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

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