9. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ, НЕ СВЯЗАННЫЕ СО ВРЕМЕНЕМ

До сих пор мы рассматривали только такие задачи динамического программирования, где планируемая операция развивалась во времени и распадалась на ряд шагов (этапов), следующих друг за другом в естественном, временном порядке — от первого шага к последнему. Вообще, это не обязательно: разбиение на шаги или «этапирование» в задачах динамического программирования может быть произведено не по времени, а по любому другому признаку, например, по порядковому номеру того Или другого объекта.

В качестве примера рассмотрим следующую задачу.

Пусть имеется группа предприятий

которые выпускают одну и ту же продукцию. В нашем распоряжении какой-то запас средств который мы можем вложить в группу предприятий (9.1) с тем, чтобы произвести сверх плана максимальное количество продукции.

Предположим, что каждое предприятие может освоить только ограниченное количество средств, и

представляют собой максимальные суммы, которые могут освоить соответственно предприятия (9.1). Если в предприятие вложены средства X, оно даст единиц дополнительной (сверхплановой) продукции.

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

не превосходящие в сумме имеющегося капитала

и требуется найти оптимальное управление, при котором

где — дополнительная продукция i-го предприятия.

Поставленная задача легко решается методом динамического программирования; «этапом» процесса распределения средств является выделение средств i-му предприятию.

Будем нумеровать этапы (шаги) в порядке номеров предприятий (т. е. в произвольном порядке). Предположим, что средства предприятиям уже выделены, и к последнему, шагу мы пришли с каким-то запасом средств К.

Очевидно, оптимальное управление на последнем шаге состоит в том, чтобы выделить предприятию все оставшиеся средства К, если они не превосходят и максимально возможное количество средств если . Таким образом, условное оптимальное управление на последнем шаге:

При таком управлении максимальный доход на последнем шаге будет

Перейдем к планированию предпоследнего шага — выделению средств на предприятие. Пусть после шагов в нашем распоряжении остались средства К. Мы должны выбрать такое управление

при котором доход на шаге плюс уже оптимизированный доход на последнем обращается в максимум:

Основное функциональное уравнение динамического программирования будет

а вся процедура условной и безусловной оптимизации ничем не отличается от той задачи о распределении ресурсов по неоднородным этапам с резервированием, которую мы рассматривали выше, в § 6.

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

Пример. Предстоит спроектировать многоступенчатую космическую ракету в пределах определенного стартового веса G Кабина космонавта имеет заданный вес Предполагается, что ракета будет иметь ступеней. Стартовый вес ракеты складывается из весов всех ступеней ракеты плюс вес кабины:

где — вес, выделенный на все ступеней.

Каждая ступень имеет какой-то запас горючего. После израсходования горючего отработанная ступень сбрасывается и вступает в действие следующая.

Скорость ракеты в конце активного участка W складывается из приращений скорости которые она приобретает на отдельных участках траектории, в результате работы каждой ступени. Добавочная скорость придаваемая ракете на шаге, зависит, во-первых, от веса выделенного на ступень, и во-вторых, от того пассивного веса Р, который приходится нести этой ступени:

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

Решение. Рассмотрим ступеней ракеты как этапов набора скорости Состояние S системы перед началом каждого шага мы будем характеризовать одним параметром Q — оставшимся весом, подлежащим распределению между ступенями Управление на шаге состоит в выборе веса отводимого из оставшегося веса Q на данную, ступень.

Так как приращение скорости, согласно формуле (9.6), зависит от двух аргументов — веса ступени и пассивного веса Р, определим этот пассивный вес Очевидно, он равен и приращение скорости будет:

Под влиянием управления система переходит из состояния Q в состояние

Основное функциональное уравнение будет иметь вид:

Оптимальное управление на шаге есть то значение при котором достигается этот максимум.

Оптимальное управление на шаге (при естественном предположении, что с увеличением веса, отводимого на ступень, приращение скорости увеличивается), состоит в том, чтобы отвести на последнюю ступень весь оставшийся вес Q При этом на последнем шаге будет приобретена скорость:

Далее процедура динамического программирования разворачивается обычным порядком. В результате находится оптимальный набор весов ступеней

придающий последней ступени (кабине) максимальную скорость: