Компьютерное моделирование производственных процессов

В зависимости от свойств функции f(x, y, z) в задачах оптимизации используются следующие основные типы целевых функций.

• Линейные, в которых функция f(x, y, z) является линейной относительно всех своих переменных. В последнем случае иногда дополнительно рассматривают:
• выпуклые (квадратичные), в которых функция f(x, y, z) является линейной относительно всех своих переменных.
• невыпуклые, в которых функция f(x, y, z) является невыпуклой относительно своих переменных.

В зависимости от количества целевых функций рассматриваются два основных типа задач оптимизации:

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

В контексте математической модели задач оптимизации требование нахождения наилучшего решения конкретизируется в требование максимизации или минимизации целевой функции. Данное требование может быть записано символически в виде: f(x, y, z) max или f(x, y, z) min. При этом максимум (минимум) целевой функции находится только среди множества допустимых альтернатив. Решением задачи оптимизации является некоторый допустимый набор значений переменных, который доставляет максимальное или минимальное значение целевой функции на множестве допустимых альтернатив.

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

                          f(x,y,z)илиf(x,y,z)                     (1.1)

 

                                где ={|(x,y,z)(=)0}, k {1,2,…,m}).                            (1.2)

 

Здесь через обозначено множество допустимых альтернатив, которое формируется посредством сужения исходного множества альтернатив с помощью совокупности ограничений, записанных в произвольной форме:(x, y, z) ≤ 0 или (x, y, z) = 0. В качестве исходного множества альтернатив выступает одно из рассмотренных ранее множеств: множество действительных чисел , множество целых чисел или множество из двух чисел: . Выбор этого множества определяется типом переменных, которые используются в постановке соответствующей задачи оптимизации. С учетом введенных обозначений общая математическая модель многокритериальной задачи оптимизации может быть записана символически в последующем виде:

 

(x,y,z)или (x,y,z),({1,2,…,n})          (1.3)

 

                          = {| (x, y, z) (=)0},  (k {1,2,…,m}).                       (1.4)

 

Здесь через также обозначено множество допустимых альтернатив, которое формируется посредством сужения исходного множества альтернатив . В случае n=2 соответствующие задачи оптимизации называются двухкритериальными, n=3 – трехкритериальными и т.д. натуральное число mопределяет общее количество ограничение задач оптимизации. В математических моделях типовых задач оптимизации явно указывают исходные множества альтернатив для точной спецификации типа переменных. Рассмотренные свойства базовых компонентов математической модели задач оптимизации позволяют выполнить общую классификацию этих задач, значение которых необходимо для правильного анализа и выбора метода для решения конкретных задач оптимизации.

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

Приведем классификацию задач оптимизации (табл.1)

Таблица 2 - Общая классификация задач оптимизации

 

Характеристика переменных	Характеристика ограничений	Характеристика целевой функции	Класс задач оптимизации
Непрерывные	Линейные	Одна, линейная	Линейное программирование
Непрерывные	Нелинейные или линейные	Одна, нелинейная	Нелинейное программирование
Целочисленные	Линейные	Одна, линейная	Целочисленное программирование
Целочисленные	Нелинейные или линейные	Одна, нелинейная	Целочисленное нелинейное программирование
Булевы	Линейные	Одна, линейная	Булево программирование
Булевы	Нелинейные или линейные	Одна, нелинейная	Булево нелинейное программирование
Непрерывные	Линейные	Несколько, линейные	Многокритериальное линейное программирование
Непрерывные	Нелинейные или линейные	Несколько, нелинейные	Многокритериальное нелинейное программирование
Целочисленные	Линейные	Несколько, линейные	Многокритериальное целочисленное программирование
Целочисленные	Нелинейные или линейные	Несколько, нелинейные	Многокритериальное целочисленное нелинейное программирование

 

 

Продолжение таблицы 2

Булевы	Линейные	Несколько, линейные	Многокритериальное булево программирование
Булевы	Нелинейные или линейные	Несколько, нелинейные	Многокритериальное булево нелинейное программирование

 

 

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

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

В общем случае под оптимальным решением однокритериальной задачи оптимизации в математической постановке (1 и 2) понимается такой набор значений переменных:x*, y*, z*, которые доставляют максимум или минимум целевой функции f(x,y,z) среди всех допустимых решений множества . Другими словами, характерным признаком оптимального решения задачи оптимизации является выполнение следующего условия:

 

                                      f(x*, y*, z*) ≥ f(x,y,z),x,y,z;                                     (1.5)

 

                                      f(x*, y*, z*)  ≤  f(x,y,z),x,y,z;            (1.6)

 

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

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

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

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

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

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

Следует различать два принципиально различных подхода к решению задач оптимизации:

• точное решение задачи оптимизации, которое соответствует нахождению единственного или нет оптимального решения x*, y*, z*, гарантирующего выполнение формальных условий (5) или (6);
• приближенное решение задачи оптимизации, которое соответствует нахождению некоторого допустимого решения x*, y*, z*, не гарантирующего выполнение формальных условий (5) или (6).

Говоря о приближенном решении задач оптимизации, часто условия (5 и 6) заменяют их более слабым аналогом:

 

       f(x*, y*, z*) ≥ f(x,y,z),           x,y,z;                                         (1.7)

 

f(x*, y*, z*)  ≤  f(x,y,z),         x,y,z;                                         (1.8)

   

где через ** обозначена некоторая окрестность решения x*, y*,z* на множестве допустимых альтернатив. В этом случае решение задачи оптимизации x*, y*,z* удовлетворяющее только условию (7) — для задачи максимизации или (8) — для задачи минимизации, называют локально-оптимальным решением. В данном контексте решение, удовлетворяющее условиям (5 и 6), называют также глобально – оптимальным решением.

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

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

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

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

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