4. Методы принятия решений, основанные на исследовании операций. Динамическое программирование.

Дискретный управляемый процесс

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

Под состоянием системы в момент времени будем понимать вектор

пространства .

Будем рассматривать процесс перехода системы из состояния в состояние при следующих предположениях:

Процесс дискретный, т.е. система может переходить их одного состояния в другое в строго определённые заранее фиксированные моменты времени , …, … Моменты времени , …, … будем называть соответственно ,… шагами процесса. Число шагов может быть как конечным, так и бесконечным.

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

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

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

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

Состояние системы в конце каждого шага зависит только от предшествующего состояния и управляющего решения, выбранного на данном шаге (свойство отсутствия последействия), то есть

(II.1)

где - произвольное состояние системы, - заданная вектор-функция, называемая оператором перехода. Равенства (II.1) называются уравнениями состояния.

Таким образом, детерминированный дискретный управляемый процесс (II.1) определяется заданием множеств , и оператора перехода .

II-2. 1. Постановка задачи принятия решений на дискретном управляемом процессе

Рассмотрим процесс

, (II.2)

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

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

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

(II.3).

Стратегию , удовлетворяющую (II.3) для любой , будем называть оптимальной.

II-2.3. Постановка задачи принятий решений на конечношаговом управляемом процессе

Рассмотрим процесс (II.2) и предположим, что число шагов конечно, то есть есть

(II.4)

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

(II.5)

Для каждого начального состояния и стратегии получаем в силу (II.4) соответствующее течение процесса или траекторию

Качество управления процессом (II.4) (эффективность стратегии ) оценим количественно-целевой функцией

(II.6)

Задача принятия решений на конечношаговом управляемом процессе (II.4) (задача пошаговой оптимизации) состоит в следующем: определить допустимое управление

, которое переводит систему из начального состояния в конечное состояние , при этом и доставляет максимальное (минимальное) значение целевой функции (II.6), т.е.

(II,7)

Допустимое управление , которое доставляет максимальное значение функции (II.6), называется оптимальным уравнением, траектория

, соответствующая управлению ,- оптимальной траекторией.

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

Если состояния и не фиксированы, то задача пошаговой оптимизации процесса (II.4) состоит в определении такого начального состояния и такого допустимого (относительно ) управления , при которых и целевая функция достигает оптимального значения.

II-2.4. Прикладные задачи. Примеры управляемых процессов

II-2.4.1. Задача распределительных капиталовложений

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

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

Все перечисленные условия можно формализовать в виде следующией модели:

Найти вектор , доставляющий максимальное значение целевой функции

и удовлетворяющий условиям

(ограничение на общее число проектов),

(ограничение на объем капиталовложений),

Рассмотрим операцию выбора проектов капиталовложений из – предложенных проектов как -шаговый процесс, понимая под шагом рассмотрение одного проекта с номером ,

Состояние системы в начале k-ого шага, состоящего в рассмотрении -ого проекта, будем характеризовать двумя фазовыми параметрами: – количество капиталовложений, оставшееся нераспределённым к началу k-ого шага, – количество проектов, которое ещё можно принять, т.е.

,

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

,

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

Таким образом, состояние системы определяется на основании следующего уравнения состояния:

Фазовые ограничения, очевидно, имеют следующий вид:

,

— целые,

При принятии на k-ом шаге решения y_k шаговый доход составит, очевидно,

рублей =

Доход от всей операции в целом есть

.

Таким образом, задача оптимизации N-шагового процесса выбора проектов капиталовложений имеет вид

II-2.4.2. Задача о животноводческом комплексе

Животноводческий комплекс имеет стадо скота. Ежегодно часть скота отправляется на мясозаготовки, остальная часть остается на ферме для воспроизводства. Минимальные ежегодные мясопоставки составляют (плановое задание). Доход от продажи скота мясозаготовительным организациям выражается функцией , где y – количество проданного скота, функция может, например, иметь вид, показанный на рис. 11 (поставки мяса сверх планового задания c_k оплачиваются по более высоким ценам).

– плановое задание

Рис. 11 Пример зависимости дохода от продажи скота

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

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

Под управляющим решением , принимаемым в состояни, будем понимать решение о продаже единиц скота в -м году (в конце -го года), .

Количество скота , имеющееся в начале k-го года, в течение k-го года увеличивается в раз, т.е. в конце k-го года на комплексе будет единиц скота. Из этого количества скота будет продано, т.е. к началу -го года на комплексе останется · единиц скота, которое и определяет состояние системы (комплекса) в начале следующего года.

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

, , .

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

,

Доход, получаемый комплексом от продажи единиц скота в конце k-го года, составляет , доход комплекса за N лет составляет

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

имеет следующий вид:

,

В поставленной задаче количество скота, оставляемое к началу следующего года, никак не регламентируется, поэтому имеется единственное фазовое ограничение

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

,

Постановку рассматриваемой задачи можно обобщить [5], если учесть, что затраты на уход и прокорм голов скота в течение k-го года равны . В этом случае доход, получаемый комплексом в k-ом году, будет равен g( , а доход за N лет составит

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

в течение N лет будет иметь вид

,

II-2.4.3. Транспортная задача (о перевозках сырья (товаров) от поставщиков (складов) к потребителям (заводам))

Пусть число складов равно 3, а число заводов . Предположим, что имеется только один вид сырья и запас сырья равен спросу, т.е.

, где

.

Стоимость перевозки y единиц с -ого склада на -й завод выражается функцией (рис. 12). Требуется с минимальными расходами перевезти сырьё со складов на заводы.

Рис. 12 Стоимость перевозки y единиц сырья с -ого склада на -й завод

Рассмотрим данную операцию перевозки грузов от трёх поставщиков к потребителям как -шаговый управляемый процесс, понимая по шагом перевозку груза от трех складов на один завод (полное удовлетворение его потребностей).

Обозначим через количество груза (сырья), которое осталось не вывезенным на i-м складе к началу -го шага ( -й шаг – перевозка груза -му заводу),

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

Так как запас сырья равен спросу, после вывоза сырья на все заводов склады останутся пустыми, т.е. .

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

Так как потребность в сырье -го завода составляет ,

откуда

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

,

т.е. уравнение состояния имеет вид , , ,

Записывая уравнение состояния по шагам, получим:

;

;

…

;

Таким образом, третья фазовая координата зависит от первых двух, т.е. можно считать, что состояние системы на k-ом шаге описывается двумерным вектором

На фазовые переменные накладываются ограничения

,

, , ,

на управляющие переменные

Стоимость всех перевозок по допустимому плану будет равна

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

, , ,

,

II-2.5. Метод динамического программирования решения задач принятия решений (оптимизации) на дискретном управляемом процессе

II-2.5.1 . Постановка задачи

Рассмотрим детерминированный многошаговый управляемый процесс

(II.8)

и задачу его оптимизации

, ( ), (II.9)

,

которую будем решать методом динамического программирования (МДП).

С помощью МДП удается решить не любую задачу (II.9). В частности, метод динамического программирования применим для решения задачи (II.9), если детерминированный многошаговый упраляемый процесс (II.8) является марковским процессом, а целевая функция F обладает специальной структурой.

II-2.5.2. Марковский процесс

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

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

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

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

состояния системы в конце -го шага

последующих управляющих решений; и не зависит от того, каким образом система пришла в это состояние.

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

II-2.5.3. Способы задания целевой функции

1. Пусть целевая функция (II.6) имеет вид:

_(II.10)

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

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

Пусть

_(II.11)

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

_(II.12)

Очевидно, что приведённые здесь целевые функции (II.10) и (II.12) обладают той структурой, теми свойствами, о которых говорилось в разделе II-2.5.2.

Целевые функции в задачах II-2.4.1 – II-2.4.4, рассмотренные в разделе II-2.4, имеют вид (II.10), т.е. эти задачи могут быть решены МДП.

II-2.5.4. Принцип оптимальности Беллмана

Рассмотрим марковский управляемый детерминированный многошаговый процесс (II.8) и задачу его оптимизации (II.9) с аддитивной функцией цели (II.10).

Преположим, что задача (II.9) с целевой функцией (II.10) имеет решение. Тогда справедлив принцип оптимальности Беллмана:

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

Доказательство. Обозначим через

(II.13)

оптимальную стратегию, являющуюсь решением задачи (1.9),

(II.14)

отвечающую ей оптимальную траекторию.

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

(II.15)

эффективность управления которым будем оценивать целевой функцией

( II.16)

где, - управление (стратегия) – шаговым процессом (II.15). В частности, при принятии в состоянии управляющего решения система перейдёт в состояние

Задача оптимизации на процессе (II.15) ставится так же, как и задача для всего процесса (II.8).

Обозначим через

(II.17)

оптимальное управление (стратегию) для процесса (II.15) с целевой функцией (II.16). Тогда в принятых обозначениях принцип оптимальности Беллмана для процесса (II.15) запишется следующим образом: для оптимальности стратегии (II.17) необходимо, чтобы для любого состояния системы и любого управляющего решения , принимаемого в этом состоянии, последующие управляющие решения

составили оптимальную стратегию для N-k- шагового процесса, начинающегося из состояния . Допустим, что это утверждение неверно, т.е. стратегия оптимальна для – шагового процесса (II.15), а управление – шаговым процессом не оптимально относительно его начального состояния

Это означает, что существует такое управление N-k- шаговым процессом , начинающимся из состояния , что

(II.18)

Очевидно, что управление является допустимым управлением – шаговым процессом, начинающимя из состояния . Оценим эффективность управления , используя (II.18) и аддитивность целевой функции

(II.19)

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

II-2.5.5. Уравнение Беллмана

На основании принципа оптимальности Беллмана можно получить основное уравнение динамического программирования, или уравнение Беллмана.

Рассмотрим -шаговый управляемый марковский процесс (II.8) с целевой функцией (II.10) и задачу его оптимизации (II.9).

Пусть стратегия (II.13) и траектория (II.14) являются соответственно оптимальной стратегией и траекторией поставленной задачи.

Выберем произвольное состояние системы в момент времени , и рассмотрим – шаговый процесс, начинающийся из состояния :

. (II.20)

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

, (II.21)

где - управление (стратегия) процессом.

Пусть - оптимальное управление процессом (II.20), а

оптимальная траектория, отвечающая этому управлению. Эффективность управления оценивается величиной

(II.22)

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

(II.23)

Равенство (II.23) имеет место, если , а Если в состоянии принимается произвольное допустимое управляющее решение , то стратегия будет являться допустимой для процесса (1.20) и её эффективность будет оцениваться величиной

(II.24)

Так как стратегия является оптимальной, можно записать

(II.25)

причём неравенство (II.25) справедливо для любых , следовательно,

(II.26)

В силу произвольности выбора момента времени и состояния полученное соотношение справедливо для любых . Полученное соотношение (II.26) называется уравнением Беллмана.

II-2.5.6. Решение уравнение Беллмана

Запишем уравнения Беллмана для k=1

(II.27)

Ясно, что есть максимальное значение функции , а - оптимальное управление процессом (оптимальная стратегия).

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

Для определения функции

, (II.28)

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

На последнем шаге процесс завершается, т.е. можно положить

,

так как доход на последующих шагах отсутствует.

Тогда уравнение (II.28) примет вид

(II.29)

Функция задана и является для каждого , функцией переменной управления , следовательно, задача (II.29) оптимизации одношагового процесса может быть решена. Решив эту задачу, мы определим оптимальное значение критерия эффективности управления одношаговым процессом и само оптимальное управление , то есть то значение переменной управления , при котором в задаче (II.29) достигается значение . Решение задачи (II .29) должно быть получено для любого состояния , . Итак, решив задачу (II.29), мы получим две функции состояния:

(II.30)

называемые соответственно условным оптимальным значеним критерия эффективности и условным оптимальным управлением одношаговым процессом. Решением уравнения (II.29) начинается первый этап решения задачи. Теперь можно решить уравнение Беллмана при , то есть уравнение

. (II.31)

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

Далее, решив уравнение Беллмана при определим для каждого две функции состояния: и

Наконец, при определим две функции состояния :

– (II.32)

условное оптимальное значение критерия эффективности управления N-шаговым процессом, начинающимся из любого начального состояния ; - условное оптимальное управление, т.е. то значение переменной , при котором достигается максимум в парвой части выражения (II.32). На этом шаге заканчивается первый этап решения задачи МДП, или этап условной оптимизации. На этом этапе было решено N задач, каждая из которых является задачей максимизации функции, зависящей только от переменной , Закончив первый этап решения задачи, мы ещё не нашли оптимальной стратегии, но построили две последовательности функций состояния:

и

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

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

Здесь возможны два случая:

Начальное состояние единственно. Тогда представляет собой максимальное значение критерия эффективности управления N-шаговым процессом (II.8).

Обозначим , т.е. получим первый элемент оптимальной траектории (II.14). Затем, используя определённую на первом этапе функцию , находим , т.е. первый элемент оптимальной стратегии (II.13).

Теперь, используя уравнение состояния и функцию определяем

и

то есть находим второй элемент оптимальной траектории и оптимальной стратегии и т.д.

_{Наконец, находим} X

, и

Итогом осуществления второго этапа решения задачи является построение оптимальной стратегии оптимальной траектории и определение максимального значения критерия эффективности управления процессом (II.8), т.е. величины . На этом решение задачи в случае 1 заканчивается.

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

, (II.33)

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

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

II-2.6. Решение задач методом динамического программирования

Задача II.3. Планируется распределение начальной суммы средств между предприятиями. Предполагается, что выделенные k-му предприятию в начале планового периода средства приносят доход Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарный доход был максимальным.

Решим задачу 1 по следующим данным: 1) .; ; 2) средства выделяются в размерах, кратных 50 млн. руб; 3) функции заданы в таблице II.1.

Таблица II.1

Пар.сост.\Предприятие	1	2	3	4
50	17	25	20	30
100	30	40	35	45
150	50	48	52	50
200	55	56	30	56
250	60	62	68	68

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

Параметры состояния (количество средств, которые остались нераспределёнными к началу k-го шага) , , параметры управления (количество средств, выделяемое одному предприятию) по условию 2) являются числами, кратными 50 млн. руб. Таким образом, фазовые ограничения имеют вид:

ограничения на управляющие переменные:

или

Уравнение состояния имеет вид

Целевая функция запишется следующим образом:

.

Запишем уравнение Беллмана

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

, т.е.

Первый этап. Расчеты располагаем в двух таблицах – основной (таблица II.3), в которой помещаем результаты условной оптимизации, т.е. последовательности функций , (k= и вспомогательной (таблица II.2), в которой определяем (k= и выполняем условную оптимизацию.

Первые три столбца таблицы II.2 являются общими для всех четырёх шагов: в первом столбце записано состояние в начале k-го шага, во втором – управление на k-м шаге, т.е. в начале k+1-го шага, которое определяется на основании уравнения состояния.

Таблица II.2

0	0	0		0		0	0	0		0	0	0		0	0	0
50	0	50		0		0	30	0+30=30		0	30	30		0	30	30
	50	50		30		20	0	20+0=20		25	0	25		17	0	17
100	0	100		0		0	45	0+45=45		0	50	50		0	75	75
	50	50		30		20	30	20+30=50		25	30	55		17	30	47
	100	0		45		35	0	35+0=35		40	0	40		38	0	38
150	0	150		0		0	50	0+50=50		0	65	65		0	75	75
	50	100		30		20	45	20+45=65		25	50	75		17	55	72
	100	50		45		35	30	35+30+65		40	30	70		38	30	68
	150	0		50		52	0	52+0=52		48	0	48		50	0	50
200	0	200		0		0	55	0+55=55		0	82	82		0	95	95
	50	150		30		20	50	20+50=70		25	65	90		17	75	92
	100	100		45		35	45	35+45=80		40	50	90		38	55	93
	150	50		50		52	30	52+30=82		48	30	78		50	30	80
	200	0		55		60	0	60+0=60		56	0	56		55	0	55
250	0	250		0		0	68	0+68=68		0	90	90		0	107	107
	50	200		30		20	55	20+55=75		25	82	107		17	95	112
	100	150		45		35	50	35+50=85		40	65	105		38	75	113
	150	100		50		52	45	52+45=87		48	50	98		50	55	105
	200	50		55		60	30	60+30=90		56	30	86		55	30	85
	250	0		68		68	0	68+0=68		62	0	62		60	0	60
1	2	3		4		5	6	7		8	9	10		11	12	13

Например, если (первый столбец), то допустимые управляющие решения равны либо 0, либо 50, либо 100 (второй столбец). Состояния в конце шага определяются по уравнениям состояния и принимают значения соответственно 100, 50, 0 (третий столбец).

Первый этап условной оптимизации начинаем с последнего, четвертого шага.

k=4

Запишем уравнение Беллмана

Условная оптимизация выполнена в четвертом столбце таблицы II.2. Так как функция монотонно возрастает (см. табл II.1.), то её максимум достигается при наибольшем значении y₄, то есть при этом , (в четвертом столбце II.2. наибольшие значения функции подчеркнуты). Результаты условной оптимизации четвертого шага помещаем во второй и третий столбцы таблицы II.3.

k=3.

Уравнение Беллмана имеет вид

Условная оптимизация выполнена в 5,6,7-м столбцах таблицы (в столбце семь наибольшие значения функции при каждом подчеркнуты).

Таблица II .3.

0	0	0		0	0		0	0		0	0
50	30	50		30	0		30	0		30	0
150	50	150		65	50(100)		75	50		75	0
200	55	200		82	150		95	100		95	0
250	68	250		90	200		107	50		113	100

Результат условной оптимизации третьего шага помещен в четвертом и пятом столбцах таблицы II.3.

k=2.

Запишем уравнение Беллмана

Условная оптимизация выполнена в 8,9,10-м столбцах таблицы II.2. Результаты условной оптимизации второго шага помещены в шестом и седьмом столбцах таблицы II.3.

k=1

Условная оптимизация выполнена в 11-13-м столбцах табл. II.2. Результаты условной оптимизации первого шага помещены в восьмом и девятом столбцах таблицы II.3.

Второй этап безусловной оптимизации начинаем с первого шага.

k=1

Из восьмого и девятого столбцов таблицы II.3 получаем, что

,

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

k=2

На основании уравнения состояния определяем остаток средств к началу второго шага (следующий элемент оптимальной траектории):

Из седьмого столбца табл. II.3 при определим следующий элемент оптимальной стратегии: , т.е. второму предприятию следует выделить 50 млн. руб.

k=3

На основании уравнения состояния определяем

и из пятого столбца II.3 находим , т.е. третьему предприятию следует выделить 50 млн. руб.

k=4

и из третьего стоблца табл. II.3 находим, что

,

то есть четвертому предприятию следует выделить 50 млн. руб.

Далее определяем

,

то есть средства будут полностью израсходованы.

Итак, оптимальная стратегия распределения 250 млн. руб. между четырьмя предприятиями имеет вид

при этом доход составит 113 млн. руб.

Задача II.4. Планируется деятельность m предприятий на N лет. Известно, что количество средств (основные и оборотные средтсва), вложенных в i-е предприятие, даёт за один год доход , , за счет этого оно уменьшается до ( за счет уменьшения стоимости основных средств).

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

Требуется произвести оптимальное распределение имеющихся ресурсов между m предприятиями в течение N лет.

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

Управляемая система характеризуется одним параметром состояния – - количеством средств, направляемых во все предприятия в начале k-го года.

Управление на k-ом шаге состоит в выборе переменных , , обозначающих средства, выделяемые в k-м году i-му предприятию, т.е. где

(II.34)

Если на k-м шаге принимается управляющее решение , то к началу следующего шага остаток средств, равный , определяет новое состояние системы, т.е.

Показатель эффективности k-го шага равен доходу, полученному от m предприятий в течение k-ого года, т.е.

.

Показатель эффективности всей операции – доход, полученный от m предприятий в течение N лет:

Рассмотрим числовой пример:

На основании (II.34)

откуда

,

т.е. управление можно рассматривать как одномерный вектор ( ),

Запишем рекуррентное уравнение Беллмана

или

Первый этап

Дифференцируя функцию , по и приравнивая производную 0, получим откуда Так как вторая производная от этой функции (-0,02) меньше нуля, является точкой максимума. Следовательно,

или

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

или

откуда

Второй этап

Так как на первом шаге процесса вкладываются все средства,

=10;

=0,7*

=0,7*

=0,7*

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

первого предприятия – (9,96; 6,6; 1);

второго предприятия – (0,04; 0,396; 3,858),

при этом доход за три года составляет 23,388 денежных единиц.

Задача II.5. В трёх районах необходимо построить 5 предприятий одинаковой мощности. Известна функция расходов , характеризующая величину затрат на строительство m предприятий в k-м районе . Данные представлены в табл. II.4. Необходимо разместить предприятия между тремя районами таким образом, чтобы суммарные затраты на их строительство были минимальными.

Рассмотрим операцию размещения предприятий между тремя районами как трёхшаговый процесс, считая за шаг размещение предприятий в одном районе.

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

— количеством предприятий, ещё не размещенных к началу k-го шага, т.е.

Таблица II.4

	0	1	2	3	4	5
,	1	27	50	72	98	122
,	1	22	47	74	96	120
,	1	25	49	72	96	121

Управляющее решение , принимаемое в состоянии , есть решение о размещении в k-м районе предприятий, т.е.

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

В этом случае одношаговый доход

представляет собой затраты на строительство предприятий в k-м районе (см. табл. II.4). Таким образом, функция , является показателем эффективности рассматриваемой операции. Для решения задачи запишем уравнение Беллмана:

Первый этап. Решение сводим в таблицы II.5- II.7.

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

Таблица II.5

	0	1	2	3	4	5
	1	27	50	72	98	122

Таблица II.6

	0	1	2	3	4	5
1	2	3	4	5	6	7	8	9
0	1+1=2	-	-	-	-	-	2	0

Продолжение табл. II.6.

1	2	3	4	5	6	7	8	9
1	1+27=28	22+1	-	-	-	-	23	1
2	1+50=51	22+27	47+1	-	-	-	48	2
3	1+72=73	22+50	47+27	74+1	-	-	72	1
4	1+98=99	22+72	47+50	74+27	96+1	-	94	1
5	1+122=123	22+98	47+72	74+50	96+27	120+1	119	2

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

Таблица II.7

	0	1	2	3	4	5
	1+119	25+94	49+72	72+18	96+23	121+2

Из табл. II.7 получаем

при .

Второй этап

Так как имеет два значения, возможны две стратегии:

По таблице 1.6 находим .

и по таблице II.5 находим

,

т.е. найдена оптимальная стратегия : предприятия размещаются: 1 – во втором и 4 – в первом районах.

Следовательно, найдена вторая оптимальная стратегия (1;1;3), т.е. 3 предприятия размещаются в третьем, 1 – во втором и 1 – в первом районах.