Задача скачана с сайта http://www.MatBuro.ru

©МатБюро - Решение задач по высшей математике

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

ЗАДАНИЕ. Для двух предприятий выделено a единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f₁(_x), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(_y). Остаток средств к концу года составляет g₁( )x для первого предприятия и g₂(_y) для второго предприятия. Задачу решить методом динамического программирования.

РЕШЕНИЕ. Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

 Обозначим a_k = x_k + y_k - средства, которые распределяются на k –ом шаге как сумма средств по предприятиям.

             Суммарный доход от обоих предприятий на k –ом шаге:

 z_k = f₁(x_k ) + f₂(a_k − x_k ) = 3x_k + 2(a_k − x_k ) = 2a_k + x_k

            Остаток средств от обоих предприятий на k –ом шаге:

 a_k+₁ = g₁(x_k ) + g₂(a_k − x_k ) = 0,1x_k + 0,5(a_k − x_k ) = 0,5a_k − 0,4x_k

 Обозначим z - максимальный доход, полученный от распределения средств a_k между двумя предприятиями с k -го шага до конца рассматриваемого периода.  Рекуррентные соотношения Беллмана для этих функций

z

z

            Проведем оптимизацию, начиная с четвертого шага:

            4-й шаг.

 Оптимальный доход равен: .к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е.

при x₄ = a₄.

            3-й шаг.

                                                                             1

Задача скачана с сайта http://www.MatBuro.ru

©МатБюро - Решение задач по высшей математике

z{2a₃ +x₃ + 3(0,5a₃ − 0,4x₃)}⁼ ₀^max_≤x3≤_a3{3,5a₃ − 0,2x₃)}= 3,5a₃, т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е.

при x₃ = 0.

            2-й шаг.

z.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е.

при x₂ =0.

            1-й шаг.

z.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е.

при x₁ = 0 .

            Результаты оптимизации:

z^∗(a ) = 3,875a ; x^∗ = 0 z

            Определим количественное распределение средств по годам:

Т., получаем a₂ = 0,5a₁ − 0,4x₁ = 500. Далее аналогично: x x x

            Представим распределение средств в виде таблицы:

            При таком распределении средств за 4 года будет получен доход, равный

z

                                                                             2