Преимущество пошагового решения задач динамического программирования

«+»Вместо решения сложной экономической задачи мы разбиваем ее на несколько этапов и решаем поэтапно, увязывая при этом один этап с другим. Целевая функция может быть как линейной, так и нелинейной.

«-»- большой объем вычислений

- отсутствие универсальности метода решения

- задача должна четко делиться на этапы

Общий вид решения задач динамического программирования может быть представлен рисунком:

S0

X₂

Sk

X₁

S₀ – область начальных допустимых решений.

S_k – область конечных оптимальных решений.

Задача состоит в том, чтобы найти такую траекторию движения от S₀ до S_k, которая при переводе системы из начального положения в конечное, обеспечивает получение оптимального значения целевой функции.

Одна из типичных задач динамического программирования – это задача распределения ресурсов отрасли экономики.

Задача: Необходимо распределить ресурсы между объектами по годам с тем, чтобы за весь планируемый период эффективность используя планируемых ресурсов, была максимальна.

Общая постановка: - исходное количество средств, надо их распределить между двумя предприятиями (объектами). X- это количество средств, выделенных для первого объекта. Y - это количество средств, выделенных для второго объекта. - это заданная отдача (эффективность) на каждый руб. вложенный к ср-в X. - это заданная отдача (эффективность) на каждый руб. вложенный к ср-в Y.

По условию оставшиеся к концу года, средства снова перераспределяются между объектами.

Цель: max распределить ресурсы по объектам и годам, чтобы за весь планируемый период, получить max V доходов.

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

2 полушаг – запланированные средства тратятся, происходит производственный процесс и следовательно получение дохода.

Для i – го года средств начального года будет X_i и y_j, т.е. столько сколько осталось от (i-1) – го года:

(со штрихом - это остатки к концу года).

Y (все средства в y)

Z₀

Y₁ C

D 1

H E

G

B

0 x₁

Z₀ (все средства в x)

Точка С (x₁, y₁) – координаты на начало первого года, показывает сколько вложили в первый объект X и второй объект Y.

Пусть СD обозначенный 1- это производство в первом году (средства тратятся, получается доход). Точка D - это средства оставшиеся на конец первого года.

Пусть 1=DE – это перераспределение оставшихся первого года между двумя объектами.