Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Принцип оптимальності

РЕФЕРАТ | Теоретині основи динамічного програмування | Метод рекурентних співвідношень | Задача про розподіл капіталовкладень між підприємствами. | Багатокроковий процес прийняття рішень | Алгоритм методу динамічного програмування | Пошук найкоротшого шляху кур’єра компанії «tianDE» на прикладі задачі кімівояжера | Застосування динамічного програмування для задачі комівояжера | Приклад | ВИСНОВКИ |


Читайте также:
  1. CASE OF KINGSLEY v. THE UNITED KINGDOM» (Application no. 35605/97, judgment date 28 May 2002) в контексті принципу «ефективного» тлумачення Судом Конвенції.
  2. I. ГЛАВНЫЙ ПРИНЦИП СОВРЕМЕННЫХ ОБЩЕСТВ
  3. I. Ценности и принципы
  4. II. Основные принципы и ошибки инвестирования
  5. IV. Принципы создания и развития системы персонального учета населения Российской Федерации
  6. SMM – основні принципи та технології.
  7. V. по функциональному принципу.

 

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

Принцип оптимальності. Оптимальна поведінка володіє такою властивістю, що яким би не був первісний стан і рішення в початковий момент, наступні рішення мають складати оптимальну поведінку відносно стану, який досягається в результаті першого рішення. [3]

Для прийняття оптимального рішення на k -му кроці багатокрокового процесу потрібна оптимальність рішень на всіх його попередніх кроках, а сукупність усіх рішень дає оптимальний розв’язок задачі лише в тому разі, коли на кожному кроці приймається оптимальне рішення, що залежить від параметра етапу , визначеного на попередньому кроці.

Цей факт є основою методу динамічного програмування і є сутністю так званого принципу оптимальності Р.Белмана,який формулюється так:

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

Доведемо справедливість такого твердження, міркуючи від супротивного. Нехай маємо задачу на максимізацію функції і вектор є її оптимальним планом (стратегією, поведінкою) n -крокового процесу (n -вимірної задачі) з початковим параметром стану b.

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

,

але

,

що суперечливо. Отже, принцип оптимальності доведено.

 


Дата добавления: 2015-08-17; просмотров: 75 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Поняття динамічного програмування| Економічна сутність задач динамічного програмування

mybiblioteka.su - 2015-2024 год. (0.005 сек.)