Экстремальные задачи

Оптимизация

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

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

Первые экстремальные задачи были сформулированы античной наукой. Они касались максимизации площадей и объемов. Так, в легенде о финикийской царевне Дидоне, основавшей около 825 года до н.э. город Карфаген, говорится, что царевна, найдя подходящее место на берегу Средиземного моря (ныне Тунисский залив), откупила у местного князя столько земли, сколько можно было покрыть бычьей шкурой. Разрезав шкуру на тонкие полоски и связав их в один длинный ремень, Дидона окружила им максимальную площадь земли и заложила на ней крепость Бирса (шкура).

Таким образом, в этой легенде речь идет о задаче максимизации площади 5¹, охватываемой кривой заданной длины Ь (длина ремня, сшитого из полосок бычей шкуры ).

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

В XVI веке появляются первые экстремальные задачи алгебраического содержания. В частности, широко известной стала задача итальянского математика Н. Тартальи: разделить число восемь на два числа так, чтобы произведение этих чисел на их разность было максимальным. Решение задачи сводится к поиску максимального значения кубического трехчлена у = х(8 - х)(2х - 8) на открытом интервале 0 < х < 8. В связи с тем что в те далекие времена дифференциальное исчисление не было известно, задача, по-видимому, решалась приближенно путем последовательного деления отрезка (0,8) пополам.

Только после открытий известных математиков П. Ферма, И. Ньютона, Г. Лейбница постепенно начал формироваться общий подход к решению экстремальных задач, использующий дифференцирование оптимизируемых функций.

Формулировка в конце XVII века И. Бернулли задачи о брахистохроне положила начало изучению нового класса экстремальных задач — вариационному исчислению. В этом разделе континуальной математики рассматривается поиск экстремумов функционалов, заданных на множестве непрерывных функций. Необходимо отметить, что основной вклад в решение таких задач, функционалы которых заданы на ограниченных множествах (задач на условный экстремум), внес французский математик Ж. Лагранж, предложивший знаменитое правило множителей сначала для задач вариационного исчисления (1788 г.), а затем для аналитических функций (1797 г.). Это правило широко используется и в настоящее время, как в практическом аспекте, так и в теори-тических исследованиях. В частности, на него опиралась группа советских математиков, возглавляемая Л. Понтрягиным, при разработке математической теории оптимального управления [29].

До начала 40-х годов XX века экстремальные задачи формулировались преимущественно в области математики, физики, техники. Однако в конце 30-х годов появляются задачи из совершенно новой области — экономики, науки о рациональном ведении хозяйства в собственном деле, фирме, отрасли, государстве. Одна из первых постановок экстремальных задач экономического содержания принадлежит советскому математику Л. Канторовичу, впоследствии лауреату Нобелевской премии в области экономики. Она изложена в его книге «Математические методы организации и планирования производства» (Л.: Изд-во ЛГУ, 1939).

Формулируемые задачи представляли собой совершенно иной класс экстремальных задач на условный экстремум, не поддающиеся решению методом Лагранжа и, таким образом, требующие разработки совершенно новых подходов к поиску наибольших значений оптимизируемых функций (функционалов). В течение 50—70-х годов XX века экономистами-приклад-никами, математиками, инженерами были сформулированы и решены тысячи экстремальных задач из области управления предприятиями, отраслью, дорожно-транспортными, электроэнергетическими, водными, нефтяными, газовыми и вычислительными сетями.

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

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

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

• 1) содержательную постановку задачи;
• 2) математическую ее формулировку;
• 3) определение методов решения математической задачи;
• 4) разработку алгоритма ее решения, доказательство его правильности и оценку временной сложности;
• 5) в случае необходимости, корректировку математической модели после экспериментальных исследований алгоритма на реальных исходных данных задачи;
• 6) внедрение найденного усовершенствования управления организационной системой в жизнь.

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

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

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

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

В свою очередь класс задач математического программирования включает обширные подклассы задач линейного, квадратичного, нелинейного, дискретного программирования. Задачи дискретного программирования — это задачи дискретной математики. Они представляют собой класс задач, которые от остальных задач математического программирования отличаются прежде всего тем, что оптимизируемые функции в этих задачах определены на дискретных конечных множествах. В задачах целочисленного линейного программирования такими множествами могут быть наборы значений целых чисел в /7-мерном эвклидовом пространстве. В частном случае это могут быть наборы, состоящие из п нулей и п единиц. В других задачах дискретные множества могут оставлять элементы комбинаторики: перестановки, сочетания, размещения, группы перестановок и т. п. Наконец, в широком классе задач на графах элементами дискретных множеств могут быть наборы вершин или дуг графа. Важно отметить то, что многие задачи дискретной оптимизации допускают разное представление как в эвклидовом пространстве, так и на языке комбинаторики и графов. Во многих случаях такое представление позволяет наиболее быстро найти самый рациональный алгоритм решения той или иной рассматриваемой задачи.

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

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

Это метод ветвей и границ [17, 26, 30] и динамическое программирование [31—33].

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

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

Идея метода состоит в том, что исходное множество решений М, на котором определена оптимизируемая функция, по некоторому принципу разбивается на конечное множество непересе-

кающихся подмножеств (классов) М_{ так, что и М₁ = М,

/

М/ П =0 для / ф у. Далее по заранее принятому правилу выбирается одно из подмножеств М₁ и в свою очередь разбивается на

конечное число классов М_к, и М_к = М₁,, М_к П М - 0, к ф р.

к

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

В целях наглядности процесс разбиения исходного множества М на подмножества изображают в виде корневого дерева (ориентированного графа). Начальной вершине этого графа У_т ставится в соответствие множество М. Множествам Л/,- ставятся в соответствие вершины У_т/, к которым направляются пути из вершины У_т, символизируя то, что эти вершины У_т1 порождены вершиной У_т. Подмножеством М_к ставятся в соответствие вершины У_тк, к которым направляются дуги из вершин У_пи и т. д. Таким образом, поскольку полученное 1 — ярусное дерево — строится образованием на каждом ярусе ветвей, сам процесс разбиения исходного множества М на подмножества получил название ветвления. В качестве примера процедуры ветвления на рис. 6.1 изображено бинарное дерево, полученное для задачи о коммивояжере и четырех городах. Вершина М этого дерева отображает все шесть замкнутых маршрутов, которые может совершить путешест-

вующий продавец, если он начинает свой путь из города 3. Множество всех маршрутов М разбивается на два подмножества Л/₍₃₄₎ и Первое из них содержит маршруты, включающие

переезд из города 3 в город 4, а второе не включает такие маршруты. В свою очередь подмножество М_(ЪА) разбивается на два подмножества А/₍| ₂) и Л/_(Т2). Первое подмножество содержит маршруты, включающие переезд из города 3 в город 4 и из города 1 в город 2, а второе подмножество М— содержит маршруты, включающие переезд из города 3 в город 4 и не включающие переезд из города 1 в город 2.

Рис. 6.1. Бинарное дерево ветвления для задачи о коммивояжере и четырех

городах

Аналогичным образом формируются остальные множества Л/(₄1), А/—, М_{2 3), А/₍узу. В результате получаем маршрут переезда продавца из города в город: 3—4—1—2—3. При известных стоимостях переездов стоимость этого маршрута равна сумме стоимости переездов. Это и есть рекорд. Одновременно с ветвлением, метод предусматривает для каждого из множеств, начиная с корневого, вычисление нижних или верхних границ в зависимости от того, отыскивается ли наименьшее или наибольшее значение оптимизируемой функции. При этом определение нижних (верхних) границ функции подчиняется обязательному правилу: нижняя граница для очередного подмножества должна быть не меньше чем такая же граница для порождающего его подмножества, верхняя граница — не больше. Иными словами, нижние границы от предка к потомку не должны убывать, верхние — не возрастать. В конечной вершине (листе) дерева границы должны представлять собой значения, соответствующие маршруту ветвления.

Вычисление нижних (верхних) границ функции, удовлетворяющих указанным требованиям, является основанием сокращения перебора элементов множества, на котором задана оптимизируемая функция. Сокращение осуществляется следующим образом. После вычисления рекорда f_r{x) метод начинает его сравнение с нижними (верхними) границами функции на подмножествах. Если для очередного подмножества снизу М_к нижняя граница f(M_k)> f_r (х), то в силу того, что для всех подмножеств, М_к+1, порождаемых М_к, нижние границы f(M_k+l) > f(M_k), а в листе нижняя граница становится рекордом, подмножество М_к не будет порождать решений /(х), меньших текущего рекорда f_r (х). Следовательно, все ветви, исходящие из вершины дерева V_mk , могут быть отброшены. Если же после обнаружения подмножества М_к, такого, что f(M_k)r(x), то в вершине дерева У_тк осуществляется ветвление, вычисление нижних границ для всех порождаемых подмножеств и сравнение их с текущим рекордом. Если полученные нижние границы функции на подмножествах меньше рекорда, осуществляется подъем вверх по дереву от вершины V_mk к вершинам меньшего яруса. Если же для некоторой вершины, порожденной V_mk, окажется, что нижняя граница меньше рекорда, осуществляется ветвление в этой вершине. Таким образом, выполняя челночные «движения» вниз-вверх по дереву, отбрасывая и порождая его ветви, метод «просматривает» все вершины дерева и находит минимальное значение функции min /(х). Поиск наибольшего ее значения шах /(х) отличается лишь тем, что отбрасываются ветви дерева, исходящие из вершины V_mk, для которой f(M_k)< f_r(x), а в тех вершинах дерева V_mk, для которых f(M_k ) < f_r (х), осуществляется ветвление.

Описанный процесс отбрасывания ветвей в дереве поиска получил название отсечения ветвей. Степень их отсечения, а, следовательно, и сокращения поиска существенно зависит от соотношений между нижними (верхними) границами (оценками функции) на подмножествах М_к и ее значениями, порождаемыми окончательным разбиением подмножеств, т. е. значением ее рекорда. Чем ближе оценка к точному значению функции, порождаемому разбиением соответствующего подмножества, тем интенсивнее отсечение, тем эффективнее метод ветвей и границ. Во многих задачах степень отсечения может быть повышена, если при минимизации функции использовать верхние границы ее значений на подмножествах разбиения, а при ее максимизации — нижние границы. Такие границы с небольшими затратами могут быть вычислены до применения метода ветвей и границ, а затем сразу же использоваться на первом его этапе. Если для некоторого сформированного подмножества М_к нижняя граница /(М_к) больше или равна верхней границе /Дх), то множество ветвей, исходящих из вершины дерева У_тк , может быть отброшено. При максимизации функции /(х) поступают наоборот: отбрасывают ветви в вершине дерева, для которой /(М_к)< /„ (х). Вычисление нижних (верхних) границ на подмножествах разбиения получило название решения оценочных задач.

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

Рис. 6.2. Дерево ветвления для задач о коммивояжере, если начальный город

первый

подмножества Л/,₂, Л/₁₃, Л/₁₄, включающие переезды из города 1 в город 2, из города 3 в город 4. Далее множество М_п разбивается на два подмножества Л/₁₂₃, Л/₁₂₄, содержащие маршруты с переездами из города 1 в город 2 и из города 2 в город 3 и 4. Аналогичным образом разбивается подмножество Л/₁₃ на два подмножества Л/]32, Л/,34 ^и подмножество Л/,4 — на подмножества Л/₁₄₂, Л/,₄₃.

Формирование подмножеств по этой схеме основано на построении полного числа перестановок для четырех городов, если продавец выезжает из города 1. Однако эта схема уступает бинарному принципу ветвления (рис 6.1), так как на первом ярусе порождает три подмножества Л/₁₂, Л/₁₃, Л/,₄ (для п городов это будет п-1 подмножеств), которые требуют решения оценочных задач и сравнения полученных оценок с рекордом или верхней (нижней) границей. При бинарном способе ветвления в такой обработке нуждаются всегда две вершины.

Правило выбора очередной вершины для ветвления среди претендующих вершин называют стратегией ветвления. Стратегии, как и схемы ветвления, также различны и для разных задач, и для одной и той же задачи. Чаще всего ветвят ту вершину дерева, которой соответствует наименьшая (наибольшая) оценка функции среди остальных оценок вершин. Если используется верхняя (нижняя) граница, ветвлению подвергают ту вершину, для которой она минимальна (максимальна). Иногда ветвят геометрически, выбирая, например, всегда крайнюю левую вершину дерева, чтобы быстрее получить рекорд /_г (х).

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

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

Как ни гибок и универсален метод ветвей и границ, не все задачи дискретной оптимизации могут быть решены этим методом в приемлемые сроки. К таким задачам, в частности, относится большинство задач составления расписаний.

Метод динамического программирования разрабатывался Р. Веллманом и его сотрудниками вначале для решения задач динамической оптимизации. Затем он был распространен для решения других классов задач, в том числе и задач оптимизации комбинаторного типа.

Суть метода состоит в том, что процесс оптимизации рассматривается как А^-шаговый процесс принятия решений (выбора управлений из допустимой области в моменты ..., /д,),

приводящий систему (оптимизируемый объект), состояние X которой описывается п координатами х_х, х₂, ..., х_п, в оптимальное состояние Х(/_Л, _{+ )}). Предполагается, что переход системы из состояния в состояние описывается рекуррентным соотношением ^(**₊₁) = Щ_к)к = 1, 2, ..., N. где ?/(/*)- решение, при

нимаемое в момент времени . Таким образом, при заданном начальном состоянии системы Т(/‘_|), используя это рекуррентное соотношение, требуется построить последовательность решений ?/(/,), ?/(/₂), ..., ?/(/д,), порождающих последовательность состояний системы Х(1₂), 2Г(/₃), ..., Х(1 д,) такую, что функционал /^г(Х(/_Уу₊₁)) достигает максимального (минимального) значения.

С традиционной точки зрения сформулированная задача представляет собой задачу математического программирования о поиске экстремума функционала /^г(Х(/_Л, _{+ |})) тх N действительных переменных с количеством т координат каждого из векторов ?/(/,), ^/(/₂), ..., и(1„) и ограничениями на значения этих координат и координаты состояний. С позиции метода динамического программирования — это последовательное решение N задач, каждая из которых с количеством переменных т. Таким образом, смысл метода Р. Веллмана — разложить сложную задачу на более простые задачи, решить их последовательно и в результате с меньшими затратами получить решение исходной задачи.

Вместе с тем, решения на каждой стадии в методе динамического программирования принимаются не обособлено, а с позиции всего процесса в целом, причем так, чтобы достигалось наилучшее значение оптимизируемого функционала (функции). Это требование достигается только тогда, когда соблюдается так называемый принцип оптимальности: оптимальная последовательность решений обладает тем свойством, что каковы бы ни были первоначальное состояние Х{1_х) и решение ?/(/,), последующие решения должны быть оптимальными относительно состояния, полученного в результате первого решения. Иными словами, для последовательности состояний ЛД/,), Х^₂), X(?₃), ..., Х{1_И+х) вся последовательность решений ?/(/,), ?/(/₂), ..., ) должна быть

оптимальной по отношению к состоянию А^г(/‘₁), последовательность ?/₂(/₂), ?/₃(/₃),) — по отношению к состоянию Х{1₂), решение ?/(/д,) должно быть оптимальным по отношению к состоянию ).

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

Обычно процесс вычислений начинают с ЛУ-й стадии, т. е. с конца. Для момента t_N рассматривают все допустимые состояния системы и для каждой из них находят значение функции Веллмана. Это может быть записано так: шах )) =

= гпах [/?(х(/д,), ?/(/д,))], где со — область допустимых управлений,

С/ЕМ

если отыскивается максимальное значение функционала. Таким образом, согласно принципу оптимальности на последней стадии N для каждого состояния системы Х(1_Ы ) действуют оптимально.

Далее переходят к предпоследней N -1 стадии. Для каждого состояния А^г(/_Л,_₁) этой стадии вычисляют функцию Веллмана по функциональному уравнению, т. е. с учетом ее значений, найденных на N - 1 стадии.

В большинстве задач, решаемых этим методом, указанное уравнение представляется как оптимальное значение суммы выигрыша, получаемой на ТУ -1 стадии и значения функции Веллмана, найденное на N стадии. Описанные действия заканчиваются вычислением функции Веллмана для первой стадии с выделением ее оптимального значения, которое представляет собой искомый результат. Последовательность оптимальных значений управлений ?/*(/,), и* (/₂), ..., ?/*(/д,) находят в обратном порядке по соотношениям Х(!_к) - Я(Х(1_к__]), ?/(/*_,)), к = 1, 2, ..., начиная с оптимального состояния X* (/„) первой стадии.

Динамическое программирование в редких случаях позволяет получить решение задачи аналитическим путем. Как правило, для достижения искомого результата применяют численные процедуры. Текущие результаты обычно заносят в таблицу, номера строк которой обозначают номера пройденных стадий процесса принятия решений, а номера столбцов — состояния системы. В качестве демонстрации метода рассмотрим решение задачи поиска кратчайшего пути во взвешенном графе (7 из вершины /₅ в вершину /V, изображенного на рис. 6.3. Числа, проставленые над дугами графа, означают их длины.

Рис. 6.3. Граф С для поиска кратчайшего пути методом динамического программирования

Определим /V-стадийный процесс принятия решений как такой, на каждой стадии которого отыскиваются пути минимальной длины из текущего множества вершин в вершину i_F. Различными состояниями системы на каждой стадии будем считать те вершины, которые имеют либо непосредственную связь по дуге с вершиной i_F, либо имеют ее через вершины, для которых оптимальные пути в i_F вычислены на предшествующих стадиях. Длину пути перемещения из вершины /' в вершину у обозначим tjj . Путь наименьшей длины перемещения из вершины у в вершину i_F по допустимым путям (значение функции Веллмана) обозначим В.. Тогда функциональные уравнения будут иметь такой вид: = О,

B_i = min (t_u + Вj).

На первой с конца стадии принятия решений различные состояния системы образуют вершины у, к, I, т, непосредственно предшествующие вершине /_F. Функции Веллмана для них вычисляются по выражению В. = min(/_;. + B_jF). В результате получаем: В_} - 5, В_к = 1, 5, = 4, В_т = 2. Вершина, следующая за этими вершинами, это вершина i_F. Полученные данные заносим в табл. 1.

Таблица 1

На второй стадии процесса принятия решений состояния системы образуют вершины g, И, /. Пользуясь данными табл. 1, вычисляем для этих вершин функции Веллмана и для каждой вершины g, /г, /' следующую за ней в оптимальном пути вершину. Полученные данные заносим в табл. 2.

Таблица 2

В_;, = тт[Д, + ЯД(Д. + В_к)] = шт[(4 + 3),(2 + 1)] = 3. Вершина к.

Я_/г - тт[Д_;А. + ЯД Д_г/ + В,)] = тт[(3 + 1),(2 + 4)] = 4. Вершина к.

В) = тт[(7_|7 + В,),(/_/ж + В_т)]~ тт[(4 + 4), (3 + 2)] = 5. Вершина т.

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

В₍, = тт[(Д + ЯД(/_Л + ЯД = тт[(7 + 3),(2 + 4)] = 6. Вершина к. В_е - тт(/_вА + В_И) - т1п(1 + 4) = 5. Вершина И.

В_г = тт[(Д + ЯД + В,)] = тт[(2 + 4),(2 +5)] = 6. Вершина к. Полученные результаты на этой стадии представлены в табл. 3.

Таблица 3

На четвертой стадии процесса состояния системы образуют вершины а, Ь, с. Функции Веллмана для них вычисляются так:

В_а = шт[(^ + ЯД + В_е)] = тт[(2 + 6),(5 + 5)] = 8. Вершина ё.

В,, = тт[(*_м + ЯД + В_е)] = тт[(1 +6),(3 + 5)] = 7. Вершина ё.

В_с = тт[(/_се + ЯД (/_с/ + В_г)] = тт[(4 + 5),(1 +6)] = 7. Вершина/

Результаты вычислений занесены в табл. 4.

Таблица 4

На пятой стадии процесса принятия решений состояние системы определяет одна вершина i_s. Функция Веллмана для этой вершины по выражению B_iS = min [(t_isa + В_а), (t_isb + B_h), (t_isC + B_c )] = = min [(5 + 8), (6 + 7), (4 + 7)] = 11. Следующей за ней в оптимальном пути является вершина с, так как (t_isc + В_с) минимально.

Таким образом, кратчайший путь в рассматриваемом графе равен 11 единицам. Он образуется вершинами i_s, c,f И, k, i_F и находится по таблицам 4—1 в обратном порядке по следованию вершин: за i_s следует с, за с следует /, за / следует к и т. д.

Несмотря на очевидные преимущества метода динамического программирования по сравнению с прямым перебором, в практическом отношении он имеет серьезные ограничения. При большом количестве состояний системы наблюдается интенсивный рост хранимых данных и объема вычислений, что вынудило Р. Веллмана в свое время назвать это явление «проклятием размерности». Кроме того, формулировка экстремальных задач в виде многошаговых процессов принятия решений с функциональными уравнениями рекуррентного характера не всегда очевидна, и на практике часто встречает трудности. Тем не менее, какими бы недостатками не обладали схемы ветвей и границ и динамического программирования, лучшие методы дискретной оптимизации относительного общего характера пока не созданы. Поэтому поиск решения вновь сформулированных задач обычно ведется по такой схеме: 1) попытка применить рассмотренные методы оптимизации и, если это удается, определить границы их возможного применения на практике; 2) максимально использовать специфику задачи и сконструировать специальный алгоритм ее решения; 3) построить приближенный алгоритм решения задачи с низкой погрешностью, если первые два этапа не дали результатов.