Использование метода динамического программирования для решения экономических задач

f1(Sn – 1) = (Rn(Sn – 1, Un) + f0(Sn));

2. найти Rn(Sn – 1, Un) из дискретного набора его значений при некоторых фиксированных Sn – 1 и Un из соответствующих допустимых областей (так как

3.

f0(Sn) = 0, то f1(Sn – 1) = Rn(Sn – 1, Un))

В результате после

первого шага известно решение Un и соответствующее значение функции f1(Sn – 1);

4. уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При l = n – k (k = ) оно имеет вид

fk(Sn – k) = (Rn–k+1(Sn – k, Un–k+1) + fk–1(Sn–k+1)); (1.2)

5. найти условно-оптимальное решение на основе выражения (1.2);

6. проверить, чему равно значение l. Если l = 0, расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если l 0, перейти к выполнению пункта 3;

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

1.4 Планирование производственной программы

Предприятие изготавливает машины, спрос на которые в каждом из месяцев равен Dt (t = ) единиц. Запас машин на складе предприятия на начало планируемого периода i0 единиц. Пусть общие затраты ct(xt, it) состоят из затрат c(xt) на производство машин и затрат hit на их содержание до отправки потребителю, т.е.

ct(xt, it) = c(xt) + hit

В свою очередь затраты c(xt) на производство машин складываются из условно-постоянных k и пропорциональных lxt (l единиц на каждую единицу продукции). Таким образом, для любого месяц

c(xt) = k + lxt

Затраты на хранение единицы продукции равны h, поэтому затраты на содержание запасов численно равны уровню запасов на конец месяца, умноженному на h. Складские площади предприятия ограничены, и хранить можно не более M единиц продукции. Производственные мощности также ограничены, и в каждом месяце можно изготовить не более B единиц продукции. Требуется определить производственную программу изготовления машин xt, удовлетворяющую спрос в каждом из месяцев планируемого периода Dt (t = ) и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен нулю.

Для решения задачи методом динамического программирования и записи рекуррентного соотношения будем использовать следующие обозначения: n (n = ) – номер планируемого отрезка времени (соответствует обратной нумерации месяцев); j – уровень запаса на конец отрезка; dn – спрос на продукцию на n-м отрезке (d1 = DT, d2 = DT-1, …, dn = D1); cn(x, j) – затраты, связанные с выпуском х единиц продукции на n-м отрезке и с содержанием запасов, объем которых на конец n-го отрезка равен j единиц; fn(i) – значение функции, равное затратам на производство и хранение продукции за n последних месяцев при условии, что уровень запасов на начало n-го месяца составляет i единиц; xn(i) – производство продукции на n-м отрезке, если уровень запасов на начало отрезка равен i единиц.

Число шагов решения задачи совпадает с числом месяцев (количеством плановых отрезков времени п). Так как уровень запасов на конец планового периода, должен равен нулю, то для п = 0

f0(0) = 0 (1.3)

Перейдем к рассмотрению первого отрезка (n = 1). Запас i1 на начало этого отрезка неизвестен. Однако ясно, что он может быть равен любому неотрицательному целому числу, не превышающему вместимости склада и спроса в рассматриваемом отрезке, т.е. не должен превышать min(d1, M). Для полного удовлетворения спроса на последнем отрезке объем должен быть равен d1 – i1. Следовательно,

f1(i) = c1(x1, j1) = c1(d1 – i, j1) = c1(d1 – i, 0), (1.4)

где i = 0, 1, ., min(d1, M).

Перейдем ко второму шагу (n = 2). Уровень запасов на начало второго отрезка равен i. При этом величина i может принимать любые неотрицательные целочисленные значения, не превышающие min(d1 + d2, M). Целочисленные значения х (обьем выпуска) во втором отрезке при заданном i должен быть не меньше, чем d2 – i (спрос на данном отрезке должен быть удовлетворен), но не больше min(d1 + d2 – i, B), так как запас на конец планового периода равен нулю и производство продукции в любом отрезке не превышает В. Минимальные суммарные затраты на производство и хранение продукции за два последних месяца

f2(i) = min(c2(x, i + x – d2) + f1(i + x – d2)), (1.5)

где i = 0, l, ., min (d1 + d2, M);

d2 – i x min (d1 + d2 – i, B).

Аналогично можно записать рекуррентное соотношение для n = 3. Общее рекуррентное соотношение имеет вид

fn(i) = min (cn(x, i + x – dn) + fn–1(i + x – dn)) (n = ) (1.6)

где i = 0, 1, …, min (d1 + d2 + … + dn, M);

dn – i x min (d1 + d2 + … + dn – i, B).

В выражении (1.6) величина i + x – dn = jn характеризует уровень запасов на конец отрезка п.

Заметим, что, поскольку уровень запасов i на начало каждого месяца (за исключением первого) неизвестен, необходимо учесть все возможные его значения и произвести поочередно вычисления: f1(i), i = 0, 1, ., min(d1, M), f2(i), i = 0, l, ., min (d1 + d2, M), …, fn – 1(i), i = 0, 1, …, min (d1 + d2 + +… + dn –1, M), fn(i0), i0 – известная величина.

На основании полученных расчетов находится объем выпуска продукции в каждом месяце, соответствующий оптимальному решению задачи. Для первого месяца планового периода он равен xN(i0) и позволяет достичь fN(i0). Уровень запасов на начало второго месяца iN – 1 = i0 + xN(i0) – dN, а объем выпуска во втором месяце xN – 1(iN – 1). Рассматривая таким образом плановые отрезки до конца планового периода, находим объем выпуска в каждом из месяцев.

1.5 Оптимальное распределение средств на расширение производство

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

Группе предприятий выделяются дополнительные средства на реконструкцию и модернизацию производства. По каждому из п предприятий известен возможный прирост gi(x) (i = ) выпуска продукции в зависимости от выделенной суммы х. Требуется так распределить между предприятиями средства с, чтобы общий прирост fn(c) выпуска продукции был максимальным.

 Скачать реферат