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

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

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

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

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

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

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

S a _ik x_k > b_i ; i=1,2,…, m. (2.1)

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

f(x) = S c_k x_k . (2.2)

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

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

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

S a_ij x_j < b_i (i Î I) (2.3)

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

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

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

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

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