Динамическое программирование в математике

Динамическое программирование это поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг

Планируя многоэтапную операцию, мы должны выбирать управление на каждом шаге, исходя не из узких интересов именно этого шага, а из более широких интересов операции в целом, и далеко не всегда эти две точки зрения совпадают

Практическая часть Компания, занимающаяся производством пищевых продуктов, поставляет их для продажи в четыре города. Этим городам поставлены в соответствие торговые зоны 1, 2, 3, 4. В каждой из зон проведено изучение состояния рынка и найдены математические ожидания доходов, как функции полных капиталовложений (складские помещения, магазины, торговые уполномоченные, реклама и т.д.) Задача о распределении вложений

Математические ожидания доходов Вложения, в млн. руб. Торговые зоны

Необходимо распределить имеющиеся 10 млн. рублей так, чтобы суммарный доход по всем зонам, в которые производились вложения, был максимален.

Введем следующие обозначения: f i (x) – доход, получаемый от вложения х млн. в i-ю зону, i=1,2,3,4; F 1,2 (А) – максимальный доход, получаемый от вложения А млн. в зоны 1 и 2 вместе; F 1,2,3 (А) – максимальный доход, получаемый от вложения А млн. в зоны 1, 2 и 3 вместе; F 1,2,3,4 (А) – максимальный доход, получаемый от вложения А млн. в зоны 1, 2, 3 и 4 вместе.

Функцию F1,2 (А) определим равенством: F1,2(А)=max [f1 (x)+f2(A-x)]

Таким образом, чтобы определить F1,2(2), надо вычислить: f1(0)+f2(2)= =0.41 f1(1)+f2(1)= =0.53 f1(2)+f2(0)=0.45+0=0.45 F 1,2 (2)=0.53

Максимальный доход, получаемый от вложения А млн. в зоны 1 и 2 вместе Вложени е (А) f 1 (x)f 2 (x)F 1,2 (A)Оптимальная стратегия при вложении в зоны 1 и (0,0) (1,0) (1,1) (2,1) (3,1) (3,2) (3,3) (4,3) (5,3) (6,3) (7,3)

Аналогично определим функцию F1,2,3(A) формулой: F1,2,3(A)=max {F1,2(x)+f3(A-x)}

Максимальный доход, получаемый от вложения А млн. в зоны 1, 2 и 3 вместе AF 1,2 (A)f 3 (x)F 1,2,3 (x) Оптимальная стратегия вложений в зоны 1,21,2,3 0000(0,0)(0,0,0) (1,0)(1,0,0) (1,1)(1,1,0) (2,1)(2,1,0) (3,1)(3,1,0) (3,2)(3,2,0) (3,3)(3,2,1) (4,3)(3,3,1) (5,3)(4,3,1) (6,3)(5,3,1) (3,3,3) (7,3)(4,3,3)

Теперь определим функцию F1,2,3,4(A)формулой: F1,2,3,4(A)=max {F1,2,3(x)+f4(A-x)}

Максимальный доход, получаемый от вложения А млн. в зоны 1, 2, 3 и 4 вместе AF 1,2,3 (A)f 4 (x)F 1,2,3,4 (x)Оптимальная стратегия вложений в зоны 1,2,31,2,3,4 0000(0,0)(0,0,0) (1,0,0) (1,1,0) (2,1,0) (3,1,0) (3,2,0) (3,2,1) (3,3,1) (4,3,1) (5,3,1) (3,3,3) (4,3,1,1) (3,3,1,2) (7,3)(4,3,1,2)

Оптимальные распределения вложений Вложения Оптимальные стратегии Максимальный доход Зона 1Зона 2Зона 3Зона