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

 

 

 

 

Метод ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

 

 

 

 

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

 

 

 

 

• решение задач поэтапно

 

 

 

 

• принятие решения;
• планирование

 

 

 

 

Принцип оптимальности  Р.Э.Беллмана

 

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

 

 

 

 

Задачи, решаемые методом  ДП

 

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

 

 

 

 

Постановка задачи ДП

 

• требуется определить такое оптимальное управление Х*, переводящее  систему за n шагов из начального состояния S⁰ в конечное состояние Sn, при котором целевая функция принимает наибольшее (наименьшее) значение: F(S⁰, X*) → extr

 

 

 

 

Особенности математической  модели ДП

 

• задача оптимизации формулируется как конечный многошаговый процесс управления;
• оптимальное управление представляет собой арифметический вектор X*, определяемый последовательностью оптимальных пошаговых управлений: X* = (х*¹, х*², …, х*^k, …, х*ⁿ), число которых и определяет количество шагов задачи;
• критерий оптимальности определяется целевой функцией, которая является аддитивной и равна сумме целевых функций каждого шага:  F(Х)= ∑φ(S^k−1, x^k) k=1,n;
• выбор управления х^k на каждом шаге зависит только от состояния системы к этому шагу S^k−1, и не влияет на предшествующие шаги (нет обратной связи);
• состояние системы S^k после каждого шага управления зависит только от предшествующего состояния системы S^k-1 и этого управляющего воздействия х^k (отсутствие последействия) и может быть записано в виде уравнения состояния системы: S^k= ƒ^k (S^k-1, х^k), k = 1, n;
• на каждом шаге управление х^k зависит от конечного числа управляющих переменных, а состояние системы S^k зависит от конечного числа параметров

 

 

 

 

При выборе шагового  управления необходимо учитывать:

 

• возможные исходы предыдущего шага    S^k-1 (условная оптимизация)
• влияние управления х^k на все оставшиеся до конца процесса шаги  (n - k) (безусловная оптимизация)

 

 

 

 

Задача о ранце

 

• Постановка задачи. Требуется погрузить на баржу грузоподъемностью w=83 груз, состоящих из предметов четырех различных типов, таким образом, чтобы суммарная стоимость всего груза оказалась максимальной. При этом известны веса и стоимости четырех предметов равны соответственно р1=24, р2=22, р3=16, р4=10, v1=96, v2=85, v3=50, v4=20.

 

• Математическая модель.

    Целевая функция – максимум стоимости груза, размещенного на барже:  maxƒ(X)=Σx_ⁱv_ⁱ i=1,n

    Ограничения:

    Σx_ⁱp_ⁱ ≤ w, i=1,n – вес груза не превышает грузоподъемность баржи;

    х_ⁱ = 0, 1, 2,….. – физическая неделимость предметов

 

 

 

 

Решение задачи о ранце  методом ДП

 

• Первый шаг оптимизации

максимальная стоимость  груза: ƒ¹ (w) = max {x¹v¹}

условия: x¹p¹ ≤ w, x¹=0, 1, 2…для нахождения max: x¹ = [w/p¹] и ƒ¹(w) = [w/p¹]v¹

 

• Второй шаг оптимизации

ƒ_²(w) = max {x_²v_² + ƒ1(w - x_²p_²)} 0 ≤ х_² ≤ [w/p_²]

где (w - x_²p_²) – вес предметов первого типа, которые может взять баржа при условии, что предметов второго типа взяли x_²;

ƒ_¹(w - x_²p_²) – максимальная стоимость предметов первого типа;

x_²v_² – максимальная стоимость предметов второго типа

 

• Третий шаг оптимизации

ƒ_³(w) = max {x_³v_³ + ƒ_²(w – x_³p_³)} 0 ≤ х_³ ≤ [w/p_³]

 

• Четвертый шаг оптимизации

ƒ_⁴(w) = max {x_⁴v_⁴ + ƒ_³(w – x_⁴p_⁴)} 0 ≤ х_⁴ ≤ [w/p_⁴].

 

 

 

 

 

Решение задачи о ранце  методом ДП

 

1

 

181

 

46-47

 

0

 

288

 

72-87

 

0

 

96

 

24-45

 

1

 

277

 

70-71

 

1

 

85

 

22-23

 

0

 

192

 

48-69

 

0

 

0

 

0-21

 

x²

 

ƒ²(w)

 

w

 

x²

 

ƒ²(w)

 

w

 

Второй шаг оптимизации

 

3

 

288

 

72-87

 

1

 

96

 

24-47

 

2

 

192

 

48-71

 

0

 

0

 

0-23

 

x¹

 

ƒ¹(w)

 

w

 

x¹

 

ƒ¹(w)

 

w

 

Первый шаг оптимизации

 

 

 

 

Решение задачи о ранце  методом ДП

 

1

 

145

 

40-45

 

0

 

288

 

72-87

 

0

 

135

 

38-39

 

0

 

277

 

70-71

 

0

 

96

 

24-37

 

1

 

242

 

64-69

 

0

 

85

 

22-23

 

0

 

192

 

48-63

 

1

 

50

 

16-21

 

0

 

181

 

46-47

 

0

 

0

 

0-15

 

x³

 

ƒ³(w)

 

w

 

x³

 

ƒ³(w)

 

w

 

Третий шаг оптимизации

 

 

 

 

Решение задачи о ранце  методом ДП

 

0

 

146

 

40-45

 

1

 

308

 

82-87

 

1

 

135

 

38-39

 

0

 

288

 

72-81

 

1

 

116

 

34-37

 

0

 

277

 

71-71

 

0

 

96

 

24-33

 

0

 

242

 

64-69

 

0

 

85

 

22-23

 

1

 

212

 

58-63

 

0

 

50

 

16-21

 

0

 

192

 

48-57

 

1

 

20

 

10-15

 

0

 

181

 

46-47

 

0

 

0

 

0-9

 

x⁴

 

ƒ⁴(w)

 

w

 

x⁴

 

ƒ⁴(w)

 

w

 

Четвертый шаг оптимизации

 

 

 

 

Решение задачи о ранце  с помощью средств MS Excel (Поиск  решения)

 

 

 

 

Решение задачи о ранце  с помощью средств MS Excel (Поиск  решения)