Введення
математичний динамічний програмування
Динамічне програмування (динамічне планування) - це розділ математичного програмування, який вивчає сукупність прийомів і методів, що дозволяють знаходити оптимальні рішення, засновані на обчисленні наслідків кожного рішення і виробленні оптимальної стратегії для наступних рішень.
Завдання динамічного програмування є багатоетапними, тому термін «динамічне програмування" не стільки визначає особливий тип завдань, скільки характеризує методи знаходження вирішення окремих класів задач математичного програмування.
У випадку завдання динамічного програмування формулюється таким чином. Наприклад, дана фізична система знаходиться в деякому початковому стані і є керованою. Завдяки здійсненню деякого управління (деякої операції) зазначена система переходить з початкового стану в кінцевий стан. При цьому якість кожного з реалізованих управлінь характеризується відповідним значенням функції. Завдання полягає в тому, щоб з безлічі можливих управлінь знайти таке, при якому функція приймає екстремальне значення.
Можна виділити два класи завдань, до яких методи динамічного програмування застосовуються найбільш вдало.
Перший клас - це завдання планування діяльності економічного об'єкта (підприємства, галузі тощо) з урахуванням зміни потреби в виробленої продукції в часі.
Другий клас завдань - завдання оптимального розподілу ресурсів між різними напрямками в часі.
Найбільшої ефективності методи динамічного програмування досягають там, де з самого суті завдання доводиться приймати рішення по етапах.
Розглянемо основні теоретичні аспекти вирішення завдань методом динамічного програмування.
Будемо вважати, що стан розглянутої системи на - му кроці
(1)
які отримані в результаті реалізації управління забезпечує перехід системи зі стану в стан.
Далі, будемо вважати, що якщо в результаті реалізації кроку забезпечений певний дохід, який також залежить від вихідного стану системи і вибраного управління, рівний, то загальний дохід за кроків становить
(2)
де.
Таким чином, сформульовані дві умови, яким повинна задовольняти розглянута задача динамічного програмування. Перша умова зазвичай називають умовою відсутності післядії, а друге - умовою адитивності цільової функції задачі оптимізації.
Завдання оптимізації в цьому випадку полягає у знаходженні оптимальної стратегії управління, тобто такої сукупності управлінь
(3)
в результаті реалізації яких система за кроків переходить з початкового стану в кінцеве і при цьому функція доходу приймає найбільше значення.
Розподіл капітальних вкладень - це нелінійна задача розподілу ресурсів між підприємствами одного виробничого об'єднання або галузі.
Припустимо, що вказано n-пунктів, де потрібно побудувати підприємства однієї галузі, для чого виділена певна сума. При цьому відомий приріст потужності або прибутку для кожного підприємства, в залежності від суми капітальних вкладень у це підприємство.
Якщо потрібно знайти розподіл капітальних вкладень між підприємствами, то завдання полягає в тому, щоб знайти такі значення, при яких значення сумарного приросту прибутку або потужності всієї галузі
(4)
було б найбільшим при обмеженнях загальної суми,
де - загальна сума капітальних вкладень.
Дана задача вирішується методом динамічного програмування. Для цього необхідно ввести параметр стану і функцію стану
де - деяка кількість підприємств, для яких визначається параметр і функція стану.
- максимальний приріст прибутку або потужності на перших -підприємством, якщо вони разом отримають - капітальних вкладень.
Якщо - кількість одиниць ресурсу, то -е підприємство отримає одиниць ресурсу, то залишок необхідно розподілити між підприємствами від -го до -го так, щоб був отриманий максимальний приріст прибутку або потужності Отже, приріст прибутку буде дорівнює і потрібно вибрати таке значення-е між 0 і x, щоб збільшення прибутку -підприємств було максимальним.
1.Построеніе математичної моделі
Загальна сума в 4 млн. руб. розподіляється між п'ятьма підприємствами в кількостях, кратних 1 млн. руб. У результаті виділення коштів підприємству в розмірі воно дає дохід=1,2,3,4,5 величина якого може бути знайдена з таблиці №1:
Таблиця №1. «Вихідні дані»
01234 0591112 034510 0791011 0481214 03579
Розподілити кошти між підприємствами так, щоб їх сумарний дохід був максимальним.
1. Заповнимо таблицю першій ітерації.
Таблиця №2. «Перша ітерація»
f...
