Динамическое программирование (методические указания). Методические указания и задания для лабораторной работы по теме Динамическое программирование. Одесса 2004

• Название: Методические указания и задания для лабораторной работы по теме Динамическое программирование. Одесса 2004
• Дата: 23.05.2021
• Размер: 419.5 Kb.
• Имя файла: Динамическое программирование (методические указания).doc
• Тип: Методические указания; #208568
• страница: 3 из 4

Так как условная оптимизация ведется на всех шагах по единообразным равенствам (1.13) и (1.14), то первые три столбца табл. 3 являются общими для всех трех шагов. Состояния в начале и в конце k-гoшага и управление на k-мшаге обозначены через _k-1, _k и x_k. Поясним вначале порядок заполнения этих столбцов. Если _k-1 = 40, то соответствующие управ­ления могут быть x_k = 0 и x_k = 40 (2-й столбец). Соответ­ствующие состояния в конце шага определяются по урав­нению состояния _к = _к-1-х_ки принимают соответствен­но значения 40-0 = 40 и 40-40 = 0 (3-й столбец). Так последовательно заполняются три столбца для _k-1 = 40; 80; 120; 160; 200.

Теперь перейдем к выполнению условий оптимизации на 3-м шаге. При этом используются формулы Z₃(₂, x₃) = f₃(x₃) + Z₄^*(₃) и Z₃^*(₂) = Z₃(_2,х₃),которые в 4, последовательно развернуты по строкам в 4,5 и 6-м столбцах. Если ₂ = 40, х₃ = 0 и ₃ = 40 (1-я строка первых трех столбцов), то получим f₃(x_з) = f₃(0) =0 (из табл. 1), Z₄^*(₃)=Z₄*(40)=4 (из табл. 2) и Z₃(₂,x₃)=0 + 4 = 4. Эти числа заносятся в 1-ю строку 4, 5 и 6-го столбцов. Аналогично заполняются все остальные строки этих же столбцов.

Сравнив величины Z₃(₂,x₃) при одном и том же зна­чении ₂, выбираем наибольшее число, которое равно величине Z₃*(₂) . Соответствующие им условные оптимальные управления x₃^*(₂) стоят в той же строке табл. 3 (во 2-м столбце). Выполнив условную оптимизацию 3-го шага, переносим в табл. 2 против соответствующих значений = ₂ значения Z₃*(₂) и соответствующие им x₃^*(₂).

Условная оптимизация 2-го шага выполняется по 7, 8 и 9-й строкам во всех столбцах табл. 3 аналогичным образом.

Приведем в качестве примера подробный расчет для ₁ = 160 (четвертая секция табл. 3). При х₂ = 0и₂ = ₁-x₂=160 получим f₂(x₂)=f(0)=0, Z₃*(₂)=Z₃*(160) = 13 (из табл. 2), поэтому Z₂(₁,x₂)= =Z₂(160, 0) = 13. При x₂ = 40 и ₂ = ₁-х₂= 160— 40=120 получим f₂(40)=6 (из табл. 1), Z₃*(120)=9 (из табл. 2), откуда Z₂(160, 40) = 6 + 9=15 и т. д. После заполнения четвертой секции в 9-м столбце получаем пять чисел: 13, 15, 16, 15 и 15, из которых наибольшее Z₂*(160) = 16, а соответствующее,x₂*(100) =80. Эти числа и занесены в основную таблицу, как результаты выполнения условной оптимизации 2-го шага при ₁= 160.

Условную оптимизацию 1-го шага (10, 11 и 12-й столб­цы табл. 3) можно было бы выполнить лишь при задан­ном состоянии о = 200 (последняя секция табл. 3). Од­нако, имея в виду последующий анализ, мы приводим расчеты для всех возможных значений о (т. е. для 40, 80, 120, 160 и 200).

Перейдем ко второму этапу расчета — безусловной оптимизации. Из 1-го (последнего по порядку действий) шага условной оптимизации получаем Z₁*(200)=24, т. е. максимальный доход, который может быть достигнут, равен 24. Здесь же получаем x₁*(200) = x₁* = 40, т. е. предприятию I следует выделить 40 млн. руб.

Дальнейшие (безусловные) оптимальные управления определяем из табл. 2 по следующей цепочке. При х₁*= 40 из уравнения состояния получаем ₁* = 200—40=160. В соответствующем (7-м) столбце табл. 2 получаем x₂*(160)=80 = x₂*. Вычисляем ₂* = 160—80 = 80 (остаток средств перед выделением предприятию III). В 5-м столбце табл. 2 находим х₃* = =x₃*(80) =40. Тогда ₃* = ₂*—х₃* = 80—40 = 40. Наконец, из 3-го столбца табл. 2 получаем x₄* = x₄*(40) =40.

Итак, максимальный доход, равный 24 млн. руб., бу­дет получен, если распределять средства между пред­приятиями следующим образом: предприятию I выде­лить x₁* = 40млн. руб., предприятию II — х₂* = 80 млн. руб., предприятию III — x₃* = 40 млн. руб., предприя­тию IV — х₄* = 40 млн. руб.


ЛИТЕРАТУРА.

1. 
   Беллман Р. Динамическое программирование. М.:ИЛ, 1960
   
2. 
   Бёеллман Р. Процессы регулирования с адацптацией. М.:Наука,1964
   
3. 
   Беллёёёман Р., Дрейфус С. Прикладные задачи динамического прграммирования. М.:Наука, 1965.
   
4. 
   Хедли Дж. Нелинейное и динамическое программирование. М.:Мир, 1967
   
5. 
   Габасов Р., Кириллова Ф.М. Основы динамического программирования. Минск,
   

БГУ, 1975

6. 
   Габасов Р., Кириллова Ф.М. Методы оптимизации. Минск, БГУ, 1975
   
7. 
   Исследование операций в экономике. Под редакцией Н.Ш.Кремера. М.: ЮНИТИ,
   

1997

8. Исследование операций в экономике.Под. ред. Кремера Н.Ш. М.:ЮНИТИ. 1997.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1.ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

	F1	F2	F3	F4	F5	F6
0	0	0	0	0	0	0
10	14	15	16	13	12	14
20	26	25	26	24	25	25
30	36	34	35	34	36	35
40	48	43	44	42	46	42
50	59	52	53	52	55	52

Варианты

№ варианта	Номера предприятий	№ варианта	Номера предприятий	№ варианта	Номера предприятий	№ варианта	Номера предприятий
1	1234	18	2564	35	4321	52	6543
2	1235	19	3214	36	5321	53	6542
3	1236	20	3215	37	6321	54	6541
4	1345	21	3216	38	5431	55	6531
5	1346	22	3241	39	6431	56	6532
6	1342	23	3245	40	2431	57	6534
7	1425	24	3246	41	5241	58	6521
8	1426	25	3251	42	6251	59	6523
9	1562	26	3254	43	2651	60	6524
10	1563	27	3256	44	3651	61	6512
11	1564	28	3261	45	4651	62	6513
12	2316	29	3264	46	1263	63	6514
13	2456	30	3265	47	1264	64	6451
14	2453	31	3451	48	1265	65	6452
15	2451	32	3452	49	1352	66	6453
16	2561	33	3456	50	1354	67	6431
17	2563	34	3465	51	1356	68	6432

2. ПОСТРОЕНИЕ МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ ЗАДАЧИ О ЗАМЕНЕ [ 8]

Определить оптимальные сроки замены оборудования в течение N лет, при которых прибыль от эксплуатации оборудования максимальна, если известны: p - начальная стоимость оборудования; f(t) - стоимость производимой продукции на оборудовании возраста t лет; r(t) - ежегодные затраты на эксплуатацию оборудования возраста t лет; y(t) - ликвидная стоимость оборудования возраста t -лет.