• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Динамічного програмування

Узагальнений алгоритм розв’язання задачі

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

Визначення параметру (параметрів), що характеризує стан системи. У розглянутій вище задачі таким параметром є вартість руху з даної точки до кінцевої точки траєкторії, тобто до точки В.

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

Ділення процесу на кроки, які складають траєкторію руху. В задачі це було ділення траєкторії на ділянки в напрямках координат х і у.

Визначення підмножини допустимих траєкторій для кожного кроку. В задачі це були допустимі шляхи руху у напрямках координат х і у.

Запис основного рівняння динамічного програмування для даної задачі, з використанням якого можна визначити “вартість” або “виграш”, який забезпечується у випадку руху системи з даної точки до кінцевої точки траєкторії. В задачі таким рівнянням була сума вартостей руху системи з даної точки до кінцевої точки В для кожної допустимої траєкторії.

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

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

Запитання для самоконтролю

1. Сформулюйте і поясніть основні особливості задач, що розв’язуються методом динамічного програмування .

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

3. В чому полягає принцип оптимальності, яким керуються у процесі розв’язання задач динамічного програмування?

4. Перерахуйте основні етапи процесу розв’язання задачі динамічного програмування способом зворотного прогону і поясніть їх сутність.

3 СТАТИСТИЧНЕ МОДЕЛЮВАННЯ ПРОЦЕСІВ ОБСЛУГОВУВАННЯ ПОВІТРЯНОГО РУХУ

Читайте також:

1. Безпосереднє програмування відеопам'яті
2. Виконання програми - реалізація мови програмування
3. Геометрична інтерпретація задачі лінійного програмування
4. Геометрична інтерпретація задачі нелінійного програмування
5. Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині
6. Графічний метод розв’язування задач лінійного програмування
7. Державне регулювання суспільного відтворення та його форми. Планування та програмування
8. Динамічне програмування.
9. Економічна і математична постановка задачі нелінійного програмування
10. Економічна і математична постановка задачі нелінійного програмування
11. Економічна і математична постановка цілочислової задачі лінійного програмування

Переглядів: 1215