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

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

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

Таблица II.1

Пар.сост.\Предприятие

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

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

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

или

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

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

.

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

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

, т.е.

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

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

Таблица II.2

0+30=30

20+0=20

0+45=45

20+30=50

35+0=35

0+50=50

20+45=65

35+30+65

52+0=52

0+55=55

20+50=70

35+45=80

52+30=82

60+0=60

0+68=68

20+55=75

35+50=85

52+45=87

60+30=90

68+0=68

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

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

k =4

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

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

k =3.

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

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

Таблица II.3.

				50(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)

откуда

,

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

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

или