Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
9. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ, НЕ СВЯЗАННЫЕ СО ВРЕМЕНЕМДо сих пор мы рассматривали только такие задачи динамического программирования, где планируемая операция развивалась во времени и распадалась на ряд шагов (этапов), следующих друг за другом в естественном, временном порядке — от первого шага к последнему. Вообще, это не обязательно: разбиение на шаги или «этапирование» в задачах динамического программирования может быть произведено не по времени, а по любому другому признаку, например, по порядковому номеру того Или другого объекта. В качестве примера рассмотрим следующую задачу. Пусть имеется группа предприятий
которые выпускают одну и ту же продукцию. В нашем распоряжении какой-то запас средств Предположим, что каждое предприятие может освоить только ограниченное количество средств, и
представляют собой максимальные суммы, которые могут освоить соответственно предприятия (9.1). Если в предприятие Требуется так распределить имеющиеся средства между предприятиями, чтобы суммарный объем W дополнительной продукции был максимальным. Управление средствами состоит в том, что предприятиям выделяются соответственно средства:
не превосходящие в сумме имеющегося капитала
и требуется найти оптимальное управление, при котором
где Поставленная задача легко решается методом динамического программирования; «этапом» процесса распределения средств является выделение средств i-му предприятию. Будем нумеровать этапы (шаги) в порядке номеров предприятий (т. е. в произвольном порядке). Предположим, что средства предприятиям Очевидно, оптимальное управление на последнем шаге состоит в том, чтобы выделить
При таком управлении максимальный доход на последнем шаге будет
Перейдем к планированию предпоследнего шага — выделению средств на
при котором доход на
Основное функциональное уравнение динамического программирования будет
а вся процедура условной и безусловной оптимизации ничем не отличается от той задачи о распределении ресурсов по неоднородным этапам с резервированием, которую мы рассматривали выше, в § 6. Таким образом, метод динамического программирования, который первоначально представлялся нам как специфический метод оптимизации процессов, развивающихся во времени, имеет гораздо более широкое поле применений. Пример. Предстоит спроектировать многоступенчатую космическую ракету в пределах определенного стартового веса G Кабина космонавта имеет заданный вес
где Каждая ступень имеет какой-то запас горючего. После израсходования горючего отработанная ступень сбрасывается и вступает в действие следующая. Скорость ракеты в конце активного участка W складывается из
Требуется найти такое распределение веса Решение. Рассмотрим Так как приращение скорости, согласно формуле (9.6), зависит от двух аргументов — веса ступени и пассивного веса Р, определим этот пассивный вес Очевидно, он равен
Под влиянием управления Основное функциональное уравнение будет иметь вид:
Оптимальное управление на Оптимальное управление на
Далее процедура динамического программирования разворачивается обычным порядком. В результате находится оптимальный набор весов ступеней
придающий последней ступени (кабине) максимальную скорость:
|
1 |
Оглавление
|