КУРСОВА РОБОТА
На тему
«Моделювання оптимальноїстратегії заміни обладнання за допомогою динамічного програмування»
Суми – 2006
Вступ
У нашчас наука приділяє велику увагу питанням організацій й керування, це приводитьдо необхідності аналізу складних цілеспрямованих процесів під кутом зору їхньоїструктури й організації. Потреби практики викликали до життя спеціальні методи,які зручно поєднувати за назвою «дослідження операцій». Під цим терміномрозуміється застосування математичних, кількісних методів для обґрунтуваннярішень у всіх областях цілеспрямованої людської діяльності.
Метоюдинамічного програмування є визначення найкращого способу дії при рішенні тогоабо іншого завдання. Для побудови математичної моделі необхідно мати строгеподання про мету функціонування досліджуваної системи й мати інформацію прообмеження, які визначають область припустимих значень. Мета й обмеження повиннібути представлені у вигляді функцій.
Практичновсі методи динамічного програмування породжують алгоритми, які є ітераційнимипо своїй природі. Це має на увазі, що завдання вирішується послідовно (ітераціонно),коли на кожному кроці (ітерації) одержуємо рішення, що поступово сходяться дооптимального рішення.
Ітераційнаприрода алгоритмів звичайно приводить до об'ємних однотипних обчислень. У цьомуй полягає причина того, що ці алгоритми розробляються, в основному, дляреалізації за допомогою обчислювальної техніки.
Метоюданої курсової роботи є знаходження оптимального плану заміни обладнання для максимізаціїприбутковості діяльності підприємства.
Об’єктомкурсової роботи виступає будь-яке підприємство яке має устаткування таобладнання, що використовує для виготовлення продукції.
Предметомкурсової роботи являється методи динамічного програмування.
1.Теоретичні відомості щодо динамічного програмування
Більшістьметодів дослідження операцій зв'язано в першу чергу із завданнями цілкомпевного змісту. Класичний апарат математики виявився малопридатним для рішеннябагатьох завдань оптимізації, що включають велике число змінних й/або обмеженьу вигляді нерівностей. Безсумнівна привабливість ідеї розбивки завдання великоїрозмірності на підзадачі меншої розмірності, що включають усього по декількохзмінних, і наступного рішення загального завдання вроздріб. Саме на цій ідеїзаснований метод динамічного програмування.
Динамічнепрограмування (ДП) являє собою математичний метод, заслуга створення й розвиткуякого належить насамперед Беллману. Метод можна використати для рішення доситьширокого кола завдань, включаючи завдання розподілу ресурсів, заміни йкерування запасами, завдання про завантаження. Характерним для динамічногопрограмування є підхід до рішення завдання по етапах, з кожним з якихасоційована одна керована змінна. Набір рекурентних обчислювальних процедур, щозв'язують різні етапи, забезпечує одержання припустимого оптимального рішеннязавдання в цілому при досягненні останнього етапу.
Походженняназви динамічне програмування, імовірно, пов'язане з використанням методів ДП узавданнях прийняття рішень через фіксовані проміжки часу (наприклад, узавданнях керування запасами). Однак методи ДП успішно застосовуються також длярішення завдань, у яких фактор часу не враховується. Із цієї причини більше вдалимпредставляється термін багатоетапне програмування, що відбиває покроковийхарактер процесу рішення завдання.
Фундаментальнимпринципом, покладеним в основу теорії ДП, є принцип оптимальності. Власнекажучи, він визначає порядок поетапного рішення завдання, що допускаєдекомпозицію, (це більше прийнятний шлях, чим безпосереднє рішення завдання увихідній постановці) за допомогою рекурентних обчислювальних процедур.
Динамічнепрограмування дозволяє здійснювати оптимальне планування керованих процесів.Під «керованими» розуміються процеси, на хід яких ми можемо в тім або іншомуступені впливати.
Нехайпередбачається до здійснення деякий захід або серія заходів («операція»), щопереслідує певну мету. Запитується: як потрібно організувати (спланувати)операцію для того, щоб вона була найбільш ефективною? Для того, щоб поставленезавдання придбало кількісний, математичний характер, необхідно ввести в розгляддеякий чисельний критерій W, яким ми будемо характеризувати якість, успішність,ефективність операції. Критерій ефективності в кожному конкретному випадкивибирається виходячи із цільової спрямованості операції й завдання дослідження(який елемент керування оптимізується й для чого).
Сформулюємозагальний принцип, що лежить в основі рішення всіх завдань динамічногопрограмування («принцип оптимальності»):
«Якийби не був стан системи S перед черговим кроком, треба вибрати керування нацьому кроці так, щоб виграш на даному кроці плюс оптимальний виграш на всіхнаступних кроках був максимальним».
Динамічнепрограмування – це поетапне планування багатокрокового процесу, при якому накожному етапі оптимізується тільки один крок. Керування на кожному кроціповинне вибиратися з обліком всіх його наслідків у майбутньому.
Припостановці завдань динамічного програмування варто керуватися наступнимизасадами:
– вибратипараметри (фазові координати), що характеризують стан S керованої системи передкожним кроком;
– розчленуватиоперацію на етапи (кроки);
– з'ясуватинабір крокових керувань xі для кожного кроку й обмеження, щонакладають на них;
– визначитиякий виграш приносить на і-ом кроці керування xі, якщо перед цимсистема могла S, тобто записати «функцію виграшу»;
– визначити,як змінюється стан S системи S під впливом керування xі на і-омкроці: воно переходить у новий стан;
– записатиосновне рекурентне рівняння динамічного програмування, що виражає умовнийоптимальний виграш Wі(S) (починаючи з і-го кроку й до кінця) черезуже відому функцію Wі+1 (S).
Цьомувиграшу відповідає умовне оптимальне керування на і-м кроці xі(S) (причому увже відому функцію Wі+1 (S) треба замість S підставити змінений стан).
– зробитиумовну оптимізацію останнього (m-го) кроку, задаючись гамою станів S, з якихможна за один крок дійти до кінцевого стану, обчислюючи для кожного з нихумовний оптимальний виграш по формулі.
– зробитиумовну оптимізацію (m-1) – го, (m-2) – го й т.д. кроків по формулі,думаючи в ній й=(m-1), (m-2),…, і для кожного із кроків указати умовнеоптимальне керування xі(S), при якому максимум досягається.
Помітимо,що якщо стан системи в початковий момент відомо (а це звичайно буває так), тена першому кроці варіювати стан системи не потрібно – прямо знаходимооптимальний виграш для даного початкового стану S0. Це і єоптимальний виграш за всю операцію.
– зробитибезумовну оптимізацію керування, «читаючи» відповідні рекомендації на кожномукроці. Взяти знайдене оптимальне керування на першому кроці; змінити стансистеми по формулі; для знову знайденого стану знайти оптимальне керування надругому кроці х2* і т.д. до кінця.
Узавданнях динамічного програмування економічний процес залежить від часу (віддекількох періодів (етапів) часу), тому перебуває ряд оптимальних рішень(послідовно для кожного етапу), що забезпечують оптимальний розвиток усьогопроцесу в цілому. Завдання динамічного програмування називаються багатоетапнимиабо багатокроковими. Динамічне програмування являє собою математичний апарат,що дозволяє здійснювати оптимальне планування багатокрокових керованих процесіві процесів, що залежать від часу. Економічний процес називається керованим,якщо можна впливати на хід його розвитку. Керуванням називається сукупністьрішень, прийнятих на кожному етапі для впливу на хід процесу. В економічнихпроцесах керування полягає в розподілі й перерозподілі засобів на кожномуетапі. Наприклад, випуск продукції будь-яким підприємством – керований процес,тому що він визначається зміною складу встаткування, обсягом поставок сировини,величиною фінансування й т.д. Сукупність рішень, прийнятих на початку кожногороку планованого періоду по забезпеченню підприємства сировиною, замінівстаткування, розмірам фінансування й т.д., є керуванням. Здавалося б, дляодержання максимального обсягу випускає продукції, що, найпростіше вкластимаксимально можлива кількість засобів і використати на повну потужністьустаткування. Але це привело б до швидкого зношування встаткування й, якнаслідок, до зменшення випуску продукції. Отже, випуск продукції требаспланувати так, щоб уникнути небажаних ефектів. Необхідно передбачити заходи,що забезпечують поповнення встаткування в міру зношування, тобто по періодахчасу. Останнє хоча й приводить до зменшення первісного обсягу випускаєпродукції, що, але забезпечує надалі можливість розширення виробництва. Такимчином, економічний процес випуску продукції можна вважати складається здекількох етапів (кроків), на кожному з яких здійснюється вплив на йогорозвиток.
Початкометапу (кроку) керованого процесу вважається момент ухвалення рішення (провеличину капітальних вкладень, про заміну встаткування певного виду й т.д.).Під етапом звичайно розуміють господарський рік.
Динамічнепрограмування, використовуючи поетапне планування, дозволяє не тільки спроститирішення завдання, але й вирішити ті з них, до яких не можна застосувати методиматематичного аналізу. Спрощення рішення досягається за рахунок значногозменшення кількості досліджуваних варіантів, тому що замість того, щоб один развирішувати складне різноманітне завдання, метод поетапного планування припускаєбагаторазове рішення щодо простих завдань.
Плануючипоетапний процес, виходять із інтересів усього процесу в цілому, тобто приухваленні рішення на окремому етапі завжди необхідно мати у виді кінцеву мету.
Однакдинамічне програмування має й свої недоліки. На відміну від лінійногопрограмування, у якому симплексний метод є універсальним, у динамічномупрограмуванні такого методу не існує. Кожне завдання має свої труднощі, і вкожному випадку необхідно знайти найбільш підходящу методику рішення. Недолікдинамічного програмування полягає також у трудомісткості рішення багатомірнихзавдань. При дуже великому числі змінних рішення завдання навіть на сучаснихЕОМ обмежується пам'яттю й швидкодією машини. Наприклад, якщо для дослідженнякожного змінного одномірного завдання потрібно 10 кроків, то у двовимірномузавданні їхня кількість збільшується до 100, у тривимірної – до 1000 і т.д.
Припустимо,якась система S перебуває в деякому початковому стані S0й єкерованою. Таким чином, завдяки здійсненню деякого керування U зазначенасистема переходить із початкового стану S0у кінцевий стан Sк.При цьому якість кожного з реалізованих керувань U характеризується відповіднимзначенням функції W(U). Завдання полягає в тім, щоб з безлічіможливих керувань U знайти таке U*, при якому функція W(U) приймаєекстремальне (максимальне або мінімальне) значення W(U*).
Завданнядинамічного програмування мають геометричну інтерпретацію. Стан фізичноїсистеми S можна описати числовими параметрами, наприклад витратою пального йшвидкістю, кількістю вкладених коштів і т.д. Назвемо ці параметри координатамисистеми; тоді стан системи можна зобразити крапкою S, а перехід з одного стануS1 в інше S2 – траєкторією крапки S. Керування U означає вибір певноїтраєкторії переміщення крапки S з S1 в S2, тобто встановлення певного законуруху крапки S.
Сукупністьстанів, у які може переходити система, називається областю можливих станів.Залежно від числа параметрів, що характеризують стан системи, область можливихстанів системи може бути різної. Нехай, наприклад, стан системи Sхарактеризується одним параметром, – координатою x. У цьому випадку змінакоординати, якщо на неї накладені деякі обмеження, зобразиться переміщеннямкрапки S по осі Оx або по її ділянці. Отже, областю можливих станівсистеми є сукупність значень x, а керуванням – закон руху крапки S зпочаткового стану S0 у кінцеве Sk по осі Ox або їїчастини (рис. 1.1).
/>/>/>/>S0 S Sk
/>
/>/>0 x
Областьможливих станів системи
Рисунок1.1. Графічне зображенняпереходу системи S
Такимчином, завданню динамічного програмування можна дати наступну геометричнуінтерпретацію. Із всіх траєкторій, що належать області можливих станів системий з'єднуючих областей S0й Sk, необхідно вибрати таку, наякій критерій W приймає оптимальне значення.
Щоброзглянути загальне рішення завдань динамічного програмування, уведемопозначення й зробимо для подальших викладів припущення.
Будемовважати, що стан розглянутої системи S на K-м кроці (k=1, n) визначаєтьсясукупністю чисел X(k) =(x1(k), x2(k),…,xn(k)), які отримані в результаті реалізації керуванняuk, що забезпечило перехід системи S зі стану X(k-1) у стан X(k).При цьому будемо припускати, що стан X(k), у яке перейшла система S,залежить від даного стану X(k-1) і обраного керування uk іне залежить від того, яким образом система S прийшла в стан X(k-1).
Далііз уважати, що якщо в результаті реалізації k-го кроку забезпечені певний доходабо виграш, що також залежить від вихідного стану системи X(k-1) іобраного керування uk і рівний Wk(X(k-1), uk),те загальний доход або виграш за n кроків становить
n
F=? Wk(X(k-1), uk) (1.1)
k=1
Такимчином, завдання динамічного програмування повинна задовольняти дві умови. Першуумову звичайно називають умовою відсутності післядії, а друге – умовоюадитивності цільової функції завдання.
Виконаннядля завдання динамічного програмування першої умови дозволяє сформулювати длянеї принцип оптимальності Беллмана. Перш ніж зробити це, треба дати визначенняоптимальної стратегії керування. Під такою стратегією розуміється сукупністькерувань U*=(u1*, u2*,…, un*), урезультаті реалізації яких система S за n кроків переходить із початковогостану X(0) у кінцеве X(k) і при цьому функція (1.1) приймаєнайбільше значення.
Принципоптимальності: яке б не був стан системи перед черговим кроком, треба вибратикерування на цьому кроці так, щоб виграш на даному кроці плюс оптимальнийвиграш на всіх наступних кроках був максимальним.
Звідситреба, що оптимальну стратегію керування можна одержати, якщо спочатку знайтиоптимальну стратегію керування на n-м кроці, потім на двох останніх кроках,потім на трьох останніх кроках і т.д., аж до першого кроку. Таким чином,рішення розглянутого завдання динамічного програмування доцільно починати звизначення оптимального рішення на останньому, n-м кроці. Для того щоб знайтице рішення, мабуть, потрібно зробити різні припущення про те, як міг скінчитисяпередостанній крок, і з обліком цього вибрати керування un0, що забезпечуємаксимальне значення функції Wn(X(n-1), un).Таке керування un0 обране при певних припущеннях про те, як скінчитьсяпопередній крок, називається умовно оптимальним керуванням. Отже, принципоптимальності вимагає знаходити на кожному кроці умовно оптимальне керуваннядля кожного з можливих варіантів попереднього кроку.
Щобце можна було здійснити практично, необхідно дати математичне формулюванняпринципу оптимальності. Для цього введемо деякі додаткові позначення. Позначимочерез Fn(X0) максимальний доход, одержуваний за n кроків припереході системи S з початкового стану X(0) у кінцевий стан X(k)при реалізації оптимальної стратегії керування U=(u1, u2,…,un), а через Fn-k(X(k)) – максимальний доход,одержуваний при переході з будь-якого стану X(k) у кінцевий стан X(n)при оптимальній стратегії керування на що залишилися n-k кроках. Тоді:
Fn(X0)=max[W1(X(0), u1)+ … + Wn(X(n-1), un)] (1.2)
Uk+j
Fn-k(X(k))=max[Wk+1(X(k), uk+1)+Fn-k-1(Xk+1))] (k=0, n-1) (1.3)
Uk+1
Останнєвираження являє собою математичний запис принципу оптимальності й зветься основногофункціонального рівняння Беллмана або рекуррентного співвідношення.Використовуючи дане рівняння можна знайти рішення завдання динамічногопрограмування.
Думаючиk=n-1 у рекуррентном співвідношенні (1.3), одержимо наступне функціональнерівняння:
F1(X(n-1)=max[Wn(X(n-1),un)+F0(X(n))] (1.4)
un
Уцьому рівнянні F0(X(n)) будемо вважати відомим.Використовуючи тепер рівняння (1.4) і розглядаючи всілякі припустимі із системиS на (n-1) – м кроці X1(n-1), X2(n-1),…,Xm(n-1),…, знаходимо умовні оптимальні рішення un0(x1(n-1)), un0(x2(n-1)),…, un0(xm(n-1)),…
івідповідні значення функції (1.4)
F10 (X1(n-1)), F10 (X2(n-1)), …, F10 (Xm(n-1)),…
Такимчином, на n-м кроці знаходимо умовно оптимальне керування при будь-якомуприпустимому стані системи S після (n-1) – го кроку. Тобто, у якому бистані система не виявилася після (n-1) – го кроку, буде відомо, яке вартоприйняти рішення на n-м кроці. Відомо також і відповідне значення функції(2.4). Розглянемо функціональне рівняння при k=n-2:
F2(X(n-1))=max[Wn-1(X(n-2),un-1)+F1(X(n-1))] (1.5)
Un-1
Длятого щоб знайти значення F2 для всіх припустимих значень X(n-2),необхідно знати Wn-1(X(n-2), un-1) і F1(X(n-1)).Що стосується значень F1(X(n-1)), те вони вже визначені. Томупотрібно зробити обчислення для Wn-1(X(n-2), un-1)при деякому відборі припустимих значень X(n-2) і відповіднихкерувань un-1. Ці обчислення дозволять визначити умовно оптимальнекерування u0n-1 для кожного X(n-2). Кожне з таких керувань разом ізуже обраним керуванням на останньому кроці забезпечує максимальне значеннядоходу на двох останніх кроках.
Послідовноздійснюючи описаний вище ітераційний процес, дійдемо до першого кроку. На цьомукроці відомо, у якому стані може перебувати система. Тому вже не потрібноробити припущень про припустимі стани системи, а залишається як тільки вибратикерування, що є найкращим з обліком умовно оптимальних керувань, уже прийнятихна всіх наступних кроках.
Такимчином, у результаті послідовного проходження всіх етапів від кінця до початкувизначається максимальне значення виграшу за n кроків і для кожного з нихзнаходимо умовно оптимальне керування.
Щобзнайти оптимальну стратегію керування, тобто визначити шукане рішення завдання,потрібно тепер пройти всю послідовність кроків, тільки цього разу від початкудо кінця. А саме: на першому кроці як оптимальне керування u1* візьмемознайдене умовно оптимальне керування u10. На другомукроці знайдемо стан X1*, у яке переводить систему керування u1*.Цей стан визначає знайдене умовно оптимальне u20, щотепер уважається оптимальним. Знаючи u2*, знаходимо X2*,а виходить, визначаємо u3* і т.д. У результаті цього найдеться рішеннязавдання, тобто максимально можливий доход й оптимальну стратегію керування U*,що включає оптимальні керування на окремих кроках: U*= (u1*, u2*,…,un*).
Отже,зі знаходження рішення завдання динамічного програмування видно, що цей процесє досить громіздким. Тому більше складні завдання вирішують за допомогою ЕОМ.
Динамічнезавдання по заміні встаткування можливо також вирішити й графічним методом. Наосі Х відкладають номер кроку (к). на осі В – вік устаткування (t). Крапка (до-1;t) на площині відповідає початку К-ого кроку по експлуатації встаткування увіці t років.
/>Будь-яка траєкторіяпереводящая крапку S (k-1; t) зі стану S0 S. Складається з відрізків, тобто ізкроків відповідним рокам експлуатації. Потрібно вибрати таку траєкторію приякій витрати на експлуатацію будуть мінімальні. Якщо відомі залежністьпродуктивності встановленого на підприємстві встаткування від часу йоговикористання R(t) і залежність витрат на ремонт устаткування при різному часійого використання S(t) і витрати пов'язані із придбанням нового обладнання, топоказником ефективності в цьому випадку є прибуток яка максимізується.
2.Застосування динамічного програмування в економічних дослідженнях
програмування економічний дослідженнядинамічний
Векономічних дослідженнях здавна застосовувалися найпростіші математичні методи.У господарському житті широко використаються геометричні формули. Так, площаділянки поля визначається шляхом перемножування довжини на ширину або обсяг силосноїтраншеї – перемножуванням довжини на середню ширину й глибину. Існує цілий рядформул і таблиць, що полегшують господарським працівникам визначення тих абоінших величин.
Застосуванняарифметики, алгебри в економічних дослідженнях, є вже питанням про культурудослідження, кожен поважаючий себе економіст володіє такими навичками. Особнякомтут стоять так звані методи оптимізації, частіше називаються якекономіко-математичні методи.
В60-і роки нашого сторіччя розгорнулася дискусія про математичні методи векономіці. Наприклад, академік Немчинов виділяв п'ять базових методівдослідження при плануванні:
1)балансовий метод;
2)метод математичного моделювання;
3)векторно-матричний метод;
4)метод економіко-математичних множників (оптимальних суспільних оцінок);
5)метод послідовного наближення.
У тойже час академік Канторович виділяв математичні методи в чотири групи:
– макроекономічнімоделі, куди відносив балансовий метод і моделі попиту;
– моделівзаємодії економічних підрозділів (на основі теорії ігор);
– лінійнемоделювання, включаючи ряд завдань, що небагато відрізняються від класичноголінійного програмування;
– моделіоптимізації, що виходять за межі лінійного моделювання (динамічне, нелінійне, цілеі стохастичне програмування).
І зтієї, і з іншою класифікацією можна сперечатися, оскільки, наприклад моделіпопиту можна по ряду особливостей віднести до нелінійного програмування, астохастичне моделювання йде коріннями в теорію ігор. Але все це проблеми класифікації,які мають певне методологічне значення, але в цьому випадку не настількиважливі.
Ізкрапки ж зору ролі математичних методів варто говорити лише про широтузастосування різних методів у реальних процесах планування.
Ізцього погляду безсумнівним лідером є метод лінійної оптимізації, що буврозроблений академіком Канторовичем в 30-і роки ХХ-го століття. Найчастіше завданнялінійного програмування застосовується при моделюванні організації виробництва.От як по Канторовичу виглядає математична модель організації виробництва:
Увиробництві беруть участь M різних виробничих факторів (інгредієнтів) – робочасила, сировина, матеріали, устаткування, кінцеві й проміжні продукти й ін. Виробництвовикористає S технологічних способів виробництва, причому для кожного з нихзадані обсяги вироблених інгредієнтів, розраховані на реалізацію цього способу зодиничною ефективністю, тобто заданий вектор ak = (a1k, a2k,…,amk), k = 1,2…, S, у якому кожна з компонентів aіk указуєобсяг виробництва, що відповідає (і-го) інгредієнта, якщо вона позитивна; іобсяг його витрати, якщо вона негативна (у способі k).
Вибірплану означає вказівка інтенсивності використання різних технологічнихспособів, тобто план визначається вектором x = (x1, x2,…, x) з невід’ємними компонентами.
Звичайнона кількості що випускають і затрачуваних інгредієнтів накладаються обмеження:зробити потрібно не менш, ніж потрібно, а затрачати не більше, ніж є. Такіобмеження записуються у вигляді
Sa ikxk > bi; i=1,2,…, m. (2.1)
Якщоі > 0, то нерівність означає, що з потреба в інгредієнті в розмірі й, якщо і
f(x) = S ckxk. (2.2)
Теперзагальне завдання лінійного програмування може бути представлена в математичнійформі.
Наоснові об'єктивно обумовлених оцінок американським математиком Дж. Данцигом– був розроблений симплекс-метод рішення завдань оптимального програмування.Цей метод досить широко застосовується. Алгоритм його досить детальнопророблений, і навіть розроблені прикладні пакети програм, які застосовуються вбагатьох галузях планування.
Методлінійної оптимізації з того моменту, як він був розроблений Канторовичем, незалишався без змін, він розвивався й продовжує розвиватися. Наприклад, формула(2.2) у сучасній інтерпретації виглядає в такий спосіб.
Saij xj
Аналогічной з ресурсами, в обмеженні беруть участь не всі ресурси відразу, а якась їхняпідмножина (і I І).
Введеннямпідмножин не обмежилося вдосконалювання методу лінійної оптимізації. Потребипрактики змусили розробити ще цілий ряд прийомів і методів для різних випадків описуреалій господарської практики у вигляді обмежень. Це такі прийоми, як записобмежень по використанню виробничих ресурсів, запис обмежень по гарантованомуобсязі робіт або виробництва продукції, прийоми моделювання при невідомихзначеннях показників і багато хто інші, на яких тут не варто зупинятися.
Ціль всіхцих прийомів – дати більше розгорнуту модель якого-небудь явища з господарськоїпрактики, заощадивши при цьому на кількості змінних й обмежень.
Незважаючина широту застосування методу лінійного програмування, він ураховує лише триособливості економічних завдань – велика кількість змінних, обмеженістьресурсів і необхідність цільової функції. Звичайно, багато завдань із іншимиособливостями можна звести до лінійної оптимізації, але це не дає нам прававипустити з уваги інший добре розроблений метод математичного моделювання – динамічнепрограмування. По суті, завдання динамічного програмування є описомбагатокрокових дій із прийняття рішень. Завдання динамічного програмуванняможна сформулювати в такий спосіб:
єдеяка кількість ресурсу х, яких можна використати N різними способами. Якщо позначитичерез хі кількість ресурсу, використовувана й-m способом, то кожному способу зіставляєтьсяфункція корисності (хі), що виражає доход від цього способу. Передбачається, щовсі доходи виміряються в однакових одиницях і загальному доході дорівнює сумідоходів, отриманих від використання кожного способу.
Теперможна поставити завдання в математичній формі. Знайти
max y1(x1)+ y2(x2)+ … + yn(xn) (2.4)
(загальнийдоход від використання ресурсів всіма способами) при умовах:
– виділюванікількості ресурсів ненегативні;
[1] x1> 0,…, x > 0
– загальнакількість ресурсів дорівнює x.
[2] x1+ x2 +… + x = x
Дляцього загального завдання можуть бути побудовані рекуррентные
співвідношення
¦1(x) = max {j1(x1)}, (2.5)
0
¦k(x) = max {jk(xk)+ ¦k-1(x – xk)}. (2.6)
к = 2,3,…, N,
задопомогою яких перебуває її рішення.
Привисновку цих рекурентних співвідношень, по суті, використався наступнийпринцип, оптимальна стратегія володіє тим властивістю, що стосовно будь-якогопервісного стану після деякого етапу рішення сукупність наступних рішень повиннастановити оптимальну стратегію. Цей принцип оптимальності лежить в основі всієїконцепції динамічного програмування. Саме завдяки йому вдається при наступнихпереходах випробовувати не всі можливі варіанти, а лише оптимальні виходи. Рекурентніспіввідношення дозволяють замінити надзвичайно трудомісткі обчислення максимумупо N змінним у вихідному завданні рішенням N завдань, у кожній з яких максимумперебуває лише по однієї змінній.
Такимчином, метод динамічного програмування дозволяє врахувати таку важливуособливість економічних завдань, як детермінованість більше пізніх рішень відбільше ранніх.
Крімцих двох, досить детально розроблених методів, в економічних дослідженнях останнімчасом стали застосовуватися безліч інших методів.
Однимз підходів до рішення економічних завдань є підхід, заснований на застосуваннінової математичної дисципліни – теорії ігор.
Сутьцієї теорії полягає в тім, що гравець (учасник економічних взаємовідношень)повинен вибрати оптимальну стратегію залежно від того, якими він представляєдії супротивників (конкурентів, факторів зовнішнього середовища й т.д.). У залежностівід того, наскільки гравець обізнаний про можливі дії супротивників, гри (а підгрою тут розуміється сукупність правил, тоді сам процес гри це партія) бувають відкритій закриті. При відкритій грі оптимальною стратегією буде вибір максимальногомінімуму виграшу (у термінах Моргерштерна – «максі-міна») із всієї сукупностірішень, представлених у матричній формі. Відповідно супротивник буде прагнепрограти лише мінімальний максимум («міні – макс») який у випадку ігор з нульовоюсумою буде дорівнює «максі-міну». В економіці ж частіше зустрічаються ігри зненульовою сумою, коли виграють обоє гравця.
Крімцього в реальному житті число гравців рідко буває дорівнює всього двом. Прибільшому ж числі гравців з'являються можливості для кооперативної гри, колигравці до початку гри можуть утворювати коаліції й відповідно впливати на хідгри.
Стратегіїгравців не обов'язково повинні містити одне рішення, може бути так, що для досягненнямаксимального виграшу буде потрібно застосовувати змішану стратегію (коли дві абокілька стратегій застосовуються з якоюсь імовірністю). Крім того в закритихіграх теж потрібно враховувати ймовірність того або іншого рішеннясупротивника. Таким чином, у теорії ігор стало із апарата теорії імовірності,що згодом знайшов своє застосування в економічних дослідженнях у виглядіокремого методу – стохастичного моделювання.
Змістметоду стохастичного програмування складається у введенні в матрицю завданняабо в цільову функцію елементів теорії імовірності. У цьому випадку звичайнобереться просто середнє значення випадкової величини, узяте щодо всіх можливихстанів.
У випадкуне твердої, або двохєтапне зі стохастичного моделювання появляється можливість коректуванняотриманого плану після того, як стане відомим стан випадкової величини.
Крімцих методів застосовуються методи нелінійного, цілочисельного програмування йбагато хто інших. Коротенько, сутність методу нелінійного програмування є взнаходженні або сідлової точки, або загального максимуму або мінімуму функції.Основна складність тут у труднощі визначення, чи є цей максимум загальним або локальним.Для цілочисельного моделювання основні труднощі саме й полягає в труднощіпідбора цілого значення функції. Загальним для застосуванням цих методів на сучасномуетапі є можливість часткової відомості їх до завдання лінійного моделювання.Можливо, у недалекому майбутньому буде знайдене якесь оригінальне рішення такихзавдань специфічними методами, більше зручними, чим сучасні методи рішенняподібних завдань (для яких вони є), і більше точні, ніж наближені рішенняметодами лінійного програмування.
3.Задача заміниобладнання
3.1Алгоритм рішення задачі заміни обладнання
Уцьому завданні як система S виступає встаткування. Стан цієї системивизначаються фактичним часом використання встаткування (його віком) t, тобто описуютьсяєдиним параметром t.
Як керуваннявиступають рішення про заміну й збереження встаткування, прийняті на початкукожного року. Позначимо через Xc рішення про збереження встаткування, а черезXз – рішення про заміну встаткування. Тоді завдання полягає в знаходженні такоїстратегії керування, обумовленої рішеннями, прийнятими на початок кожного року,при якій загальний прибуток підприємства за вісім років є максимальною.
Процесрішення завдання здійснюється в такий спосіб. Береться період в N років. Доцього часу встаткування відробило якусь кількість років і прийшло t0 віку.
Рішеннязавдання починається з останнього N-го року, складається пара функціональнихрівнянь у припущенні, що прийшло старе встаткування без заміни:
1) розраховуєтьсядоход від експлуатації встаткування при заміні;
2) розраховуєтьсядоход від експлуатації встаткування протягом року за умови його старіння.
Другагіпотеза: до N-ому року встаткування могло прийти заміненим у якомусь році,тоді складається пара рівнянь, у яких визначається доход за рік відексплуатації одиниці встаткування за умови заміни або збереження встаткування.
Крокдругої: розглядаємо (N-1) рік.
Розглядаютьсядві гіпотези:
– прийшлостаре встаткування без заміни;
– прийшловстаткування, що було замінено.
Кроктретій: розглядається (N-2) рік при двох гіпотезах, складаються рівняння,розраховується доход.
Рішеннятриває по всіх кроках. На першому році буде одна гіпотеза, що прийшло старевстаткування, використовуване t0 років.
Підкритерієм оптимальності може бути прийнятий будь-який економічний показник,якщо він добре підготовлений, тобто він повинен бути відчищений від факторів,що не залежать від роботи устаткування.
r(t) –вартість продукції, створеною одиницею устаткування віку t років за рік.
U(t) –витрати на протягом року одиниці встаткування віку t років.
С(t) –витрати на заміну одиниці устаткування віку t років (витрати на придбання,налагодження за винятком залишкової вартості старого встаткування).
і – рікустановки нового обладнання.
Доходзаміни встаткування розраховується:
f' = r(t) –U(t) – C(t) (3.1)
Доходвід збереження встаткування:
f'' =r(t) – U(t) (3.2)
Якщоf' > f'', то встаткування необхідно замінити, якщо f' ? f'' – залишити.
Крок1-й: N-й рік.
Гіпотеза1: прийшло старе встаткування віку N+t0 років.
Тодідоход за N-й рік за умови заміни або збереження встаткування:
/> (3.3)
Гіпотеза2: прийшло нове обладнання.
/> (3.4)
ВізьмемоN-t-й рік:
/> (3.5)
Крок2-й: (N-1) – й рік.
Розраховуєтьсясумарний умовний доход, за умови заміни або збереження.
Гіпотеза1: прийшло старе устаткування.
/> (3.6)
Гіпотеза2: прийшло нове устаткування.
/> (3.7)
3.2Контрольний приклад
Дляконтрольного прикладу необхідно сформулювати дані про показники, які буде матистаре та нове обладнання на протязі певного періоду часу, в нашому випадку 5років. Тобто, треба визначити, вартість продукції, виробленою одиницеюобладнання за рік – r(t), витрати на експлуатацію обладнання протягом року – U(t),витрати на заміну одиниці устаткування – С(t) (див. Додаток А).
Задачубудемо розглядати в п’ять етапів. Тобто в кожному році ми будемо шукатинайоптимальніші варіанти заміни обладнання.
Напершому етапі ми розраховуємо за п’ять років максимальний прибуток, тобто за t=12,1,2,3,4.
Розраховуєтьсяза допомогою формул (3.3) та (3.4) відповідно до старого та нового обладнання.По розрахунках робимо висновок заміняти чи зберегти обладнання. На цьому етапіми робимо висновок зберегти обладнання. (див. Додаток Б)
Надругому етапі ми розраховуємо ефективність, коли t=11,1,2,3, для цього використовуємоформули(3.6) (3.7), також відповідно для нового та старого обладнання. Вирішуємо, щоt=11 потрібнозамінити, а інші залишити (див. Додаток В).
Натретьому, четвертому та п’ятому етапі також використовуємо формули (3.6) та(3.7), відповідно до старого та нового обладнання, та робимо висновки, щодозаміни обладнання (див. Додаток Г, Д, Є).
Післярозрахунку максимальних прибутків на кожному з етапів ми отримуємо:
– в1 році зберегти обладнання, при цьому дохід складе (300–263)=37 тис. грн.;
– на2 рік, зберегти при доході (263–172)=91 тис. грн.;
– на3 році – змінити, при збитку (172–201)=55 тис. грн.;
– на4 рік – зберегти, при доході (201–97)=104 тис. грн.,
– на5 році – зберегти, при доході 97 тис. грн.
Такаполітика являється оптимальною. Вона забезпечує максимальний прибуток 300 тис. грн.
Висновки
Динамічнепрограмування – це область математичного програмування, що включає сукупністьприйомів і засобів для знаходження оптимального рішення, а також оптимізаціїкожного кроку в системі й виробленні стратегії керування, тобто процескерування можна представити як багатокроковий процес. Динамічне програмування,використовуючи поетапне планування, дозволяє не тільки спростити рішеннязавдання, але й вирішити ті з них, до яких не можна застосувати методиматематичного аналізу. Спрощення рішення досягається за рахунок значногозменшення кількості досліджуваних варіантів, тому що замість того, щоб один развирішувати складне різноманітне завдання, метод поетапного планування припускаєбагаторазове рішення щодо простих завдань. Плануючи поетапний процес, виходятьіз інтересів усього процесу в цілому, тобто при ухваленні рішення на окремомуетапі завжди необхідно мати у виді кінцеву мету.
Однакдинамічне програмування має й свої недоліки. На відміну від лінійногопрограмування, у якому симплексний метод є універсальним, у динамічномупрограмуванні такого методу не існує. Кожне завдання має свої труднощі, і вкожному випадку необхідно знайти найбільш підходящу методику рішення. Недолікдинамічного програмування полягає також у трудомісткості рішення багатомірнихзавдань. Завдання динамічного програмування повинна задовольняти дві умови.Першу умову звичайно називають умовою відсутності післядії, а друге – умовоюадитивності цільової функції завдання.
Напрактиці зустрічаються такі завдання планування, у яких помітну роль граютьвипадкових факторів, що впливають як на стан системи, так і на виграш. Існуєрізниця між детермінованою й стохастичним завданнями динамічного програмування.У детермінованому завданні оптимальне керування є єдиним і вказуєтьсязаздалегідь як тверда програма дій. У стохастичним завданню оптимальнекерування є випадковим і вибирається в ході самого процесу залежно від випадковосформованої ситуації. У детермінованій схемі, проходячи процес по етапах відкінця до початку, теж перебуває на кожному етапі цілий ряд умовних оптимальнихкерувань, але із всіх цих керувань, в остаточному підсумку здійснювалося тількиодне. У стохастичній схемі це не так. Кожне з умовних оптимальних керувань можевиявитися фактично здійсненим, якщо попередній хід випадкового процесу приведесистему у відповідний стан.
Принципоптимальності є основою поетапного рішення завдань динамічного програмування.Типовими представниками економічних завдань динамічного програмування є такназивані завдання виробництва й зберігання, завдання розподілукапіталовкладень, завдання календарного виробничого планування й інших.Завдання динамічного програмування застосовуються в плануванні діяльностіпідприємства з урахуванням зміни потреби в продукції в часі. В оптимальномурозподілі ресурсів між підприємствами в напрямку або в часі.
Описхарактеристик динамічного програмування й типів завдань, які можуть бутисформульовані в його рамках, по необхідності повинне бути дуже загальним і трохиневизначеним, тому що існує неозора безліч різних завдань, що укладаються всхему динамічного програмування. Тільки вивчення великої кількості прикладівдає виразне розуміння структури динамічного програмування.
Перелікпосилань
1. Акулич И.Л. Математичнепрограмування в прикладах і завданнях. – М.: Вища школа, 1993.
2. Дудорин В.И. Моделюванняв завданнях керування виробництвом.-М.: Статистика, 1980.
3. Дослідження операцій векономіці: навчальний посібник для вузів / під ред. Кремера Н.Ш. – М.:Банки й Біржі, ЮНИТИ, 1997.
4.www.dis.ru/manag/arhiv/2002/
5.www.math.mrsu.ru/programs/ivt/e-learn/7.html#zachin
ДодатокА
/>
ДодатокБ
/>
ДодатокВ
/>
ДодатокГ
/>
ДодатокД
/>