Ссылка для цитирования: Фролов И.В., Боднар А.В. Методологические основы решения оптимизационных задач // — Сборник материалов XV Международной научно-технической конференции в рамках X Международного Научного форума Донецкой Народной Республики. — 2024. — №15. — С. 125-134.

Методологические основы решения оптимизационных задач

Фролов И.В., Боднар А.В.

ФГБОУ ВО Донецкий национальный технический университет

кафедра программной инженерии им. Л.П. Фельдмана

E-mail: f-r-o-l-o-v2000@mail.ru

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

Abstract: Frolov I.V., Bodnar A.V. Methodological foundations for solving optimization problems. The article discusses the basic principles of optimization theory as a set of mathematical methods for finding the best solution among a variety of alternatives. The most significant provisions of the optimization theory are described, the classification of optimization problems and methods of their solution is carried out. The author concludes that optimization tasks are important for the economy of modern enterprises.

Ключевые слова: оптимизация, классификация, анализ, статистика, решение, метод.

Keywords: optimization, classification, analysis, statistics, solution, method.

Введение

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

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

Можно было бы подумать, что распространенность таких задач давно должна была найти отражение в математике. Однако до середины XX века задачи с экстремумами рассматривались в математике лишь эпизодически, а теория и методы решения таких задач были разработаны сравнительно недавно.

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

Первые исследования предельных задач с общими ограничениями (в виде равенств и неравенств) были проведены в конце 30-х — начале 40-х годов XX века. Здесь следует упомянуть имена американских ученых, принадлежащих к Чикагской школе, таких как Г. Блисс, О. Больц, Э. Макшейн и Л. М. Грейвс. Помимо работ американских ученых, тема оптимизации развивалась и в СССР. Одним из пионеров в этой области был Л.В. Канторович, который в 1939 году опубликовал книгу, содержащую математические формулировки ряда экономических задач. Однако работа Канторовича, как и работы американских ученых, не привлекла внимания математиков и в основном осталась незамеченной.

Эти проблемы созрели несколько позже, в конце 40-х годов прошлого века. Под влиянием прикладных вопросов, которыми ему пришлось заниматься во время Второй мировой войны (проблема снабжения плацдармами армий второго фронта в Европе и Африке), американец Данциг начал работать над проблемой минимизации при линейных ограничениях, известной как задача линейного программирования (ЗЛП). Под влиянием работ фон Неймана по теории игр Данциг, Гел, Кун и Такер создали теорию двойственности в ЛП — специальную формулировку условий существования избытка.

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

1. Основные положения теории оптимизации

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

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

1) Определение границ оптимизационной задачи.

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

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

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

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

2) Выбор управляющих переменных.

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

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

3) Определение ограничений на управляемую переменную.

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

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

4) Выбор численных критериев оптимизации.

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

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

Решения определяются в каждом конкретном случае. Например, среди большого количества критериев, характеризующих различные цели оптимизации, один критерий выбирается как основной, а остальные — считаются второстепенными. Кроме того, второстепенные критерии либо не учитываются, либо учитываются лишь частично в связи с дополнительными ограничениями на управляющие переменные. Эти ограничения обеспечивают варьирование второстепенных критериев в определенном диапазоне допустимых значений.

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

5) Формулировка математической оптимизационной задачи.

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

Под минимизацией (максимизацией) функции n переменных f(х) = f(xl, ..., хn) на заданном множестве Un — мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x) [3].

2. Классификация задач оптимизации

Многие оптимизационные задачи основаны на поиске минимального (или максимального) значения объективной функции или показателя качества. В зависимости от типа целевой функции и типа ограничений на область и параметры функции существуют различные типы оптимизационных задач.

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

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

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

Рассмотрим общую проблему формулировки одномерных оптимизационных задач. С математической точки зрения такая задача может быть сформулирована следующим образом: найти минимальное (или максимальное) значение объективной функции f(x), заданной на множестве X, и определить значение переменной x є X, при котором она принимает экстремальные значения.

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

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

Во многих практических ситуациях возникает проблема оптимизации решения, каждый компонент которого представляет собой выбор между одной из двух возможных альтернатив: если присвоить j-й альтернативе операционную переменную хi, которая принимает значение 0 или 1 в зависимости от того, какая из двух альтернатив выбрана, то получится частный случай целочисленной задачи оптимизации — с булевыми переменными.

3. Классификация методов оптимизации

Для каждого класса оптимизационных задач существуют различные (чаще всего специфические) методы их решения. Рассмотрим классификацию основных из них [6].

Классификация методов оптимизации может быть выполнена следующим образом:

— По размерности решаемой задачи: одномерные и многомерные.

— По способу формирования шага многомерные методы делятся на следующие виды:

— градиентные;

— безградиентные;

— случайного поиска.

В свою очередь, градиентные методы можно классифицировать:

— по алгоритму коррекции шага;

— по алгоритму вычисления новой точки (одношаговые и многошаговые).

Безградиентные методы делятся на методы: с поочередным изменением переменных и с одновременным изменением переменных.

Методы случайного поиска делятся на методы; с чисто случайной стратегией и со смешанной стратегией.

3) По наличию активных ограничений методы оптимизации можно разделить:

— без ограничений (безусловные);

— с ограничениями (условные).

В свою очередь, последние могут быть:

— с ограничениями типа равенства;

— ограничениями типа неравенств;

— смешанные.

Одномерные методы оптимизации служат основой для различных "многомерных" методов. В многомерной градиентной оптимизации последовательность улучшений формируется в зависимости от скорости изменения критериев по различным направлениям. В этом случае порядок улучшения — это порядок в каждой точке, где значение критерия оптимизации лучше предыдущего [х0, х1, ... xi, … ]. В безградиентном методе величина и направление шагов, ведущих к оптимуму при построении последовательности уточнений, однозначно определяются заданной детерминированной функцией, которая зависит от характера критериев оптимальности в окрестности текущей точки, без использования производных (т.е. градиентов). Рандомизированные методы используются в задачах высокой размерности. В многомерной условной оптимизации рассматриваются активные ограничения, выраженные в терминах равенства и неравенства.

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

К методам одномерной оптимизации (т. е. методам решения задач оптимизации вида f(х) > min(max), а < х < b, где х — скаляр, а и b — соответственно минимальное и максимальное возможные значения переменной х относятся следующие методы:

— метод сканирования. Достоинство метода состоит, в том, что можно найти глобальный максимум критерия, если f(x) — многоэкстремальная функция.

К недостаткам метода относится значительное число повторных вычислений f(x), что в случае сложной функции f(x) требует существенных затрат времени;

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

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

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

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

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

— метод Гаусса-Зейделя (метод координатного спуска). Этот метод прост в реализации. На эффективность метода влияет порядок изменения переменных. Недостатками метода являются низкая эффективность функции Гурри и чувствительность к выбору системы координат;

— метод Розенброка. Он направлен на устранение одного из недостатков предыдущего метода;

— чувствительность к выбору системы координат;

— метод координат. Особенно полезен для квадратичных функций;

— симплекс-метод. В n-мерном пространстве симплекс — это фигура, содержащая n+1 вершин (треугольники на плоскости, тетраэдры в трехмерном пространстве и т.д.);

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

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

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

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

4. Практическое применение оптимизационных задач

Оптимизационные задачи имеют широкое прикладное значение в различных сферах деятельности человека. Рассмотрим некоторые примеры их возможного применения:

— бизнес и менеджмент: оптимизационные модели могут быть использованы для определения оптимального ассортимента продукции, планирования производства, распределения ресурсов, ценообразования, управления запасами и многих других бизнес-процессов (методы линейного программирования);

— производство и технологии: проектирование производственных систем, разработка новых продуктов, планирование производственных процессов и оптимизации производственных операций (метод динамического программирования);

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

— логистика и транспорт: планирование маршрутов доставки, оптимизация загрузки транспортных средств, управление распределением товаров и услуг, планирование перевозок в аэропортах и на вокзалах;

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

— здравоохранение: планирование и управления ресурсами в медицинских учреждениях, оптимизация распределения медицинских ресурсов, разработка новых методов лечения и диагностики, а также решение многих других проблем в области здравоохранения;

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

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

Выводы

Хотя методы оптимизации как самостоятельное направление возникли в середине 1960-х годов, их развитие продолжается и сегодня. Поэтому проанализировать все существующие группы проблем и их решения в рамках одного исследования не представляется возможным.

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

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

Литература

1. Aбчук, В.A. Cпрaвoчник пo иccледoвaнию oперaций / В.A. Aбчук. – М.: Вoениздaт, 1979. – C. 2.4.0.

2. Лукин A.И. Cиcтемы мaccoвoгo oбcлуживaния / A.И. Лукин. - М.: Вoениздaт, 1980. – C. 2.1.8.

3. Пoнтрягин Л.C. Мaтемaтичеcкaя теoрия oптимaльных прoцеccoв /Л.C. Пoнтрягин. – М.: Нaукa, 1983. – C. 283.

4. Эльcгoльц Л.Э. Дифференциaльные урaвнения и вaриaциoннoе иcчиcление /Л.Э. Эльcгoльц. – М.: Нaукa, 1969. – C. 146.

5. Бaнди Б. Метoды oптимизaции. Ввoдный курc: Пер. c aнгл. / Б. Бaнди. – М.: Рaдиo и cвязь, 1988. – C. 128.

6. Хедли Дж. Нелинейнoе и динaмичеcкoе прoгрaммирoвaние: Пер. c aнгл. /Дж. Хедли. – М.: Мир, 1969. – C. 424.

7. Cухaрев, A.Г. Курc метoдoв oптимизaции. / A.Г. Cухaрев, A.В. Тимoхoв, В.В. Федoрoв. – М.: Нaукa, 1986. – C. 328.

8. Дaнциг Дж. Линейнoе прoгрaммирoвaние: Пер. c aнгл. / Дж. Дaнциг – М.: Прoгреcc. 1966. – 600 c. 9 Мину М. Мaтемaтичеcкoе прoгрaммирoвaние. Теoрия и aлгoритмы: Пер. c фрaнц. / М. Мину. – М.: Нaукa, 1990. – C. 487.

9. Фейгин М.И. Прoявление эффектoв бифуркaциoннoй пaмяти в пoведении динaмичеcкoй cиcтемы // Coрocoвcкий oбрaзoвaтельный журнaл : журнaл. – 2001. – Т. 7, № 3. – C. 121– 127.