2015-10-13
6281
В этом параграфе мы рассмотрим (и даже решим до конца) несколько простых (до крайности упрощенных) примеров задач динамического программирования.
1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий
два пункта А и В, из которых второй лежит к северо- востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 13.1). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны.
Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути, и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В на отдельные шаги (один шаг — один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным «слепым» перебором.
Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном — на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из т = 7 + 5 = 12 отрезков, направленных на восток или на север (рис. 13.2). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна.
Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной (х) и северной (у), обе — целочисленные (0 < х < < 7, 0 < y < 5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 13.2) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление «с») или на восток (управление «в»). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по- прежнему будем называть «условным оптимальным выигрышем» (хотя в данном случае это не «выигрыш», а «проигрыш») для данного состояния системы S перед началом очередного шага.
Процедуру условной оптимизации будем разворачивать в обратном направлении — от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 13.3). Где мы можем находиться после 11-го шага? Только
там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из точек В1 или В2. Если мы находимся в точке В\, у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В\, а оптимальное управление покажем короткой стрелкой, исходящей из В1 и направленной на восток. Для точки B2 управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В2. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В1, В2 найден и записан в соответствующем кружке.
Теперь давайте оптимизировать предпоследний (11- й) шаг. После предпредпоследнего (10-го) шага мы могли оказаться в одной из точек С1, С2, С3 (рис. 13.4). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти на восток; обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при B). Число 21 записываем в кружке при точке С1. Для точки С2 управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В2 до конца — еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С2 — идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2). Для точки С3 управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С3).
Аналогично, «пятясь» от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление («с» или «в»), которое обозначим стрелкой, и условный оптимальный выигрыш (расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним — уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 13.5.
Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем, куда идти (стрелка) и во что нам обойдется путь до конца (число в кружке).. В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В: W* = 118.
Теперь остается построить безусловное оптимальное управление — траекторию, ведущую из А и В самым дешевым способом. Для этого нужно только «слушаться стрелок», т. е. прочитать, что они предписывают делать на каждом шаге. Такая оптимальная траектория отмечена на рис. 13.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:
х * = (с, с, с, с, в, в, с, в, в. в, в, в, в),
т. е. первые четыре шага мы должны делать на север, следующие два — на восток, затем опять один на север и остальные пять — на восток. Задача решена.
Заметим, что в ходе условной оптимизации мы можем столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, т. е. приводят к одинаковому расходу средств от этой точки до конца, Например, в точке с координатами (5; 1) оба управления «с» и «в» являются оптимальными и дают расход до конца равным 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали «с»; с тем же успехом мы могли бы выбрать «в»). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании; в дальнейшем мы специально отмечать их не будем, а попросту выберем произвольно любой из равноценных вариантов. От этого произвола, разумеется, может зависеть оптимальное у п р а в л е ние всем процессом, но не оптимальный выигрыш. Вообще, в задачах динамического программирования (как и в задачах линейного) решение далеко не всегда единственное.
А теперь вернемся к началу и попробуем решить задачу «наивным» способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два, выбираем любое). Таким способом мы получим управление
х = (с. С, в, в, в, в, с, в, в, в, с, с)
Подсчитаем расходы для этой траектории. Они будут равны W = 10 +12 + +8+ 10 + 11 + 13+ 15 + 8 + + 10 + 9 + 8+14= 128, что безусловно больше, чем W* = 118. В данном случае разница не очень велика, но в других она может быть существенной.
В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь «по ступенькам», перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: «с» или «в». Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, по, разумеется, усложняет и удлиняет расчеты.
Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике: например, при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле расхода горючего) набора скорости и высоты летательным аппаратом.
Сделаем одно попутное замечание. Внимательный читатель, вероятно, заметил, что в нашей задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные — в обратном направлении. Действительно, это так: в любой задаче динамического программирования «начало» и «конец» можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на «уже сложившиеся» условия к началу данного шага, чем на те, которые еще «предстоят» после этого шага. По существу же оба подхода совершенно равносильны.
2. Задача о распределении ресурсов. Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, [6, 10]). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между т предприятиями Пі, П2,..., П т. Каждое из предприятий Ц при вложении в него каких-то средств х приносит доход, зависящий от х, т. е. представляющий собой какую-то функцию φ(х). Все функции φ(х) (i = 1, 2,..., т) заданы (разумеется, эти функции — неубывающие). Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?
Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй — в П2 и т. д.
Управляемая система S в данном случае — средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S — наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х1, x2,..., хт, выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел х1, x2,..., хт, при которой суммарный доход максимален:
Решим эту задачу сначала в общем, формульном виде, а потом — для конкретных числовых данных. Найдем для каждого 7-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш W7(S), а соответствующее ему условное оптимальное управление — средства, вкладываемые в 7-е предприятие, — x7(S).
Начнем оптимизацию с последнего, m-го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие П т. Поэтому условное оптимальное управление на т-м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.
а условный оптимальный выигрыш
Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать xm(S) и Wm(S). Последний шаг оптимизирован.
Перейдем к предпоследнему, (т — 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим Wm- 1(S) условный оптимальный выигрыш на двух последних шагах: (т — 1)-м и т-м (который уже оптимизирован). Если мы выделим на (т — 1)-м шаге (т— 1)-му предприятию средства х, то на последний шаг останется S — х. Наш выигрыш на двух последних шагах будет равен
и нужно найти такое х, при котором этот выигрыш максимален:
Знак 
означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достигается,— условное оптимальное управление на (т — 1)-м шаге. Далее оптимизируем (т — 2)-й, (т — 3)-й и т. д. шаги. Вообще, для любого i-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле
и соответствующее ему условное оптимальное управление xi(S) — то значение х, при котором этот максимум достигается.
Продолжая таким образом, дойдем, наконец, до 1-го предприятия П1. Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:
Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение х, при котором достигается максимум (13.4), и есть оптимальное управление xt * на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у нас их останется К—x1*. «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: x2* = х2 (К — x1*), и т. д. до конца.
А теперь решим численный пример. Исходный запас средств К = 10 (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями (т = 5). Для простоты предположим, что вкладываются только целые количества средств. Функции дохода ф7(х) заданы в таблице 13.1.
Таблица 13.1
| х | | φ1(х) | φ2(х) | φ3(х) | φ4(х) | φ5(х) |
| 0,5 | 0,1 | 0,6 | 0,3 | 1,0 | |
| 1,0? | 0,5 | 1,1 | 0,6 | 1,2 | |
| І А | 1,2 | 1,2 | 1,3 | 1,3 | |
| 2,0 | 1,3 | М | 1,4 | 1,3 | |
| 2,5 | 2,5 | 1,6 | 1,5 | 1,3 | |
| 2,8 | 2,9 | 1,7 | 1,5 | 1,3 | |
| 3,0 | 3,5 | 1,8 | 1,5 | 1,3 | |
| 3,0 | 3,5 | 1,8 | 1,5 | 1,3 |
В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно «освоить» лишь ограниченное количество средств).
Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум — условный оптимальный выигрыш.
В таблице 13.2 даны результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага. В первом столбце каждой пары приводится значение условного оптимального управления, во втором
Таблица 13.2
| S | i = 5 | i = 4 | і = 3 | i = 2 | і = 1 | |||||
| x5(S) | W5(S) | x4(S) | W4(S) | x3(S)| W3(S> | x2(S) | W2(S) | x1(S) | W1(S) | ||
| 1,0 | 1,0 | 1,0 | 1,0 | |||||||
| 1,2 | 1,3 | 1,6 | 1,6 | |||||||
| 1,3 | 1,6 | |2| | 2,1 | 2,1 | ||||||
| 1,3 1,3 1,3 1,3 | 2,3 2,5 2,6 2,7 | 2,4 2,9 3,4 3,6 | 2,4 2,9 3,5 4,1 | |||||||
| 1,3 | 2,8 | 3,7 | 4,6 | |||||||
| 1,3 | 2,8 | 3,9 | 5,1 | |||||||
| 1,3 | 2,8 | 4,1 | 5,6 | \ 5,6 |
— условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом — последнем — шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию — в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: S0 = К = 10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму — пять единиц, третьему — две, четвертому — ни одной, пятому — одну единицу. При этом распределении доход будет максимален и равен 5,6.
Чтобы читателю было понятно, как заполняется таблица 13.2, продемонстрируем это на одном образце расчета. Пусть, например, нам нужно оптимизировать решение х3(7)— как поступать на третьем шаге, если мы подошли к нему с запасом средств S = 7, и сколько максимум мы можем выиграть на всех оставшихся шагах, включая третий?
Таблица 13.3
| X | 7 — х |  |
W4(7 – x) | Φ2(x) + W4(7 - x) |
| 1,8 | 1,8 | |||
| 1,7 | 1,0 | 2,7 | ||
| 1,6 | 1,3 | 2,9 | ||
| м | 1,6 | 3,0 | ||
| 1,2 | 2,3 | 3,5 | ||
| 1*1 | 1,1 | 2,5 | ||
| 0,6 | 2,6 | 3,2 | ||
| 2,7 | 2,7 |
Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т. е. заполнены две первые пары столбцов таблицы 13.2. Найдем х3(7) и W3(7). Для этого составим вспомогательную табличку (см. таблицу 13.3). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие 5 = 7. Во втором столбце — то, что останется после такого вложения от запаса средств S = 7. В третьем столбце — выигрыш на третьем шаге от вложения средств х в третье предприятие (заполняется по столбцу φ3(х) таблицы 13.1). В четвертом столбце — оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i = 4 таблицы 13.2). В пятом столбце — сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг.
Из всех выигрышей последнего столбца выбирается максимальный (в таблице 13.3 он равен W3(7) = 3,6, а соответствующее управление x(7) = 2).
Возникает вопрос: а что если во вспомогательной таблице типа 13.3 максимум достигается не при одном х, а при двух или больше? Отвечаем: совершенно все равно, какое из них выбрать; от этого выигрыш не зависит. Вообще, в задачах динамического программирования решение вовсе не должно быть единственным (мы об этом уже упоминали).
3. Задача о загрузке машины. Пользуясь методом динамического программирования, можно с успехом решать ряд задач оптимизации, описанных в главе 3, в частности, некоторые задачи целочисленного программирования. Заметим, что целочисленность решений, так затрудняющая задачи линейного программирования, в данном случае не усложняет, а наоборот, упрощает процедуру (как нам ее упростила целочисленность вложений в предыдущей задаче).
В качестве примера рассмотрим задачу о загрузке машины (мы уже упоминали о ней в предыдущей главе): имеется определенный набор предметов П1, П2,......, Пп (каждый в единственном экземпляре); известны их веса q1 q2,..., qn и стоимости с1 c2,..., сп Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе < Q) была максимальна?
Нетрудно заметить, что эта задача, в сущности, ничем не отличается от предыдущей (распределение ресурсов между п предприятиями), но несколько проще ее. В самом деле, процесс загрузки машины можно ' представлять себе как состоящий из п шагов; на каждом шаге мы отвечаем на вопрос: брать данный предмет в машину или не брать? Управление на i -м шаге равно единице, если мы данный (i -й) предмет берем, и нулю — если не берем. Значит, на каждом шаге у нас всего два управления, а это очень приятно.
А чем мы будем характеризовать состояние системы S перед очередным шагом? Очевидно, весом S, который еще остался в нашем распоряжении до конца (полной загрузки машины) после того, как предыдущие шаги выполнены (какие-то предметы погружены в машину). Для каждого из значений S мы должны. найти Wi (S) — суммарную максимальную стоимость предметов, которыми можно «догрузить» машину при данном значении S, и положить xi (S) = 1, если мы данный (i -й) предмет берем в машину, и xi (S) = 0, если не берем. Затем эти условные рекомендации должны быть прочтены, и дело с концом!
Решим до конца конкретный числовой пример: имеется шесть предметов, веса и стоимости которых указаны в таблице 13.4.
Таблица 13.4
| Предмет П i | П1 | П2 | П3 | П4 | П5 | П6 |
| Вес qi | ||||||
| Стоимость ci |
Суммарная грузоподъемность машины Q = 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна1.
Как и ранее, будем придавать S только целые значения. Условная оптимизация решения показана в таблице 13.5, где в каждой строке для соответствующего номера шага (номера предмета) приведены: условное оптимальное управление х, (0 или 1) и условный оптимальный выигрыш Wi (стоимость всех оставшихся до конца предметов при оптимальном управлении на всех шагах). Как эта таблица составляется, мы уже объяснять не будем — тут полная аналогия с предыдущей задачей, с той разницей, что возможные управления только 0 или 1.
В таблице 13.5 выделены: оптимальный выигрыш W* = 57 и оптимальные
Предметы в таблице 13.4 перенумерованы в порядке возрастания веса; стоимости их также возрастают, что не обязательно, но естественно. Заранее ясно, что загружать машину предметами большого веса и малой стоимости нецелесообразно.
шаговые управления, при которых этот выигрыш достигается: Xj* = 0, х2* = 1, х3* = = 0, x4* = 1, х5* = 1, х6* = 0, т. е. загрузить машину надо предметами 2,
4 и 5, суммарный вес которых равен в точности 35 (вообще это необязательно; при оптимальном выборе грузов может быть и некоторый общий «недогруз»). Таблица 13.5
| S | i = 6 | i = -5 | і =4 | i = 3 | i = 2 | i = 1 | |||||||
| хi | W i | хi | Wi | хi | Wi | хi | Wi | хi | Wi | хi | Wi | ||
| 0 | |||||||||||||
| n | |||||||||||||
| 1 | |||||||||||||
| 1 | 0 | ||||||||||||
| 1 | 0 | 57 | |||||||||||
Заметим, что в нашем элементарном примере, возможно, было бы проще искать решение «простым перебором»), пробуя все возможные комбинации предметов, проверяя на каждой из них, «влезают» ли они в заданный вес, и выбирая ту, для которой стоимость максимальна. Но при большом числе предметов это было бы затруднительно: число комбинаций неумеренно растет при увеличении числа предметов. Для метода же динамического программирования увеличение числа шагов не страшно: оно только приводит к пропорциональному возрастанию объема расчетов.
