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

I. Динамическое программирование (ДП) -это метод многошаговой оптимизации.

Алгоритм реализации ДП содержит 7 этапов:

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

2. Определяются функции эффекта (выигрыша) на i - шаге в зависимости от состояния системы в начале этого шага S_i и используются управления U_i : W_i = W_i (S_i, U_i).

3. Определяются функции, выражающие изменение состояния системы S_i под влиянием управления U_i на i - шаге процесса: S_i* = j(S_iU_i).

4. Составляется основные реккурентное соотношение (это равенство, описывающее значение функции в нескольких связанных определенным отношением предшествования точках считая известными значения можно вычислить значения функции в остальных точках) динамического программирования:

5. Определяется условно-оптимальный эффект (выигрыш) для последнего n-го шага рассматриваемого процесса W_n(S_n), а также соответствующее ему оптимальное управление U_i*.

6. Определяются условно-оптимальные эффекты (выигрыши) и соответствующие этим эффектам управления от предпоследнего (n-1) -го и до первого шагов процесса:

7. Определяется начальное состояние (если оно не задано), выбираются оптимальные эффекты и безусловные управления для 1-го, 2-го и так далее до n-го шага рассматриваемого процесса.

II. Пример:

1. Исходные данные задачи ДП:

1) распределение объема строительно-монтажных работ на объекте по кварталам планового года составляет

квартал
финансирование	2 млн.	5 млн.	3 млн.	1 млн.

Перед началом планового периода на объекте имеется производственных мощностей для выполнения работ объемом 2 млн.

2) - затраты по переброске производственных мощностей с расматриваемого объекта на другие С1 = 70тыс,

- затраты по вводу новых производственных мощностей на объекте С2 = 100тыс.

- потери от простоя оборудования С3 = 80тыс.

- затраты при организации 3-ей смены С4 = 110тыс.

3). эффект (выйгрыш) состоит в минимизации затрат.

2. 1-й этап: описание системы и процесса её изменений (динамики):

- обозначение производственных мощностей, имеющихся в начале i-го квартала i=1, 2, 3, 4, исходя из того, что за единицу принимаются производственные мощности для выполнения работ в 1 млн; тогда требуемое количество производственных мощностей для выполнения заданного в i-м квартале объёма работ: m₁ = 2, m₂ = 5, m₃ = 3, m₄ = 1;

- состояние системы S_i определяется величиной использованных производственных мощностей x_i;

- управление U_i состоит в:

а) переброске производственных мощностей с данного объекта на другие или переброске производственных мощностей с других объектов на данный;

б) организации дополнительной 3-ей смены при нехватке мощностей;

- естественным временным шагом процесса управления системой (её динамики) является квартал планового года, то есть процесс управления состоит из 4-х шагов.

3. 2-й этап: определение функций эффекта (затрат) для i - го шага:

- при переброске мощностей функция затрат имеет вид

- общая функция эффектов (затрат) имеет вид W_i (x_i) = f_i(x_i) + ji(x_i)

4.3-й этап: определение функции изменения состояния системы (производственных мощностей) на i-м шаге:

- в конце i-го шага производственные мощности должны быть равны мощностям в начале (i + 1)-го шага,

- функция изменения состояния системы на i-м шаге примет вид S_i = x_i+ x_i+1.

5.4-й этап:запись основного реккурентного соотношения ДП в виде

6. 5-й этап: определение условно-оптимальных затрат на 4-м (последнем) шаге процесса:

- запись формулы

где:

х₃, х₄ - производственные мощности, используемые в 3-м и 4-м кварталах,

- делается предположение, что производственные мощности в 3-м квартале могут быть 0, 1, 2, 3, 4, 5млн,

- расчет условных минимальных затрат для каждого предположения при x₄= var в результате осуществления различных управлений а) и б):

х₃= 0, х₄= 0	w₄(x₄) = 0 + 110 (1-0) = 110 тыс
х₃ = 0, х₄ = 1	w₄(x₄) = 100 (1-0) + 0 = 100 тыс
х₃ = 0, х₄ = 2	w₄(x₄) = 100 (2-0) + 80 (2-1) = 280 тыс

Очевидно, что при росте х₄ величина w₄(x₄) будет только рости, поэтому min w₄(x₄) = 100 тыс.

Повторение процедуры для х₃= 1, х₃= 2, х₃= 3, х₃= 4, х₃= 5

х₃= 1, х₄= 0	w₄(x₄) = 70 (1+0) + 110 (1-0) = 180 тыс
х₃ = 1, х₄ = 1	w₄(x₄) = 0 + 0 = 0
х₃ = 1, х₄ = 2	w₄(x₄) = 110 (2-1) + 80 (2-1) = 180 тыс

х₃= 2, х₄= 0	w₄(x₄) = 70 (2 - 0) + 110 (1-0) = 250 тыс
х₃ = 2, х₄ = 1	w₄(x₄) = 70 (2 – 1) + 0 = 70 тыс
х₃ = 2, х₄ = 2	w₄(x₄) = 0 + 80 (2-1) = 80 тыс

х₃= 1, х₄= 0	w₄(x₄) = 70 (3 - 0) + 110 (1-0) = 320 тыс
х₃ = 3, х₄ = 1	w₄(x₄) = 70 (3 – 1) + 0 = 140 тыс
х₃ = 3, х₄ = 2	w₄(x₄) = 70 (3 - 2) + 80 (2-1) = 150 тыс

х₃= 4, х₄= 0	w₄(x₄) = 70 (4 - 0) + 110 (1-0) = 390 тыс
х₃ = 4, х₄ = 1	w₄(x₄) = 70 (4 – 1) + 0 = 210 тыс
х₃ = 4, х₄ = 2	w₄(x₄) = 70 (4 - 2) + 80 (2-1) = 220 тыс

х₃= 5, х₄= 0	w₄(x₄) = 70 (5 - 0) + 110 (1-0) = 450 тыс
х₃ = 5, х₄ = 1	w₄(x₄) = 70 (5 – 1) + 0 = 280 тыс
х₃ = 5, х₄ = 2	w₄(x₄) = 70 (5 - 2) + 80 (2-1) = 290 тыс

- выбор минимальных значений затрат в 4-м квартале и соответствующих им величин производственных мощностей (управлений).

Таблица 1

х₃	W₄(х₄)	х₄

х₄ – производственные мощности в 4-м квартале.

W₄(х₄) – условно-оптимальные затраты в 4-м квартале,

Оптимальное управление на 4-м шаге х₄= 1, при котором W₄(х₄) = 0.

7.6-й этап: определение условно-оптимальных затрат, а такде соответствующих им величин производственных мощностей (управлений) на 3-м, 2-м и 1-м шагах процесса:

- для 3-го шага рекуррентное соотношение имеет вид

где

Делается предположение, что производственные мощности во 2-м квартале могут быть 0, 1, 2, 3, 4, 5 млн. Значения W₄(х₄) берутся из табл. 1. Проводятся расчеты аналогичные п.5, результаты сводятся в табл. 2.

Таблица 2

х₂	W₄(х₄)	х₃	х₄

х₃– производственные мощности в 3-м квартале,

W₄(х₄) – условно-оптимальные затраты в 3-м квартале.

Оптимальное управление на 3-м шаге х₃= 3, при котором W₃(х₃) = 140.

- для 2-го шага рекуррентное соотношение имеет вид

где

Делается предположение, что производственные мощности во 1-м квартале могут быть 0, 1, 2, 3, 4, 5 млн. Значения W₃(х₃) берутся из табл. 2. Проводятся расчеты аналогичные п.5, результаты сводятся в табл. 3.

Таблица 3

х₁	W₂(х₂)	х₂	х₃	х₄

х₂– производственные мощности в 2-м квартале

W₂(х₂) – условно-оптимальные затраты в 2-м квартале

Оптимальное управление на 2-м шаге х₂= 5, при котором W₂(х₂) = 280

- для 1-го шага рекуррентное соотношение имеет вид

где:

Поскольку х₀ = 2 задано по условиям задачи, то необходимо найти условно-оптимальные затраты только при х₀(значения W₂(х₂) из таб. 3.

х₀= 2, х₁= 0	W₁(x₁) = 70 (2 - 0) + 110 (2-0) + 660 = 1020 тыс
х₀= 2, х₁= 1	W₁(x₁) = 70 (2 – 1) + 110 (2 – 1) + 560 = 740 тыс
х₀= 2, х₁= 2	W₁(x₁) = 0 + 0 + 460 = 460 тыс
х₀= 2, х₁= 3	W₁(x₁) = 100 (3 - 2) + 80 (3 - 2) + 360 = 540 тыс

Следовательно, условно-оптимальные затраты на первом шаге процесса состовляют 460 тыс. при управлении х₁= 2.

8.7 -й этап: определение безусловно-оптимальных затрат на управления:

- для затрат в 1-м квартале оптимальным является управление х₁= 2, а так как х₁= х₀, то затраты в 1-м квартале равны 0,

- для затрат во 2-м квартале оптимальным является управление х₂= 5, при котором составляют 280 тыс.

- для затрат в 3-м квартале оптимальным является управление х₃= 5, при котором составляют 140 тыс.

- для затрат в 4-м квартале оптимальным является управление х₄= 1, при котором составляют 0 .

- общая сумма затрат 420 тыс.

9.Общий вывод:

Таким образом, оптимальное распределение производственных мощностей на строящемся объекте соответствует следующему плану:

1) в 1-м квартале используются имеющиеся производственные мощности, рассчитанные на объем 2 млн;

2) во 2-м квартале прозводственные мощности увеличиваются на 3 условных единиц;

3) в 3-м квартале производственные мощности снижаются на 2 условные единицы;

4) в 4-м две условные единицы производственных мощностей перебрасываются на другие объекты;

5) затраты по управлению распределением производственных мощностей при этом плане минимальные и составляют 420 тыс.

Пример 3.