Тема 2.3 Динамическое программирование

Понятие динамического программирования. Общая постановка задачи динамического программирования. Геометрическая интерпретация задачи динамического программирования. Принцип поэтапного построения оптимального управления. Простейшие задачи, решаемые методом динамического программирования. Задача о минимизации расхода горючего самолетом при наборе высоты и скорости. Задача о назначении. Задача определения кратчайших расстояний по заданной сети. Задача распределения ресурсов. Задачи замены оборудования. Оптимальное распределение инвестиций как задача динамического программирования.

Студент должен:

Знать:

понятие: динамическое программирование;

принципы моделирования динамических систем;

метод динамического программирования;

геометрическую интерпретацию задачи динамического программирования;

метод функциональных уравнений;

Уметь:

решать задачу о минимизации расхода горючего;

определять оптимальное назначение работников на работы методами динамического программирования;

находить решение задачи определения кратчайших расстояний методом динамического программирования;

решать задачи распределения ресурсов и замены оборудования методом функциональных уравнений;

находить оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

Практическая работа № 1 «Решение простейших задач методами динамического программирования» (1 ч)

Вопросы для самопроверки по теме 2.3:

Сформулируйте задачу динамического программирования.

Дайте геометрическую интерпретацию задачи динамического программирования.

В чем состоит сущность принципа поэтапного построения оптимального управления?

Сформулируйте задачу минимизации расхода горючего самолетом при наборе высоты и скорости.

Что необходимо учитывать при выборе способа нумерации узловых точек?

В каких случаях оптимальное решение задачи не является единственным?

Приведите понятие сети. Какая сеть называется достаточно связанной?

Сформулируйте задачу определения кратчайших расстояний по заданной сети. На сколько этапов разбивается задача? Сколько шагов содержится в каждом этапе и в чем суть этапа и шага?

Расскажите алгоритм решения задачи определения кратчайших расстояний по заданной сети.

В чем суть метода функциональных уравнений?

Составьте функциональное уравнение для многоэтапного процесса распределения.

Напишите функциональное уравнение общего вида для дискретного процесса и объясните входящие в него величины.

Составьте функциональные уравнения для задачи распределения ресурсов, если величина дохода зависит не только от количества ресурсов и этапов, но и от времени начала процесса.

Сформулируйте задачу загрузки самолета, запишите ее математическую модель и составьте функциональные уравнения для ее решения.

Как интерпретировать задачу загрузки самолета, чтобы с ее помощью можно было решить задачу раскроя материалов?

Сформулируйте задачу замены оборудования и составьте функциональные уравнения, если возраст оборудования отсчитывается в прямом, а этапы – в обратном направлении.

Составьте функциональные уравнения задачи замены оборудования, если возраст оборудования и этапы отсчитывается в одном направлении.