Исследование операций

В качестве критерия оптимизации принята суммарная себестоимость выполнения всех работ.

Таблица 9.3

2. Проверка решения на оптимальность

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

Таблица 9.4

Переходим к следующему этапу.

3. Поиск минимального набора строк и столбцов, содержащих нули.

Необходимо отметить звездочкой:

а) все строки, не имеющие ни одного отмеченного звездочкой нуля (таблица 9.5, строка 4);

б) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных звездочкой строк (таблица 9.5, столбец 3);

в) все строки, содержащие отмеченные звездочкой нули хотя бы в одном из помеченных столбцов (таблица 9.5, строка 3). Далее повторяются поочередно действия б) и в) до тех пор, пока есть что отмечать.

Таблица 9.5

После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец. Цель этого этапа - провести минимальное число горизонтальных и вертикальных прямых, пересекающих, по крайней мере, один раз все нули.

4. Перестановка некоторых нулей.

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

Таблица 9.6

Эта операция не изменяет оптимального решения. После нее выполняется новая итерация, цикл расчета начинается с этапа 2 и так до тех пор, пока не будет получено оптимальное решение. Поскольку число нулей, отмеченных звездочкой, не равно n, выполняется новый итерационный цикл, после чего находится оптимальное решение (таблица 9.7).

Таблица 9.7

Из полученного решения видно, что Х15 = 1, Х21 = 1, ХЗЗ = 1 и т.д. Это означает: чтобы оптимально распределить пять кранов на пять объектов, необходимо первый кран направить на пятый объект, второй - на первый, третий - на третий, четвертый кран возводит четвертый объект, а пятый кран возводит второй объект. Первая цифра в переменной X определяет машину, а вторая - объект работы, при этом суммарная себестоимость выполнения всех работ будет минимальной и составит Ymin = 220.

§7. Задачи целочисленного программирования. Понятие о нелинейном программировании

1. Задачи целочисленного программирования.

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

Рассмотрим пример такой задачи. Пусть имеется ряд предметов (ценностей) П1, П2, ..., Пn, которые требуется перевезти из одного города в другой. Известны стоимости этих предметов: с1, c2, ..., сn и их веса q1, q2, ..., qn. Количество и вид предметов, которые можно перевезти, лимитируется грузоподъемностью Q машины. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в Q.

Введем переменные х1, x2, ..., xn, определяемые условием: xi = 1, если в машину берётся предмет Пi, и xi = 0,-- если не берётся.

При заданных значениях х1, x2, ..., xn суммарный вес предметов, которые берутся в машину, равен q1x1 + q2x2 + ... + qnxn. Условие ограниченной грузоподъемности запишется в виде неравенства:

q1x1 + q2x2 + ... + qnxn Q (10.1)

Запишем общую стоимость предметов, которую нужно максимизировать:

n

L = ci xi max (10.2)

i = 1

Таким образом, задача похожа на обычную задачу линейного программирования: найти неотрицательные значения переменных х1, x2, ..., xn, которые удовлетворяют неравенству (10.1) и обращают в максимум линейную функцию этих переменных (10.2). На первый взгляд может показаться, что и решать ее надо как задачу линейного программирования, введя дополнительные ограничения-неравенства (каждый предмет -- только один!):

x1 1, x2 1, ..., xn 1.

Найденное таким образом решение может оказаться не целым, а дробным, а значит неосуществимым. Данная задача отличается от обычной задачи линейного программирования: она представляет собой задачу целочисленного программирования.

Если задачу решать как обычную задачу линейного программирования и округлить полученные значения xi до ближайшего из целых чисел 0 или 1, то полученное таким образом решение даже может не удовлетворять ограничению (10.1), т. е. «не влезет» в данный вес Q. А если и «влезет», то может быть совсем не оптимальным.

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

2. Задачи нелинейного программирования

Общая постановка задачи нелинейного программирования следующая. Найти неотрицательные значения переменных х1, x2, ..., xn, удовлетворяющие каким-то ограничениям произвольного вида, например

ц1(х1, х2, . . . , хn) ? 0,

ц2(х1, х2, . . . , хn) ? 0, (10.3)

цm(х1, х2, . . . , хn) ? 0,

и обращающие в максимум произвольную нелинейную функцию этих переменных:

W = W(х1, x2, ..., xn) max. (10.4)

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

Задачи нелинейного программирования па практике возникают довольно часто, например, когда затраты растут не пропорционально количеству закупленных или произведенных товаров (эффект «оптовости»), но многие нелинейные задачи могут быть приближенно заменены линейными, по крайней мере в области, близкой к оптимальному решению. Если это и невозможно, все же обычно нелинейные задачи, возникающие на практике, приводят к сравнительно «благополучным» формам нелинейности. В частности, нередко встречаются задачи «квадратичного программирования», когда W есть полином 2-й степени относительно переменных х1, x2, ..., xn, а неравенства (10.3) линейны. В ряде случаев при решении задач нелинейного программирования может быть с успехом применен так называемый «метод штрафных функций», сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще. Идея метода состоит в том, что вместо того, чтобы наложить на решение жесткое требование вида ц(х1, х2, . . . , хn) ? 0 можно наложить некоторый достаточно большой «штраф» за нарушение этого условия и добавить к целевой функции W(х1, x2, ..., xn) штраф вида aц(х1, х2, . . . , хn) ? 0 где а -- коэффициент пропорциональности (в случае, когда целевая функция максимизируется, а отрицательно, если минимизируется -- положительно). Далее можно, увеличивая абсолютное значение а, посмотреть, как изменяется при этом оптимальное решение (х1*, x2*, ..., xn*), и, когда оно ужо практически перестает меняться, остановиться на нем. В ряде случаев при решении задач нелинейного программирования оказываются полезными так называемые «методы случайного поиска», состоящие в том, что вместо упорядоченного перебора возможных вариантов решения применяется случайный розыгрыш.

Раздел 3. Динамическое программирование

§1. Метод динамического программирования

Динамическое программирование - это особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (или «многоэтапным») операциям.

Рассмотрим операцию O, состоящую из m шагов (этапов), например, деятельность отрасли промышленности в течение ряда хозяйственных лет.

Пусть эффективность операции характеризуется каким-то показателем W, который будем называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах:

m

W = wi (11.1)

i = 1

где wi, -- выигрыш на i-м шаге.

Если W обладает таким свойством, то его называют «аддитивным критерием».

Операция O представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Такое решение называется «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой х, а шаговые управления -- буквами х1, x2, ..., xm:

х = ( х1, x2, ..., xm). (11.2)

В общем случае х1, x2, ..., xm могут быть не только числа, а и векторы, функции и т. д.

Требуется найти такое управление x, при котором выигрыш W обращается в максимум:

m

W = wi max (11.3)

i = 1

То управление х*, при котором этот максимум достигается, будем называть оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений:

x* = ( х*1, x*2, ..., x*m). (11.4)

Тот максимальный выигрыш, который достигается при этом управлении, будем обозначать W*:

W* = mах {W (х)}. (11.5)

Формула (11.5) читается так: величина W* есть максимум из всех W(x) при разных управлениях х (максимум берется по всем управлениям х, возможным в данных условиях).

Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности) W.

1. Планируется деятельность группы промышленных предприятий П1, П2, ..., Пk на период m хозяйственных лет. В начале периода на развитие группы выделены какие-то средства М, которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

m

W = wi (11.6)

i = 1

и, значит, обладает свойством аддитивности.

Управление хi, на i-м шаге состоит в том, что в начале i-го года предприятиям выделяются какие-то средства хi1, хi2, ..., хik (первый индекс -- номер шага, второй -- номер предприятия). Таким образом, шаговое управление есть вектор с k составляющими:

xi = (хi1, хi2, ..., хik). (11.7)

Величины wi в формуле (11.6) зависят от количества вложенных в предприятия средств.

Управление х всей операцией состоит из совокупности всех шаговых управлений:

x = (x1, x2, ..., xm). (11.8)

Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление х*), при котором величина W обращается в максимум.

В этом примере шаговые управления были векторами.

2. Космическая ракета состоит из m ступеней, а процесс ее вывода на орбиту -- из m этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес:

G = G1+G2+...+Gm,

где Gi -- вес i-й ступени.

В результате i-го этапа (сгорания и сбрасывания i-й ступени) ракета получает приращение скорости t , зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет

m

V = i (11.9)

i = 1

где i--выигрыш (приращение скорости) на i-м шаге.

Управление х представляет собой совокупность весов всех ступеней Gi:

x = (G1, G2, ..., Gm).

Оптимальным управлением х* будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление -- одно число, а именно, вес данной ступени.

3. Владелец автомашины эксплуатирует ее в течение m лет. В начале каждого года он может принять одно из трех решений:

1) продать машину и заменить ее новой;

2) ремонтировать ее и продолжать эксплуатацию;

3) продолжать эксплуатацию без ремонта.

Шаговое управление -- выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш») равен

m

W = wi (11.10)

i = 1

где wi -- расходы в i-м году. Величину W требуется обратить в минимум.

Управление операцией в целом представляет собой какую-то комбинацию чисел 1, 2, 3, например:

x = (3,3, 2, 2, 2, 1, 3, ...),

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

x = (j1, j2, ... , jm), (11.11)

где каждое из чисел j1, j2, ..., jm имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (11.11), при которой величина (11.10) минимальна.

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

Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше много раз решить сравнительно простую задачу, чем один раз -- сложную.

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

Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции -- получить за m лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но такое решение будет неверным с точки зрения эффективности операции в целом, т.к. имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы.

Планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный.

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

Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, m-й шаг. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, (m -- 1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на m-м шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то и так-то).

Предположим, что это сделано, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m-м шаге. Теперь можно оптимизировать управление на предпоследнем, (m -- 1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (m -- 2)-й шаг, и для каждого из этих предположений найдем такое управление на (m--1)-м шаге, при котором выигрыш за последние два шага (из которых m-й уже оптимизирован!) максимален. Так находим для каждого исхода (m -- 2)-го шага условное оптимальное управление на (m -- 1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, «пятясь назад», оптимизируем управление на (m -- 2)-м шаге и т. д., пока не дойдем до первого.

Предположим, что все условные оптимальные управления и условные оптимальные выигрыши на всех шагах процесса известны. Теперь можно построить уже не условно оптимальное, а просто оптимальное управление х* и найти не условно оптимальный, а просто оптимальный выигрыш W*.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз -- от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз -- от начала к концу, когда остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление х*, состоящее из оптимальных шаговых управлений х1*, х2*, ... , хm*.

§2. Примеры решения задач динамического программирования

1. Прокладка наивыгоднейшего пути между двумя пунктами. Требуется проложить путь, соединяющий два пункта А и B, из которых второй лежит к северо-востоку от первого.

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

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

Y (север) В

А

Х (восток)

Рисунок 12.2

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

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

Процедуру условной оптимизации будем разворачивать в обратном направлении -- от конца к началу. Прежде всего, произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол прямоугольной сетки (рисунок 12.3). После 11-го шага будем находится там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из точек B1 или В2.

Рисунок 12.3

Если находимся в точке B1 - выбора нет (управление вынужденное): надо идти на восток, и это обойдется в 10 единиц. Запишем это число 10 в кружке у точки В1, а оптимальное управление покажем короткой стрелкой, исходящей из В1 и направленной на восток. Для точки В2 управление тоже вынужденное (север), расход до конца равен 14, запишем его в кружке у точки В2. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В1, В2 найден и записан в соответствующем кружке.

Оптимизируем предпоследний (11-й) шаг. После 10-го шага можно оказаться в одной из точек С1, C2, C3 (рисунок 12.4).

Рисунок 12.4

Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти на восток; обойдется это до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при B1). Число 21 записываем в кружке при точке С1. Для точки С2 управление уже не вынужденное: можно идти как на восток, так и на север. В первом случае затраты на данном шаге составят 14 единиц и от В2 до конца -- еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке C2 -- идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2). Для точки С3 управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С3).

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

В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В: W* = 118.

Построим безусловное оптимальное управление -- траекторию, ведущую из А и В самым дешевым способом. Такая оптимальная траектория отмечена на рисунке 12.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:

х* = (с, с, с, с, в, в, с, в, в, в, в, в),

т. е. первые четыре шага - на север, следующие два -- на восток, затем опять один на север и остальные пять -- на восток. Задача решена.

Y (север)

А Х (восток)

Рисунок 12.5

В ходе условной оптимизации можно столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, т. е. приводят к одинаковому расходу средств от этой точки до конца. Например, в точке с координатами (5; 1) оба управления «с» и «в» являются оптимальными и дают расход до конца равным 62. Из них произвольно выбирается любое (в данном случае выбрали «с»). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании; от этого может зависеть оптимальное управление всем процессом, но не оптимальный выигрыш.

2. Задача о распределении ресурсов. Метод динамического программирования позволяет решать многие экономические задачи. Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между m предприятиями П1, П2, ..., Пm. Каждое из предприятий Пi при вложении в него каких-то средств х приносит доход, зависящий от x, т. е. представляющий собой какую-то функцию i(х). Все функции i(х) (i = 1, 2, ..., m) заданы. Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

Эта задача решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй -- в П2 и т. д.

Управляемая система S в данном случае -- средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S -- наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х1, x2, ..., xm, выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел х1, x2, ..., xm, при которой суммарный доход максимален:

m

W = цi (xi) max (12.1)

i = 1

Решим эту задачу сначала в общем, формульном виде, а потом -- для конкретных числовых данных. Найдем для каждого i-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш Wi(S), а соответствующее ему условное оптимальное управление -- средства, вкладываемые в i-е предприятие, -- xi(S).

Начнем оптимизацию с последнего, m-го шага. Пусть мы подошли к этому шагу с остатком средств S. Вложим всю сумму S целиком в предприятие Пm. Условное оптимальное управление на m-м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.

xm (S) = S,

а условный оптимальный выигрыш

Wm(S )= m(S).

Задавая значения S, мы для каждого значения S будем знать xm(S) и Wm(S). Последний шаг оптимизирован.

Перейдем к предпоследнему, (m -- 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим Wm-1(S) условный оптимальный выигрыш на двух последних шагах: (m -- 1)-м и m-м (который уже оптимизирован). Если мы выделим на (m--1)-м шаге (m--1)-му предприятию средства х, то на последний шаг останется S -- х. Наш выигрыш на двух последних шагах будет равен

m-1 (х) + Wm(S --x),

и нужно найти такое x, при котором этот выигрыш максимален:

Wm-1(S) = max {m-1(х) + Wm (S - х)}. (12.2)

x ? S

Знак max означает, что берется максимальное значение по всем x какие

x ? S

только возможны , от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достигается,-- условное оптимальное управление на (m--1)-м шаге. Далее оптимизируем (m -- 2)-й, (m -- 3)-й и т. д. шаги. Вообще, для любого i-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле

Wi(S) = max {(i(х) + Wi+1 (S - х)} (12.3)

x ? S

и соответствующее ему условное оптимальное управление xi(S) -- то значение х, при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до 1-го предприятия П1. Здесь не нужно будет вычислять значения S; мы точно знаем, что запас средств перед первым шагом равен К:

W* = W1 (К) = max {1(х) + W2(К - х)}. (12.4)

x ? К

Максимальный выигрыш (доход) от всех предприятий найден. Значение х, при котором достигается максимум (12.4), и есть оптимальное управление х1* на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у нас их останется К--х1*. Выделяем второму предприятию оптимальное количество средств: x2* = x2(K-x1*), и т. д. до конца.

Решим численный пример. Исходный запас средств К =10 (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями (m = 5). Для простоты предположим, что вкладываются только целые количества средств. Функции дохода i(x) заданы в таблице 12.1.

Таблица 12.1

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

Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 12.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум -- условный оптимальный выигрыш.

В таблице 12.2 даны результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага. В первом столбце каждой пары приводится значение

Таблица 12.2

условного оптимального управления, во втором -- условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом -- последнем -- шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию -- в данном случае он равен 5,6. В последних двух столбцах таблицы 12.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: So = К = 10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму -- пять единиц, третьему -- две, четвертому -- ни одной, пятому -- одну единицу. При этом распределении доход будет максимален и равен 5,6.

Чтобы было понятно, как заполняется таблица 12.2, продемонстрируем это на одном образце расчета. Пусть, например, нужно оптимизировать решение х3(7) -- как поступать на третьем шаге, если мы подошли к нему с запасом средств S = 7, и сколько максимум мы можем выиграть на всех оставшихся

Таблица 12.3

шагах, включая третий? Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т. е. заполнены две первые пары столбцов таблицы 12.2. Найдем х3(7) и W3(7). Для этого составим вспомогательную табличку (см. таблицу 12.3). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие S = 7. Во втором столбце -- то, что останется после такого вложения от запаса средств S =7. В третьем столбце -- выигрыш на третьем шаге от вложения средств х в третье предприятие (заполняется по столбцу 3(х) таблицы 12.1). В четвертом столбце -- оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i = 4 таблицы 12.2). В пятом столбце -- сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг.

Из всех выигрышей последнего столбца выбирается максимальный (в таблице 12.3 он равен W3 (7) = 3,6, а соответствующее управление x(7) =2).

Если во вспомогательной таблице типа 12.3 максимум достигается не при одном х, а при двух или больше - совершенно все равно, какое из них выбрать; от этого выигрыш не зависит. В задачах динамического программирования решение вовсе не должно быть единственным.

3. Задача о загрузке машины. Пользуясь методом динамического программирования, решим задачу о загрузке машины: имеется определенный набор предметов П1, П2, ..., Пn (каждый в единственном экземпляре); известны их веса q1, q2, ..., qn и стоимости c1, c2, ..., cn. Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе Q) была максимальна?

Процесс загрузки машины можно представлять себе как состоящий из n шагов; на каждом шаге мы отвечаем на вопрос: брать данный предмет в машину или не брать? Управление на i-м шаге равно единице, если мы данный (i-й) предмет берем, и нулю -- если не берем.

Состояние системы S характеризуется весом S, который еще остался в нашем распоряжении до конца (полной загрузки машины) после того, как предыдущие шаги выполнены (какие-то предметы погружены в машину). Для каждого из значений S мы должны найти Wi(S) -- суммарную максимальную стоимость предметов, которыми можно «догрузить» машину при данном значении S, и положить xi(S) = 1, если мы данный (i-й) предмет берем в машину, и xi(S) = 0, если не берем.

Решим числовой пример: имеется шесть предметов, веса и стоимости которых указаны в таблице 12.4.

Таблица 12.4

Суммарная грузоподъемность машины Q = 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна.

Будем придавать S только целые значения. Условная оптимизация решения показана в таблице 12.5, где в каждой строке для соответствующего номера шага (номера предмета) приведены: условное оптимальное управление хi (0 или 1) и условный оптимальный выигрыш Wi (стоимость всех оставшихся до конца предметов при оптимальном управлении на всех шагах).

В таблице 12.5 выделены: оптимальный выигрыш W* = 57 и оптимальные шаговые управления, при которых этот выигрыш достигается: х1* = 0, х2* = 1, x3* = 0, х4* = 1, x5* = 1, x6* = 0, т. е. загрузить машину надо предметами 2, 4 и 5, суммарный вес которых равен в точности 35 (при оптимальном выборе грузов может быть и некоторый общий «недогруз»).

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

Таблица 12.5

§3. Задача динамического программирования в общем виде. Принцип оптимальности

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

Объясняется это правило так: при решении задачи динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники в замен устаревшей на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на этот процесс.

Другой момент, который следует учитывать при выборе управления на данном шаге,--это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств, вкладываемых в предприятие в i-м году, необходимо знать, какая прибыль получена в предыдущем (i-1)-м году. Таким образом, при выборе шагового управления необходимо учитывать:

1) возможные исходы предыдущего шага;

2) влияние управления на все оставшиеся до конца процесса шаги.

В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и приводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Вначале оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления xm на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, делая предположения об исходах окончания (m-2)-го шага и определяя условное оптимальное управление на (m-1)-м шаге, приносящее оптимальный выигрыш на двух последних шагах--(m-1)-м и m-м. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно.

Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является безусловным оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех шагах.

Раздел 4. Марковские случайные процессы

§1. Основные понятия теории марковских процессов

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

Пусть имеется некоторая физическая система S, которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда будем говорить, что в системе S протекает случайный процесс.

Под «физической системой» можно понимать что угодно: техническое устройство, группу таких устройств, предприятие, отрасль промышленности, живой организм, популяцию и т. д. Большинству процессов, протекающих в реальных системах, свойственны, в той или иной мере, черты случайности, неопределенности.

Например: система S -- техническое устройство, состоящее из ряда узлов, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в этой системе, безусловно, случаен.

Случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 u не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t0 (см. рисунок 14.1) система находится в определенном состоянии S0.

Рисунок 14.1

Мы наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю предысторию процесса, все, что было при t < t0. Нас интересует будущее (t > t0). Так как в точности его предугадать мы не можем - наш процесс случайный, значит -- непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время система S окажется в состоянии S1 или сохранит состояние S0, и т. п.

Если процесс -- Марковский, то предсказывать можно, только учитывая настоящее состояние системы S0 и забыв о его «предыстории» (поведении системы при t < t0). Само состояние S0, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Иначе формулируя, в Марковском процессе «будущее зависит от прошлого только через настоящее».

В исследовании операций большое значение имеют так называемые Марковские случайные процессы с дискретными состояниями и непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3,., . можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, если переход может осуществиться, в принципе, в любой момент. Мы будем рассматривать только процессы с дискретными состояниями и непрерывным временем.

Пример такого процесса: техническое устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможные состояния системы можно перечислить:

So -- оба узла исправны,

S1 -- первый узел ремонтируется, второй исправен,

S2 -- второй узел ремонтируется, первый исправен,

S3 -- оба узла ремонтируются.

Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или другого узла или окончания ремонта.

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой -- так называемым графом состояний.

Состояния системы изображаются прямоугольниками, а возможные переходы из состояния в состояние -- стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S1, S2, ...., Sn.

Построим граф состояний для рассмотренного выше примера (см. рисунок 14.2).

Рисунок 14.2

Стрелка, направленная из S0 в S1, означает переход в момент отказа первого узла; стрелка, направленная обратно, из S1 в S0,-- переход в момент окончания ремонта этого узла. Остальные стрелки объясняются аналогично.

Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем, является Марковским, то для его описания можно построить довольно простую математическую модель.

§2. Потоки событий

Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Например: поток вызовов на телефонной станции; поток отказов (сбоев) ЭВМ; поток железнодорожных составов, поступающих на сортировочную станцию; поток частиц, попадающих на счетчик Гейгера, и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени Ot (рисунок 15.1); положение каждой из них случайно, и на рисунке 15.1 изображена только какая-то одна реализация потока.

Рисунок 15.1

Важной характеристикой потока событий является его интенсивность -- среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть как постоянной ( = const), так и переменной, зависящей от времени t. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик -- интенсивнее, чем в другие часы.

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока должна быть постоянной.

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут считаться стационарными. Например, поток вызовов, поступающих на АТС между 13 и 14 часами, практически стационарен; тот же поток в течение суток уже не стационарен.

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени 1 и 2 (см. рисунок 15.2) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой.

Рисунок 15.2

Это означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А вот поток покупателей, отходящих от прилавка с купленными товарами, уже имеет последействие (т.к. интервал времени между отдельными покупателями не может быть меньше, чем минимальное время t0 обслуживания каждого из них).

Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по несколько сразу. Например, поток клиентов, направляющихся в парикмахерскую или к зубному врачу, обычно ординарен, чего нельзя сказать о потоке клиентов, направляющихся в загс для регистрации брака. Поток поездов, подходящих к станции, ординарен, а поток вагонов -- неординарен. Если поток событий ординарен, то вероятностью попадания на малый участок времени t двух или более событий можно пренебречь.

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» связано с тем, что процессы, связанные с простейшими потоками, имеют наиболее простое математическое описание.

§3. Уравнения Колмогорова для вероятностей состояний

Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, представим, что все переходы системы S из состояния в состояние происходят под действием каких-то потоков событий. Если все потоки событий, переводящие систему S из состояния в состояние,-- простейшие, то процесс, протекающий в системе, будет Марковским.