(динамическое программирование)
В трех районах города предприниматель планирует строительство пользующихся спросом одинаковых по площади мини-магазинов “Продукты”. Известны места, в которых их можно построить. Подсчитаны затраты на их строительство и эксплуатацию.
Необходимо так разместить мини-магазины, чтобы затраты на их строительство и эксплуатацию были минимальные.
Значения функции gi(х) приведены в таблице (gi(х) – функция расходов в ден. ед., характеризующая величину затрат на строительство и эксплуатацию в зависимости от количества размещаемых предприятий в i-м районе).
6.
x 1 2 3 4
g1(x), ден. ед. 10 21 29 45
g2(x), ден. ед. 11 22 30 36
g3(x), ден. ед. 9 20 28 40
Решение:
Решение задачи проводим с использованием рекуррентных соотношений:
для первого района: φ1(x)=g1(x)
для остальных районов: φ k(x)= min{φ k(xk) + φ k-1(x- xk )}, k =