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

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

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

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

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

Рассмотрим общую постановку задачи этого программирования. Пусть исследуется некоторый экономический процесс, имеющий п последовательных этапов. На каждом 7-м этапе процесс может быть в разных состояниях бы, каждый из которых характеризуется конечным множеством параметров. С каждым этапом задачи связано принятие определенного управленческого решения хи, которое переводит систему из одного состояния в другое. Предполагается, что состояние si системы в конце 7-го этапа определяется только предыдущим состоянием si_1 и управлением хи на 7-м этапе и не зависит от предыдущих состояний и управлений. Тогда состояние si системы записывается в виде зависимости

Si = ф (в, _!, Хи), i = 1, П.

Эффективность всего процесса управления может быть представлена как сумма эффективностей управленческих решений отдельных этапов, то есть

При названных условиях задача динамического программирования формулируется так: определить такую допустимую последовательность управленческих решений X = {x1, x2, хп}, которая переводит систему из начального состояния 50 в завершающий состояние sn и при которой достигается максимальная эффективность управления.

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

Максимум целевой функции на заключительном п-м этапе равна

^ п-О = шах / п ^ п-и хп).

Соответственно, на (п - 1) -етапи имеем

г * п-1 (5п-2) = ШaХ ((fn-1 (sn-2, хп-1) + г * п ^ п-1)).

Учитывая эту закономерность, для произвольного k-этапа можем записать рекуррентную зависимость

г * (пятый-1) = Шахи (Л (ик-1, хк) + г * + 1)).

Такая рекуррентная зависимость представляет собой математическую запись принципа оптимальности Беллмана.

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

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

1. Идея и метод динамического программирования больше приспособлены к дискретных задач, которыми в большинстве являются задачи управления.

2. Метод динамического программирования можно применять при любом способа задания целевой функции и с любой допустимой множеством состояний и управлений. Этого преимущества лишены классические методы оптимизации и другие вычислительные методы математического программирования.

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

4. Метод динамического программирования дает возможность анализа чувствительности к изменению исходных данных состояний sk и их количества п. Фактически здесь на каждом шагу решается не одна задача, а множество однотипных задач для различных состояний sk и различных к (1 <к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

Выводы

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

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

3. В отличие от задач линейного программирования, для решения нелинейных задач не существует универсального метода. В каждом конкретном случае необходимо выбирать лучший метод.

4. Динамическое программирование - это математический аппарат, с помощью которого решаются многошаговые задачи оптимального управления. Во многостепенность понимают или многоступенчатую структуру процесса, или распределения управления на ряд последовательных этапов, соответствующих, как правило, различным моментам времени.

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

6. Решение задач динамического программирования базируется на принципе оптимальности Беллмана. В процессе оптимизации управления методом динамического программирования многошаговый процесс выполняется дважды. Первый раз - от конца к началу, в результате чего находят условно оптимальные управления. Второй - от начала до конца, в результате чего находят оптимальное управление процессом в целом.

Для выбора оптимального решения при выполнении задач программирования иногда требуется перебирать большое количество комбинаций данных, что нагружает память персонального компьютера. К таким методам относится, например, метод программирования «разделяй и властвуй». В данном случае алгоритмом предусмотрено разделение задачи на отдельные мелкие подзадачи. Такой метод применяется только в тех случаях, когда мелкие подзадачи независимы между собой. Для того чтобы избежать выполнения лишней работы в том случае, если подзадачи взаимозависимы, используется метод динамического программирования, предложенный американцем Р.Беллманом в 50-х годах.

Суть метода

Динамическое программирование заключается в определении оптимального решения n-мерной задачи, разделяя ее n отдельных этапов. Каждый из них является подзадачей по отношению к одной переменной.

Основным преимуществом такого подхода можно считать то, что разработчики занимаются одномерными оптимизационными задачами подзадач вместо n-мерной задачи, а решение главной задачи собирается «снизу вверх».

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

Задача динамического программирования оптимизации. Автором этого метода Р. Беллманом был сформулирован принцип оптимальности: каким бы ни являлось начальное состояние на каждом из шагов и решение, определенное на этом шаге, все следующие выбираются оптимальными по отношению к тому состоянию, которое принимает система в конце шага.

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

Построение алгоритма задачи

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

Иногда на 3-м шаге нужно дополнительно запоминать некоторую вспомогательную информацию о ходе выполнения каждой подзадачи. Это называется обратным ходом.

Применение метода

Динамическое программирование применяется при наличии двух характерных признаков:

• оптимальность для подзадач;
• наличие в задаче перекрывающихся подзадач.

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

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

Особенно эффективно применение динамического программирования тогда, когда по существу задачи нужно принимать решения поэтапно. Например, рассмотрим простой пример задачи замены и ремонта оборудования. Допустим, на литейной машине завода по изготовлению шин делают одновременно шины в двух разных формах. В том случае, если одна из форм выходит из строя, приходится машину разбирать. Понятно, что иногда выгоднее заменить и вторую форму для того, чтобы не разбирать машину на случай, если и эта форма окажется неработоспособной на следующем этапе. Тем более, бывает проще заменить обе работающие формы до того, как они начнут выходить из строя. Метод динамического программирования определяет наилучшую стратегию в вопросе о замене таких форм, учитывая все факторы: выгоду от продолжения эксплуатации форм, потери от простоя машины, стоимость забракованных шин и другое.

На уроке будет рассмотрено понятие динамического программирования и исторический аспект его появления. Рассмотрены задачи динамического программирования и некоторые примеры их решения

Само понятие «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения другой задачи, «предшествующей» ей.
Таким образом, американский математик и один из ведущих специалистов в области математики и вычислительной техники — Ричард Эрнст Беллман — стал прородителем динамического программирования.

Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом.

Слово «программирование» в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет . Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».

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

В общем же для начала, неформальное определение понятия динамического программирования может звучать так:

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

Задачи оптимизации , как правило, связаны с задачей максимизации или минимизации той или иной целевой функции (например, максимизировать вероятность того, что система не сломается, максимизировать мат. ожидание получения прибыли и т.д.).

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

То есть, ДП решает не все задачи, а лишь некоторые, определенный класс подзадач. Но этот класс подзадачи используется во многих областях знаний: программирование, математика, лингвистика, статистика, теория игр, экономика, в компьютерных науках и т.п.

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

Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы:
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается .

Примеры, решаемых при помощи динамического программирования задач

Сначала рассмотрим задачи оптимизации (задачи 1-5):

1. Маршрут оптимальной длины

Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б . Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.

Целевой функцией здесь является расстояние от А до Б . Т.е. наша цель — минимизировать расстояние.

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

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

2. Замена машины (минимизация расходов)

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

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

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

3. Биржевой портфель

Пример: Игра на бирже, приобретение акций каких-либо компаний


Целевая функция: максимизация средних доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.

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

4. Составление плана оптимального производства (логистика)

Пример: Есть завод, изготавливающий мебель. На заводе работает определенное количество работников, которые могут изготовить соответствующее кол-во определенной мебели (стулья, столы, шкафы и т.п.)


Целевая функция : максимизация прибыли.

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

5. Игры (вероятностные или не вероятностные)

Пример: Участие в различных играх


Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Задачи 1 — 5 — это примеры задач оптимизации.

Комбинаторика:

6. Графы и деревья

Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п.

7. Задача о размене монет или количество способов вернуть сдачу

Пример: Есть монеты разного достоинства, какими способами можно вернуть сдачу.

Это краткое описание задач для динамического программирования, которые подробно будут рассмотрены позднее.

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

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

Для достижения цели максимизации прибыли необходимо решить множество подзадач:

• сколько стульев произвести — переменная X1 ,
• сколько столов произвести — переменная X2 ,
• сколько нанять работников — переменная X3 ,
• … Хn .

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

Поэтому ДП предлагает следующее:

• берем одну подзадачу с переменной X1 , об остальных подзадачах пока забываем.

Например, завод производит только стулья. У директора стоит задача получения максимальной прибыли с продажи стульев.

• После того, как найдем оптимальное решение для первой подзадачи, берем подзадачу для двух переменных Х1 и Х2 , и решаем ее с помощью уже найденного решения для первой подзадачи .
• Получаем решение уже для большей подзадачи, где фигурируют переменные Х1 и Х2 . Затем, используя полученное решение, берем подзадачи, охватывающие X1 , X2 и Х3 .
• И так продолжаем пока не получим решение для всей общей задачи.

Формальная идея ДП

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

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

Дело в том, что:

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

При этом важно, что при решении более сложной задачи, мы не решаем заново маленькую подзадачу, а используем уже решенный ответ этой подзадачи.
На графике это может выглядеть так:

Важно: По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!) , сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании

Когда мы решаем задачу с производными, множествами Ла-Гранжа и т.п., то мы работаем с непрерывными функциями. При решении же задач ДП мы будем работать в основном с дискретными функциями, поэтому говорить здесь о применении непрерывных функций неуместно.
По этой причине во многих задачах, но не во всех, применение аппарата математического анализа будет неприемлемым.

Простой пример решения задач при помощи ДП

Рассмотрим вариант решения задачи с помощью динамического программирования.

Пример: Необходимо вычислить сумму n чисел: 1 + 2 + 3 + ... + n

В чем состоит якобы «сложность» данной задачи: в том, что необходимо сразу взять большое количество чисел и получить ответ.

Попробуем применить к задаче идеи ДП и решить ее, разбивая на простые подзадачи.
(В ДП всегда необходимо сначала определить начальные условия или условие)

• Начнем с суммы одного первого элемента, т.е. просто берем первый элемент:
  F(1) = 1
• теперь с помощью решения для первого элемента, решим
  F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
• F(3) = F(2) + 3 = 6
• по аналогии продолжаем и получаем целевую функцию:
  F(n) = F(n-1) + An

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

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

Пример: имеется лесенка из n ступенек, перед которой находится человек, который за 1 шаг умеет подниматься либо на следующую ступеньку, либо перепрыгивает через одну ступеньку. Вопрос: сколькими способами он может попасть на последнюю ступеньку?

Решение:

Рассмотрим самые простые варианты (подзадачи):

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

1. с i-1 ступеньки, а на i-1 ступеньку мы могли попасть a i-1 способами
2. с i-2 ступеньки, а на i-2 ступеньку мы могли попасть a i-2 способами

Например, как попасть на 4-ю ступеньку :

Т.о., общее количество способов попасть на i ступеньку:
f(a i) = f(a i-1) + f(a i-2)

Определим начальные значения , с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Задание 1: реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.

Дополните код:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: integer ; procedure getKolSposob(i, n: integer ) ; begin writeln (i+ n, " " ) ; inc(c) ; if ... then getKolSposob(...,... ) end ; begin c: = 1 ; getKolSposob(0 , 1 ) ; end .

var c:integer; procedure getKolSposob(i,n: integer); begin writeln (i+n," "); inc(c); if ... then getKolSposob(...,...) end; begin c:=1; getKolSposob(0,1); end.

Задание 2:
Решение 15-го типа заданий ЕГЭ (Графы. Поиск количества путей).

Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (или «многоэтапным») операциям.

Представим себе некоторую операцию О, распадающуюся на ряд последовательных «шагов» или «этапов», - например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой самолетов нескольких полос противовоздушной обороны; или последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции (подобно вышеприведенным) расчленяются на шаги естественно; в некоторых членение приходится вводить искусственно - скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает какое-то время

Итак, рассмотрим операцию О, состоящую из шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:

где - выигрыш на i-м шаге.

Если W обладает таким свойством, то его называют аддитивным критерием .

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

Следует иметь в виду, что в общем случае - не числа, а, может быть, векторы, функции и т. д.

Требуется найти такое управление при котором выигрыш W обращается в максимум:

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

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

Формула (12.5) читается так: величина W есть максимум из всех при разных управлениях (максимум берется по всем управлениям возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут:

Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности)

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

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

значит, обладает свойством аддитивности.

Управление на шаге состоит в том, что в начале года предприятиям выделяются какие-то средства (первый индекс - номер шага, второй - номер предприятия). Таким образом, шаговое управление есть вектор с к составляющими:

Разумеется, величины в формуле (12.6) зависят от количества вложенных в предприятия средств.

Управление всей операцией состоит из совокупности всех шаговых управлений:

Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление при котором величина W обращается в максимум.

В этом примере шаговые управления были векторами; в последующих примерах они будут проще и выражаться просто числами.

2. Космическая ракета состоит из ступеней, а процесс ее вывода на орбиту - из этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:

где - вес ступени.

В результате этапа (сгорания и сбрасывания ступени) ракета получает приращение скорости А, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы, скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет

где А - выигрыш (приращение скорости) на шаге.

Управление представляет собой совокупность весов всех ступеней

Оптимальным управлением будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление - одно число, а именно, вес данной ступени.

3. Владелец автомашины эксплуатирует ее в течение лет. В начале каждого года он может принять одно из трех решений:

1) продать машину и заменить ее новой;

2) ремонтировать ее и продолжать эксплуатацию;

3). продолжать эксплуатацию без ремонта.

Шаговое управление - выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен

(12.10)

где - расходы в i-м году. Величину W требуется обратить в минимум.

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

где каждое из чисел имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (12.11), при которой величина (12.10) минимальна.

4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 12.1).

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

В этой задаче, в отличие от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на i-м шаге представляет собой угол , который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений:

Требуется выбрать такое (оптимальное) управление при котором суммарные затраты на сооружение всех участков минимальны:

(12.12)

Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи?

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

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

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

В самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, разбить ее на ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальна. Не так ли?

Нет, вовсе не так! Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Что толку, если мы выберем на данном шаге управление, при котором эффективность этого шага максимальна, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах?

Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции - получить за лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение - расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.

Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в «болото»?

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

Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой принес наибольшую выгоду.

Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых мы приступаем к последнему шагу?

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

Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем, условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, и найти не условно оптимальный, а просто оптимальный выигрыш .

В самом деле, пусть мы знаем, в каком состоянии была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S и в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление которое к концу второго шага переводит систему в состояние и т. д. Что касается оптимального выигрыша W за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление состоящее из оптимальных шаговых управлений

Первый этап - условной оптимизации - несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.

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