Аналитические методы моделирования систем
Рассматриваются основной понятийный аппарат методов классической математики и математической физики и возможности их применения для моделирования систем при решении многокритериальных задач. Кратко характеризуются детерминированные математические методы оптимизации, методы математического программирования (конечномерной оптимизации) и вариационного исчисления как методы принятия решений в условиях полной информации: приведены основные идеи и алгоритмы методов линейного, квадратичного и динамического программирования; методы принятия решений в условиях неопределенности: методы системных (решающих) матриц.
Основной понятийный аппарат аналитических методов
Основу понятийного (терминологического) аппарата аналитических методов составляют понятия классической математики (величина, формула, функция, уравнение, система уравнений, логарифм, дифференциал, интеграл, теорема и т.д.).
Аналитические представления имеют многовековую историю развития, и для них характерно не только стремление к строгости терминологии, но и к закреплению за некоторыми специальными величинами определенных букв (например, удвоенное отношение площади круга к площади вписанного в него квадрата я " 3,14; основание натурального логарифма е " 2,7 и т.д.). Выявленным закономерностям, представляемым в виде формул или уравнений, доказанным теоремам присваивают имена их авторов — уравнение Даламбера, формула Коши, теорема Бернулли и т.п.
На базе аналитических представлений возникли и развиваются математические теории различной сложности — от аппарата классического математического анализа (методов исследования функций, их вида, способов представления, поиска экстремумов функций и т.п.) до таких новых разделов современной математики, как математическое программирование (линейное, нелинейное, динамическое и т.п.), теория игр (матричные игры с чистыми стратегиями, дифференциальные игры и т.п.). В их числе — возникшие в древние времена и средние века арифметика, алгебра и геометрия, составляющие основу школьной математики, развивающиеся на их основе линейная алгебра, аналитическая геометрия, интегро-дифференциальное исчисление, теория предельных переходов, регрессионный и функциональный анализы и другие направления, формирующие дисциплины вузовской математики.
Математика постоянно развивается. Возникают новые направления, комбинированные или комплексированные направления, объединяющие средства, существовавшие ранее. По образному выражению Б. В. Гнеденко, математика — большой город, в котором "происходит непрерывный процесс роста и совершенствования... возникают новые области, строятся изящные и глубокие новые теории подобно строительству новых кварталов и зданий... Старые теории включаются в новые, более общие; возникает потребность укрепления фундаментов старых построек. Приходится прокладывать и новые улицы...".
Теоретические направления математики стали основой многих прикладных дисциплин, в том числе теоретической механики, теории автоматического управления, теории оптимальных решений и т.д.
Вначале в прикладных исследованиях разрабатывали модели, основанные на поиске экстремумов функций. Затем, по мере отражения в модели все большего числа реальных факторов моделируемого объекта или ситуации, стало применяться вариационное исчисление, основанное на отыскании экстремумов функционалов. В качестве самостоятельного класса в математике формировался класс приближенных вычислений, идея которых была еще в работах И. Ньютона. Этот класс в настоящее время называют численными методами. Основу численных методов составляет организация процесса получения решения в виде последовательности однотипных шагов, итераций, помогающих направлять и корректировать ход решения задачи.
Рассмотрим краткую историю возникновения этих методов и терминологии, используемой при их применении.
Вариационное исчисление — раздел математики, в котором изучаются вариации функционалов. Главная типичная задача вариационного исчисления состоит в отыскании экстремумов функционалов.
Методы вариационного исчисления широко применяются в различных областях математики, физики, техники.
Например, в дифференциальной геометрии с их помощью ищут геодезические линии и минимальные поверхности. В физике вариационный метод используют для получения уравнений движения (например, "принцип наименьшего действия) как для дискретных, так и для распределенных систем, в том числе и для физических полей.
Однако вариационные задачи, относящиеся к категории изопериметрических задач, возникли еще в античные времена и были известны древнегреческим ученым (Архимеду, Зенодору и др.), и становление вариационного исчисления имеет длительную историю.
Первый вариационный принцип сформулировал для траекторий отраженных световых лучей Герои Александрийский (I в. н.э.). В средневековой Европе изопериметрическими задачами занимались И. Сакробоско (XIII в.) и Т. Брадвардин (XIV в.).
После разработки анализа появились новые типы вариационных задач, в основном механического характера. Среди других задач стоит отметить определение формы цепной линии (т.е. формы равновесия тяжелой однородной нити, 1690 г.). Общих методов решения вариационных задач в этот период еще не существовало, каждая задача решалась с помощью остроумных (и не всегда безупречных) геометрических рассуждений.
Исторически первой задачей вариационного исчисления считают задачу, поставленную и решенную И. Ньютоном в работе "Математические начала натуральной философии" (1687), в которой требовалось найти кривую, проходящую через три заданные точки, такую, чтобы она при вращении вокруг заданной осп образовывала тело вращения, испытывающее наименьшее сопротивление среды при движении вдоль этой оси. Ньютон нашел решение своей задачи в виде геометрической пропорции, являющейся, как было показано в последующем, эквивалентом дифференциального уравнения.
Другой задачей такого рода является задача о брахистохроне И. Бернулли, поставленная в 1696 г.: определить кривую, соединяющую две заданные точки Л и В, не лежащие на одной вертикальной прямой, и обладающую тем свойством, что материальная точка под действием силы тяжести скатится по этой кривой из точки Л в точку В в кратчайшее время. В этой задаче функционал представляет собой время скатывания точки по кривой.
П. Ферма сформулировал основной принцип геометрической оптики, в силу которого свет в неоднородной среде выбирает путь, занимающий наименьшее время. В 1744 г. П. Мопертюн обобщил это правило, введя в науку первый принцип наименьшего действия, один из вариационных принципов механики, согласно которому для данного класса сравниваемых друг с другом движений механической системы действительным является то, для которого физическая величина, называемая действием, имеет экстремум.
В самостоятельную область математики вариационное исчисление сформировалось в XVIII в. благодаря работам Л. Эйлера и Ж. Лагранжа.
Первый общий метод решения вариационных задач был разработан Л. Эйлером в серии работ 1726—1744 гг. Эйлеру принадлежит первое систематическое изложение вариационного исчисления и сам термин (1766). Лагранж независимо получил (с 1755 г.) многие основополагающие результаты и ввел понятие вариации. Вето работах было показано, что между вариациями и приращениями функционала в вариационном исчислении, с одной стороны, и дифференциалом независимой переменной сх и дифференциалом функции у = /(л) в дифференциальном исчислении — с другой, существует аналогия.
Были выведены уравнения Эйлера — Лагранжа, представляющие собой необходимое условие экстремума, которое стало аналитическим фундаментом вариационных методов. Простейшая задача вариационного исчисления и условия Эйлера — Лагранжа рассматриваются в параграфе 2.2.
Затем, однако, выяснилось, что решения этих уравнений не во всех случаях дают реальный экстремум, и встала задача найти достаточные условия, гарантирующие экстремум. Исследования А. Лежандра, Ж. Лагранжа, К. Якоби, К. Вейерштрасса позволили получить достаточные условия, которые называются уравнениями Якоби.
Вклад в развитие вариационного исчисления внесли П. Дирихле, У. Гамильтон, Д. Гильберт, В. Ритц, Г. Вейль, А. Лебег, Р. Курант. Большое значение имели исследования отечественных ученых Л. А. Люстерника, И. Г. Петровского, М. Л.Лаврентьева, Н. И. Боголюбова. II. М. Крылова и др. Исследованиями этих ученых созданы теоретические основы вариационного исчисления и решены многие практические задачи. Среди последних следует отметить использование необходимых условий вариационного исчисления и вариационных принципов при выводе дифференциальных уравнений состояния физических систем и создание так называемых прямых методов вариационного исчисления, которые нашли очень широкое применение в вычислительной практике.
Важнейшими понятиями вариационного исчисления являются следующие:
- • вариация (первая вариация);
- • вариационная производная (первая вариационная производная);
- • вариации и вариационные производные второго и высших порядков.
Термин "варьирование" ("варьировать") применяется в вариационном исчислении для обозначения нахождения вариации или вариационной производной (это аналог термина "дифференцирование" для случая бесконечномерного аргумента, являющегося предметом вариационного исчисления). Нередко для краткости (особенно в приложениях) термин "варьирование" применяется для обозначения решения вариационной задачи, сводимой к нахождению вариационной производной и приравниванию ее нулю.
Для теории систем и системного анализа наибольший интерес представляет направление вариационного исчисления, получившее особое развитие во второй половине XX в. и вошедшее составной частью в современную теорию оптимальных процессов. Начальный толчок этому направлению был дан Л. С. Понтрягиным, рассмотревшим задачу с ограничениями, задаваемыми замкнутой областью допустимых изменений управляющих параметров. Такие задачи получили название неклассических задач вариационного исчисления, хотя ограничения замкнутого типа изучались еще К. Вейерштрассом.
Численные методы в исходном понимании — это методы приближенного решения математических задач, сводящиеся к выполнению конечного числа элементарных операций над числами. В качестве элементарных операций фигурируют арифметические действия, выполняемые обычно приближенно, а также вспомогательные операции — записи промежуточных результатов, выборки из таблиц и т.п. Числа задаются ограниченным набором цифр в некоторой позиционной системе счисления (десятичной, двоичной и т.п.). Таким образом, в этом классе методов числовая прямая заменяется дискретной системой чисел (сеткой); функция непрерывного аргумента заменяется таблицей ее значений в сетке; операции анализа, действующие над непрерывными функциями, заменяются алгебраическими операциями над значениями функций в сетке. В результате численные методы сводят решение математических задач к вычислениям. При этом вычисления могут быть выполнены как вручную, так и с помощью вычислительных машин.
Элементы численных методов появились еще в Древнем мире. В Вавилонии использовались математические таблицы и была известна приближенная формула вычисления квадратного корня. В Древней Греции применялись методы приближенного нахождения числа п путем построения сближающихся приближений сверху и снизу (Архимед, III в. до н.э.) и тригонометрической таблицы Птолемея (II в. н.э.). В Средние века в странах Средней Азии и Ближнего Востока получили развитие и широкое применение: позиционная система счисления, приближенные формулы, численное решение кубических уравнений методом последовательных приближений, высокоточные вычисления с применением развитой системы контроля, построение таблиц (например, таблиц синусов Улугбека) с высокой точностью.
В XVI—XVII вв. в Европе численные методы повлияли на развитие математики в целом. Открытие логарифмов привело к созданию методики вычислений, основанной на приведении формул к виду, удобному для логарифмирования, и применении логарифмических таблиц. Французский математик Ф. Внет предложил для приближенных решений алгебраических уравнений метод, сходный с методом Ньютона. Во второй половине XVIII в. для вычислений стали широко применяться бесконечные процессы, обрываемые на конечном этапе, итерационные процессы, непрерывные дроби, бесконечные произведения, ряды. В рамках математического анализа развиваются отдельные самостоятельные области: численное решение уравнений, приближенное вычисление значений функций, численное интегрирование, численное решение дифференциальных уравнений и др.
Разработка новых численных методов и применение ЭВМ привели к возникновению направления — вычислительная математика, которое в настоящее время нередко включают в состав класса численных методов, т.е. в узком понимании рассматривают как теорию численных методов и алгоритмов решения типовых математических задач.
Вычислительные методы применяют для решения систем линейных уравнений, интерполирования и приближенного вычисления функций, численного интегрирования, численного решения систем нелинейных уравнений, численного решения обыкновенных дифференциальных уравнений, численного решения уравнений в частных производных (уравнений математической физики), решения задач оптимизации и т.д.
Таким образом, исходное понимание класса численных методов постепенно расширялось, и в настоящее время в этом классе выделяют конечные и бесконечные численные методы.
Конечные методы позволяют получать решение за конечное (но обычно заранее неизвестное) число шагов. К ним относят: симплекс-метод (с полной симплексной таблицей, с использованием обратной матрицы, с мультипликативным представлением обратной матрицы); двойственный симплекс-метод; метод последовательного сокращения невязок (комбинация обычного и двойственного симплекс-метода); метод наискорейшего спуска; метод сопряженных градиентов для минимизации квадратичной функции; методы условной минимизации, основанные на теореме Куна — Таккера. Эти методы более подробно охарактеризованы в гл. 2. Область применения конечных методов ограничена линейным и квадратичным программированием.
Бесконечные методы основаны на построении последовательности все более точных приближений к решению. При этом, прекращая процесс на том или ином шаге итераций, можно получить решение с заданной точностью. К этой группе методов относят: метод Брауна — Робинсона, основанный на связи между парой задач линейного программирования (исходной и двойственной) и матричной игрой, т.е. на применении при решении задач математического программирования методов теории игр; метод штрафных функций, или метод штрафов, базирующийся на использовании функций штрафов.
Поскольку конечные и бесконечные численные методы обладают общими достоинствами и недостатками, вводят классификацию методов по видам итераций.
При этом выделяют четыре вида итераций.
1. Методы возможных направлений.
Строится последовательность х*, к = О, 1,так что каждое х* удовлетворяет всем ограничениям задачи. Вблизи очередного приближения х* минимизируемая функция и ограничения (существенные для х*) аппроксимируются более простыми (как правило, линейными или квадратичными). Решая получающуюся вспомогательную задачу линейного или квадратичного программирования, находят возможное (т.е. не выходящее за пределы области допустимых решений) направление, являющееся одновременно и направлением убывания функции. Сдвиг по этому направлению приводит к новой точке х*+1. Примерами могут служить симплексный метод в линейном программировании и метод проекции градиента и условного градиента, метод возможных направлений Зойтендейка в нелинейном программировании.
2. Методы, в которых последовательные приближения хк не удовлетворяют ограничениям, и в процессе итераций невязка в выполнении ограничений сводится к нулю.
При этом обычно используются те же приемы и аппроксимации и решения вспомогательных задач, что и в 1-й группе. К этой группе относят двойственный симплекс-метод в линейном программировании, метод отсечения в выпуклом программировании, при этом точка хк отсекается путем добавления нового линейного ограничения.
3. Итерационный процесс ведется не только по исходный, но и по двойственным переменным (множителям Лагранжа, оптимальным оценкам).
Одна итерация метода заключается в решении задачи о выборе оптимального варианта при заданных ценах на ресурсы (без учета их ограниченности) и в последующем пересчете цен в зависимости от степени нарушения ограничений на ресурсы. К этой группе относится градиентный метод Эрроу — Гурвица — Удзавы.
4. Методы, основанные на учете ограничении с помощью штрафов.
Штрафы включаются в минимизируемую функцию. При этом получается последовательность задач на безусловный минимум, каждая из которых может решаться с помощью различных методов: градиентного метода, метода сопряженных градиентов, метода Ньютона и т.д.
К численным методам относят также методы решения задач специального вида: транспортные (транспортная задача), блочные (блочное программирование).
В современных условиях при применении ЭВМ число методов расширяется. В частности, разрабатываются методы, основанные на использовании кусочно-линейной аппроксимации, комбинаторных алгоритмов, разработке непрерывных вариантов дискретных методов, строится непрерывная траектория х(г). задаваемая дифференциальными уравнениями.
В последующем в качестве наиболее значимого и получившего широкое распространение выделили направление, обычно кратко называемое математическим программированием.
Математическое программирование и теория оптимизации — математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).
Первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств были задачи линейного программирования. Подобные задачи были впервые поставлены в 1820 г. Ж.-Б. Фурье.
Важным вкладом в развитие вычислительной математики было применение функционального анализа. Впервые в вычислительной математике его применил Л. В. Канторович, который развил общую теорию приближенных методов, построил эффективные методы решения операторных уравнений (в том числе метод наискорейшего спуска и метод Ньютона для таких уравнений).
Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 1930-м гг. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Д. фон Нейман — математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Л. В. Канторович, который в 1939 г. предложил оригинальный способ решения задачи раскроя фанеры — метод разрешающих множителей. Эта идея не сразу была воспринята. Однако независимо ее предложили и развивали Т. Кунманс и Дж. Данциг, который в 1947 г. предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.
Зарубежные исследователи признали приоритет Л. В. Канторовича, и метод математического программирования получил широкое применение в экономике.
Термин "линейное программирование" был предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.
Присутствие в названии термина слова "программирование" объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово означает "планирование, составление планов или программ". Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и ее экономической интерпретацией (изучение оптимальной экономической программы). Поэтому наименование "математическое программирование" связано с тем, что целью решения задач является выбор оптимальной программы действий.
В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название "проблема выбора"; метод решения получил название "венгерский метод". В 1949 г. Л. В. Канторовичем совместно с М. К. Гавуриным разработан метод потенциалов, который применяется при решении транспортных задач.
В последующих работах Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, Л. Л. Лурье, Л. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна, С. А. Соколицына, Б. И. Кузина, В. Н. Юрьева и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение ее методов к исследованию различных экономических проблем, и в настоящее время экономику невозможно представить без экономико-математических методов, основанных на математическом программировании. Методам линейного программирования посвящено много работ зарубежных ученых. В 1£М г. Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 г. Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Г. Купа, А. Таккера, С. Гасса, А. Чарнеса, Е. М. Била и др.
Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо то и другое нелинейны. В 1951 г. была опубликована работа Г. Куна и А. Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения задач нелинейного программирования. Эта работа послужила основой для последующих исследований в этой области.
Начиная с 1955 г. опубликовано много работ, посвященных квадратическому программированию (работы Р. Дорфмана, М. Франка, П. Вольфа и др.). В работах Дж. Денниса, Дж. Розена и Г. Зонтендейка разработаны градиентные методы решения задач нелинейного программирования.
В настоящее время для эффективного применения методов математического программирования и решения задач па компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPI, и LINGO. Существуют также пакеты прикладных программ для реализации симплекс-метода.
Методы математического программирования рядом исследователей считаются самостоятельным классом математических методов. Однако нередко их включают в число численных методов.
Область применения конечных численных методов -линейное и квадратичное математическое программирование.
Теория математического программирования является основой теории оптимизации.
Экстремальные задачи, способствующие формированию теории оптимизации, независимо от Канторовича исследовались в математике параллельно в рамках классической математики (работы Р. Л. Стратоновича и Л. С. Понтрягина), применительно к теории управления — В. Г. Болтянским. В результате сформировалась теория оптимальных процессов.
Л. С. Понтрягиным и его учениками был создан метод решения оптимальных задач, получивший название "принцип максимума Л. С. Понтрягина". Этот метод является обобщением необходимого условия Вейерштрасса — сильного минимума функционала задачи оптимизации, и для большинства практических оптимальных задач получается как непосредственное следствие этого условия.
Р. Л. Стратонович записал обобщенное уравнение Беллмана для условного риска, позволяющее найти алгоритмы оптимального управления в условиях неполной информации.
Теория оптимизации развивается и как самостоятельная дисциплина. Существуют различные классификации методов оптимизации.
С появлением новых разделов математики вводятся и новые понятия и термины, которые кратко характеризуются при изложении истории возникновения методов, а затем — при рассмотрении сути и примеров применения методов в последующих параграфах данной главы.
Поскольку для целей системного анализа в большей мере используются методы вариационного исчисления и математического программирования, они и рассматриваются в последующих параграфах.
