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

Значение функции f2(i), записанное в правом крайнем столбце таблицы 2.10, представляет собой минимальную из всех сумм в клетках строки для каждого фиксированного i, а x2(i) – соответствующий выпуск продукции. Например, при i = 0 оптимальный выпуск равен 6 ед., так как наименьшая сумма в этой строке (23 + 4 + 0) находится в столбце, соответствующем х = 6.

Для п = 3 рекуррентное соотношение

имеет вид

f3(i) = min(c3(x) + h(i + x – d3) + f2(i + x – d3))

где i = , 4 – i x 6.

Расчет значений f3(i) приведен в таблице 2.11:

Таблица 2.11

Аналогично для п = 4 рекуррентное соотношение имеет вид

f4(i) = min(c4(x) + h(i + x – d4) + f3(i + x – d4)),

где i = i0 = 2, d4 – i0 = 1 x 6 = min (d1 + d2 + d3 + d4 – i, B).

Расчет значений f4(i) приведен в таблице 2.12. Таблица состоит из двух строк: заглавной и предназначенной для записи вычислений при начальном уровне запаса i0 = 2. Здесь можно сделать предположений о значениях i, так как запас на начало первого месяца планового периода известен.

Таблица 2.12

Минимальные затраты, связанные с производством и хранением продукции за четыре месяца, f4(i) = 56.

При x4 = 5 уровень запасов на начало второго месяца (конец первого) равен i3 = i0 + x4 – d4 = 2 + 5 – 3 = 4. Рассматривая строку таблицы 2.11, соответствующую i3 = 4, видим, что x3 = 0. Поскольку запас продукции на начало третьего месяца равен нулю (i2 = i3 + x3 – d3 = 4 + 0 – 4 = 0), из таблицы 2.10 находим x2 = 6. Аналогично i1 = i2 + x2 – d2 = 0 + 6 – 4 = 2, из таблицы 2.9 находим x1 = 0. Таким образом, чтобы достичь оптимальных затрат, равных 56 единицам, требуется в первый месяц изготовить 5 машин, во второй – 0, в третий – 6 и в четвертый – 0.

Пример 2

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

с(0) = 0, с(1) = 13, с(2) = 15, с(3) = 17, с(4) = 19, с(5) = 21, с(6) = 23

Плановый период состоит из четырех месяцев

(t = ). D1 = 3, D2 = 3, D3 = 2, D4 = 4, i0 = 1, h = 1, B = 5, M = 4

Решение.

Рассмотрим n = 0 (отрезок за пределом планового периода). В соответствии с формулой (1.3) уровень запасов на конец планового периода равен нулю: f0(0) = 0.

D1 = d4 = 3, D2 = d3 = 3, D3 = d2= 2, D4 = d1= 4.

Для п = 1 (см. формулу (1.4)):

x1(i) = d1 – i;

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

i =

Расчет всех значений f1(i) выполним в таблице 2.13, где f1(i) = c1(2 – i).

Таблица 2.13

Для второго отрезка (n = 2) значения функции f2(i) вычисляются по формуле (1.5):

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

где i = , 2 – i x 5.

Таблица 2.14

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