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

В таблице 2.10 приведены все возможные значения сумм c2(x) + h(i + x d2) + f1(i + x – d2). Здесь предусмотрено по одной строке для каждого возможного значения начального уровня запаса i, который не должен превышать min (d1 + d2, M), и по одному столбцу для возможных значений выпуска х. Поскольку спрос на продукцию в каждом месяце должен быть удовлетворен, а уровень запасов конец каждого отрез

ка не может превысить 4 ед., некоторые клетки в таблице зачеркнуты. Эти клетки соответствуют недопустимым сочетаниям значений i и х. Так, если i = 0, то спрос удается удовлетворить только при условии х 4. Если i = 4, то х 2, иначе запас на конец планового периода будет больше нуля. В каждой клетке таблицы слева от двойной черты записана сумма трех слагаемых. Первое слагаемое – значение c(x), второе слагаемое – затраты на содержание запасов, равные уровню запасов на конец отрезка, умноженному на h = 2. Так, например, при i = 2 и x = 4 уровень запасов на конец отрезка равен 2, следовательно, в соответствующей клетке таблицы второе слагаемое равно 4. Наконец, третье слагаемое есть ранее вычисленное значение f1(i + x – d2) = f1(i + x – 4),взятое из таблицы 2.9.

Значение функции 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 = , 3 – i x 5.

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

Таблица 2.15

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

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

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

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

Таблица 2.16

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

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

2.3 Задачи оптимального распределения средств на расширение производства

В задачах оптимального распределения средств на расширение производства естественное деление на шаги, т. е. число шагов совпадает с числом предприятий.

Пример 1

Производственному объединению из четырех предприятий выделяется банковский кредит в сумме 60 млн. ден. ед. для реконструкции и модернизации производства с целью увеличения выпуска продукции. Значения gi(xi) (i = ) дополнительного дохода, получаемого на предприятиях объединения в зависимости от выделенной суммы xi, приведены в таблице 2.17. Распределить выделенный кредит между предприятиями так, чтобы дополнительный доход объединения был максимальным.

Таблица 2.17

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