Зміст
Введення
1. Основні поняття
1.1. Модель динамічного програмування
1.2. Принцип оптимальності. Рівняння Беллмана
2. Оптимальний розподіл ресурсів
2.1 Постановка завдання
2.2 Двовимірна модель розподілу ресурсів
2.3 Дискретна динамічна модель оптимального розподілу ресурсів
2.4 Облік післядії в задачах оптимального розподілу ресурсів
Висновок
Список використовуваних джерел
Додаток 1. Лістинг програми для вирішення задачі оптимального розподілу ресурсів з заданими параметрами. Результати роботи програми
Введення
Протягом усієї своєї історії люди при необхідності приймати рішення вдавалися до складних ритуалів. Вони влаштовували урочисті церемонії, приносили в жертву тварин, ворожили по зіркам і стежили за польотом птахів. Вони покладалися на народні прикмети і намагалися дотримуватися примітивним правилам, що полегшує їм важке завдання прийняття рішень. В даний час для прийняття рішення використовують новий і, мабуть, більш науковий В«ритуалВ», заснований на застосуванні електронно-обчислювальної машини. Без сучасних технічних засобів людський розум, ймовірно, не може врахувати численні і різноманітні фактори, з якими стикаються при управлінні підприємством, конструюванні ракети або регулюванні руху транспорту. Існуючі в даний час численні математичні методи оптимізації вже досить розвинені, що дозволяє ефективно використовувати можливості цифрових і гібридних обчислювальних машин. Одним з цих методів є математичне програмування, що включає в себе як окремий випадок динамічне програмування.
Більшість практичних завдань має кілька (а деякі, можливо, навіть нескінченне число) рішень. Метою оптимізації є знаходження найкращого рішення серед багатьох потенційно можливих відповідно до деяким критерієм ефективності або якості. Завдання, що допускає лише одне рішення, не вимагає оптимізації. Оптимізація може бути здійснена за допомогою багатьох стратегій, починаючи з вельми складних аналітичних і чисельних математичних процедур і кінчаючи розумним застосуванням простої арифметики.
Динамічне програмування - метод оптимізації, пристосований до операцій, в яких процес прийняття рішень може бути розбитий на окремі етапи (кроки). Такі операції називаються багатокрокових.
Як розділ математичного програмування, динамічне програмування (ДП) почало розвиватися в 50-х роках XX в. завдяки роботам Р. Беллмана та його співробітників. Вперше цим методом вирішувалися задачі оптимального управління запасами, потім клас задач значно розширився. Як практичний метод оптимізації, метод динамічного програмування став можливий лише при використанні сучасної обчислювальної техніки.
В основі методу динамічного програмування лежить принцип оптимальності, сформульований Беллманом. Цей принцип і ідея включення конкретної задачі оптимізації в сімейство аналогічних багатокрокових завдань призводять до рекурентним співвідношенням - функціональним рівнянням - щодо оптимального значення цільової функції. Їх рішення дозволяє послідовно отримати оптимальне управління для вихідної задачі оптимізації.
1. Основні поняття
1.1 Модель динамічного програмування
Дамо загальний опис моделі динамічного програмування.
Розглядається керована система, яка під впливом управління переходить з початкового стану в кінцевий стан. Припустимо, що процес управління системою можна розбити на п кроків. Нехай,, ..., - стану системи після першого, другого, ..., п -го кроку. Схематично це показано на рис. 1.
Малюнок 1
Стан системи після k-го кроку ( k = 1,2 ..., n ) характеризується параметрами, , ..., Які називаються фазовими координатами. Стан можна зобразити точкою s-мірного простору званого фазовим простором. Послідовне перетворення системи (по кроках) досягається за допомогою деяких заходів,, ...,, які складають управління системою, де - управління на k -му кроці, що переводить систему зі стану в стан (рис. 1). Управління на k -ом кроці полягає у виборі значень певних керуючих змінних * .
Припускаємо надалі, що стан системи в кінці k-го кроку залежить тільки від попереднього стану системи та управління на даному кроці (рис. 1). Таке властивість отримало назву відсутності післядії. Позначимо цю залежність у вигляді
, (1.1)
Рівності (1.1) отримали назву рівнянь станів. Опції вважаємо заданими.
Варіюючи управління U , отримаємо різну В«ефективністьВ» процесу **, яку будемо оцінювати кількісно цільовою функцією Z , залежної від початкового стану системи і від обраного управління U :
. (1.2)
Показник ефективності k-го кроку процесу управління, який залежить від стану на початку цього кроку і управління, обраного на цьому кроці, позначимо через розглянутій задачі покрокової оптимізації цільова функція (1.2) повинна бути адитивною, т. тобто
. (1.3)
Якщо властивість адитивності цільової функції Z не виконується, то цього іноді можна домогтися деякими перетвореннями функції. Наприклад, якщо Z-мультиплікативна функція, задана у вигляді, то можна розглянути функцію, яка є адитивної.
Зазвичай умовами процесу на управління на кожному кроці накладаються деякі обмеження. Управління, що задовольняють цим обмеженням називаються допустимими .
Завдання покрокової оптимізації можна сформулювати так: визначити сукупність допустимих управлінні,, ...,, переводять систему з початкового стану в кінцеве стан і максимізують або мінімізують показник ефективності (1.3).
Для однаковості формулювань (але не обчислювальних процедур!) надалі ми будемо говорити тільки про завдання максимізації, маючи на увазі, що якщо необхідно мінімізувати Z , то, замінивши Z на Z ' =-Z перейдемо до максимізації Z '.
Початковий стан і кінцевий стан можуть бути задані однозначно або можуть бути вказані безліч початкових станів безліч кінцевих станів так, що,. В останньому випадку в задачі покрокової оптимізації потрібно визначити сукупність допустимих управлінь, переводять систему з початкового стану в кінцевий стан і максимізує цільову функцію (1.3). Управління, при якому досягається максимум цільової функції (1.3), називається оптимальним управлінням і позначається через.
Якщо змінні управління приймають дискретні значення, то модель ДП називається дискретної. Якщо ж зазначені змінні змінюються безперервно, то модель ДП називається безперервної. В Залежно від числа параметрів станів (s) і числа керуючих змінних на кожному кроці ( r ) розрізняють одновимірні і багатовимірні моделі ДП. Число кроків в задачі може бути або кінцевим, або нескінченним.
Динамічне програмування застосовується при оптимізації як детермінованих, так і стохастичних процесів.
У деяких завданнях, розв'язуваних методом ДП, процес управління природно розбивається на кроки. Наприклад, при розподілі на кілька років ресурсів діяльності підприємства кроком природно вважати часовий період; при розподілі коштів між n підприємствами номером кроку природно вважати номер чергового підприємства. В інших завданнях розбиття на кроки вводиться штучно. Наприклад, безперервний керований процес можна розглядати як дискретний, умовно розбивши його на деякі тимчасові відрізки - Кроки. Виходячи з умов кожної конкретної задачі, довжину кроку вибирають таким чином, щоб на кожному кроці отримати просту задачу оптимізації та забезпечити необхідну точність обчислень.
1.2 Принцип оптимальності. Рівняння Беллмана
Метод динамічного про...
