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

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

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

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

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

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

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

7 Введем следующие обозначения: 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 вместе.

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

9 Таким образом, чтобы определить 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

10 Максимальный доход, получаемый от вложения А млн. в зоны 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)

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

12 Максимальный доход, получаемый от вложения А млн. в зоны 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)

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

14 Максимальный доход, получаемый от вложения А млн. в зоны 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)

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