Решение примера

Вернёмся к примеру с загрузкой самого ценного оборудования. Представим схему оптимизации как трёхшаговый процесс, на каждом из которых определяется количество и общий вес предметов данного типа. На k-ом шаге s_k-1 – одномерный вектор состояния системы (скаляр) – недогруз самолёта после его заполнения предметами типов от 1 до k –1. Исходное состояние s₀=5 . Решение-скаляр х_k – вес предметов k-го типа. Тогда эффективность решения на (k – 1)-ом шаге – стоимость загруженных предметов (k – 1)-го типа, эффективность всей загрузки самолёта – , . Данные задачи дискретны, поэтому зависимости надо исследовать табличным методом (таблица 2).

Последний шаг, поиск по .

Таблица 2

s2	x3
		150

Возможности существования состояний s₂ мы не обсуждаем ввиду неизвестности решений х₁ и х₂ . Максимум достигается при x₃ = 5 (в самолёт загружаются 5 предметов оборудования 1-ого типа весом в 1 тонну каждый). Теперь рассмотрим решения и состояния на двух последних шагах. Построим аналогичную таблицу. Так как у нас только три шага, эта таблица будет и последней, для любого сочетания решений х₂ и x₃ решение х₁ определяется однозначно ввиду ограничения: максимальная грузоподъёмность самолёта равна 5 тоннам. Поэтому к таблице присоединим столбцы значений х₁ и эффективностей. Вообще, для n-шаговой задачи надо строить n–1 таблицу.

Два последних шага, поиск и

по

Таблица 3

s1	x2	s2	x3		x1
					0 0 0
	0		1		4 130 160
					3 – невозможно
					2 65 145
					2 65 155
					1 – невозможно
					0 0 140
					0 0 150

Решение задачи подчёркнуто в таблице 3: . Оно обеспечивает загрузку самолёта самым ценным оборудованием общей стоимостью в 160 тыс. рублей. При этом:

.

Замечания. Для дискретной задачи метод динамического программирования фактически сводится к организованному перебору вариантов решений. Преимущества динамического программирования проявляются в случае, когда удаётся установить функциональные зависимости . Нулевые строки в таблицах 2, 3 означают отказ от загрузки и необходимы для обоснования существования нулевой эффективности.