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




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


в В, при котором суммарные затраты минимальны.

Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В

на отдельные шаги (один шаг — один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным «слепым» перебором.

Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В

в восточном направлении, скажем, на 7 частей, а в северном — на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В

состоит из т = 7 + 5 == 12 отрезков, направленных на восток или на север (рис. 13.2). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В,

для которого сумма чисел, стоящих на отрезках, минимальна.

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

 х

5
 7, 0
 у

 5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 13.2) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление «с») или на восток (управление «в»). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по-прежнему будем называть «условным оптимальным выигрышем» (хотя в данном случае это не «выигрыш», а «проигрыш») для данного состояния системы S перед началом очередного шага.

Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу.


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