Оптимизация динамических систем

1. Путешественник должен добраться из пункта А в пункт Б, посетив по дороге несколько промежуточных пунктов:

а) на первом этапе путешественник может добраться из пункта А до одного из промежуточных пунктов 1, 2, 3 или 4, причем расстояния до этих пунктов равны 450, 250, 350 и 500 км соответственно;

б) на втором этапе путешественник должен добраться из выбранного им пункта 1, 2, 3 или 4 до одного из промежуточных пунктов 5, 6, 7 или 8. Расстояние от пункта 1 до пункта 5 равно 400 км, до пункта 6 – 350 км, а в пункты 7 или 8 из пункта 1 дороги нет. Расстояние от пункта 2 до пункта 5 равно 500 км, до пункта 6 – 450 км, до пункта 7 – 500 км, а в пункт 8 из пункта 2 дороги нет. Расстояние от пункта 3 до пункта 6 равно 450 км, до пункта 7 – 400 км, до пункта 8 – 400 км, а в пункт 5 из пункта 3 дороги нет. Наконец, расстояние от пункта 4 до пункта 7 равно 400 км, до пункта 8 – 300 км, а в пункты 5 или 6 из пункта 4 дороги нет;

в) на третьем этапе путешественник должен добраться из выбранного им пункта 5, 6, 7 или 8 до одного из промежуточных пунктов 9 или 10. Расстояние от пункта 5 до пункта 9 равно 400 км, а в пункт 10 из пункта 5 дороги нет. Расстояние от пункта 6 до пункта 9 равно 350 км, до пункта 10 – 450 км. Расстояние от пункта 7 до пункта 9 равно 550 км, до пункта 10 – 350 км. Наконец, расстояние от пункта 8 до пункта 10 равно 300 км, а в пункт 9 из пункта 8 дороги нет.

г) на четвертом этапе путешественник должен добраться из выбранного им пункта 9 или 10 до конечного пункта Б. Расстояние от пункта 9 до пункта Б равно 500 км. Расстояние от пункта 10 до пункта Б равно 400 км.

Найти кратчайший маршрут, применив метод динамического программирования (то есть, выписав уравнение Беллмана и решив его).

2. Финансово-промышленная группа выделяет 4 миллиона рублей для инвестирования трех предприятий. Ожидается, что на i -м предприятии инвестированные средства х_i принесут прибыль в размере F_i(х_i) миллионов рублей, i =1,2,3. Предполагается, что сумма денег, вложенных в одно предприятие, может принимать только целочисленные значения, т.е. .

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

3. Фирма вырабатывает план замены однотипного оборудования. Планирование производится на 7 лет вперед, после чего фирма прекращает существование, распродав оборудование по остаточной стоимости. Считается, что замена может осуществляться в начале любого года (практически моментально), причем частичная замена оборудования невозможна (т.е. или менять все, или не менять ничего). Стоимость приобретения нового оборудования и замены старого оборудования на новое составляет p миллионов рублей. После замены старое оборудование продается по остаточной стоимости. Известно, что прибыль от реализации продукции, произведенной за год на оборудовании, эксплуатировавшемся до этого t лет, , определяется формулой миллионов рублей. Остаточная стоимость определяется формулой миллионов рублей.

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

а) p=9 миллионов рублей;

б) p=17 миллионов рублей.

4. Динамика фирмы описывается моделью (в безразмерных переменных)

K_{t+ 1} =K_t + (1 – u_t) δ K_t , K₀ = 1,

C_{t+ 1} = C_t + u_t δ K_t , C₀ = 0,

где t = 0,1,2,…, T -1. В этой модели

K_t – стоимость основных фондов к началу периода [ t, t +1];

C_t – суммарные дивиденды с момента 0 до начала периода [ t, t +1];

u_t – доля дивидендов в период [ t, t +1] в прибыли фирмы, которая считается равной δ K_t, где δ – заданный постоянный параметр.

Величина u_t является управлением в модели, причем 0 ≤ u_t ≤ 1, t =0,1,2,…, T -1.

Пользуясь методом динамического программирования, построить оптимальное управление, максимизирующее суммарные дивиденды за весь период времени [0, T ], то есть С_T.

а) δ = 0.6; T = 4;

б) δ = 0.4; T = 4.