И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 4
Текст из файла (страница 4)
Читателя не должна смущать недостаточная полнота комментариев в тексте алгоритмов. Она компенсируется достаточными библиографическими указаниями в конце каждого параграфа. Список литературы включает лишь те работы, которые непосредственно использовались авторами при разработке алгоритмов. 31 Книга состоит из шести глав. В первой главе описаны 20 алгоритмов одномерной оптимизации, во второй — более 40 алгоритмов безусловной минимизации дифференцируемых функций, в третьей — более 40 алгоритмов минимизации недифференцируемых функций и отыскания седловых точек. В четвертой главе описано около 30 алгоритмов решения задач линейного программирования, пятая — содержит более 100 алгоритмов решения задач нелинейного и стохастического программирования, а шестая — около 20 алгоритмов решения минимаксных задач.
Так как почти все алгоритмы сопровождаются теоретическим обоснованиемв виде соответствующих теорем, то предлагаемое пособие будет полезным и для специалистов по теории оптимизации. В силу объективных причин далеко не все результаты по численным методам оптимизации нашли отражение в данном пособии.
Однако обширный охват материала и выбранный способ изложения позволяют надеяться, что предлагаемая книга послужит хорошим путеводителем по современным публикациям в данной области, облегчит студентам изучение и усвоение результатов цитированных публикаций, поможет преподавателям ускорить процесс обучения студентов навыкам решения практических задач на ЭВМ. Авторы выражают глубокую благодарность академику АН УССР В, С, Михалевичу, профессору Н.
3. Шору, заведующему кафедрой теории управления Львовского госуниверситета М. Я. Бартишу и сотрудникам кафедры моделирования сложных систем Киевского госуниверситета за ценные предложения по улучшению пособия. ВВЕДЕНИЕ алименты теории оптимизации и вправления 0.1. Математические методы управления н задачи оптнмнзацнн 1. О матомотпчоскпх методах пококп оптпмахьпьгх рошоппа Идеи оптимизации и оптимального управления за последние 30 — 40 лет глубоко проникли во многие области научных исследований, в инженерно-конструкторские разработки, в различные сферы управления социально-экономическими процессами. Этому способствовали два благоприятствующих фактора.
Во-первых, подавляющее большинство самых разнообразных задач управления и оптимизации приводятся к «стандартной» математической задаче оптимизации: найти среди влелгентов х из заданного мноасества Х глот элемент х* е Х, который доставляет наименьшее значение го (х*) заданной функции го.
Во-вторых, усилия математиков увенчались за эти годы разработкой многих эффективных алгоритмов решения математических задач оптимизации на ЭВМ для широких классов множеств Х и функций )«. Поэтому исследователю в любой конкретной области науки и техники часто достаточно перевести свою конкретную задачу управления (оптимизации) на математический язык, т. е. сформулировать ее ввиде математической задачи оптимизации, для которой уже известен алгоритм решения, и затем, воспользовавшись этим готовым алгоритмом, вычислить на ЭВМ искомое оптимальное решение х', т. е. тот элемент из множества Х, который удовлетворяет неравенствам ~о(х*)(~о(х), тГхЕХ.
(о. 0 Например, весьма близкими и часто легко приводимыми к математической задаче оптимизации оказываются те повседневные задачи, которые формулируются в виде: какое из возможных действий (далее перечисляются все эти возможные конкретные действия) следует предпринять и осуществить, чтобы обеспечить достижение заданной цели (далее дается конкретная формулировка преследуемой цели)? Чтобы подобную практическую задачу привести к виду математической задачи оптимизации, необходимо, во-первых, преследуемую цель выбрать конкретно. Для этого потребуется выбрать некоторый важный количественный показатель у„минимизация (или максимизация) которого наиболее соответствовала бы целям разумного управления. К сожалению, единой методики по выявлению и выбору «наиболее важного» у, не существует.
Более того, аксиомой важной математической теории коллективных решений и конфликтов (69, 259, 260) является предположение, что существует !3 столько же методов конкретизации целей, сколько ответственных управляющих с их личным опытом, умением и навыками. Во-вторых, необходимо позаботиться и о том, чтобы вы ранный показатель у, являлся прогнозируемым. Для этого тре ется построить определенную математическую модель управл мого процесса, т. е.
сперва перечисленные возможные действ описать с помощью элементов х некоторого множества Х, а тем определить на Х такую вычислимую (возможно, алгоритмически) функцию 7„значения которой гз (х) могли бы служить надежным прогнозом для ожидаемых значений у, при выборе тех нли иных возможных действий х. Если 7, дает для у, надежный прогноз, то построенную математическую модельуз = 7, (х) называют у,-адекватной. И, наконец, построенная математическая модель должна бытьдостаточно простой, чтобы имелись реальные возможности для вычисления искомого решения х* задачи (0.1) в требуемые сроки и с помощью имеющейся вычислительной техники.
Такую математическую модель называют реализуемой. Трудные вопросы практического построения у,-адекватных и одновременно реализуемых моделей исследовались в работах (22, 23, 26, 75, 260, 336, 242, 22?, 208, 177, 178, 330, 355, 356, 228). Таким образом, специалист, желающий решить свою практическую задачу с помощью математических методов оптимизации, должен располагать некоторым запасом реализуемых моделей, среди которых может выбирать у,-адекватную модель. С этой целью данное пособие, во-первых, знакомит читателей с широким кругом тех задач оптимизации, для которых уже разработаны теоретически обоснованные методы их решения и, во-вторых, доводит все эти методы до детально разработанных алгоритмов, чтобы облегчить их практическое использование.
2. Оеяозиыз задачи опзимиззяаз Обычно задачи оптимизации классифицируют по тем свойствам допустимого множества Х и минимизируемой функции ), которые обеспечивают или облегчают практическое отыскание оптимального решения. В теории оптимизации выделяют три основных класса задач: задачи безусловной оптимизации, или задачи без ограничений (в этих задачах не накладываются ограничения на допустимые значения переменной х, т. е. множество Х совпадает со всем пространствам Х'определения переменной х); задачи условной оптимизации, или задачи с ограничениями (в этих задачах Х чь«') и задачи оптимизации при неполных данных; в этих задачах 1 и (или) Х зависят от некоторого параметра р (числового, векторного или функционального), значение которого не полностью определено в момент выбора решения х. В дальнейшем будем обозначать через агя ппп?(х) оптималь«ех ное рсшение х«задачи (О 1), т.
е. тот элемент х' из множества Х, который доставляет функции ) наименьшее значение на множестве Х, а множество всех оптимальных решений — через Агу ппп 1 (х). «вх Это множество может состоять из одного илн многих элементов, нлн может'оказаться пустым (в этом случае задача оптимизации не имеет решения) н даже может совпадать со всем множеством Х— все зависит от свойств конкретно выбранной функции ~ и множества Х.
Множество Х принято называть допустимым множеством, или множествам допустимых решений, а функцию ~ — минимизируемой функцией, или целевой функцией, нли функцией затрат. В некоторых случаях требуется найти элемент х**, максимнзирующнй функцию г на множестве Х, т. е. удовлетворяющий условию ~ (х*") в 1(х) Ч х ~ Х (например, если значением ((х) оценивают «прибыль» от использования решения х).
Такое оптимальное решение х" обозначается через агд шах((х), а множество всех оптимальных решений— «ЕХ через Агу шах 1 (х). Функцию) называют соответственно максимизи- «ЕХ руемой (функцией полезности, критерием качества и др,). Очевидно, задача максимизации переходит в задачу минимизации (0.1),если умножить функцию г на ( — 1). » я В настоящее время наиболее изученными являются задачи линейного программирования (в этих задачах функция ~ линейная, а множество Х задается системами линейных равенств н (илн) неравенств) н задачи выпуклого программирования (в этих задачах ) и Х выпуклы). Для решения этих задач (хороших в том смысле, что все их локальные решения х«, удовлетворяющие неравенствам 1(х*)(~(х) (о з) для всех х с Х из окрестности точки х', являются одновременно искомыми оптимальными решениями х*) разработаны довольно эффективные численные алгоритмы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
