Оптимальные модели экономической динамики

5. Оптимальные модели экономической динамики Оптимальные модели экономической динамики представляют важный класс задач теории оптимального управления. Динамические экономические модели – это модели, описывающие экономические показатели и их взаимосвязь в развитии. При этом отдельные показатели в данный момент времени зависят от других показателей в предыдущие моменты времени. Математическое описание динамических моделей производится в виде разностных уравнений в моделях с дискретным временем, с помощью дифференциальных уравнений в моделях с непрерывным временем, а также систем обыкновенных алгебраических уравнений. Особый интерес вызывают экономические процессы, одной из основных черт которых является "многошаговость". Изучением таких процессов занимается динамическое программирование. 5.1. Метод динамического программирования и общий принцип оптимальности Многоэтапность ("многошаговость") ассоциируется прежде всего с развитием процесса во времени. Поэтому динамическое программирование хорошо применимо к динамическим системам управления, в которых должно быть принято не однократное оптимальное решение, а ряд последовательных во времени решений, обеспечивающих оптимальность всего развития в целом. Метод динамического программирования опирается на общий принцип оптимальности: Если некоторая последовательность решений оптимальна, то на любом этапе остающиеся решения образуют оптимальную политику по отношению к результату предшествующих решений. Именно на основе общего принципа оптимальности можно уверенно отбрасывать некоторые решения на последних этапах, даже не зная тех решений, которые были приняты на предшествующих этапах. В теории динамического программирования изучаются как стохастические, так и детерминированные процессы. Для этих процессов на основе общего принципа оптимальности строятся некоторые функциональные уравнения, которые позволяют установить ряд важных свойств изучаемого процесса и определять оптимальное направление его развития. Динамическое программирование (иначе "динамическое планирование") есть особый метод оптимизации решений, специально приспособленный к так называемым "многошаговым" (или "многоэтапным") операциям. Представим себе некоторую операцию Ơ, распадающуюся на ряд последовательных "шагов" или "этапов", например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой самолетов нескольких полос противовоздушной обороны; или же последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции (подобно вышеприведенным) расчленяются на шаги естественно; в некоторых членение приходится вводить искусственно – скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает какое-то время Δt. Итак, рассмотрим операцию Ơ, состоящую из m шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть "выигрышем". Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах: , где wi – выигрыш на t-м шаге. Если W обладает таким свойством, то его называют "аддитивным критерием". Операция Ơ, о которой идет речь, представляет собой управляемый процесс, т.е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение "шаговым управлением". Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой х, а шаговые управления – буквами х1, х2, …, хт: . Следует иметь в виду, что х1, х2, …, хт в общем случае – не числа, а, может быть, векторы, функции и т.д. Требуется найти такое управление х, при котором выигрыш W обращается в максимум: . То управление х*, при котором этот максимум достигается, будем называть оптимальным равнением. Оно состоит из совокупности оптимальных шаговых управлений: Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать W*: . Эта формула читается так: величина W* есть максимум из всех W(x) при разных управлениях х (максимум берется по всем управлениям х, возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут . Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под "управлением" и каков "выигрыш" (показатель эффективности) W. 1. Планируется деятельность группы промышленных предприятий П1, П2, ..., Пk на период т хозяйственных лет (т-летку). В начале периода на развитие группы выделены какие-то средства М, которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за т лет был максимальным? Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах): и, значит, обладает свойством аддитивности. Управление х на i-м шаге состоит в том, что в начале 1-го года предприятиям выделяются какие-то средства xi1, хi2, ..., хik (первый индекс – номер шага, второй – номер предприятия). Таким образом, шаговое управление есть вектор с k составляющими: Разумеется, величины w1 в формуле зависят от количества вложенных в предприятия средств. Управление х всей операцией состоит из совокупности всех шаговых управлений: . Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление х*), при котором величина W обращается в максимум. В этом примере шаговые управления были векторами, в последующих примерах они будут проще и выражаться просто числами. 2. Космическая ракета состоит из т ступеней, а процесс ее вывода на орбиту – из т этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета "полезного" веса кабины) выделен какой-то общий вес: , где Gi – вес i-й ступени. В результате i-го этапа (сгорания и сбрасывания i-й ступени) ракета получает приращение скорости Δi, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы скорость ракеты V при ее выводе на орбиту была максимальна? В данном случае показатель эффективности (выигрыш) будет , где Δi, – выигрыш (приращение скорости) на i-м шаге. Управление х представляет собой совокупность весов всех ступеней Gi: . Оптимальным управлением х* будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление – одно число, а именно вес данной ступени. 3. Владелец автомашины эксплуатирует ее в течение т лет. В начале каждого года он может принять одно из трех решений: 1) продать машину и заменить ее новой; 2) ремонтировать ее и продолжать эксплуатацию; 3) продолжать эксплуатацию без ремонта. Шаговое управление – выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т.е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение готовых машин были минимальны? Показатель эффективности (в данном случае это не "выигрыш", а "проигрыш", но это неважно) равен , где wi – расходы в i-м году. Величину W требуется обратить в минимум. Управление операцией в целом представляет собой какую-то комбинацию чисел 1, 2, 3, например: , что означает: первые два года – эксплуатировать машину без ремонта, последующие три года – ее ремонтировать, в начале шестого года – продать, купить новую, затем снова эксплуатировать без ремонта и т.д. Любое управление представляет собой вектор (совокупность чисел) где каждое из чисел i1, i2, ..., im имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел, при которой величина минимальна. 4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 7). Местность пересеченная, включает лесистые зоны, холмы, болота, репу, через которую надо строить мост. Требуется так провести дорогу из А в В, чтобы суммарные затраты нa сооружение участка были минимальны. Рис. 7 В этой задаче, в отличие от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на т частей, провести через точки деления прямые, перпендикулярные АВ, и считать за "шаг" переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на i-м шаге представляет собой угол i, который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений: . Требуется выбрать такое (оптимальное) управление х*, при котором суммарные затраты на сооружение всех участков минимальны: Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи. Любую многошаговую задачу можно решать по-разному: либо искать сразу все элементы решения на всех т шагах, либо же строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз – сложную. С первого взгляда идея может показаться довольно тривиальной. В самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, разбить ее на ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальна. Не так ли? Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции – получить за т лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение – расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы. Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в "болото"? Значит, планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на i-м шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой, принес наибольшую выгоду. Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего, планируется последний, т-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Т.е. не знаем условий, в которых мы приступаем к последнему шагу? Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, (т-1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на т-м шаге ("условное" потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то и так-то). Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на т-м шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, (т-1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (т-2)-й шаг, и для каждого из этих предположений найдем такое управление на (т-1)-м шаге, при котором выигрыш за последние два шага (из которых т-й уже оптимизирован!) максимален. Так мы найдем для каждого исхода (т-2)-го шага условное оптимальное управление на (т-1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, "пятясь назад", оптимизируем управление на (т-2)-м шаге и т.д., пока не дойдем до первого. Предположим, что все условные оптимальные управления и условные оптимальные выигрыши за весь "хвост" процесса (на всех шагах, начиная от данного и до конца) нам известны. Это значит: мы знаем, что надо делать, как управлять на данном шаге и что мы за это получим на "хвосте", в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно-оптимальное, а просто оптимальное управление х* и найти не условно-оптимальный, а просто оптимальный выигрыш W*. В самом деле, пусть мы знаем, в каком состоянии S0 была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим состояние системы на некоторое новое ; в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление , которое к концу второго шага переводит систему в состояние , и т.д. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге. Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды: первый раз – от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся "хвост" процесса; второй раз – от начала к концу, когда нам остается только "прочитать" уже готовые рекомендации и найти безусловное оптимальное управление х*, состоящее из оптимальных шаговых управлений . Первый этап – условной оптимизации – несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений. 5.2. Примеры решения задач динамического программирования 1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим, что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 8). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А в В, при котором суммарные затраты минимальны. Рис. 8 Как это сделать? Можно поступить одним из двух способов: либо перебрать все возможные варианты пути и выбрать тот, на котором затраты минимальны (а при большом числе отрезков это очень и очень трудно!); либо разделить процесс перехода из А в В на отдельные шаги (один шаг – один отрезок) и оптимизировать управление по шагам. Оказывается, второй способ несравненно удобнее! Тут, как и везде в исследовании операций, сказываются преимущества целенаправленного, организованного поиска решения перед наивным "слепым" перебором. Продемонстрируем, как это делается, на конкретном примере. Разделим расстояние от А до В в восточном направлении, скажем, на 7 частей, а в северном – на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из т = 7 + 5 = 12 отрезков, направленных на восток или на север (рис. 9). Проставим на каждом из отрезков число, выражающее (в каких-то условных единицах) стоимость прокладки пути по этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна. Рис. 9 Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной х и северной у, обе – целочисленные (0≤х≤7, 0≤у≤5). Для каждого из состояний системы (узловой точки прямоугольной сетки на рис. 9) мы должны найти условное оптимальное управление: идти нам из этой точки на север (управление с) или на восток (управление в). Выбирается это управление так, чтобы стоимость всех оставшихся до конца шагов (включая данный) была минимальна. Эту стоимость мы по-прежнему будем называть "условным оптимальным выигрышем" (хотя в данном случае это не "выигрыш", а "проигрыш") для данного состояния системы S перед началом очередного шага. Процедуру условной оптимизации будем разворачивать в обратном направлении – от конца к началу. Прежде всего произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 5). Где мы можем находиться после 11-го шага? Только там, откуда за один (последний) шаг можно попасть в В, т.е. в одной из точек В1 или В2. Если мы находимся в точке В1, у нас нет выбора (управление вынужденное): надо идти на восток, и это обойдется нам в 10 единиц. Запишем это число 10 в кружке у точки В1, а оптимальное управление покажем короткой стрелкой, исходящей из В1 и направленной на восток. Для точки В2 управление тоже вынужденное (север), расход до конца равен 14, мы его запишем в кружке у точки В2. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В1, В2 найден и записан в соответствующем кружке. Рис. 10 Рис. 11 Теперь давайте оптимизировать предпоследний (11-й) шаг. После предпоследнего (10-го) шага мы могли оказаться в одной из точек С1, С2, С3 (рис. 6). Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти на восток; обойдется это нам до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при B1). Число 21 записываем в кружке при точке С1. Для точки С2 управление уже не вынужденное: мы можем идти как на восток, так и на север. В первом случае мы затратим на данном шаге 14 единиц и от В2 до конца – еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке С2 – идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2). Для точки С3 управление снова вынужденное (с), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С3). Рис. 12 Аналогично, "пятясь" от предпоследнего шага назад, найдем для каждой точки с целочисленными координатами условное оптимальное управление (с или в), которое обозначим стрелкой, и условный оптимальный выигрыш (расход до конца пути), который запишем в кружке. Вычисляется он так: расход на данном шаге складывается с уже оптимизированным расходом, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним – уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 12. Таким образом, условная оптимизация уже выполнена: в какой бы из узловых точек мы ни находились, мы уже знаем, куда идти (стрелка) и во что нам обойдется путь до конца (число в кружке). В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В: W* = 118. Теперь остается построить безусловное оптимальное управление – траекторию, ведущую из А и В самым дешевым способом. Для этого нужно только "слушаться стрелок", т.е. прочитать, что они предписывают делать на каждом шаге. Такая оптимальная траектория отмечена на рис. 12 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет х* = (с, с, с, с, в, в, с, в, в, в, в, в), т.е. первые четыре шага мы должны делать на север, следующие два – на восток, затем опять один на север и остальные пять – на восток. Задача решена. Заметим, что в ходе условной оптимизации мы можем столкнуться со случаем, когда оба управления для какой-то точки на плоскости являются оптимальными, т.е. приводят к одинаковому расходу средств от этой точки до конца. Например, в точке с координатами (5; 1) оба управления (с и в) являются оптимальными и дают расход до конца равным 62. Из них мы произвольно выбираем любое (в нашем случае мы выбрали с; с тем же успехом мы могли бы выбрать в). Такие случаи неоднозначного выбора оптимального управления постоянно встречаются в динамическом программировании; в дальнейшем мы специально отмечать их не будем, а попросту выберем произвольно любой из равноценных вариантов. От этого произвола, разумеется, может зависеть оптимальное управление всем процессом, но не оптимальный выигрыш. Вообще, в задачах динамического программирования (как и в задачах линейного) решение далеко не всегда единственное. А теперь вернемся к началу и попробуем решить задачу "наивным" способом, выбирая на каждом шаге, начиная с первого, самое выгодное (для этого шага) направление (если таких два, выбираем любое). Таким способом мы получим управление х = (с, с, в, в, в, в, с, в, в, в, с, с). Подсчитаем расходы для этой траектории. Они будут равны W=10+12+8+10+11+13+15+8+10+9+8+14=128, что, безусловно, больше, чем W*=118. В данном случае разница не очень велика, но в других она может быть существенной. В решенной выше задаче условия были намеренно до крайности упрощены. Разумеется, никто не будет вести железнодорожный путь "по ступенькам", перемещаясь только строго на север или строго на восток. Такое упрощение мы сделали для того, чтобы в каждой точке выбирать только из двух управлений: с или в. Можно было бы вместо двух возможных направлений ввести их несколько и, кроме того, взять шаги помельче; принципиального значения это не имеет, но, разумеется, усложняет и удлиняет расчеты. Заметим, что задачи, сходные с рассмотренной выше, очень часто встречаются на практике, например при выборе наискорейшего пути между двумя точками или наиболее экономного (в смысле расхода горючего) набора скорости и высоты летательным аппаратом. Заметим, что в нашей задаче точки А и В (начало и конец) в принципе ничем друг от друга не отличаются: можно было бы строить условные оптимальные управления не с конца к началу, а с начала к концу, а безусловные – в обратном направлении. Действительно, это так: в любой задаче динамического программирования "начало" и "конец" можно поменять местами. Это совершенно равносильно описанной ранее методике в расчетном отношении, но несколько менее удобно при словесном объяснении идеи метода: легче аргументировать, ссылаясь на "уже сложившиеся" условия к началу данного шага, чем на те, которые еще "предстоят" после этого шага. По существу же, оба подхода совершенно равносильны. 2. Задача о распределении ресурсов. Метод динамического программирования позволяет с успехом решать многие экономические задачи. Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между т предприятиями П1, П2,..., Пт. Каждое из предприятий Пi при вложении в него каких-то средств х приносит доход, зависящий от х, т.е. представляющий собой какую-то функцию I(х). Все функции i(х) (i=1, 2,..., т) заданы (разумеется, эти функции – не убывающие). Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход? Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй – в П2 и т. д. Управляемая система S в данном случае – средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S – наличным запасом еще не вложенных средств. В этой задаче "шаговыми управлениями" являются средства х1, х2, …, хт, выделяемые предприятиям. Требуется найти оптимальное управление, т.е. такую совокупность чисел х1, х2, …, хт, при которой суммарный доход максимален: . Решим эту задачу сначала в общем, формульном виде, а потом – для конкретных числовых данных. Найдем для каждого i-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш Wi(S), а соответствующее ему условное оптимальное управление – средства, вкладываемые в i-е предприятие, – хi(S). Начнем оптимизацию с последнего, т-го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Пт. Поэтому условное оптимальное управление на т-м шаге: отдать последнему предприятию все имеющиеся средства S, т.е. , а условный оптимальный выигрыш . Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать хт(S) и Wт(S). Последний шаг оптимизирован. Перейдем к предпоследнему, (т-1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим Wm(S) условный оптимальный выигрыш на двух последних шагах: (т–1)-м и т-м (который уже оптимизирован). Если мы выделим на (т–1)-м шаге (т–1)-му предприятию средства х, то на последний шаг останется S – х. Наш выигрыш на двух последних шагах будет равен , и нужно найти такое х, при котором этот выигрыш максимален: . Знак означает, что берется максимальное значение по всем х, какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение х, при котором этот максимум достигается, – условное оптимальное управление на (т–1)-м шаге. Далее оптимизируем (т–2)-й, (т–3)-й и т.д. шаги. Вообще, для любого i-го шага будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле и соответствующее ему условное оптимальное управление Xi(S) – то значение х, при котором этот максимум достигается. Продолжая таким образом, дойдем, наконец, до 1-го предприятия П1. Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К: Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только "прочесть рекомендации". То значение х, при котором достигается максимум, и есть оптимальное управление на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у нас их останется К–. "Читая" рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: и т. д. до конца. А теперь решим численный пример. Исходный запас средств К=10 (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями (т=5). Для простоты предположим, что вкладываются только целые количества средств. Функции дохода i (х) заданы в табл. 7. Таблица 7 х 1 (х) 2 (х) 3 (х) 4 (х) 5 (х) 1 0,5 0,1 0,6 0,3 1,0 2 1,0 0,5 1,1 0,6 1,2 3 1,4 1,2 1,2 1,3 1,3 4 2,0 1,8 1,4 1,4 1,3 5 2,5 2,5 1,6 1,5 1,3 6 2,8 2,9 1,7 1,5 1,3 7 3,0 3,5 1,8 1,5 1,3 8 3,0 3,5 1,8 1,5 1,3 В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно "освоить" лишь ограниченное количество средств). Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по табл. 7, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум – условный оптимальный выигрыш. В табл. 8 даны результаты условной оптимизации по всем шагам. Таблица построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага. В первом столбце каждой пары приводится значение условного оптимального управления, во втором – условного оптимального выигрыша. Таблица 8 S i=5 i=4 I=3 i=2 i=1 х5(s) W5(s) х4(s) W4(s) х3(s) W3(s) х2(s) W2(s) х1(s) W1(s) 1 1 1,0 1,0 1,0 1,0 2 2 1,2 1 1,3 1 1,6 1,6 3 3 1,3 2 1,6 2 2,1 2,1 4 4 1,3 3 2,3 2 2,4 о 2,4 5 5 1,3 3 2,5 1 2,9 о 2,9 6 6 1,3 4 2,6 2 3,4 5 3,5 7 7 1,3 5 2,7 2 3,6 5 4,1 8 8 1,3 5 2,8 4 3,7 5 4,6 9 9 1,3 6 2,8 5 3,9 7 5,1 10 10 1,3 7 2,8 5 4,1 7 5,6 2 5,6 Таблица заполняется слева направо, сверху вниз. Решение на пятом – последнем шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию – в данном случае он равен 5, 6. В последних двух столбцах табл. 8 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: S0=К=10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму – пять единиц, третьему – две, четвертому – ни одной, пятому – одну единицу. При этом распределении доход будет максимален и равен 5, 6. Порядок заполнения табл. 8: пусть необходимо оптимизировать решение х3(7) – как поступать на третьем шаге, если мы подошли к нему с запасом средств S=7, и сколько максимум мы можем выиграть на всех оставшихся шагах, включая третий? Таблица 9 х 7–х 3(х) W4(7–х) 3(х)+W4(7–х) 7 1,8 1,8 6 1 1,7 1,0 2,7 5 2 1,6 1,3 2,9 4 3 1,4 1,6 3,0 3 4 1,2 2,3 3,5 2 5 1,1 2,5 3,6 1 6 0,6 2,6 3,2 7 2,7 2,7 Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т.е. заполнены две первые пары столбцов табл. 8. Найдем х3(7) и w3(7). Для этого составим вспомогательную табличку (табл. 9). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие S=7. Во втором столбце – то, что останется после такого вложения от запаса средств S=7. В третьем столбце – выигрыш на третьем шаге от вложения средств х в третье предприятие (заполняется по столбцу 3(х) табл. 7). В четвертом столбце – оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i=4 табл. 8). В пятом столбце – сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг. Из всех выигрышей последнего столбца выбирается максимальный (в табл. 8 он равен W3(7)=3,6, а соответствующее управление х(7)=2). Возникает вопрос: а что если во вспомогательной табл. 8 максимум достигается не при одном х, а при двух или больше? Отвечаем: совершенно все равно, какое из них выбрать; от этого выигрыш не зависит. Вообще, в задачах динамического программирования решение вовсе не должно быть единственным (мы об этом уже упоминали). 3. Задача о загрузке машины. Пользуясь методом динамического программирования, можно с успехом решать ряд задач оптимизации, описанных в главе 3, в частности, некоторые задачи целочисленного программирования. Заметим, что целочисленность решений, так затрудняющая задачи линейного программирования, в данном случае не усложняет, а наоборот, упрощает процедуру (как нам ее упростила целочисленность вложений в предыдущей задаче). В качестве примера рассмотрим задачу о загрузке машины (мы уже упоминали о ней в предыдущей главе): имеется определенный набор предметов П1, П2,..., Пn (каждый в единственном экземпляре); известны их веса q1, q2,...,qn и стоимости c1, с2,..., сn. Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе ≤ Q) была максимальна? Нетрудно заметить, что эта задача, в сущности, ничем не отличается от предыдущей (распределение ресурсов между n предприятиями), но несколько проще ее. В самом деле, процесс загрузки машины можно представлять себе как состоящий из n шагов; на каждом шаге мы отвечаем на вопрос: брать данный предмет в машину или не брать? Управление на i-м шаге равно единице, если мы данный i-й предмет берем, и нулю – если не берем. Значит, на каждом шаге у нас всего два управления, а это очень приятно. А чем мы будем характеризовать состояние системы S перед очередным шагом? Очевидно, весом S, который еще остался в нашем распоряжении до конца (полной загрузки машины) после того, как предыдущие шаги выполнены (какие-то предметы погружены в машину). Для каждого из значений S мы должны найти Wi(S) – суммарную максимальную стоимость предметов, которыми можно "догрузить" машину при данном значении S, и положить xi(S)=1, если мы данный i-й предмет берем в машину, и xi (S)=0, если не берем. Затем эти условные рекомендации должны быть прочтены, и дело с концом! Решим до конца конкретный числовой пример: имеется шесть предметов, веса и стоимости которых указаны в табл. 9. Таблица 10 Предмет Пi П1 П2 П3 П4 П5 П6 Вес qi 4 7 11 12 16 20 Стоимость сi 7 10 15 20 27 34 Суммарная грузоподъемность машины Q = 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна. Как и ранее, будем придавать S только целые значения. Условная оптимизация решения показана в табл. 10, где в каждой строке для соответствующего номера шага (номера предмета) приведены: условное оптимальное управление хi (0 или 1) и условный оптимальный выигрыш Wi (стоимость всех оставшихся до конца предметов при оптимальном управлении на всех шагах). Как эта таблица составляется, мы объяснять не будем – тут полная аналогия с предыдущей задачей, с той разницей, что возможные управления только 0 или 1. В табл. 10 выделены: оптимальный выигрыш W*=57 и оптимальные шаговые управления, при которых этот выигрыш достигается: ; ; ; ; ; , т.е. загрузить машину надо предметами 2, 4 и 5, суммарный вес которых равен в точности 35 (вообще это необязательно; при оптимальном выборе грузов может быть и некоторый общий "недогруз"). Заметим, что в нашем элементарном примере, возможно, было бы проще искать решение "простым перебором", пробуя все возможные комбинации предметов, проверяя на каждой из них, "влезают" ли они в заданный вес, и выбирая ту, для которой стоимость максимальна. Но при большом числе предметов это было бы затруднительно: число комбинаций неумеренно растет при увеличении числа предметов. Для метода же динамического программирования увеличение числа шагов не страшно: оно только приводит к пропорциональному возрастанию объема расчетов. Таблица 10 s i=6 i=5 i=4 i=3 i=2 i=1 хi1 Wi хi1 Wi хi1 Wi хi1 Wi хi1 Wi хi1 Wi 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 1 10 8 n 1 10 9 1 10 10 1 10 11 1 15 15 12 1 20 20 20 13 1 20 20 20 14 1 20 20 20 15 0. 0. 0. 1 20 20 20 16 1 27 27 27 27 17 1 27 27 27 27 18 1 27 27 27 27 19 1 27 27 27 1 30 20 1 34 34 34 34 34 21 1 34 34 34 34 34 22 1 34 34 34 ?4 34 23 1 34 34 34 1 35 1 37 24 1 34 34 34 1 35 1 37 25 1 34 34 34 1 35 1 37 26 1 34 34 34 1 35 1 37 27 1 34 34 34 1 42 1 44 28 1 34 34 1 47 47 47 29 1 34 34 1 47 47 47 30 1 34 34 1 47 47 47 31 1 34 34 1 47 1 49 49 32 1 34 34 1 54 54 54 33 1 34 34 1 54 54 54 34 1 34 34 1 54 54 54 35 1 34 34 1 54 54 1 57 57 5.3. Задача динамического программирования в общем виде Рассмотренные выше простейшие задачи динамического программирования дают понятие об общей идее метода: пошаговая оптимизация, проходимая в одном направлении "условно", в другом – "безусловно". Метод динамического программирования является очень мощным и плодотворным методом оптимизации управления; ему не страшны ни целочисленность решения, ни нелинейность целевой функции, ни вид ограничений, накладываемых на решение. Но в отличие от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре; оно может быть передано на машину только после того, как записаны соответствующие формулы, а это часто бывает не так-то легко. Рассмотрим основные вопросы по формулировке и решению задач динамического программирования. Вопрос 1: какими параметрами характеризуется состояние управляемой системы S перед каждым шагом? От удачного выбора набора этих параметров часто зависит возможность успешно решить задачу оптимизации. В трех конкретных примерах, которые мы решали в предыдущем параграфе, состояние системы характеризовалось очень небольшим числом параметров: двумя координатами – в первом примере, одним числом – во втором и третьем. Но такие ультрапростые задачи не так уж часто встречаются на практике. Если, как это обычно и бывает, состояние системы описывается многими параметрами (так называемыми "фазовыми координатами"), то становится трудно перед каждым шагом перебрать все их варианты и для каждого найти оптимальное условное управление. Последнее еще больше затрудняется в случае, когда число возможных вариантов управления велико. В этих случаях над нами повисает, по меткому выражению Р. Беллмана, "проклятие многомерности" – бич не только метода динамического программирования, но и всех других методов оптимизации. Обычно задачи динамического программирования решаются не вручную, а на ЭВМ, однако многие такие задачи не под силу даже современным машинам. Поэтому очень важно уметь правильно и "скромно" поставить задачу, не переобременяя ее лишними подробностями, упрощая, если возможно, описание управляемой системы и вариантов управления. Так что в методе динамического программирования очень многое зависит от искусства и опыта исследователя. Вторая задача после описания системы и перечня управлений – это членение на шаги (этапы). Иногда (на счастье) оно бывает задано в самой постановке задачи (например, хозяйственные годы в экономических задачах), но часто членение на шаги приходится вводить искусственно, как мы сделали, например, в задаче 1 п. 2.2.2. Если бы мы в этой задаче не ограничились самым примитивным случаем всего двух управлений (с и в), то было бы удобнее членение на шаги произвести иначе, например, считая за "шаг" переход с одной прямой, параллельной оси ординат, на другую. Можно было бы вместо прямых рассмотреть окружности с центром в точке А или же другие кривые. Все такие способы выбора наивыгоднейшего пути неизбежно ограничивают выбор возможных направлений. Если за "шаги" считать переходы с одной прямой, параллельной оси ординат, на другую, то здесь множество возможных управлений не предусматривает "пути назад", т.е. с более восточной прямой на более западную. В большинстве задач практики такие ограничения естественны (например, трудно себе представить, чтобы наивыгоднейшая траектория космической ракеты, пущенной с Земли, на каких-то участках включала движение "назад", ближе к Земле). Но бывает и другая обстановка. Например, путь по сильно пересеченной местности ("серпантинная" дорога в горах) часто "петляет" и возвращается ближе к исходному пункту. При постановке задачи динамического программирования, в частности при выборе системы координат и способа членения на шаги, должны быть учтены все разумные ограничения, накладываемые на управление. Вопрос 2: как быть с числом шагов т? С первого взгляда может показаться, что чем больше т, тем лучше. Это не совсем так. При увеличении т возрастает объем расчетов, а это не всегда оправдано. Число шагов нужно выбирать с учетом двух обстоятельств: 1) шаг должен быть достаточно мелким для того, чтобы процедура оптимизации шагового управления была достаточно проста, и 2) шаг должен быть не слишком мелким, чтобы не производить ненужных расчетов, только усложняющих процедуру поиска оптимального решения, но не приводящих к существенному изменению оптимума целевой функции. В любом случае практики нас интересует не строго оптимальное, а "приемлемое" решение, не слишком отличающееся от оптимального по значению выигрыша W*. Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования (его часто называют "принципом оптимальности"): Каково бы ни было состояние системы S перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах были максимальными. Сформулируем несколько практических рекомендаций, полезных начинающему при постановке задач динамического программирования. Эту постановку удобно проводить в следующем порядке. 1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом. 2. Расчленить операцию на этапы (шаги). 3. Выяснить набор шаговых управлений хi для каждого шага и налагаемые на них ограничения. 4. Определить, какой выигрыш приносит на i-м шаге управление хi, если перед этим система была в состоянии S, т.е. записать "функции выигрыша": . 5. Определить, как изменяется состояние S системы S под влиянием управления хi, на i-м шаге: оно переходит в новое состояние "Функции изменения состояния" тоже должны быть записаны. 6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Wi(S) (начиная с i-го шага и до конца) через уже известную функцию Wi+1(S): . Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (подчеркнем, что в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние S'=I(S, хi)). 7. Произвести условную оптимизацию последнего, т-го шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле и находя условное оптимальное управление xт(S), для которого этот максимум достигается. 8. Произвести условную оптимизацию (т–1)-го, (т–2)-го и т.д. шагов по формуле (14.3), полагая в ней i=(т–1), (т–2), ..., и для каждого из шагов указать условное оптимальное управление хi(S), при котором максимум достигается. Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно – прямо находим оптимальный выигрыш для данного начального состояния S0. Это и есть оптимальный выигрыш за всю операцию: . 9. Произвести безусловную оптимизацию управления, "читая" соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (19); для вновь найденного состояния найти оптимальное управление на втором шаге и т.д. до конца. Сделаем несколько дополнительных замечаний общего характера. До сих пор мы рассматривали только аддитивные задачи динамического программирования, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Но метод динамического программирования применим также и к задачам с так называемым "мультипликативным" критерием, имеющим вид произведения: (если только выигрыши wi положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (14.3) вместо знака "плюс" ставится знак умножения : . В заключение несколько слов о так называемых "бесконечношаговых" задачах динамического программирования. На практике встречаются случаи, когда планировать операцию приходится не на строго определенный, а на неопределенно долгий промежуток времени, и нас может интересовать решение задачи оптимального управления безотносительно к тому, на каком именно шаге операция заканчивается. В таких случаях бывает удобно рассмотреть в качестве модели явления бесконечношаговый управляемый процесс, где не существует "особенного" по сравнению с другими последнего шага (все шаги равноправны). Для этого, разумеется, нужно, чтобы функции i выигрыша и функции i изменения состояния не зависели от номера шага. 6. Условная оптимизация и достаточные условия оптимальности Оптимизация – нахождение всех минимизирующих элементов. В пассивных экономических моделях (таких, как изучающие общее равновесие) нас интересует оптимальное поведение лица, принимающего решение. В активных моделях (таких, как модели эффективного роста) мы сами заинтересованы в получении оптимума. В последние годы появилась тенденция к переходу от моделей типа "затраты – выпуск" к моделям анализа производственных процессов, от простейших моделей роста к моделям, изучающим траектории эффективного и оптимального роста. В макроэкономических политико-ориентированных моделях, где оптимизация в основном порождена параметрическими оценками, направление исследования изменилось в сторону более сложных моделей выбора оптимальной политики. Значительное развитие теории оптимизации за последние годы привело к целому ряду различных методов анализа и оптимизации процессов в экономике. Рассмотрим общую постановку задачи условной оптимизации. 6.1. Общая постановка задачи условной оптимизации Сформулируем общую постановку задачи оптимизации в стандартной форме. Рассматривается max f(x), x=(x1, …, xn), при следующих ограничениях: 1) gi(x)≤0, i=1, …, m; 2) xk≥0, kS, где S – некоторое подмножество индексов (1, …, n), f(x) – целевая функция, x – n-мерный вектор переменных задачи. Ограничения (1) – функциональные ограничения, ограничения (2) – прямые. Функции f, gi – непрерывные. Удобно иметь все неравенства одного знака. Если же встретятся неравенства вида ai(x) ≥0, всегда можно, обозначив gi(x)= – ai(x), свести систему к стандартной форме. Приведенный выше выбор знака для задачи на максимум (и обратные знаки в задаче на минимум) естественен во многих экономических задачах и задачах линейного программирования. Задача на оптимум не всегда имеет решение. Например, задача max (х1+х2) при условии, что х1–х2≤0, имеет неограниченное допустимое множество и не имеет решений: для любого Х можно найти другой допустимый вектор, дающий большее значение целевой функции. Тем не менее, можно выделить широкий класс задач, для которых гарантируется существование оптимума. 6.2. Достаточные условия существования оптимума Теорема Вейерштрасса: непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (минимума) по крайней мере в одной точке этого множества. Достаточные условия оптимизации, сформулированные в теореме Вейерштрасса, позволяют выделить последовательность этапов оптимизации для задачи вида max (или min) f(x) при х, принадлежащих замкнутому допустимому множеству k, если оно существует, является либо критической точкой функции f(x), либо граничной точкой множества k, либо тем и другим одновременно. Выделим основные этапы решения: 1) находятся критические точки f(x); 2) вычисляются значения f(x) вдоль границы; 3) сравниваются полученные значения целевой функции; 4) выбираются точки, дающие максимум или минимум функции f(x). Если f(x) не является всюду дифференцируемой, то вместе с критическими и граничными точками необходимо исследовать и точки, в которых f(x) не дифференцируема. 6.3. Классические методы решения задач на условный оптимум Как указывалось при обсуждении общей структуры задач оптимизации, классические методы условной оптимизации могут применяться к задаче, характеризующейся следующими особенностями: а) целевая функция и функции ограничений обладают подходящими свойствами гладкости. Обычно они принадлежат классу С2. Этого достаточно для всех целей; б) все функциональные ограничения являются равенствами; в) отсутствуют прямые ограничения на переменные (ограничения на неотрицательность). Классическая задача на условную оптимизацию в стандартной форме записывается в виде max f(x) (x – n-мерный вектор) В этой задаче все ограничения эффективны. Поэтому допустимое множество К состоит только из граничных точек и, следовательно, внутренние оптимумы исключаются. Если не все ограничения линейны, то, вообще говоря, К невыпуклое множество. Здесь рассматривается система из т уравнений с п переменными, где т < п. Если соответствующий якобиан не вырожден, можно п – т переменных выразить через остальные т (по теореме о неявной функции). Эти значения подставляются в целевую функцию, и решается задача на безусловный оптимум относительно п – т переменных. Казалось бы, этот подход обладает всеми чертами хорошей процедуры: уменьшается число переменных и задача сводится к уже исследованной. Непосредственная подстановка (замещение) часто используется при решении задач, в которых желательно получить явное решение. Однако приведенная выше процедура не столь полезна, как кажется с первого взгляда. Весьма редко удается получить явное решение системы уравнений, если они нелинейны. В типичных задачах математической экономики вид функций f и gi не определен явно. Некоторые свойства оптимального решения могут быть объяснены при использовании соотношений между производными, задаваемыми теоремой о неявной функции. Однако получаемые при этом результаты несимметричны по отношению к выбору зависимых и независимых переменных. Мы далее увидим, что, как это ни парадоксально, более полезным методом исследования свойств оптимального решения классической задачи является метод, который не уменьшает числа переменных задачи, а увеличивает его. 6.4. Метод Лагранжа Исследуем свойства функции вида: где – произвольные величины. Функция называется функцией Лагранжа, а величины – множителями Лагранжа. Иногда линейная комбинация функций, определяющих ограничения задачи, прибавляется к целевой функции, а не вычитается из нее. Разница здесь только в знаках . Форма, принятая здесь, более целесообразна для экономической интерпретации , которая будет приведена ниже. Рассмотрим производные функции по : Кроме того, для всех Если достигает максимума по х,  в точке х*, *, тогда, поскольку оптимум безусловный, это критическая точка и все частные производные в ней равны нулю. Поскольку частные производные по i равны нулю, х* К и , то x* обеспечивает максимум f(х) при х  К. Следовательно, х* является решением классической задачи на условный максимум. И наоборот, если f(х) достигает максимума в точке х*, принадлежащей К, то и . Таким образом, можно сформулировать утверждение, оправдывающее введение функции Лагранжа: а) если (х*, *) – критическая точка L (х, ), то х* К; б) если L (х, ) достигает максимума в точке х*, *, тогда f(х) достигает максимума на К в точке х*. Если же f(х) достигает максимума на множестве К в точке х*, то существует вектор *, такой, что L(х*, *) максимальна. Эти утверждения справедливы и для задачи на минимум. В методе Лагранжа строится функция Лагранжа и затем находятся ее критические точки. Частные производные функции L(х, ) можно разделить на две группы. Частные производные по  являются функциями ограничений gi. Приравнивая эти производные нулю, получаем, что х  К. Для вычисления оптимума решающую роль играют производные по х. Если их приравнять нулю, получим п уравнений вида Представим это выражение в векторной форме: где и Приведенное выражение является системой уравнений относительно х и . Функции f и gi не содержат . Поэтому система может рассматриваться как линейная относительно  с матрицей G и вектором свободных членов . Рассматриваемая система содержит п уравнений и т переменных . Поэтому решение существует только тогда, когда не более т уравнений линейно независимы. Если ограничения задачи независимы, это условие выполняется. Таким образом, можно решать систему относительно множителей и получить единственный набор *, не все компоненты которого равны нулю. Пример. Пусть производственные функции каждого из двух продуктов зависят от двух (одних и тех же) факторов. Суммарное количество каждого фактора фиксировано. Пусть заданы цены продуктов. При каких условиях доход от выпуска будет максимальным? Обозначим через x1, x2 объемы выпуска первого и второго продуктов соответственно. Пусть x3, x4 – объемы факторов, использованные при производстве первого продукта с производственной функцией x1 = F1(х3, х4). Аналогично х2 = F2 (x5, x6). Предполагается, что x3 и x5 представляют один и тот же фактор, так же как и x4 и х6. Задача состоит в следующем: Функция Лагранжа в этом случае запишется в виде Приравнивая частные производные по х нулю, получим шесть уравнений: Отсюда легко получить знакомые условия на выпуск, максимизирующий доход: Следовательно, стоимость предельного продукта по каждому фактору будет одна и та же в обеих отраслях. Заметим, что все множители Лагранжа оказались равными ценам. Если в приведенном случае имеет место конкурентное ценообразование, то 1, 2 – цены продуктов, а 3, 4 – цены факторов. 6.5. Интерпретация множителя Лагранжа В примере, приведенном в предыдущем параграфе, множители Лагранжа оказались равными ценам. Такими же свойствами обладают двойственные переменные в теории линейного программирования. Ниже будет предложена формальная интерпретация множителей Лагранжа. Рассмотрим стандартную задачу условной оптимизации. Решим ее с помощью метода Лагранжа, который дает оптимальные векторы х*, *. Пусть i-e ограничение имеет вид gi (х) = bi. Первоначально полагалось, что bi = 0. Исследуем здесь влияние малого ослабления ограничения. Обозначим через V* оптимальное значение целевой функции [V* = f(х*)]. Малое ослабление i-гo ограничения приводит к малым изменениям оптимальных значений переменных. Однако предполагается, что условия оптимальности по-прежнему удовлетворяются, так что новое состояние, достигаемое в результате ослабления ограничений, также оптимально. Влияние ослабления на оптимальное значение целевой функции определяется формулой Из ограничении имеем Умножим k-e равенство на и просуммируем по k. Получим . Вычтем это выражение из (4.3.1.). Получим Выражение справа в скобках в силу условия оптимальности равно нулю, поэтому . Таким образом, соответствует маргинальной (предельной) скорости изменения целевой функции относительно малого ослабления i-го ограничения при условии, что все остальные ограничения неизменны. Эта интерпретация аналогична интерпретации двойственных переменных в теории линейного программирования. В типичных экономических приложениях ограничения могут задаваться лимитами на ресурсы, а целевая функция – некоторым индексом общественного благосостояния. Тогда оптимальные множители Лагранжа соответствовали бы маргинальным (предельным) общественным оценкам ресурсов. В примере, рассмотренном в предыдущем параграфе, множители соответствуют ценам на продукты и на факторы. Цены на факторы соответствуют предельным оценкам для фиксированного предложения факторов. Чему же соответствуют цены на продукты? Оказывается, они соответствуют маргинальным оценкам производственных функций, выступающих в качестве ограничений, или параметрам эффективности производственных функций. 7. Эффективность и оптимальность в динамических моделях экономики. Теорема о магистрали Рассмотрим модель экономической системы, содержащей три продукта – один потребительский продукт С и два вида капитала K1, К2. Предполагается, что производство зависит только от запасов капитала так, что комбинации потребительского продукта и приращений запасов капитала связаны производственной функцией Рост запасов капитала задается динамическими соотношениями Очевидно, что при произвольных заданных начальных запасах K1(0) и К2(0) экономическая система может иметь бесконечное число траекторий роста в том смысле, что две из трех переменных С(t), K1(t), К2(t) могут быть произвольными внутри некоторой области. Нас интересует критерий выбора среди этих траекторий. Если рассматривается только конечное число периодов времени, можно в принципе оптимизировать некоторую целевую функцию общего вида при выполнении ограничения, задаваемого производственной функцией, и при начальных запасах K1(0), К2(0). Исследование оптимальных динамических моделей требует упрощения целевой функции Ф. Можно выделить два важных случая. 1. Оптимизация конечных запасов (конечная оптимизация). Здесь С(n) предполагается заданным для всех n (в простейших моделях С(n) = 0 для всех n), и целевая функция Ф[K1(N), K2(N)] является функцией только конечных запасов капитала. Ограничения определяются траекторией С(n), условиями на производство и начальными запасами. 2. Непрерывная оптимизация. Здесь значения С(n) являются наиболее важными аргументами целевой функции. Она может иметь вид Ф[С(0), С(1), ..., С(N)], т.е. целевая функция зависит только от потребления во все интервалы времени. Оптимизация проводится при ограничении на конечные запасы и при обычных производственных и начальных ограничениях. При достаточно большом N влияние конечных запасов ослабевает и им можно пренебречь. В терминах теории благосостояния наше внимание должна была бы привлечь только непрерывная оптимизация, поскольку только потребление может породить индивидуальную полезность. Однако в этом случае возникают существенные трудности при постановке задачи. Дело в том, что, несмотря на некоторый прогресс в этой области, до сих пор нет хорошо разработанной теории для определения природы динамической функции полезности. Простейший вариант задачи непрерывной оптимизации – задача оптимальных сбережений – был исследован Рамсеем в 1927 г., а новые варианты рассматриваются различными авторами. Обычно предполагается, что целевая функция представлена в одной из двух приведенных ниже формулах: или Рассмотрим конечную оптимизацию, при которой целевая функция, зависящая только от величин, измеренных в одно и то же время, может быть определена в общем виде таким же образом, как и в статической модели. Последующие параграфы этой главы посвящены изучению конечно-оптимального роста. Ряд утверждений, характеризующих природу роста в многосекторных моделях, могут быть получены из этого анализа, хотя принцип оптимизации по конечным запасам, отвечающим некоторому определенному моменту времени, может не иметь устойчивой основы. Этот принцип может быть реализован разве только через планируемые расходы. Как в статических, так и в динамических моделях понятия эффективности и оптимальности тесно связаны. Если бы мы пожелали четко подчеркнуть различие между этими понятиями, то следовало бы обратить внимание на следующие нюансы. Оптимальная траектория предполагает, что критерий оптимальности указан. Эффективная траектория – это траектория, оптимальная по некоторому подходящему критерию. Таким образом, неэффективная траектория не может быть оптимальной, а оптимальная траектория всегда эффективна. Мы оставим термин "эффективная траектория" для траектории, которая является конечно-оптимальной для некоторого выбора целевой функции. Во всех случаях, которые мы будем рассматривать в последующих параграфах, целевая функция будет линейной и будет соответствовать некоторой оценке конечных запасов в заданных ценах. При рассмотрении оптимальных траекторий роста весьма полезно понятие, известное как принцип оптимальности. Это понятие в частной форме, приведенной ниже, было предложено Беллманом как основа динамического программирования. Принцип оптимальности. Оптимальная политика обладает тем свойством, что, каковы бы ни были первоначальное состояние и первоначальное решение, последующие решения должны основывать оптимальную политику относительно состояния, полученного в результате предыдущего решения. Принцип оптимальности в ряде работ использован для определения оптимальной политики. Первоначально он был предназначен для конечно-оптимальных задач. Однако, несмотря на его интуитивную привлекательность, допустимость его применения должна быть проверена в каждом классе задач. Осложнения могут возникнуть в применении принципа к непрерывно-оптимальным классам. Применительно к теории роста принцип оптимальности приводит к следующему выводу. Если траектория конечно-оптимальна, начинается из точки х(0) и проходит через х(n) на пути к конечной точке х(N), тогда часть траектории от х(n) до х(N) будет конечно-оптимальна относительно начальной точки х(n). Интуитивно ясно, что часть траектории от х(0) до х(n) должна быть конечно-оптимальна относительно х(n) по какому-нибудь подходящему критерию и поэтому должна быть эффективной. Таким образом, можно сформулировать обобщенный принцип оптимальности для эффективных траекторий. Принцип оптимальности для эффективного роста. Любая часть траектории эффективного роста сама является траекторией эффективного роста. При применении этого принципа к конечно-оптимальным траекториям подходящий конечный критерий для частей траектории должен выбираться в каждом случае по-своему. Пусть, например, максимизируется стоимость конечных запасов х(N) в некоторых ценах. Тогда цены, подходящие для х(n), рассматриваемой в качестве конечной точки, будут, вообще говоря, отличаться от цен, соответствующих точке х(N). Класс теорем, устанавливающих связь оптимальных траекторий роста с неймановской траекторией, особенно в смысле "близости" к неймановской траектории, называется теоремами о магистрали. Впервые это название, хотя и звучное, но, вообще говоря, не подходящее, было дано Дорфманом, Самуэльсоном и Солоу. Различные теоремы о магистрали достаточно разных видов были доказаны Раднером и Никайдо, Мак-Кензи и Моришимой. Представленная здесь теорема основана на теореме Раднера (которая является замечательным примером изобретательности), но модифицирована и расширена в соответствии с работами Никайдо. Мы будем заниматься тем же процессом роста, который изучался в двух предыдущих параграфах, но с некоторыми слабыми дополнительными условиями. Будем предполагать, что преобразование Т строго выпукло в окрестности неймановского луча и что допустимо свободное перераспределение (неэффективное производство в статическом случае). Ни одно из этих предположений не требовалось в предшествующем обсуждении. Теорема имеет дело с расстоянием (в некотором смысле) конечно-оптимальной траектории от неймановской траектории. Выберем меру, инвариантную относительно умножения на скаляр, т.е. такую, что расстояние между х и y будет таким же, что и расстояние между х и у. Здесь будет использоваться "нормализованное расстояние" где |v|— эвклидова норма v. Поскольку |х| = |х| и |y| = |y| (,  > 0), то Следовательно, d(х, у) обладает желаемым свойством. В дальнейшем расстояние между двумя векторами х, у всегда будет измеряться при помощи меры d(х, у). Обозначим неймановские пропорции через х* (т. е. неймановский луч есть полупрямая х*,   0), а неймановские цены и коэффициент роста – через р* и *. Предположение о строгой выпуклости Т принимается для того, чтобы сделать следующий вывод: для всех x, не равных x*. Отсюда, в свою очередь, следует лемма. Для любого  > 0 существует  > 0, такое, что для всех у, х, для которых Т(у, х) = 0 и d(х, х*)  , имеем Теперь мы в состоянии сформулировать важную теорему. Теорема о магистрали. Рассмотрим экономику с неоклассическим соотношением преобразования Т(у, х) = 0, таким, что Т(у, х) строго выпукло в окрестности неймановского луча. Утверждается, что: для любого  > 0 конечно-оптимальная траектория с конечным числом периодов N находится на расстоянии, большем или равном , от неймановской магистрали для не более, чем М, периодов, где М – конечное число, не зависящее от N, но зависящее, вообще говоря, от . При дополнительных специальных предположениях может быть также доказано следующее. Если конечными ценами являются неймановские цены, конечно-оптимальная траектория с увеличением номера периода приближается к неймановской траектории и при бесконечно возрастающем N асимптотически стремится к неймановской траектории. У конечно-оптимальной траектории, проходящей через две точки, находящиеся на одинаковом расстоянии от неймановской траектории, все промежуточные точки будут ближе к неймановской траектории, чем крайние точки. Используя эту теорему совместно с принципом оптимальности, легко охарактеризовать и проиллюстрировать область типичных конечно-оптимальных траекторий (рис. 12 и 14). Рис. 13. Теорема о магистрали Рис. 14. Теоремы о магистрали Доказательство теоремы о магистрали основано на сравнении двух траекторий – оптимальной и некоторой образцовой траектории (comраrision path). При заданных конечных ценах и начальной точке стоимость конечного выпуска должна быть самой высокой на оптимальной траектории. Это соображение используется для того, чтобы установить свойства траектории.