4.Задача о замене.

а) Постановка задачи.

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

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

r(t) – стоимость продукции, производимой за год на оборудовании возрастаt;

s(t) – остаточная стоимость оборудования возрастаt;

u(t) – эксплуатационные издержки за год оборудования возрастаt;

p– цена нового оборудования, которым можно заменить устаревшее:

n– число лет в рассматриваемом п/п.

Для дискретности решения задачи возраст оборудования tбудем отсчитывать с интервалом 1 год. Управление составляют два возможных решения на каждом этапе (в начале каждого года): «сохранение» – продолжение эксплуатации имеющегося оборудования; «замена» – реализация старого оборудования по остаточной стоимости и приобретение нового по ценеp. Целевая функция – суммарная прибыль за п/пF→max. Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, т.к. оно уже досконально изучено.

б) Схема решения.

Задача решается методом ДП на основе принципа оптимальности Беллмана. В процессе «обратного хода» рассматриваются этапы – временные шаги от конца п/п к его началу.

Введем последовательность функций: z_i(t),i=– максимальная прибыль за последниеiлет п/п. Очевидно, чтоz_n(t₀) =maxF=F*, гдеt₀– возраст оборудования в начале п/п. Итак, сначала рассматриваем только последнийn-ый год п/п,i= 1. Пусть в начале этого года, когда оборудование имеет возрастtлет, выбирается одно из управлений: 1) сохранение оборудования наn-ый год, тогда прибыль за оставшийся год п/п составитr(t) –u(t); 2) замена новым, продажа старого по остаточной стоимости, тогда прибыль составитs(t) –p+r(0) –u(0), гдеr(0) – стоимость продукции, на новом оборудовании за 1-й год его эксплуатации,u(0) – эксплуатационные издержки нового оборудования за 1-й год. Определяем оптимальное управление, исходя из критерия замены:

- если s(t) –p+r(0) –u(0) ≤r(t) –u(t), то «сохранить»,

- если s(t) –p+r(0) –u(0) >r(t) –u(t), то «заменить».

z₁(t) =max

Теперь включаем в рассмотрение предпоследний шаг, (n– 1)-й год,i= 2 и установим прибыль за два последних годаz₂(t).

Пусть в начале (n– 1)-го года возраст оборудованияt, и было принято решение о его сохранении. Тогда прибыль к концу года зависитr(t) –u(t). При этом на началоn-го года оборудование уже будет иметь возрастt+1, следовательно, в последнем году оно даст прибыльz₁(t+1), а общая прибыль за два последних года составитr(t) –u(t) +z₁(t+1).

Если же в начале (n-1)-го года выбрано управление ”замена”, то прибыль за два последних года составитs(t) –p+r(0) –u(0) +z₁(1), следовательно,

z₂(t) =max

Аналогично для iпоследних лет:

z_i(t) =max

Дойдя до последнего шага (i=n), попадаем в начало п/п, гдеtизвестно:t=t₀, и, следовательно, можно начать ”прямой ход”.

Задавая t₀и длительность п/п, находимF* =z_n(t₀) и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.

в) Расчет.

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

1. Определить φ (t) =r(t) –u(t),m₁=S(t) –p+ φ(0):

- если m₁=const, то справа к таблице прибавляется дополнительный столбецm_i;

- если m₁=m₁(t), то над каждой строкойz_i(t) вводится дополнительная строкаm_i=m_i(t)

(или m_i(t) вписывается в клетки значенийz_i(t) как тарифы транспортной задачи).

2. Заполнить строку z₁(t), переписав из таблицы данных соответствующие значения

φ(t) ≥m₁, все значения φ(t) <m₁заменить наm₁.

3. Начиная с индекса i= 2, расчет по строкам производится в следующей последовательности:

а) вычислить m_i=m₁+z_i-1(1), гдеz_i-1(1) берется из уже заполненной строки;

б) вычислить z_i(t) =z₁(t) +z_i-1(t+1), где сумма и слагаемые образуют треугольник, у

которого одна из вершин всегда в первой строке над искомым значением, а 2-ая - в

последней заполненной строке следующего столбца. Получаемые значения z_i(t) ≥m_i

вносить в соответствующие клетки строки; начиная с первого z_i(t) <m_i, оставшиеся

клетки заполнить значением m_i;

в) клетки с первым значением z_i(t) <m_iв процессе заполнения таблицы отделить от

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

г) если таблица не заполнена до последней строки, перейти к п. а) и выполнить расчет

для следующего значения индекса i.

Замечания:

1. Для задачи об оптимальном распределении капиталовложений по полученной расчетной таблице можно получить стратегию вложения средств, например, только в первые 3 филиала, исключив из рассмотрения 4-й, или, например, для суммы в 150 млн. руб. (а не 200 ) между 4-мя филиалами, или только 3-мя первыми и т.д.

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

Это так называемый «принцип погружения» метода динамического программирования.

2. Решенную задачу о замене оборудования можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом имеется три возможных управления: сохранить старое, купить новое, купить не новое.