Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 79


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

А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два, выбираем любое). Таким способом мы получим управление

х = (с, с, в, в, в, в, с, в, в, в, с, с).

Подсчитаем расходы для этой траектории. Они будут равны W

=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, что безусловно больше, чем W* = 118. В данном случае разница не очень велика, но в других она может быть существенной.

В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, но, разумеется, усложняет и удлиняет расчеты.

Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике: например, при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле расхода горючего) набора скорости и высоты летательным аппаратом.

Сделаем одно попутное замечание. Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные — в обратном направлении. Действительно, это так: в любой задаче динамического программирования «начало» и «конец» можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на «уже сложившиеся» условия к началу данного шага, чем на те, которые еще «предстоят» после этого шага.


Содержание  Назад  Вперед