При этом, в случае оптимального управления
т
W = max ^Г о}. (6.66)
;=1
Существо решения задач динамического программирования заключается в следующем:
— оптимизация производится методом последовательных при-ближений (итераций) в два круга: вначале от последнего шага операции к первому, а затем наоборот, от первого к последнему;
— на первом круге, идя от последующих шагов к предыдущим, находится так называемое условное оптимальное управление; условное оптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивали максимальную эффективность последующего шага, иными словами, на каждом шаге имеется такое управление, которое обеспечивает оптимальное продолжение операции; этот принцип выбора управления называется принципом оптимальности;
— так продолжается до первого шага, но поскольку первый шаг не имеет предыдущего, то полученное для него условное оптимальное управление теряет свой условный характер и становится просто оптимальным управлением, которое мы ищем;
— второй круг оптимизации начинается с первого шага, для которого оптимальное управление известно.
Имея для всех шагов после первого условные оптимальные управления, мы знаем, что необходимо делать на каждом последующем шаге. Это дает нам возможность последовательно переходить от условных к оптимальным управлениям для всех последующих шагов, что обеспечивает оптимальность операции в целом.
Пусть имеется т типов различных грузов, которыми необходимо загрузить транспортное средство (корабль, самолет, автомобиль) таким образом, чтобы общая ценность груза Жбыла максимальной. Ценность груза является функцией от грузоподъемности транспортного средства
W=f(G). (6.67)
Известны массы грузов /-го типа Р, и их стоимость С/.
Необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза была максимальной
W=fm( G)=max|>q, (6.68)
; = 1
где Xj — число предметов груза /-го типа, загружаемых в транспортное средство; Xj выступает здесь в качестве управления (Ц = xj).
Ограничивающими условиями являются:
т
I-v/' < G: (6.69)
;=1
jq = 0, 1, 2... (6.70)
Первое условие требует, чтобы общая масса груза не превышала грузоподъемности транспортного средства, а второе — чтобы предметы, составляющие груз различных типов, были неделимы.
Пример 6.8
Самолет грузоподъемностью G = 83 условных единицы груза предполагается загрузить четырьмя типами груза (т = 4). Массы и стоимость грузов /-го типа в условных единицах заданы в табл. 6.23.
Необходимо загрузить самолет таким образом, чтобы общая ценность груза была максимальной.
Таблица 6.23
Массы и стоимость груза /-го типа (в условных единицах)
Показатель, услов Тип груза, /
ные единицы 1 2 3 4
Pi 10 16 22 24
СІ 20 50 85 96
Решение
В данном примере нет естественного разделения операции загрузки на шаги. Такое разделение, в интересах решения задачи, целесообразно ввести искусственно, принимая за шаги загрузку самолета предметами различных типов. Таких шагов будет четыре.
Последовательность расчетов при этом будет следующей.
На первом круге оптимизация начинается с четвертого типа груза — четвертого шага. При этом принимается, что самолет загружают только предметами 4-го типа. В этих условиях максимальная ценность груза на четвертом шаге
щ = Д (G) = max {х4 (6.71)
при условиях, вытекающих из условий (6.69) и (6.70)
Х4Р4 < <7;
Х4 = 0, 1, 2, ...
Из первого условия следует, что
Х4 < ; х4 < Ц; х4 < 3,46.
-*4 Zt-
G
- 3.
= |3,46|
Это и есть условное оптимальное управление на последнем четвертом шаге
Щ = Х4 = 3.
Из второго условия следует, что х4 может быть только целым числом, поэтому в качес тве Х4 берется целая часть полученной дроби
Максимальная ценность груза при такой загрузке определяется по формуле (6.71):
034 =/4(G) = max {3 х 96} = 288.
Переходим к предыдущему, третьему шагу, на котором самолет загружается предметами четвертого типа и, кроме того, предметами третьего типа.
Взяв на этом шаге хз предметов третьего типа, мы тем самым устанавливаем, что количество предметов четвертого типа по весу не может быть более (G — Х3Р3). Максимальная ценность этого груза равна Д(G - х3Р3).
(6.72)
(6.73)
Максимальная ценность груза, состоящего из предметов четвертого и третьего типов, определится по формуле, вытекающей из формулы (6.68), с ограничениями (6.69) и (6.70):
f3(G) = max {Х3С3 +MG - х3Р3)}
при
G
О < х, <
Расчет по формуле (6.72) производится следующим образом. Из ограничения (6.73) следует:
п ^ 83
О < х, < —.
22
Это означает, что хз может принимать значение не больше:
х3 = 0, 1, 2, 3.
Для каждого из этих четырех значений вычисляется величина, стоящая в фигурных скобках формулы (6.72), причем /4(G) рас-считывается по формуле (6.71):
0 {0 х 85 + /4(83 -0x22)} = {0+/4(83)} = ь 83 24 %1
= {° + 288} = 288; 61
24
1 {1 х 85 + /4(83 -1X 22)} = {85+/4(61)}=< 85 + 96
х}
{х, X 85 + /4 (83 - х} X 22)}
= {85 + 192} =277;
Затем рассчитывается максимальная из полученных величин: f3(G) = max (288; 277; 266; 255) = 288.
Соответствующее этой наибольшей ценности количество груза х3 = 0 и будет условным оптимальным управлением на третьем шаге
U3 = x3 = 0.
Далее переходим к предыдущему, второму шагу — к загрузке предметов второго типа — и для него аналогичным путем находим
/2(G) = 288 и соответствующее Ui = хт = 0.
Точно так же для первого шага
MG) = 308 и Щ = X! = 1.
Для первого шага условное оптимальное управление одновременно является оптимальным управлением U[:
и; =и1= і.
Начинается второй круг оптимизации от первого шага к последнему.
Поскольку нам известно, что оптимальное управление на первом шаге требует одной единицы груза первого типа, то в дальнейшем распределяется только то, что остается на остальные типы груза, а именно
G' = 83 — 1 х 10 = 73 единицы.
Производя расчеты, аналогичные тем, которые выполнялись на первом круге, последовательно получаем оптимальные управления для второго, третьего и четвертого шага:
и"2 =0; и; =0; U\ =3.
39
96
{2 х 85 + /4(83 - 2 х 22)} = {170 + /4(39)} = < { 170 + = {170 + 96} =266;
96
24
{3 х 85 + /4(83 - 3 х 22)} = {255 + /4(17)} = \ 255 + = {255 + 0} =255.
Оптимальное управление обеспечивает следующую максимальную общую ценность груза, рассчитываемую по формуле (6.68):
W= 1 х 20 + 0 х 50 + 0 х 85 + 3 х 96 = 308.
В рассмотренном примере оптимизация могла быть осуществлена, начиная с любого типа предметов. Принятый нами порядок соответствует общей идее динамического программирования.
Пример 6.9
