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

Аналогично вычислим значения функции для третьего шага (n = 3):

f3(2) = min(c2,4 + f2(4); c2,5 + f2(5)) = min(20; 16) = 16, s = 2, j3(2) = 4;

f3(3) = min(c3,4 + f2(4); c3,6 + f2(6)) = min(18; 25) = 18, s = 3, j3(3) = 4.

Занесем данные в таблицу.

Таблица 2.7

Вычисления для четвертого шага (п = 4).

f4(1) = min(c1,2 + f3(2); c1,3 + f3(3)) = min(19; 20) = 19, s = 1, j4(1) = 2.

Таблица 2.8

Очевидно, что минимальные затраты f4(1) = 19 и оптимальный маршрут проходит через вторую вершину, так как j4(1) = 2. Далее из таблицы 2.7 при s = 2 следует, что оптимальный маршрут проходит через вершину 4, так как j3(2) = 4. Продолжая рассмотрение таблиц, для п = 2 определяем, что оптимальный маршрут проходит через вершину 7 (j2(4) = 7). Наконец, из вершины 7 попадаем в конечную вершину 10. Таким образом, двигаясь от последней таблицы к первой, определяем оптимальный маршрут = (1 – 2 – 4 – 7 – 10), затраты прохождения пути составляют f4(1) = 3 + 6 + 3 + + 7 = 19.

2.2 Задачи планирования производственной программы

В задачах планирования производственной программы естественное деление на шаги, т. е. число шагов совпадает с числом месяцев (количеством плановых отрезков времени п).

Пример 1

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

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

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

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

Решение.

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

f0(0) = 0.

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

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

x1(i) = d1 – i;

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

i =

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

Таблица 2.9

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

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

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

В таблице 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 = 3 и x = 1 уровень запасов на конец отрезка равен нулю, поэтому в соответствующей клетке второе слагаемое равно нулю. При i = 2 и x = 4 уровень запасов на конец отрезка равен 2, следовательно, в соответствующей клетке таблицы второе слагаемое равно 4. Наконец, третье слагаемое есть ранее вычисленное значение f1(i + x – d2) = f1(i + x – 4),взятое из таблицы 2.9.

Таблица 2.10

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