На головну

Динамічне програмування. Загальна постановка задачі.

  1. C) загальна і особлива частини
  2. Cегментація ринку. Основні завдання. Критерії сегментації на В2С ринку.
  3. D-постановка
  4. I. Загальна характеристика
  5. II етап. Динамічне оновлення.
  6. L - постановка
  7. O розробка і постановка рекламних сувенірів, установки до них;

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

Виникло і сформувалося в 1950-1953 рр. завдяки роботам Р. Беллмана над динамічними завданнями управління запасами. У спрощеній формулюванні динамічне програмування являє собою спрямований послідовний перебір варіантів, який обов'язково призводить до глобального максимуму.

Основні необхідні властивості задач, до яких можливо застосувати цей принцип:

1. Завдання має допускати інтерпретацію як n-шаговий процес прийняття рішень.

2. Завдання має бути визначена для будь-якого числа кроків і мати структуру, яка не залежить від їх числа.

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

4. Вибір рішення (управління) на k-м кроці не повинен впливати на попередні рішення, крім необхідного перерахунку змінних.

Завдання про вибір траєкторії, завдання послідовного прийняття рішення, завдання про використання робочої сили, завдання управління запасами - класичні задачі динамічного програмування.



Опуклі безлічі, опуклі і увігнуті функції. Теорема Куна-Таккера. | Постановка завдання динамічного програмування.

Метод штучного базису. | Теореми подвійності. | Критерії оптимальності. | Теорема про існування оптимального рішення. | Цілочисельні ЗЛП, графічний метод рішення в разі двох змінних. | Задачі про призначення і про комівояжера як окремі випадки цілочисельних ЗЛП. | Метод гілок і меж. | Локальний екстремум. Необхідна і достатня умови. | Глобальний і умовний екстремуми | Множники Лагранжа. |

© um.co.ua - учбові матеріали та реферати