Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Знаходження най коротшої відстані між двома вузлами на мережі доріг
Це одна з перших транспортних задач, що були вирішені методи ДП[12]. Нехай відома мережа автомобільних доріг, яка з'єднує пункти А і Б. Ця мережа складається із сукупності вузлів і з'єднуючих їх доріг. Поставимо задачу пошуку найкоротшого шляху між пунктами А і Б (див. рис.7.1).
Рис.7.1 До визначення найкоротшого шляху
Рухаючись від останнього кроку до першого (від Б до А), знайдемо умовно оптимальне рішення на кожному кроці. VІ-й крок. На цьому кроці є одна умовна крапка. Припустимо, що ми вже потрапили в цю крапку (незалежно як) і будемо намагатися потрапити в кінцеву крапку Б. Є тільки один шлях, тому це і буде найкоротша відстань =12 (оцінку цієї вузлової крапки змінимо 12). V - крок. На цьому кроці маємо 3 крапки. Якщо ми потрапимо (незалежно як) у верхню крапку, то найкоротша відстань до Б буде дорівнює 13,для другої крапки 10, для третьої - 9, покажемо стрілками напрямок руху в крапку В. IV - крок. На цьому кроці маємо дві крапки. З верхньої країн виходить три напрямки. Необхідно вибрати оптимальний напрямок. Якщо рухатися в напрямку крапки 13, то відстань до крапки Б, буде 6+(13)=19. Якщо рухатися в напрямку крапки з оцінкою (10), то відстань до неї буде дорівнює 5 + (10) = 15; а якщо в напрямку крапки з оцінкою (9), 8+(9)=17 нас цікавить напрямок, який дасть мінімальну оцінку, тому змінимо оцінку цієї крапки, рівної мінімальній з перелічених (15). Аналогічно знаходимо оцінку для другої крапки кроку IV 6+(10)=16; 2+(9)=11; 7+(12)=13. Мінімальне значення в напрямку крапки (9) далі буде дорівнює (11). Оптимальні значення позначимо стрілками. III-крок. На цьому кроці одна вузлова крапка з якої виходить три напрямки 3+(13)=16; 4+(10)=14; 11+(9)=20. Мінімальну оцінку (14) одержимо рухаючи у вузлову крапку з оцінкою (10). II – крок. На цьому кроці 3 вузлові крапки: Для другої: 5+(14)=19; 9+(15)=24; 10+(П)=21. мінімальна оцінка (19) у напрямку крапки з оцінкою (14; Для третьої: 4+(15)=19; 5+(11)=16. Умовно - оптимальної є оцінка (13) і умовно - оптимальним управлінням - рух у кутову крапку з оцінкою (11). І – крок містить 4 можливі напрямки: 3+(21)=24; 6+(14)=20; 4+(19)=23; 8+(16)=24. Мінімальна сума (20) у напрямку крапки з оцінкою (14). Таким чином, оцінка (20) для початкової крапки є найкоротшою відстанню між А і Б. Для вибору оптимального управління (вибору найкоротшого напрямку руху) необхідно знайти такий шлях від А до Б, на якому не перериваються стрілки. Таким шляхом буде
А→(14) →(10) →В.
Варто мати на увазі, що потрапивши в будь-яку крапку, ми завжди знайдемо найкоротший маршрут у Б. Наприклад, із крапки (16) таким маршрутом буде: (16) → (11) → (9) → Б, з відстанню, яка дорівнює 11 + 15=26. Відзначимо, що цей алгоритм обчислення найкоротшої відстані зветься алгоритмом дослідження всіх можливих шляхів або алгоритмом Кука і Холсея (по імені його авторів).
Задачі розподілу ресурсів При рішенні подібних задач широко використається ДП. Словесно ми вже описали алгоритм рішення. Спробуємо формалізувати і вирішити вказану задачу, спираючись на алгоритм ДП [12]. Припустимо, що на розвиток АТП відпущена певна сума коштів К, яку необхідно розподілити між двома АТП. Ефективність вкладення коштів у перше підприємство оцінюється коефіцієнтом річного прибутку α, у друге - β, причому α < 1 і β<1 і дорівнюють відповідно α=0,4 β =0,5. Наприкінці кожного року відбувається зменшення первісної суми законом φ((х)=γх; φ(у)=θу, γ=0,8; θ=0,75 (х - сума капіталовкладень у перше підприємство, у - в друге). Суми, що залишилися, наприкінці кожного року заново перерозподіляються. Обумовимо також, що сума, що залишилася наприкінці кожного року до прибутку не додається. Необхідно знайти такий розподіл капіталовкладень в перше та в друге підприємство, при якому досягається максимальна сума прибутку за всі 5 років. Неважко уявити, що поставлена задача є класичною задача оптимізації багатокрокових процесів, саме яку доцільно вирішувати застосуванням ДП. Рішення
Представимо функціональну модель задачі у наступному вигляді (рис.7.2).
Рис.7.2 Функціональна модель задачі ДП Вузловими крапками моделі є крапки розподілу суми коштів Kі між підприємствами. Практично це початок кожного календарного року. Таких кроків буде 5. Далі для спрощення виразимо уі через хі тобто уі = кі — хі. Записуємо функцію переходу ψі виграш z і для кожного з етапі починаючи, як це витікає з методу ДП, з п'ятого (останнього) етапу.
Етап 5 З огляду на те, що у5=к5-х5 і враховуючи а=0,4 β=0,5 γ=0,8 θ=0,75 запишемо рівняння переходу:
ψ5=γх5+ θу5=(γ-θ)х5+θК5=0,05х5+0,75К5
За умовою цей залишок у прибуток не включається. Величина отриманого прибутку протягом цього року:
z5=αx5+βy5=(α-β)x5+βx5=-0,1x5+0,5y5.
Шукаємо максимум цього прибутку: Z5 =max [-0,1х5+0,5у5]=0,5К5, якщо х5=0, у5=К5. Етап 4. Робимо аналогічні дії:
ψ4=γх4+θу4=(γ-θ)х4+θК4=0,05х4+0,75К4=К5,
оскільки це те, що залишилося після 4го року). z4=αx4+βy4=z5max=(α-β)x4+βK4+z5max,
тому що прибуток за четвертий рік додається до прибутку 5-го року. Враховуючи, що z5max=0,5K5:
Z4=max (-0,1x4+0,5K4+0,5K5).
Підставимо значення К5 і отримаємо для сумарного прибутку за 4-й і 5-й роки:
Z4=max [-0,1х4+0,5К4+0,5(0,05х5 +0,75К4)] (при 0<х4<К4)→ Z4=max [0,875К4 - 0,095х4] → Z4max=0,875К4,
якщо х4=0 і у4-К4
Етап 3. ψ3=К4=0,05х3+0,75К3 z3=(α -β)х3+βу3+z4тах. З урахуванням, що z4max=0!87 5 К4 одержимо:
Z3=(-0,1x3+0,5K3+0,875K4). Враховуючи К4=0,05х3+0,75К3, одержимо: Z3=(1,1K3+ 0,02х3) ( при 0<х3<К3) → Z3max,=1,12K3,
якщо х3=К3 (максимально можливе значення) y3=0/ Етап 2. Робимо як завжди: ψ2=К3=0,05х2+0,75К2; z2=0,4x2+0,5(K2-x2)+z3max → Z2Max = мах [1,34до2 - 0,044x2] (при 0<х2<К2) → Z2max,=1,34K2,
якщоx2=0 і y2=K2 Етап 1. По аналогії з попередніми етапами: ψ 1=0,05x1+0,75K1=K2 z1=0,4xi+0,5(K1-x1)+z2max Z1max=max[1,505K1 - 0,023x1] (npu 0<x1< K1) → Z1max=1,505K}=1,505K,
при х1=0 і у1=К (тому що K1=K). Отже: максимальний прибуток діяльності 2-х підприємств за 5 років буде дорівнювати 1,505 від суми первісного вкладення, якщо на 1 і 2 роки усю суму капіталовкладень вкладати в друге підприємство, на 3-му році в перше, а на 4 і 5 роках - знову в друге підприємство. Така стратегія оптимального управління розвитком 2х підприємств. Досі ми розглядали простий випадок, коли αі β однакові для всіх етапів. Зустрічаються задачі, де αі β на кожному етапі різні (це є задача розподілу ресурсів з неоднорідними етапами). Рішення цієї задачі практично не відрізняється від розглянутої раніше і вирішується аналогічно із застосуванням поточних значень α i і βi на кожному i -му розвитку підприємства. Зустрічаються також задачі розподілу ресурсів, коли отриманий прибуток відчисляється не повністю, а частково вкладається в розвиток виробництва. У цьому випадку відрахований прибуток на будь-якому і -мукроці записується у виді:
Zimax=max[αxi+β (Кi – xі] - r[αхі+β(Кi-xi)],
де r - коефіцієнт, який характеризує частину прибутку, що вкладається розвиток виробництва. Основне функціональне рівняння при цьому приймає вид: Zimax=max[αxi+β (Кi – xі) - r[αхі+β(Кi-xi))+Z(i+1)max]. при 0≤ xi ≤ Кi.
В подальшому процедура рішення залишається незмінною. Якщо розглядається задача розподілу ресурсів між п об'єктами господарської діяльності, то приходиться на кожнім кроці мати п оптимальних рішень (але не 2, як ми розглядали). Тоді ui =(xi(1), xi(2)…… xi(n)) – вектор вкладень в підприємства на початок і-го року. Процес пошуку оптимальної стратегії управління вкладеннями на кожному кроці також зважується поетапно. Стан системи перед початком кожного етапу як і раніше буде характеризуватися одним числом (Кi) (,m – число етапів). Складніше буде с вибором управлінь (капіталовкладень в к-е підприємство на кожному і-му етапі xik).
Необхідно виконати наступні умови на i -му кроці:
При цьому основне функціональне рівняння матиме вид: Це вже класична задача ЛП, розв'язання якої вже розглядалося у попередньому розділі, що має вирішуватися для кожного i -го кроку. Досить часто в практиці приходиться вирішувати задачу розподілу ресурсів із вкладенням прибутку в розвиток виробництва. Подібні задачі називаються виродженими. Особливістю їх є те, що вони вирішуються з першого до останнього кроку, (тільки вперед), що значно спрощує процедуру рішення. Наприклад, для закупівлі устаткування 2-х типів, виділена сума 20000грн.. Ефективність вкладення цих засобів в устаткування оцінюється тим прибутком, що одержить підприємство, використовуючи це устаткування. Нехай для устаткування 1-го типу коефіцієнт ефективності (прибутку) складає α1= 0,4; для 2-го типу α2 =0,42. Наприкінці звітного періоду використане устаткування реалізується за ціною 0,7 і 0,6 первісної вартості (коефіцієнти амортизації відповідно β1=0,7 і β2=0,6). Отримані від продажу кошти, а також отриманий прибуток знову вкладаються в придбання устаткування 1-го і 2-го типів. Ставиться задача знайти оптимальний розподіл коштів для їх ^купівлі протягом 3-х років. Рішення Складемо функціональну модель процесу (рис.7.3). Рис.7.3 Модель процесу з вкладенням коштів у розвиток виробництва Перший крок. Знаючи початкове значення К1, одержуємо для К2:
К2 = [ α1х1 + α 2х2 + β1x1 + β 2x2 ]
Враховуючи x2=К1 – х1 запишемо:
К2 = [ α1х1 + α2(k1 –х1) + β1x1 +β2 (К1 –х1)] = = [(α1 – α2 + β1 – β2 )x1 + (α 2 + β2)K1] K2 буде максимальним при х1 =K1
Таким чином, стратегія управління на 1-му кроці: x1=K1; x2=0. При
α1 =0,4, α2 =0,42; β1 =0,7; β2 =0,5:
Величина капіталовкладень на початок другого року K2=1,1K1. Другий крок. Аналізується аналогічно першому: К2 = [ α1х1 + α 2х2 + β1x1 + β 2x2 ] = = [ (α1 – α2 + β1 – β2 )x1 + (α 2 + β2)K2 ]= = max[ 0.08x1 + 1.02K2 ]=1,1 K2= 1,12 K1 при х1 =К1 і т.д.. Очевидно, що можливі варіанти закупівлі устаткування різного типу на кожен етап розвитку. У цьому випадку уточнюється значення αi і βi на кожному кроці. Можливо також поєднання різних схем використання коштів. Пропонуємо читачам самим вирішити задачу за умови, що на 1-му етапі весь прибуток вкладається в придбання устаткування, а на наступному повністю відраховується як дивіденд від діяльності підприємства Необхідно максимізувати прибуток за останні 2 роки.
|
|||||||||||
Последнее изменение этой страницы: 2017-01-25; просмотров: 112; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.67.251 (0.045 с.) |