Розробка програми «Визначення оптимального строку заміни обладнання»
Курсовий проект
З дисципліни: «Математичні методи»
Зміст
Введення
. Постановка завдання
. Складання математичної моделі динамічного програмування
3. Оптимізація
. Вибір оптимальної стратегії заміни обладнання як задача динамічного програмування
. Алгоритм рішення задачі
. Порядок установки
Висновок
Додаток А, форми програми
Додаток В, лістинг програми
Введення
У ряді реальних економічних і виробничих завдань необхідно враховувати зміну модельованого процесу в часі і вплив часу на критерій оптимальності. Для вирішення зазначених завдань використовується метод динамічного планування (динамічне планування). Цей метод більш складний у порівнянні з методами розрахунку статичних оптимізаційних задач, викладених вище. Також не простою справою є процес побудови реального завдання математичної моделі динамічного програмування.
1. Постановка задачі динамічного програмування. Основні умови і область застосування
Нехай розглянута задача, що розпадається на m кроків або етапів, наприклад планування діяльності підприємства на декілька років, поетапне планування інвестицій, управління виробничими потужностями протягом тривалого терміну. Показник ефективності завдання в цілому позначимо через W, а показники ефективності на окремих кроках - через? I, i=1, m. Якщо W має властивість адитивності, тобто
m =? ? i,
I=1
Те можна знайти оптимальне рішення задачі методом динамічного програмування.
Таким чином, динамічне програмування - це метод оптимізації багатокрокових або багатоетапних процесів, критерій ефективності яких володіє властивістю. В задачах динамічного програмування критерій ефективності називається виграшем. Дані процеси керовані, і від правильного вибору управління залежить величина виграшу.
Змінна хi, від якої залежать виграш на i-му кроці і, отже, виграш в цілому, називається кроковим управлінням, i =.
Управлінням процесу в цілому (х) називається послідовність крокових управлінь х=(х1, х2, ..., хi, ..., хm).
Оптимальне керування х * - це значення управління х, при якому значення W (х *) є максимальним (або мінімальним, якщо потрібно зменшити програш)
*=W (х *)=max {W (х)}, x € X,
де X - область допустимих управлінь.
Оптимальне керування х * визначається послідовністю оптимальних крокових управлінь
х *=(х * 1, х * 2 ..., х * i,, х * m).
В основі методу динамічного програмування лежить принцип оптимальності Беллмана, формулюється таким чином; управління на кожному кроці треба вибирати так, щоб оптимальною була сума виграшів на всіх залишилися до молодика процесу кроках, включаючи виграш на даному кроці.
При вирішенні завдання динамічного програмування на кожному кроці вибирається управління, яке повинне привести до оптимального виграшу. Якщо вважати всі кроки незалежними один від одного, то оптимальним кроковим управлінням буде те управління, яке приносить максимальний виграш саме на цьому кроці. Але, наприклад, при покупці нової техніки замість застарілої на її придбання затрачаються певні кошти. Тому прибуток від її експлуатації, спочатку може бути невеликою. Однак у наступні роки нова техніка буде приносити більший прибуток. І, навпаки, якщо керівник прийме рішення залишити стару техніку для отримання прибутку в поточному році, то в подальшому це призведе до значних збитків. Даний приклад демонструє наступний факт: в багатокрокових процесах всі кроки залежать один від одного, і, отже, управління на кожному конкретному кроці треба вибирати з урахуванням його майбутніх впливів на весь процес.
Другий момент, який слід враховувати при виборі управління на даному кроці, - це можливі варіанти закінчення попереднього кроку. Ці варіанти визначають стан процесу. Наприклад, при визначенні кількості коштів, вкладених у підприємство в i-му році, необхідно знати, скільки коштів залишилося в наявності до цього року, який прибуток отримана в попередньому (i-м) році. Таким чином, при виборі крокового управління необхідно враховувати:
