>КУРСОВАРОБОТА
На тему
«>Моделюванняоптимальноїстратегіїзаміниобладнання задопомогоюдинамічногопрограмування»
>Суми – 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 тис. грн.
>Висновки
>Динамічнепрограмування –це областьматематичногопрограмування, щовключаєсукупністьприйомів йзасобів длязнаходження оптимальногорішення, атакожоптимізації шкірногокроку всистемі івиробленністратегіїкерування,тобто процескерування можнапредставити якбагатокроковий процес.Динамічнепрограмування,використовуючипоетапнепланування,дозволяє не лишеспроститирішення заподіяння, але й івирішити тих із них, до яких, можназастосуватиметодиматематичногоаналізу.Спрощеннярішеннядосягається зарахунокзначногозменшеннякількостідосліджуванихваріантів, бозамість того,щоб одного разувирішуватискладнерізноманітне заподіяння, методпоетапногоплануванняприпускаєбагаторазоверішеннящодопростихзавдань.Плануючипоетапний процес,виходять зінтересівусьогопроцесу вцілому,тобто приухваленнірішення наокремомуетапізавждинеобхідно матір увидікінцеву мітку.
Однакдинамічнепрограмуваннямає і своїнедоліки. Навідміну відлінійногопрограмування, уякомусимплексний методєуніверсальним, удинамічномупрограмуванні такого методу