ЗАДАНИЕ 5. Тема: «ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ».

Задача 5.1

Для реконструкции и модернизации производства на четырех предприятиях выделены денежные средства С = 80 ден. ед. По каждому предприятию известен возможный прирост g_i(х) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы. Требуется:

1) распределить средства С между предприятиями так, чтобы суммарный прирост продукции на всех четырех предприятиях достиг максимальной величины;

2) используя решение основной задачи, найти оптимальное распределение 80 ден. ед. между тремя предприятиями.

Необходимые числовые данные приведены в табл. 5.1.

Таблица 5.1

Задача 5.2

В начале планового периода продолжительностью 6 лет имеется обо­рудование, возраст которого t. Оборудование не должно быть старше 6 лет. Известны: стоимость r(t) продукции, произведенной в течение года с помощью этого оборудования; ежегодные расходы u(t), связанные с экс­плуатацией оборудования; его остаточная стоимость s; стоимость р нового оборудования, включающая расходы, связанные с установкой, наладкой и запуском оборудования. Требуется:

1) составить матрицу максимальных прибылей f_n(t) за 6 лет;

2)сформировать по матрице максимальных прибылей оптимальные
стратегии замены оборудования возрастов t и t₁ лет в плановом периоде
продолжительностью 6 и N лет.

Необходимые данные приведены в табл. 5.2.

Таблица 5.2

Методические указания

Рассмотрим задачу о замене оборудования.

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

В начале планового периода N = 4 годам, имеется оборудование, возраст которого t = 2 года. Для каждого года планового периода известны
стоимость r(t) произведенной с использованием имеющегося оборудования
продукции и затраты v(t), связанные с его эксплуатацией. Эти характеристики зависят от возраста оборудования. Известны также остаточная стоимость оборудования s = 4 ден. ед., не зависящая от его возраста, и стоимость нового оборудования р = 13 ден, ед., не меняющаяся в рассматриваемом плановом периоде. Срок эксплуатации данного оборудова­ния не более 6 лет.

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

Состояние системы (S) будем характеризовать возрастом оборудова­ния t = 0, 1,.... Значение t = 0 соответствует новому оборудованию. Пусть х_i - управление на i-м шаге, которое имеет два варианта - "сохранение" и "замена".

Рассмотрим основное функциональное уравнение на последнем, N-м шаге: .

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

.

Если при этом в начале года выбрано управление "сохранение", то прибыль выражается разностью , если же выбрано управление "замена", то прибыль можно записать в виде .

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

При произвольном шаге (i < N) основное функциональное уравнение принимает вид . Прибыль на i-м шаге по-прежнему определяется парой формул: , если вы­брано управление "сохранение", и – в противо-положном случае.

Применим рассмотренный алгоритм к решению конкретной задачи. Начнем с последнего, четвертого года планового периода. Имеем:

- в случае "сохранения" оборудования и

- в случае его "замены".

Составляем первую таблицу, рассматривая все возможные начальные состояния оборудования, т.е. его возраст S₃ = 1 – 6 лет.

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

Переходим к анализу ситуации перед третьим годом исследуемого периода.

- в случае "сохранения" оборудования и

- в случае его "замены".

Теперь следует оптимизировать расходы за двухлетний период (по­следний и предпоследний годы). Оптимальную прибыль за четвертый год следует взять из первой таблицы. Подчеркнем, что - возраст оборудования в начале третьего года сразу после принятия решения о его сохране­нии или замене; - возраст оборудования к концу третьего года. Данные в колонку F₄ переносятся из предыдущей таблицы в соответствии со значе­нием параметра

.

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

Последняя таблица завершает условную оптимизацию.

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

Матрица максимальных прибылей.

Сформулируем оптимальную политику в отношении оборудования, возраст которого 2 года. В таблице для t = 2 в первой колонке стоит сум­марная прибыль 33 ден. ед. за четыре года, при этом выбор управления – "замена". К началу второго года возраст оборудования составит 3 года, поэтому в следующей колонке мы выбираем строку, соответствую­щую возрасту 3 года. Оптимальная прибыль за второй - четвертый годы -24 ден. ед., и мы находимся в области "замены" оборудования, следова­тельно, к началу третьего года оборудование будет иметь возраст 1 год. Прибыль за третий - четвертый годы для такого оборудования равна 21 деи. ед., за последний, четвертый год - 10 ден. ед.и находятся в области “сохранения”. Таким образом, рекомендуется замена оборудования в начале второго года.