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

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

Рассмотрим несколько примеров.

10.1. Задача об инвестировании предприятий

Требуется оптимальным образом распределить 120 (R=120) ед. средств между тремя предприятиями (m=3), прибыль от которых в зависимости от количества вложенных средств (х) определяется таблицей

Здесь f_i (x_j ) – прибыль i–го предприятия при вложении в него x_j средств так, чтобы суммарная прибыль со всех предприятий была максимальна.

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

.                                                                    (1)

Очевидно, что при вложении в к-е предприятие  средств мы получим прибыль f_k() . Неизвестные (параметры управления) удовлетворяют ограничениям:

                                                                  (2)

Требуется найти неизвестные , удовлетворяющие системе ограничений (2) и обращающие в максимум функцию (1).

Обычно  называют оптимальным управлением.

Первый этап. Условная оптимизация

1. Разобьем процесс решения задачи на m=3 шагов (номер шага совпадает с номером предприятия).

2. Начнем оптимизацию с последнего третьего шага. Пусть мы подошли к этому шагу с остатком средств 0≤С₃≤R. Очевидно, надо вложить всю сумму С₃ целиком в последнее предприятие, чтобы получить максимум прибыли. Поэтому условное оптимальное управление на 3-м шаге - отдать последнему предприятию все имеющиеся средства С₃, т.е. , а условная оптимальная прибыль .

3. Перейдем к предпоследнему шагу (m-1=2). Допустимые средства на 2-м шаге могут быть: .

Пусть мы подошли к этому шагу с остатком средств С₂.

Обозначим  условную оптимальную прибыль на двух последних шагах (m-1=2)-м и (m =3)-м (который уже оптимизирован).

Если мы выделим на 2-м шаге 2-му предприятию средства х₂, то на последний шаг останется С₃ = С₂ - х₂ .

Обычно С_m  = С_m-1-х _m-1  (m=1,2,3), где С_m –количество средств, оставшихся после к- го шага, называют уравнением  состояния.

Прибыль на последних двух шагах будет составлять

.

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

Тогда

, при .

4.Перейдем к 1-му шагу, т.е. мы перейдем к 1-му предприятию. Количество средств перед первым шагом R=120, т.е. допустимое количество средств может быть только С₁= 120.Тогда:

Второй этап. Безусловная оптимизация

1 шаг .k=1

С₁= R =120, , , т.е. максимальный доход, который может быть достигнут при вложении R =120 ед. в три предприятии, равен 141, при этом первому предприятию следует выделить   ед.

2 шаг .k=2

На основании уравнения состояния определяем остаток средств к началу второго шага ,,, т.е. второму предприятию следует выделить  30 ед.

3 шаг .k=3

,  ,, т.е. третьему предприятию следует выделить  30 ед. Итак, оптимальный план инвестирования предприятий  принесет прибыль

Z^* = Z₁(120) = max Z = 141 ед. средств, т.е. максимум суммарной прибыли равен 141 при условии, что 1-му предприятию выделено 60 ед., 2-му и 3-му – по 30 ед. средств.

10.2. Задача о замене оборудования