Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
иваемый временной промежуток - плановый период (п/п) с тем, чтобы суммарная прибыль за этот период была оптимальной.
Введем обозначения.
r(t) - стоимость продукции, производимой за год на оборудовании возраста t;
s(t) - остаточная стоимость оборудования возраста t;
u(t) - эксплуатационные издержки за год оборудования возраста t;
p - цена нового оборудования, которым можно заменить устаревшее:
n - число лет в рассматриваемом п/п.
Для дискретности решения задачи возраст оборудования t будем отсчитывать с интервалом 1 год. Управление составляют два возможных решения на каждом этапе (в начале каждого года): сохранение - продолжение эксплуатации имеющегося оборудования; замена - реализация старого оборудования по остаточной стоимости и приобретение нового по цене p. Целевая функция - суммарная прибыль за п/п F>max. Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, т.к. оно уже досконально изучено.
б) Схема решения.
Задача решается методом ДП на основе принципа оптимальности Беллмана. В процессе обратного хода рассматриваются этапы - временные шаги от конца п/п к его началу.
Введем последовательность функций: zi(t), i = - максимальная прибыль за последние i лет п/п. Очевидно, что zn(t0) = max F = F*, где t0 - возраст оборудования в начале п/п. Итак, сначала рассматриваем только последний 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), то заменить.
1(t) = max
Теперь включаем в рассмотрение предпоследний шаг, (n - 1)-й год, i = 2 и установим прибыль за два последних года z2 (t).
Пусть в начале (n - 1)-го года возраст оборудования t, и было принято решение о его сохранении. Тогда прибыль к концу года зависит r (t) - u (t). При этом на начало n-го года оборудование уже будет иметь возраст t+1, следовательно, в последнем году оно даст прибыль z1(t+1), а общая прибыль за два последних года составит r (t) - u (t) + z1(t+1).
Если же в начале (n-1)-го года выбрано управление замена, то прибыль за два последних года составит s (t) - p + r (0) - u (0) + z1(1), следовательно,
z2(t) = max
Аналогично для i последних лет:
zi(t) = max
Дойдя до последнего шага (i = n), попадаем в начало п/п, где t известно: t = t0, и, следовательно, можно начать прямой ход.
Задавая t0 и длительность п/п, находим F* = zn(t0) и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.
в) Расчет.
Для заполнения расчетной таблицы можно использовать следующий алгоритм.
. Определить ? (t) = r(t) - u(t), m1 = S(t) - p + ?(0):
если m1 = const, то справа к таблице прибавляется дополнительный столбец mi;
если m1 = m1(t), то над каждой строкой zi(t) вводится дополнительная строка mi = mi(t) (или mi(t) вписывается в клетки значений zi(t) как тарифы транспортной задачи).
. Заполнить строку z1(t), переписав из таблицы данных соответствующие значения ?(t) ? m1, все значения ?(t) < m1 заменить на m1.
. Начиная с индекса i = 2, расчет по строкам производится в следующей последовательности:
а) вычислить mi = m1 + zi-1(1), где zi-1(1) берется из уже заполненной строки;
б) вычислить zi(t) = z1(t) + zi-1(t+1), где сумма и слагаемые образуют треугольник, у которого одна из вершин всегда в первой строке над искомым значением, а 2-ая - в последней заполненной строке следующего столбца. Получаемые значения zi(t) ? mi вносить в соответствующие клетки строки; начиная с первого zi(t) < mi, оставшиеся клетки заполнить значением mi;
в) клетки с первым значением zi(t) < mi в процессе заполнения таблицы отделить от расположенных в строке левее разделительной границей смены управления;
г) если таблица не заполнена до последней строки, перейти к п. а) и выполнить расчет для следующего значения индекса i.
Замечания:
. Для задачи об оптимальном распределении капиталовложений по полученной расчетной таблице можно получить стратегию вложения средств, например, только в первые 3 филиала, исключив из рассмотрения 4-й, или, например, для суммы в 150 млн. руб. (а не 200 ) между 4-мя филиалами, или только 3-мя первыми и т.д.
Для задачи о замене по расчетной таблице можно получить решение на любой п/п длительностью, не превосходящей исходный.
Это так называемый принцип погружения метода динамического программирования.
2. Решенную задачу о замене оборудования можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом имеется три возможных управления: сохранить старое, купить новое, купить не новое.
5. Задача управления производством и запасами
Предприятие производит партиями некоторые изделия. Оно получило заказы на n месяцев. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение. Обозначим:
) xj - число изделий, производимых в j-м месяце;