Реферати українською » Экономико-математическое моделирование » Моделювання оптімальної стратегії заміні обладнання за допомог дінамічного програмування


Реферат Моделювання оптімальної стратегії заміні обладнання за допомог дінамічного програмування

Страница 1 из 2 | Следующая страница

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

На тему

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

>Суми – 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.S0. Це йєоптимальнийвиграш заоперацію.

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

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

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

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

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

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

>Припустимо,якась система P.Sперебуває вдеякомупочатковомустані P.S0 ієкерованою. Таким чином,завдякиздійсненнюдеякогокерування Uзазначена система переходити зпочаткового стану P.S0 укінцевий стан 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 поосіOx чиїїчастини (рис. 1.1).

P.S0 P.S P.S>k


0 x

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

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

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

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

>Будемовважати, що станрозглянутоїсистеми P.S наK-мкроці (>k=1, n)визначаєтьсясукупністю чисел X(>k) =(x1(>k), x2(>k),…, xn(>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*=(u1*, u2*,…, un*), урезультатіреалізації які система P.S за nкроків переходити зпочаткового стану X(0) укінцеве X(>k) й при цьомуфункція (1.1)приймаєнайбільшезначення.

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

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

>Щобце можна було бздійснити практично,необхіднодатиматематичнеформулювання принципуоптимальності. Для цоговведемодеякідодатковіпозначення.Позначимо через Fn(X0)максимальний дохід,одержуваний за nкроків припереходісистеми P.S ізпочаткового стану X(0) укінцевий стан X(>k) приреалізаціїоптимальноїстратегіїкеруванняU=(u1, u2,…, un), а ще через F>n-k(X(>k)) –максимальний дохід,одержуваний припереході ізбудь-якого стануX(k) укінцевий стан X(n) приоптимальнійстратегіїкерування на щозалишилисяn-kкроках.Тоді:

Fn(X0)=>max[W1(X(0), u1)+ … + Wn(X(n-1), un)] (1.2)

U>k+j

Fn->k(X(>k))=>max[W>k+1(X(>k), u>k+1)+Fn->k-1(X>k+1))] (>k=0,n-1) (1.3)

U>k+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) йрозглядаючивсілякіприпустимі зсистеми P.S на (>n-1) – мкроці X1(>n-1), X2(>n-1),…, X>m(>n-1),…,знаходимоумовніоптимальнірішення un0(x1(n-1)), un0(x2(n-1)),…, un0(x>m(n-1)),…

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

F10 (X1(n-1)), F10 (X2(n-1)), …, F10 (X>m(n-1)),…

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

F2(X(>n-1))=>max[W>n-1(X(>n-2), u>n-1)+F1(X(>n-1))] (1.5)

Un-1

Ащобзнайтизначення F2 для всіхприпустимихзначень X(>n-2), >необхідно знаті W>n-1(X(>n-2), u>n-1) й F1(X(>n-1)). Колистосуєтьсязначень F1(X(>n-1)), ті смердоті ужевизначені. Томупотрібнозробитиобчислення для W>n-1(X(>n-2), u>n-1) придеякомувідборіприпустимихзначень X(>n-2) йвідповіднихкерувань u>n-1.Ціобчислення дозволятивизначитиумовнооптимальнекеруванняu0n-1 для шкірного X(>n-2).Кожне із такихкерувань разом з вжеобранимкеруванням наостанньомукроцізабезпечуємаксимальнезначення прибутку на двохостанніхкроках.

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

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

>Щобзнайтиоптимальнустратегіюкерування,тобтовизначитишуканерішення заподіяння,потрібнотепер пройти всюпослідовністькроків, лише цого разу від початку докінця. Асаме: напершомукроці якоптимальнекерування u1*візьмемознайденеумовнооптимальнекерування u10. На іншомукроцізнайдемо стан X1*, у яку переводити системукерування u1*.Цей станвизначаєзнайденеумовнооптимальне u20, щотеперуважаєтьсяоптимальним.Знаючи u2*,знаходимо X2*, авиходить,визначаємо u3* й т.д. Урезультаті цогонайдетьсярішення заподіяння,тобто максимальноможливий дохід іоптимальнустратегіюкерування U*, щовключаєоптимальнікерування на окремихкроках: U*= (u1*, u2*,…, un*).

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

>Динамічне заподіяння позамінівстаткуванняможливотакожвирішити іграфічним методом. Наосі Хвідкладають номеркроку (до). наосі У –вікустаткування (>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 xj < bі (і I) (2.3)

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

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

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

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

>єдеякакількість ресурсу x, яких, можнавикористати 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 <=X1<= 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 тис. грн.


>Висновки

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

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

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація