>КУРСОВАРОБОТА

На тему

«>Моделюванняоптимальноїстратегіїзаміниобладнання задопомогоюдинамічногопрограмування»

>Суми – 2006

>Вступ

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

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

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

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

>Метоюданоїкурсової роботиєзнаходження оптимального планузаміниобладнання длямаксимізаціїприбутковостідіяльності підприємства.

>Об’єктомкурсової роботивиступаєбудь-якепідприємство якумаєустаткування таобладнання, щовикористовує длявиготовленняпродукції.

Предметомкурсової роботиявляєтьсяметодидинамічногопрограмування.

1.Теоретичнівідомостіщододинамічногопрограмування

>Більшістьметодівдослідженняопераційзв'язано впершучергу ззавданнямицілкомпевногозмісту.Класичнийапарат математикивиявивсямалопридатним длярішеннябагатьохзавданьоптимізації, щовключаютьвелике числозміннихй/абообмежень увиглядінерівностей.Безсумнівнапривабливість ідеїрозбивки заподіяннявеликоїрозмірності напідзадачіменшоїрозмірності, щовключаютьусього подекількохзмінних, йнаступногорішеннязагального заподіяннявроздріб.Саме націй ідеїзаснований методдинамічногопрограмування.

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

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

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

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

>Нехайпередбачається доздійсненнядеякийзахід чисеріязаходів («>операція»), щопереслідуєпевну мітку.Запитується: якпотрібноорганізувати (>спланувати)операцію у тому,щоб вон бувнайбільшефективною? А,щобпоставлене заподіянняпридбалокількісний,математичний характер,необхідно вводити нарозгляддеякий численнийкритерій W,яким ми будемохарактеризуватиякість,успішність,ефективністьоперації.Критерійефективності вкожному конкретномувипадкивибираєтьсявиходячи зцільовоїспрямованостіоперації і заподіяннядослідження (>якийелементкеруванняоптимізується і для чого).

>Сформулюємозагальний принцип, щолежить восновірішення всіхзавданьдинамічногопрограмування («принципоптимальності»):

«>Який бі не був стансистеми P.S передчерговимкроком,требавибратикерування на цьомукроці так,щобвиграш наданомукроці плюсоптимальнийвиграш на всіхнаступнихкроках бувмаксимальним».

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

Припостановцізавданьдинамічногопрограмування вартокеруватисянаступними засідками:

–вибратипараметри (>фазовікоординати), щохарактеризують стан P.Sкерованоїсистеми передкожнимкроком;

–розчленуватиоперацію наетапи (>кроки);

–з'ясуватинабіркроковихкерувань x_й для шкірногокроку іобмеження, щонакладають ними;

–визначитиякийвиграш приносити наі-омкроцікерування x_й,якщо передцим система могла P.S,тобтозаписати «>функціювиграшу»;

–визначити, якзмінюється стан P.Sсистеми P.S подвпливомкерування x_й наі-омкроці: воно та переходити уновий стан;

–записатиосновнерекурентнерівняннядинамічногопрограмування, щовиражаєумовнийоптимальнийвиграш W_й(P.S) (>починаючи ізі-гокроку і докінця) черезвідомуфункцію W_й+1 (P.S).

>Цьомувиграшувідповідаєумовнеоптимальнекерування наі-мкроціxі(S) (>причому у ужевідомуфункцію W_й+1 (P.S)требазамість P.Sпідставитизмінений стан).

–зробитиумовнуоптимізаціюостаннього (>m-го)кроку,задаючисьгамоюстанів P.S, із яких, можна закрокдійти докінцевого стану,обчислюючи для шкірного із нихумовнийоптимальнийвиграш поформулі.

–зробитиумовнуоптимізацію (>m-1) – го, (>m-2) – го і т.д.кроків поформулі,думаючи внійй=(m-1), (>m-2),…, й для шкірного зкроківуказатиумовнеоптимальнекерування x_й(P.S), приякому максимумдосягається.

>Помітимо, щоякщо стансистеми впочатковий моментвідомо (ацезвичайнобуває так), тобі й маєшпершомукроціваріювати стансистеми непотрібно – прямознаходимооптимальнийвиграш дляданогопочаткового стану P.S₀. Це йєоптимальнийвиграш заоперацію.

–зробитибезумовнуоптимізаціюкерування, «>читаючи»відповіднірекомендації накожномукроці.Взятизнайденеоптимальнекерування напершомукроці;змінити стансистеми поформулі; длязновузнайденого станузнайтиоптимальнекерування на іншомукроці x₂* й т.д. докінця.

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

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

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

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

Однакдинамічнепрограмуваннямає і своїнедоліки. Навідміну відлінійногопрограмування, уякомусимплексний методєуніверсальним, удинамічномупрограмуванні такого методу неіснує.Кожне заподіяннямає своїтруднощі, й вкожномувипадкунеобхіднознайтинайбільшпідходящу методикурішення.Недолікдинамічногопрограмуванняполягаєтакож утрудомісткостірішеннябагатомірнихзавдань. Придуже великомучислізміннихрішення заподіяннянавіть насучаснихЕОМобмежуєтьсяпам'яттю ішвидкодієюмашини.Наприклад,якщо длядослідження шкірногозмінногоодномірного заподіянняпотрібно 10кроків, те вдвовимірномузавданніїхнякількістьзбільшується до 100, утривимірної – до 1000 й т.д.

>Припустимо,якась система P.Sперебуває вдеякомупочатковомустані P.S₀ ієкерованою. Таким чином,завдякиздійсненнюдеякогокерування Uзазначена система переходити зпочаткового стану P.S₀ укінцевий стан P.S_до. При цьомуякість шкірного ізреалізованихкерувань Uхарактеризуєтьсявідповіднимзначеннямфункції W^(U).Завданняполягає втім,щоб ізбезлічіможливихкерувань Uзнайтитаке U*, приякомуфункція W^(U)приймаєекстремальне (>максимальне чимінімальне)значення W^(U*).

>Завданнядинамічногопрограмуваннямаютьгеометричнуінтерпретацію. Станфізичноїсистеми P.S можнаописатичисловими параметрами,наприкладвитратоюпального ішвидкістю,кількістю вложеннихкоштів й т.д.Назвемоціпараметри координатамисистеми; тоді стансистеми можназобразитикрапкою P.S, аперехід із одного стануS1 віншеS2 –траєкторієюкрапки P.S.Керування Uозначаєвибірпевноїтраєкторіїпереміщеннякрапки P.S ізS1 вS2,тобтовстановленняпевного закону рухукрапки P.S.

>Сукупністьстанів, у котріможепереходити система,називаєтьсяобластюможливихстанів.Залежно від числапараметрів, щохарактеризують стансистеми, областьможливихстанівсистемиможе бутирізної.Нехай,наприклад, стансистеми P.Sхарактеризується одним параметром, –координатою x. У цьомувипадку змінукоординати,якщо нанеїнакладенідеякіобмеження,зобразитьсяпереміщеннямкрапки P.S поосі Про_x чи поїїділянці. Отже,областюможливихстанівсистемиєсукупністьзначень x, акеруванням – закон рухукрапки P.S ізпочаткового стануS0 укінцеве P.S_>k поосіO_x чиїїчастини (рис. 1.1).

P.S₀ P.S P.S_>k

0 x

Областьможливихстанівсистеми

Малюнок 1.1.Графічнезображення переходусистеми P.S

Таким чином,завданнюдинамічногопрограмування можнадатинаступнугеометричнуінтерпретацію. З всіхтраєкторій, що належатиобластіможливихстанівсистеми із'єднуючих областей P.S₀ і P.S_>k,необхідновибратитаку, наякійкритерій Wприймаєоптимальнезначення.

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

>Будемовважати, що станрозглянутоїсистеми P.S наK-мкроці (>k=1, n)визначаєтьсясукупністю чисел X^(>k) =(x₁^(>k), x₂^(>k),…, x_n^(>k)), котріотримані врезультатіреалізаціїкеруванняuk, щозабезпечилоперехідсистеми P.Sзі стану X^(>k-1) у стан X^(>k). При цьому будемоприпускати, що стан X^(>k), у якуперейшла система P.S,залежить відданого стану X^(>k-1) йобраногокерування u_>k й не проти того,яким чином система P.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*), урезультатіреалізації які система P.S за nкроків переходити зпочаткового стану X⁽⁰⁾ укінцеве X^(>k) й при цьомуфункція (1.1)приймаєнайбільшезначення.

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

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

>Щобце можна було бздійснити практично,необхіднодатиматематичнеформулювання принципуоптимальності. Для цоговведемодеякідодатковіпозначення.Позначимо через F_n(X⁰)максимальний дохід,одержуваний за nкроків припереходісистеми P.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) йрозглядаючивсілякіприпустимі зсистеми P.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-оюкроцізнаходимоумовнооптимальнекерування прибудь-якомуприпустимомустанісистеми P.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 років.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P.S a _>ikx_>k > b_і;i=1,2,…,m. (2.1)

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

>f(x) = P.S з_>kx_>k. (2.2)

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

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

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

P.S a_>ij x_j < b_і (і I) (2.3)

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

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

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

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

>єдеякакількість ресурсу x, яких, можнавикористати Nрізними способами.Якщопозначити черезхікількість ресурсу,використовуванай-m способом, токожному способузіставляєтьсяфункціякорисності (>хі), щовиражає дохід від цого способу.Передбачається, що усідоходивиміряються воднаковиходиницях йзагальномудоходідорівнюєсумідоходів,отриманих відвикористання шкірного способу.

>Тепер можнапоставити заподіяння вматематичнійформі.Знайти

>max y₁(x₁)+ y₂(x₂)+ … + y_n(x_n) (2.4)

(>загальний дохід відвикористанняресурсів всіма способами) приумовах:

–виділюванікількостіресурсівненегативні;

[1]x1 > 0,…, x > 0

–загальнакількістьресурсівдорівнює x.

[2]x1 +x2 +… + x = x

Для цогозагального заподіянняможуть бутипобудованірекуррентние

>співвідношення

¦₁(x) =max {j₁(x₁)}, (2.5)

0 <=X₁<= X

¦_>k(x) =max {j_>k(x_>k)+ ¦_>k-1(x – x_>k)}. (2.6)

до = 2,3,…, N,

задопомогою якіперебуваєїїрішення.

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

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

>Крімцих двох,досить детальнорозробленихметодів, векономічнихдослідженняхостаннім годиною стализастосовуватисябезлічіншихметодів.

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

Сутьцієїтеоріїполягає втім, щогравець (>учасникекономічнихвзаємовідношень) виненвибратиоптимальнустратегіюзалежно від того,якимивінпредставляє діїсупротивників (>конкурентів,факторівзовнішньогосередовища і т.д.). Узалежності від того,наскількигравецьобізнаний проможливі діїсупротивників,гри (а подгрою тутрозумієтьсясукупність правил, тоді сам процесгрицепартія)буваютьвідкриті ізакриті. Привідкритій груоптимальноюстратегією якщовибір максимальногомінімумувиграшу (утермінахМоргерштерна – «>максі-міна») звсієїсукупностірішень,представлених уматричнійформі.Відповідносупротивник якщопрагнепрогратилишемінімальний максимум («>міні –макс»)який увипадкуігор ізнульовоюсумою якщодорівнює «>максі-міну». Уекономіці жчастішезустрічаютьсяігри ізненульовоюсумою, коливиграютьобоєгравця.

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

>Стратегіїгравців необов'язковоповинніміститиоднерішення,може бути так, що длядосягнення максимальноговиграшу якщопотрібнозастосовуватизмішанустратегію (колидві чикількастратегійзастосовуються ізякоюсьімовірністю).Крім цього узакритихіграхтежпотрібновраховуватиймовірність того чиіншогорішеннясупротивника. Таким чином, утеоріїігор стало запарататеоріїімовірності, щозгодомзнайшовсвоєзастосування векономічнихдослідженнях увиглядіокремого методу –стохастичногомоделювання.

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

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

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

3. Завданнязаміниобладнання

3.1 Алгоритмрішеннязадачізаміниобладнання

У цьомузавданні як система P.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),відповідно до старого та новогообладнання, таробимовисновки,щодозаміниобладнання (див.Додаток Р, Д,Є).

>Післярозрахункумаксимальнихприбутків накожному ізетапів миотримуємо:

– одинроцізберегтиобладнання, при цьомудохід складі (300–263)=37 тис. грн.;

– на 2рік,зберегти придоході (263–172)=91 тис. грн.;

– на 3році –змінити, призбитку (172–201)=55 тис. грн.;

– на виборах 4рік –зберегти, придоході (201–97)=104 тис. грн.,

– п'ятьроці –зберегти, придоході 97 тис. грн.

>Така політикаявляєтьсяоптимальною.Воназабезпечуємаксимальнийприбуток 300 тис. грн.

>Висновки

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

Однакдинамічнепрограмуваннямає і своїнедоліки. Навідміну відлінійногопрограмування, уякомусимплексний методєуніверсальним, удинамічномупрограмуванні такого методу