Динамическое программирование

 

1.4  ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ

 

Требуется распределить имеющиеся В единиц средств среди n предприятий, доход g_i(x_i) от которых, в зависимости от количества вложенных средств х_i, определяется матрицей (n*n), приведенной в табл. 1, так, чтобы суммарный доход со всех предприятий был бы максимальным.

 

 

 

 

Таблица 1

x  \ gi	g1	g2	…	gi	…	gn
x1	g1(x1)	g2(x1)	…	gi (x1)	…	gn (x1)
x2	g1(x2)	g2(x2)	…	gi (x2)	…	gn (x2)
xi	…	…	…	gi(xi)	…	…
xn	g1(xn)	g2(xn)	…	…	…	gn (xn)

 

Запишем математическую модель задачи.

Определить  X* = (х^*₁, х^*₂, …, х^*_i, …, х^*_n), удовлетворяющий условиям

и обеспечивающий максимум целевой функции

F(X) = ∑x_i g_i ( x_i ) → max

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

С этой целью разобьем процесс  оптимизации на n шагов и будем  на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с k-го по n-е. При этом естественно считать, что в остальные предприятия (с первого по (k–1)-е тоже вкладываются средства, и поэтому на инвестирование предприятий с k-го по n-е остаются не все средства, а некоторая меньшая сумма С_k ≤ В. Эта величина и будет являться переменной состояния системы. Переменной управления на k-м шаге назовем величину х_k средств, вкладываемых в k-e предприятие. В качестве функции Беллмана F_k(C_k) на k-м шаге можно выбрать максимально возможный доход, который можно получить с предприятий с k-го по n-е при условии, что на их инвестирование осталось С_k средств. Очевидно, что при вложении в k-e предприятие х_k средств будет получена прибыль g_k(x_k), а система к (k+1)-му шагу перейдет в состояние S_k+1 и, следовательно, на инвестирование предприятий с (k+1)-го до n-го останется С_k+1 = (С_k – х_k) средств.

Таким образом, на первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств С_n, 0 ≤ С_n ≤ В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е. F_n(С_n) = g_n(С_n) и х_n = С_n.

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на k-м шаге для инвестирования предприятий с k-го по n-е осталось С_k средств (0 ≤ С_k ≤ В). Тогда от вложения в k-e предприятие х_k средств будет получена прибыль g_k(C_k), а на инвестирование остальных предприятий (с k-го по n-е) останется            С_k+1 = (С_k – х_k) средств. Максимально возможный доход, который может быть получен с предприятий (с k-го по n-е), будет равен:

F_k (C_k) = max {g_k(x_k ) + F_k+1 (с_k - x_k )} , k = 1, …, n

Максимум выражения  достигается на некотором значении х^*_k, которое является оптимальным управлением на k-м шаге для состояния системы S_k. Действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага k = 1.

Значение функции Беллмана F₁(c₁) представляет собой максимально возможный доход со всех предприятий, а значение х^*₁, на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина С_k = (С_k-1 – х_k-1) оптимальным управлением на k-м шаге является то значение х_k, которое обеспечивает максимум дохода при соответствующем состоянии системы S_k.

 

 

1.5 ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ

 

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

Предположим, что  планируется эксплуатация оборудования в течение некоторого периода  времени продолжительностью n лет. Оборудование имеет тенденцию с течением времени  стареть и приносить все меньший доход r(t)          (t – возраст оборудования). При этом есть возможность в начале любого года продать устаревшее оборудование за цену S(t), которая также зависит от возраста t, и купить новое оборудование за цену P.

Под возрастом  оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Требуется найти оптимальный план замены оборудования с тем, чтобы суммарный доход за все n лет был бы максимальным, учитывая, что к началу эксплуатации возраст оборудования составлял t₀ лет.

Исходными данными  в задаче являются доход r(t) от эксплуатации в течение одного года оборудования возраста t лет, остаточная стоимость S(t), цена нового оборудования P и начальный возраст оборудования t₀.

Таблица 2

t	0	1	…	n
r	r(0)	r(1)	…	r(n)
S	S(0)	S(1)	…	S(n)

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

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

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

1 ≤ t ≤ t₀ + k – 1

Это выражение свидетельствует о том, что t не может превышать возраст оборудования за (k–1)-й год его эксплуатации с учетом возраста к началу первого года, который составляет t₀ лет; и не может быть меньше единицы (этот возраст оборудование будет иметь к началу k-го года, если замена его произошла в начале предыдущего (k–1)-го года).

Таким образом, переменная t в данной задаче является переменной состояния системы на k-м шаге. Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года:

x_k(t) = { С, если оборудование сохраняется

                                      {  З, если оборудование заменяется

Функцию Беллмана F_k(t) определяют как максимально возможный доход от эксплуатации оборудования за годы с k-го по n-й, если к началу k-го возраст оборудования составлял t лет. Применяя то или иное управление, система переходит в новое состояние. Так, например, если в начале k-го года оборудование сохраняется, то к началу (k + 1)-го года его возраст увеличится на единицу (состояние системы станет t+1), в случае замены старого оборудования новое достигнет к началу (k + 1)-го года возраста t = 1 год.

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

Если в начале каждого года сохраняется оборудование, возраст которого t лет, то доход за этот год составит r(t). К началу (k+1)-го года возраст оборудования достигнет (t+1) и максимально возможный доход за оставшиеся годы (с (k+1)-го по n-й) составит F_k+1(t+1). Если в начале k-го года принято решение о замене оборудования, то продается старое оборудование возраста     t лет по цене S(t), приобретается новое за P единиц, а эксплуатация его в течение k-го года нового оборудования принесет прибыль r(0). К началу следующего года возраст оборудования составит 1 год и за все оставшиеся годы с (k+1)-го по n-й максимально возможный доход будет F_k+1(1). Из двух возможных вариантов управления выбирается тот, который приносит максимальный доход.

Функция F_k(t) вычисляется на каждом шаге управления для всех                1 ≤ t ≤ t₀ + k – 1. Управление при котором достигается максимум дохода, является оптимальным.

Значения функции F_n(t), определяемые F_n-1(t), F_n-2(t) вплоть до F₁(t). F₁(t₀) представляют собой возможные доходы за все годы. Максимум дохода достигается при некотором управлении, применяя которое на первом году, мы определяем возраст оборудования к началу второго года. Для данного возраста оборудования выбирается управление, при котором достигается максимум дохода за годы со второго по n-й и так далее. В результате на этапе безусловной оптимизации определяются годы, в начале которых следует произвести замену оборудования.

        

2   РАСЧЕТНАЯ ЧАСТЬ

Построение  оптимальной последовательности операций в коммерческой деятельности

Пример

Пусть на оптовую  базу «Ларес» прибыло 10 машин с товаром для разгрузки и   8 машин для загрузки товаров, направляемых в магазины. Материально-ответственное лицо оптовой базы осуществляет оформление документов по операциям разгрузки или загрузки для одной машины, а затем переходит к обслуживанию другой машины. Известны затраты по выполнению каждой операции, которые показаны на ребрах графа (рис. 2). Издержки от операций обусловлены простоем транспорта, типом операции (прием или отправка товара) и не зависят от конкретной машины. Необходимо спланировать последовательность операций обоих видов таким образом, чтобы суммарные издержки по приему и отправке товаров для всех машин были минимальными.

Решение:

Из условия  следует, что состояние экономической системы характеризуется двумя параметрами: количеством принятых и оформленных машин по разгрузке товара и количеством машин, отправленных с товаром в магазины. Поэтому решение будем искать на плоскости X0Y, на ограниченном прямыми прямоугольнике, который является областью допустимых состояний системы. Если по оси X отложить число (10) разгруженных машин, а по оси Y – число (8) загруженных товаром машин, то можно построить на плоскости граф состояний процесса, в котором каждая вершина характеризует состояние операции приема и отгрузки товара на оптовой базе. Ребра этого графа означают выполнение работы по приему или отправке товара на очередной машине. Каждому ребру можно сопоставить издержки, связанные с выполнением операции по разгрузке или загрузке машины.

Точка S₀ определяет начало процесса, a S₁ – конечное состояние, соответствующее приему и отправке всех машин. Оптимизацию процесса будем производить с конечного состояния S₁. Весь процесс разобьем на шаги, их количество k = n + m = 10 + 8 = 18. Каждый шаг представляет собой сечение графа состояний, проходящее через вершины (на рис. 2 сечения показаны косыми линиями).

    К=18     К=17    К=16      К=15    К=14    К=13     К=12       К=11      К=10     К=9

Рисунок 2 – Графическая схема связи операций

 

I этап. Условная оптимизация.

1-й шаг. k = 1. На первом шаге, с задаваемым сечением А₁В₁, из состояний      А₁ и B₁ возможен только один вариант перехода в конечное состояние S₁. Поэтому в вершинах А₁ и B₁ записываем соответственно издержки 13 и 10. Ребра A₁S₁ и B₁S_l обозначаем стрелкой, направленной в вершину S₁, как показано на рис. 3.