Как решать задачи по динамическому программированию

Как решать задачи по динамическому программированию Вклады Восточный Банк

Задача распределения инвестиций

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

Таблицы могут иметь разный вид.
Таблица 1 – Первый вариант таблицы исходных данных

xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2

* – здесь значение 5 – максимальное значение (сумма для распределения).

Таблица 2 – Второй вариант таблицы исходных данных

x10203040
f1(x)4578
f2(x)3346
f3(x)4456

Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y).

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

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

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

Методы оптимальных решений

Лекция 5

Тема лекции 5: «Задачи динамического программирования в
экономике»

Как решать задачи по динамическому программированию

Разделы лекции:

1. Модели динамического программирования.
Принцип оптимальности Р. Беллмана. Уравнение Беллмана.

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

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

Как решать задачи по динамическому программированию

РАЗДЕЛ 1. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.ПРИНЦИП
ОПТИМАЛЬНОСТИ Р. БЕЛЛМАНА. УРАВНЕНИЕ БЕЛЛМАНА.

ЧТО ТАКОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ?

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

КАКИЕ ЗАДАЧИ РЕШАЮТСЯ МЕТОДАМИ
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

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

– распределе­ния дефицитных капитальных
вложений между новыми направ­лениями их использования;

– разработки правил управления спро­сом
или запасами, устанавливающими момент пополнения запаса и размер пополняющего
заказа;

 
разработки принципов ка­лендарного планирования производства и
выравнивания занятости в условиях колеблющегося спроса на продукцию;

– составле­ния календарных планов
текущего и капитального ремонтов обо­рудования и его замены;

– поиска кратчайших расстояний на транспортной
сети;

– формирование последовательности
развития коммерческой операции и т.д.

В це­лом, математический аппарат ДП  можно представить как пошаговое или поэтапное
программирование. Однако, если в задачах линейного программирования зависи­мости
между критериальной функцией и переменными обяза­тельно линейны, то в задачах
ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать
как для ре­шения задач, связанных с динамикой процесса или системы, так и для
статических задач, связанных, например, с распределением ресурсов. Для
процессов с непрерывным временем ДП рассматривает­ся как предельный вариант
дискретной схемы решения. Получа­емые при этом результаты практически совпадают
с теми, кото­рые получаются методами максимума Л.С. Понтрягина или Га­мильтона
— Якоби — Беллмана. Это значительно расширяет область применения ДП для решения
задач управления. Следует заметить, что методы динамического программирования
успешно применяются и при решении задач, в которых фактор времени не
учитывается. А возможность упрощения про­цесса решения, которая достигается за
счет ограничения области и количества исследуемых при переходе к очередному
этапу ва­риантов, усиливает достоинства этого метода.

НА ЧЕМ ОСНОВАНО РЕШЕНИЕ ЗАДАЧ МЕТОДАМИ ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ?

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

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

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

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

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

Постановку задачи динамического программирования
рас­смотрим на примере инвестирования, связанного с распределе­нием средств
между несколькими предприятиями. В результате управления инвестициями система
последовательно переводится из начального состояния S0 в конечное состояние S
n.  Предположим, что уп­равление можно разбить на n шагов и
решение принимается последовательно на каждом шаге, а управление представляет
собой совокупность
n
пошаговых управлений. На каждом шаге необхо­димо определить два типа переменных
— переменную состояния системы S
k и переменную управления xk. Переменная
S
kопреде­ляет, в каких состояниях может
оказаться система на рассматри­ваемом
k-м шаге. В зависимости от состояния Sk на этом шаге можно
применить некоторые управления, которые характеризу­ются переменной
xk,
удовлетворяющей определенным ограничениям, и называются допустимыми.

Допустим, X = (x1, x2, …, xk, …, xn) – арифметический вектор (X – управление),
переводящий систему из состояния
S0 в состояние Sn,  а Sk
промежуточное состояние системы на
k-м шаге управ­ления. Тогда последовательность состояний
системы можно представить в виде графа (рисунок 1).

Как решать задачи по динамическому программированию

Рисунок
1. Граф состояний системы.

Применение управляющего воздействия xk на каждом шаге переводит
систему в новое состояние S
k и приносит некоторый результат: φk(Sk-1,
xk).
Для каждого возможного состояния на каж­дом шаге среди всех возможных
управлений выбирается опти­мальное управление х*
k такое, чтобы результат, который дости­гается
за шаги с
k-го
по последний
n-й,
оказался бы оптималь­ным. Числовая характеристика этого результата называется функцией
Беллмана F
k(Sk)
и зависит от номера шага
k
и состоя­ния системы S
k-1.

КАК ФОРМУЛИРУЕТСЯ ЗАДАЧА ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ?

Задача динамического программирования
формулируется следующим образом: требуется определить такое управление
X*, переводящее
систему из начального состояния S0  в
конечное со­стояние
Sn,
при котором целевая функция принимает наиболь­шее (наименьшее) значение F(S0,
X*) → extr.

В ЧЕМ ЗАКЛЮЧАЮТСЯ ОСОБЕННОСТИ МОДЕЛИ
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ?

Особенности математической модели
динамического про­граммирования заключаются в следующем:

1) задача оптимизации формулируется как
конечный много­шаговый процесс управления;

2) показатель эффективности или
критерий оптимальности операции определяется целевой функцией, которая является
ад­дитивной функцией от каждого шага оптимизации. То есть

           n

F(X) = ∑ φk(Sk-1, xk);

          k=1        

3) выбор управления хk
на каждом шаге зависит только от состояния системы к этому шагу S
k-1
и не влияет на предшествую­щие шаги (нет обратной связи);

4) состояние системы Sk
после каждого шага управления за­висит только от предшествующего состояния
системы
Sk-1
и уп­равляющего воздействия хk (отсутствие последействия) и может быть
записано в виде уравнения состояния системы:

Sk =fk(Sk-1, xk),
k=1, …, n;

5) на каждом шаге управление xk зависит от конечного числа управляющих
переменных, а состояние системы S
k зависит от ко­нечного числа параметров;

6) оптимальное управление представляет
собой арифметичес­кий вектор X*, определяемый последовательностью оптималь­ных
пошаговых управлений: X* = (x*1, х*2, …, х*
k, …, х*n), число которых и определяет
количество шагов задачи.

Как решать задачи по динамическому программированию

ПРИНЦИП ОПТИМАЛЬНОСТИ И МАТЕМАТИЧЕСКОЕ
ОПИСАНИЕ ДИНАМИЧЕСКОГО ПРОЦЕССА УПРАВЛЕНИЯ.

В основе метода ДП лежит принцип
оптимальности, впервые сформулированный в 1953 г. американским математиком Р.Э.
Беллманом.

КАКОВО БЫ НИ БЫЛО СОСТОЯНИЕ СИСТЕМЫ В
РЕЗУЛЬТАТЕ КАКОГО-ЛИБО ЧИСЛА ШАГОВ, НА БЛИЖАЙШЕМ ШАГЕ НУЖНО ВЫБИРАТЬ УПРАВЛЕНИЕ
ТАК, ЧТОБЫ ОНО В СОВОКУПНОСТИ С ОПТИМАЛЬНЫМ УПРАВЛЕНИЕМ НА ВСЕХ ПОСЛЕДУЮЩИХ
ШАГАХ ПРИВОДИЛО К ОПТИМАЛЬНОМУ ВЫИГРЫШУ НА ВСЕХ ОСТАВШИХСЯ ШАГАХ, ВКЛЮЧАЯ
ВЫИГРЫШ НА ДАННОМ ШАГЕ.

Как решать задачи по динамическому программированию

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

ПРИМЕР 1.

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

Читайте также:  Все вклады Ренессанс Кредит Банка в Москве - условия вкладов Ренессанс Кредит Банка для физических лиц в 2022 на сегодня, ставки

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

ПРИМЕР 2.

Например, при определении количества
средств, вкладываемых в предприятие в
i-м году, необходимо знать, сколько средств осталось в
наличии к этому году,  и какой доход
получен в предыдущем (
i
– 1)-м году.

КАКИЕ ТРЕБОВАНИЯ НЕОБХОДИМО УЧИТЫВАТЬ
ПРИ ВЫБОРЕ ШАГОВОГО УПРАВЛЕНИЯ?

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

1) возможные исходы предыдущего шага Sk-1;

2) влияние управления xk на все
оставшиеся до конца процес­са шаги  (
nk).

В задачах динамического
программирования первое требова­ние учитывают, делая на каждом шаге условные
предположения о возможных вариантах окончания предыдущего шага и проводя для
каждого из вариантов УСЛОВНУЮ ОПТИМИЗАЦИЮ. Выполнение второго требования
обеспечивается проведением БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ в обратном порядке.

В ЧЕМ ЗАКЛЮЧАЕТСЯ УСЛОВНАЯ ОПТИМИЗАЦИЯ?

УСЛОВНАЯ ОПТИМИЗАЦИЯ.
На первом этапе решения задачи, на­зываемом условной оптимизацией, определяются
функция Беллмана и оптимальные управления для всех возможных состояний на
каждом шаге, начиная с последнего в соответствии с алгорит­мом обратной
прогонки. На последнем,
n-м,
шаге оптимальное управление х*
n
определяется функцией Беллмана: F(S) =
maxn(S,xn)}, в соответствии с которой максимум
выбирается из всех возможных значений х
n,  причем хn принадлежит управлению X (xnÎX). Дальнейшие
вычисления проводятся согласно рекуррентно­му соотношению, связывающему функцию
Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В
общем виде это соотношение имеет вид:

Fn(S) = maxn(Sn-1,
xn)
Fk 1(fk(Sk-1,
xk))},
х
kÎХ.

Этот максимум (или минимум)
определяется по всем возмож­ным для
kи Sзначениям переменной управления хnÎХ.

Как решать задачи по динамическому программированию

В ЧЕМ ЗАКЛЮЧАЕТСЯ БЕЗУСЛОВНАЯ
ОПТИМИЗАЦИЯ?

БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.
После того как функция Беллмана и соответствующие оптимальные управления
найдены для всех шагов с
n-го
 по первый, осуществляется второй этап
решения за­дачи, называемый безусловной оптимизацией, проводимой в об­ратном
порядке.

Пользуясь тем, что на первом шаге (k=1) состояние
системы известно – это ее начальное состояние S0, можно  найти опти­мальный результат за все
n шагов и
оптимальное управление на первом шаге
x*1, которое этот результат доставляет. После приме­нения
этого управления система перейдет в другое состояние S1=
f1(S,
x*1),
зная которое, можно, пользуясь результатами ус­ловной оптимизации, найти
оптимальное управление на втором шаге
x*2 и так далее до последнего n-го шага.

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

РАЗДЕЛ 2. ЗАДАЧА ОПТИМАЛЬНОГО
РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ. ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ ОБНОВЛЕНИЯ ОБОРУДОВАНИЯ.

Требуется распределить имеющиесяB
единиц средств среди
nпредприятий, доход gi(xi)
от которых в зависимости от количест­ва вложенных средств
xi определяется матрицей размера (nxn)
(таблица 1), так, чтобы суммарный доход со всех пред­приятий был бы
максимальным. Состояние системы перед каж­дым шагом определяется числом еще не
вложенных средств.

Таблица 1.

Как решать задачи по динамическому программированию

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

Определить вектор X* = (x*1, x*2,…, х*k,
…, х*
n),
удовлетворяющий ус­ловиям:

n

xi= B; (1)

i=1

xi≥0, i =1, …, n; (2)

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

          n

F(X)=∑gi(xi)
→max
. (3)

        i=1

Как решать задачи по динамическому программированию

Теперь необходимо записать рекуррентное
соотношение свя­зи между шагами управления: F
k(x)  и Fk 1(x).

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

С этой целью разобьем процесс
оптимизации на
n
шагов и бу­дем на каждом
k
шаге оптимизировать инвестирование не всех предприятий, а только предприятий с
k-го по n-е. При этом
есте­ственно считать, что в остальные предприятия (с первого по (
k–1)-е тоже
вкладываются средства, и поэтому на инвестирова­ние предприятий с
k-го по n-е остаются
не все средства, а неко­торая меньшая сумма с
k≤В. Эта величина и будет являться
пере­менной состояния системы. Переменной управления на
k-м шаге
назовем величину х
kсредств, вкладываемых в k-е
предприятие. В качестве функции Беллмана
Fk(ck)  на k-м шаге можно выбрать максимально возможный доход, который
можно получить с пред­приятий с
k-го  по n-е при
условии, что на их инвестирование ос­талось с
k средств. Очевидно, что при вложении в k
предприятие х
k
средств будет получена прибыль g
k(xk),
а система к (
k 1)-му
шагу перейдет в состояние S
k 1,  и, следовательно, на инвестиро­вание
предприятий с  (
k 1)-го до n-го останется средств: ck 1=(ck
xk).

Таким образом, на первом шаге условной
оптимизации при
k=n функция
Беллмана представляет собой прибыль только с
n-го предприятия. При этом на его
инвестирование может ос­таться количество средств с
n, где 0≤cnB. Чтобы получить макси­мум прибыли с
этого предприятия, можно, например, вложить в него все эти средства, т.е.
Fn(cn)=gn(cn),
и х
nn.

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

Fk(ck) = max{gk(xk) Fk 1(ckxk)},
по всем х
kck, k=1, …, n. (4)

Как решать задачи по динамическому программированию

Максимум выражения (4) достигается на
некотором зна­чении
x*k, которое
является оптимальным управлением на
k-м шаге для состояния системы Sk. Действуя так, мы можем определить
функцию Беллмана и оптимальные управления по­следовательно вплоть до шага
k=1.

Значение функции Беллмана F1(c1)
представляет собой мак­симально возможный доход со всех предприятий, а значение
х*1, на котором достигается максимум дохода, является оптимальным количеством
средств, вложенных в первое предприятие. Затем на этапе безусловной оптимизации
для всех последующих шагов вычисляется величина
ck=(ck-1xk-1),
 и оптимальным управле­нием на
k шаге является то значение хk, которое
обеспечивает максимум дохода при соответствующем состоянии системы S
k.

ПРИМЕР 3 (ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ
ИНВЕСТИЦИЙ).

На развитие трех предприятий g1, g2, g3 выделено 5
млн. руб. Известна эффективность капитальных вложений в каждое предприятие,
заданная значением нелинейной функции gi(x
i), и представленная в таблице 2.
Необходимо распределить выделенные средства между предприятиями таким образом,
чтобы получить максимальный суммарный доход. Для упрощения расчетов
предполагаем, что распределение средств осуществляется в целых числах:
xi={0, 1, 2, 3,
4, 5} млн. руб.

Таблица 2.

xi

g1

g2

g3

1

2,2

2

2,8

2

3

3,2

5,4

3

4,1

4,8

6,4

4

5,2

6,2

6,6

5

5,9

6,4

6,9

Как решать задачи по динамическому программированию

РЕШЕНИЕ.

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ
(
k=3,2,1).

1-й шаг: k=3. Предположим, что все средства в
количестве
x3=5
млн. руб. отданы третьему предприятию. В этом случае мак­симальный доход, как
это видно из таблицы 3, составит
g3(x3)=6,9
млн. руб., следовательно:
F3(c3)=g3(x3).

 Таблица 3.

Как решать задачи по динамическому программированию

2-й шаг: k=2. Определяем оптимальную стратегию
при рас­пределении денежных средств между вторым и третьим предпри­ятиями. При
этом рекуррентное соотношение Беллмана имеет вид: F2(c2)=
max{g2(x2) – F3(c2–x2)}, по всем x2≤c2. На основе полученного рекуррентного
соотношения составлена таблица 4 по данным таблицы 2.

Таблица 4.

Как решать задачи по динамическому программированию

3-й шаг: k=1. Определяем оптимальную стратегию
при рас­пределении денежных средств между первым и двумя другими предприятиями,
используя следующую формулу для расчета сум­марного дохода:

F1(c1)=max {g1(x1) – F2(c1–x1)}, по всем x1≤c1.

На основе полученного рекуррентного
соотношения составлена таблица 5.

Таблица 5.

Как решать задачи по динамическому программированию

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ
(
k=1,2,3).

Определяем компоненты оптимальной
стратегии.

1-й шаг: k=1. По данным из таблицы 5 максимальный
доход при распределении 5 млн. руб. между тремя предприятиями со­ставляет: с1=5,
F1(5)=10,8 млн. руб. При этом первому предприятию нужно выделить х*1 = 1 млн.
руб.

2-й шаг: k=2. Определяем величину оставшихся
денежных средств, приходящуюся на долю второго и третьего предприятий.

C2=c1 – x*1=5–1=4 млн. руб.

По данным таблицы 4 находим, что оптимальный
вариант распределения денежных средств размером 4 млн. руб. между вто­рым и
третьим предприятиями составляет: F2(4)=8,6 млн. руб., при выделении второму
предприятию
x*2=2
млн. руб.

3-й шаг: k=3. Определяем величину оставшихся
денежных средств, приходящуюся на долю третьего предприятия:

c3=c2 – x*2=4 – 2=2 млн. руб.

Как решать задачи по динамическому программированию

По данным таблицы 5 находим:

F3(2) = 5,4 млн. руб., и x*3=2 млн.  руб.

Таким образом, оптимальный план
инвестирования предпри­ятий:
x*1
= 1 млн. руб.,
x*2=2
млн.  руб.,
x*3=2 млн.  руб.

X* = (1,2,2), который обеспечит
максимальный доход, равный

F(5) = g1(l) g2(2) g3(2) = 2,2 3,2 5,4 = 10,8 млн.  руб.

Как решать задачи по динамическому программированию

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

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

Читайте также:  Вклады на год в ВТБ 24% 13.03.2022 | Банки.ру

Предположим, что планируется
эксплуатация оборудования в течение некоторого периода времени
продолжительностью
n
лет.

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

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

Таблица 6.

Как решать задачи по динамическому программированию

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

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

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

1≤tt k – 1. (5)

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

Таким образом, переменная t в данной
задаче является пере­менной состояния системы на
k-м шаге.

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

xk(t) = (C), если оборудование сохраняется;

xk(t)=(З), если оборудование заменяется.

Как решать задачи по динамическому программированию

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

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

Если в начале каждого года сохраняется
оборудование, возраст которого t лет, то доход за этот год составит
r(t). К началу (k 1)-го года
возраст оборудования достигнет (
t 1),  и макси­мально
возможный доход за оставшиеся годы (с (
k 1)-го по n-й) составит Fk 1(t 1).

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

Fk(t)  = max{r(t) Fk 1(t 1)} в случае
(С);

Fk(t) 
=
max{S(t) – P r(0) Fk 1(1)}
в случае (З).

Как решать задачи по динамическому программированию

Функция Fk(t) вычисляется на каждом шаге управления
для всех
t
удовлетворяющих условию: 1≤
tt0 k – 1. (5)  Управление, при котором достигается мак­симум
дохода, является оптимальным.

Для первого шага условной оптимизации
при
k=n функция Беллмана
представляет собой доход за последний
n-й год:

Fn(t) 
=
max{r(t)} в случае (С);  Fn(t) 
=
max{S(t) – P r(0)} в случае (З).
(6)

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

ПРИМЕР 4 (ВЫБОР ОПТИМАЛЬНОЙ СТРАТЕГИИ
ЗАМЕНЫ ОБОРУДОВАНИЯ).

Найти оптимальную стратегию
эксплуатации обору­дования на период продолжительностью 6 лет, если годовой до­ход
r(
t)
и остаточная стоимость S(t) в зависимости от возраста за­даны в таблице 7,
стоимость нового оборудования равна Р = 13 у.е.,  а возраст оборудования к началу
эксплуатационного периода со­ставлял 1 год.

Таблица 7.

Как решать задачи по динамическому программированию

РЕШЕНИЕ.

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ
(
k=
6, 5, 4, 3, 2, 1).

1-й шаг: k=6. Для первого шага возможные
состояния систе­мы
t=1,
2, 3, 4, 5, 6, а функциональные уравнения (6) имеют вид:

Как решать задачи по динамическому программированию

2-й шаг: k=5. Для второго шага возможные состояния
систе­мы  
t=1, 2, 3,4, 5;  а функциональное уравнение (6) имеет вид:

в соответствии с которым вычисляем:

Как решать задачи по динамическому программированию

3-й шаг: k=4; Для третьего шага возможные
состояния систе­мы 
t=1,2, 3,4;  а функциональное уравнение (6) имеет вид:

в соответствии с которым вычисляем:

Как решать задачи по динамическому программированию

4-й шаг: k=3; t= 1, 2, 3.

Тогда

Как решать задачи по динамическому программированию

5-й шаг: k=2; t=1,2. Из функционального уравнения (6)
получим:

Как решать задачи по динамическому программированию

6-й шаг: k= 1; t =1. Тогда из (6) имеем:

Как решать задачи по динамическому программированию 

Результаты вычислений по уравнениям
Беллмана F
k(t) приве­дены
в таблице 8, в которой
k
 год эксплуатации, а
t – возраст оборудования.

Таблица 8.

Как решать задачи по динамическому программированию

В таблице 8 выделено значение функции,
соответствующее состоянию «З» — замена оборудования.

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ
(
k=1,
2, 3, 4, 5, 6).

Безусловная оптимизация начинается с
шага при
k=1.
Мак­симально возможный доход от эксплуатации оборудования за го­ды с 1-го по
6-й составляет
F1(1)
= 37. Этот оптимальный выиг­рыш достигается, если на первом году не производить
замены оборудования. Тогда к началу второго года возраст оборудования увеличится
на единицу и составит:
t2
=
t1 1=1 1=2.
Безус­ловно, оптимальное управление при
k=2, x2(2) = (С), т.е.
макси­мум дохода за годы со 2-го по 6-й достигается, если оборудование сохраняется,
т.е. не заменяется.

К началу третьего года при k=3 возраст
оборудования станет t3=
t2 1=2 1=3.
Безусловное оптимальное управление:
x3(3)=(З), т.е.
для получения максимума прибыли за оставшиеся годы необхо­димо в этом году
провести замену оборудования.

К началу четвертого года при k=4 возраст
оборудования ста­нет равен
t4=1.
Безусловное оптимальное управление
x4(1) = (С).

Далее соответственно для оставшихся
шагов
k=5
и
k=6
получим:

k=5, 
t5=t4 1=1 1=2; x5(2)=(C);

k=6, 
t6=t5 1=2 1=3; x6(3)=(C).

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

Как решать задачи по динамическому программированию

РАЗДЕЛ 3. ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА
ПЕРЕВОЗКИ ГРУЗОВ.  ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ.

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

Пусть транспортная сеть состоит из 10
узлов. На рисунке 2 по­казаны сеть дорог и стоимость перевозки единицы груза
между пунктами сети. Ребра являются вариантами выбора решения. Необходимо
определить маршрут доставки груза из пункта 1 в пункт 10, обеспечивающий наименьшие
транспортные расходы.

Как решать задачи по динамическому программированию

Рисунок
2. Модель транспортной сети.

В задаче имеется ограничение —
двигаться по изображенным на схеме маршрутам можно только слева направо, то
есть, попав, например, в пункт 7, мы имеем право переместиться только в пункт 10
и не можем возвратиться обратно в 5-й или 6-й. Эта особен­ность транспортной
сети дает право отнести каждый из десяти пунктов к одному из поясов. Будем
считать, что пункт принадлежит к
k-му поясу, если из него можно попасть в конечный пункт ровно
за
k
шагов, т.е. с заездом ровно в (
k–1)-й
промежуточный пункт. Таким образом, пункты 7, 8 и 9 принадлежат к первому
поясу, 5 и 6 — ко второму, 2, 3 и 4 — к третьему и 1 — к четвертому. Тогда на
k -м шаге
будем находить оптимальные маршруты перевозки гру­за из пунктов
k-го пояса до
конечного пункта. Оптимизацию бу­дем производить с конца процесса, и потому,
дойдя до
k-то
шага, неизвестно, в каком из пунктов
k-го пояса окажется груз, перево­зимый из первого пункта.

Введем обозначения:

k – номер шага (k=1, 2, 3, 4);

i – пункт, из которого осуществляются
перевозки (
i=1,2,…,
9);

j – пункт, в который доставляется груз (j=2, 3,…,
10);

cij стоимость перевозки груза из пункта i в пункт j.

Fk(i) – минимальные затраты на перевозку
груза на
k
шаге решения задачи из пункта
i
до конечного пункта.

Читайте также:  Банковская гарантия: что это, виды, бухгалтерский учет и как получить банковскую гарантию

Как решать задачи по динамическому программированию

Очевидно, что минимум затрат на
перевозку груза из пунктов
k-то
пояса до пункта 10 будет зависеть от того, в каком пункте этого пояса мы
оказались. Номер
i
пункта, узел, принадлежащий
k-му  поясу, будет являться переменной состояния
системы на
k
шаге. Поскольку оптимизация осуществляется с конца процесса, то, находясь в
некотором пункте
ik-то
пояса, принимается реше­ние о перемещении груза в один из пунктов (
k – 1)-го
пояса, а на­правление дальнейшего движения известно из предыдущих ша­гов. Номер
j
пункта (
k
– 1)-го пояса будет переменной управле­ния на
k-м шаге.

Для первого шага управления (k=1) функция
Беллмана пред­ставляет собой минимальные затраты на перевозку груза из пунк­тов
1-го пояса в конечный пункт, т.е. F1(i) =
ci10. Для последую­щих шагов затраты
складываются из двух слагаемых  – стоимости
перевозки груза
cijиз пункта ik-го пояса в пункт j (k – 1)-го по­яса
и минимально возможных затрат на перевозку из пункта
j до конечного пункта, т.е. Fk-1(j),
Таким образом, функциональное уравнение Беллмана будет иметь вид:

Fk(i) = min{cij Fk-1(j)} по всем j(j=2,
3,…, 10).  (
7)

Минимум затрат достигается на некотором
значении
j*,
кото­рое является оптимальным направлением движения из пункта
i в конечный
пункт.

На четвертом шаге попадаем на 4-й пояс;
состояние системы становится определенным
i=1. Функция F4(1) представляет со­бой
минимально возможные затраты по перемещению груза из 1-го пункта в 10-й.
Оптимальный маршрут определяется в ре­зультате анализа всех шагов в обратном
порядке, а выбор некото­рого управления
j на k-м шаге приводит к тому, что состояние
си­стемы на (
k
– 1)-м шаге становится определенным.

ПРИМЕР 5 (ВЫБОР ОПТИМАЛЬНОГО МАРШРУТА
ПЕРЕВОЗКИ ГРУЗОВ).

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

ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ.

1-й шаг: k=1. Функциональное уравнение Беллмана
(7) на первом шаге имеет вид:
F1(i)=Ci,10.
Все возможные перемещения груза на первом шаге и резуль­таты расчета приведены
в таблице 9. На первом шаге в пункт 10 груз может быть доставлен из пунктов 7,
8 или 9 (см.: таблица 9).

Таблица 9.

Как решать задачи по динамическому программированию

2-й шаг: k=2. Функциональное уравнение (7) на
втором шаге принимает вид:

F2(i) = min{Cij
F1(j)} по всем j.

Все возможные перемещения груза на втором
шаге и резуль­таты расчета приведены в таблице 10.

Таблица10.

Как решать задачи по динамическому программированию

3-й шаг: k=3. Функциональное уравнение Беллмана
(7) на третьем шаге имеет вид:

F3(i) = min{Cij F2(j)} по всем j.

Все возможные перемещения груза на третьем
шаге и резуль­таты расчета приведены в таблице 11.

Таблица 11.

Как решать задачи по динамическому программированию

4-й шаг: k=4. 
Функциональное уравнение Беллмана (7) на четвертом  шаге имеет вид:

F4(i) = min{Cij F3(j)} по всем j.

Все возможные перемещения груза на
четвертом шаге и резуль­таты расчета приведены в таблице 12.

Таблица 12.

Как решать задачи по динамическому программированию

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.

На этапе условной оптимизации получено,
что минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют
F4(1) = 20.
Данный результат достигается при движении груза из 1-го пункта в 3-й. По данным
таблицы 11, из пункта 3 необходимо двигаться в пункт 6, затем — в пункт 7 (см.
таблица 10) и из него – в конечный пункт (см. таблица 9). Таким образом,
оптимальный маршрут доставки груза: 1→3→6→7→10. (На рисунке
3 он по­казан «двойными» стрелками.)

Как решать задачи по динамическому программированию

Рисунок
3. Транспортная сеть с оптимальным маршрутом.

ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ.

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

Из условия следует, что состояние
экономической системы характеризуется двумя параметрами: количеством принятых и
 оформленных машин по разгрузке товара и
количеством машин, отправленных с товаром в магазины. Поэтому решение будем
искать на плоскости
XOY,
в прямоугольнике, который является областью допустимых состояний системы. Если
по оси
OX
отложить число
n
разгруженных машин, а по оси
OY—
число
m
загруженных товаром машин, то можно построить на плоско­сти
XOYграф состояний процесса, в котором каждая вершина харак­теризует
состояние операции приема и отгрузки товара на опто­вой базе. Ребра этого графа
означают выполнение работы по приему или отправке товара на очередной машине.
Каждому ребру можно сопоставить издержки, связанные с выполнением опера­ции по
разгрузке или загрузке машины.

ПРИМЕР 6 (ПОСТРОЕНИЕ ОПТИМАЛЬНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ В КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ).

Пусть на оптовую базу прибыло 6 машин с
товаром для раз­грузки и 4 машины для загрузки товаров, направляемых в магазины
(то есть
n=6,
m=4). Известны затраты по выполнению каждой операции, которые показаны на
ребрах графа (рисунок 4). Точка S0 определяет начало процесса, а
S1 – конечное
состоя­ние, соответствующее приему и отправке всех машин. Оптимиза­цию процесса
будем производить с конечного состояния —
S1. Весь процесс разобьем на шаги, их
количество
k=n m= 6 4=10. Каждый
шаг представляет собой сечение графа состояний, про­ходящее через вершины (на
рисунке 4 сечения показаны косыми линиями).

Как решать задачи по динамическому программированию

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

 ЭТАП 1. УСЛОВНАЯ ОПТИМИЗАЦИЯ.

1-й шаг: k=1. На первом шаге с задаваемым
сечением А1, В1 из состояний A1 и B1 возможен только один вариант перехода в конечное
состояние S1. Поэтому в вершинах
A1 и B1 записываем соответственно издержки 8 и 11. Ребра A1S1
и B1S1 обозначаем стрелкой, направленной в вершину
S1, как показано на рисунке 5.

Как решать задачи по динамическому программированию

Рисунок 5. Фрагмент связи операции (шаг
1).

2-й шаг: k=2. Второй шаг оптимизации задается
сечением по вершинам A2, В2,
C1.
Из состояний
A2
и С1 возможен единствен­ный переход в вершины A1 и В1 соответственно, поэтому в
вер­шинах
A2
и
C1
записываем суммарные издержки 17 и 22 на первых двух шагах перехода в конечное
состояние
S1.

Из вершины B2 возможны два варианта перехода: в
вершину А1 или вершину В1. При переходе B2→A1 сумма издержек состав­ляет
10 8=18, на переходе
B2→В1
сумма составляет 13 11=24. Из двух вариантов суммарных издержек выбираем
наименьшую (18) и обозначаем стрелкой условно оптимальный переход B2→A1, как
показано на рисунке 6.

Как решать задачи по динамическому программированию

Рисунок
6. Сетевая модель операции (шаг 2).

3-й шаг: k=3. На третьем шаге сечение проходит
через вер­шины
A3,
B3,
С2,
D1.
Из вершин А3 и D1 возможен единственный переход в вершины A2 и
C1
соответственно. Суммарные издержки для состояния
D1 равны 22 12=34. Из вершины B3 возможны два
варианта перехода: в вершину
A2
издержки равны 17 8=25; в вершину
B2 издержки равны: 18 9=27.

Для вершины C2 возможен переход в
вершину
B2
(издержки: 18 10=28) и в вершину C1 (издержки: 22 12=34). Выбираем для вершин В3
и C2 наи­меньшие суммарные издержки и обозначаем стрелкой условно оптимальный
переход, как показано на рисунке 7.

Как решать задачи по динамическому программированию

Рисунок
7. Сетевая модель операции (шаг 3).

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

Как решать задачи по динамическому программированию

Рисунок
8. Сетевая модель связи расходов операций.

Минимально возможные суммарные издержки
по обслужи­ванию всех 10 машин на оптовой базе составляют 88 у. е.

ЭТАП 2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ.

Определяем оптимальную траекторию на
исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая,
что выбор некоторого управления на
k-м шаге приво­дит к тому, что состояние на (k – 1)-м шаге
становится опреде­ленным. В результате строим ориентированный граф перехода из
со­стояния S0 в состояние
S1,
представленный на рисунке 9; на каж­дом шаге безусловной оптимизации переход
почти всегда единст­венный и совпадает с построенными условно оптимальными пе­реходами.

Как решать задачи по динамическому программированию

Рисунок
9. Оптимальная последовательность операций.

Минимальные издержки Fmin
соответствуют следующему оп­тимальному пути на графе:

(S0→E6 →D6 →D5→D4→D3→C3→B3→A2→A1→S1);

и равны: Fmin=12 9 9 7 7 10 9 8 9 8=88 усл. ед.

ВЫВОД. В
соответствии с решением, оптимальное уп­равление процессом разгрузки и загрузки
машин товаром состо­ит в следующем: на первом шаге следует оформить документы
по разгрузке одной машины, на втором  – по
загрузке одной маши­ны, далее обслуживать три машины по разгрузке товара, три
ма­шины по загрузке и на последних двух шагах оформить докумен­ты по разгрузке
двух машин.

СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

[1] Таха Х.А. Введение
в исследование операций.
6-е изд. Пер. с англ. — М.: Издательский дом
«Вильямс»
, 2001. — 912 с: ил.

[2] Фомин Г. П.Математические
методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и
доп. — М.: Финансы и статистика, 2005. — 616 с: ил.

Как решать задачи по динамическому программированию

 [3] Шелобаев С. И. Математические методы и модели в
экономике,  финансах, бизнесе: Учебное
пособие для вузов. — М.: ЮНИТИ – ДАНА, 2001. – 367 с.

[4] Шикин Е.
В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное
пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический
университетский учебник»).

[5]
Экономико-математические методы и прикладные модели: Учебное пособие для вузов/
В.В. Федосеев, А.Н. Гармаш,  Д.М.
Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. – 391 с.

Как решать задачи по динамическому программированию

Оцените статью
Adblock
detector