Задачи многокритериальной оптимизации

Оптимизационные задачи, их классификация

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

Оптимизационная задача задаётся тройкой , гдеF – функция, определённая на множестве , аD – некоторое подмножество множества .

Функция F называется целевой функцией;

D – множеством допустимых решений (допустимой областью)

оптимизационной задачи;

_U_{- пространством оптимизации.}

Оптимизационная задача максимизации (минимизации) состоит в отыскании наибольшего (наименьшего) значения целевой функции F на допустимом множестве D.

Любая задача максимизации сводится к задаче минимизации .

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

_{Методы решения оптимизационных задач зависят как от вида целевой функции}F, так и от вида множества допустимых решения D. _{- оптимизируемая целевая функция, или целевой функционал , критерий качества - численно выражает степень достижения целей функционирования оптимизируемого объекта. Целевая функция представляет собой набор критериев качества, которые должны быть оптимизированы одновременно. Соответственно, приk=1 имеем задачу однокритериальной илискалярной оптимизации, а при k>1 – задачу многокритериальной или векторной оптимизации.}

_{Вектор неизвестных может содержать одну компоненту (n=1) и тогда мы имеем задачу одномерной оптимизации, а может иметь и много составляющих (n>1) и тогда это задача многомерной оптимизации или задача оптимизации со многими переменными.}

_{Допустимая область D может совпадать с пространством оптимизации (D =U ), что означает отсутствие каких-либо ограничений на неизвестные. В этом случае имеем задачубезусловной оптимизации или задачу оптимизации без ограничений. Если же , то в задаче не все значения переменных допустимы, т.е. имеются некоторые ограничения на них. Соответствующая задача оптимизации называетсяусловной или задачей с ограничениями.}

_{Пространство оптимизации U может совпадать с евклидовым пространством и мы получаем задачу оптимизации с непрерывными переменными.}

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

_{Если же значение целевой функции зависит от некоторых комбинаций объектов из конечного набора, их размещения или способа упорядочения, то такие задачи называются задачами комбинаторной оптимизации.}

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

_{Приведем классификацию задач оптимизации с учетом конкретной формы задачи и свойств функции, входящих в ее постановку, как это сделано в работе [15]}

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

_{Если же все функции, входящие в постановку задачи, записываются в явном аналитическом виде , то соответствующая задача оптимизации называется задачейматематического программирования. Чаще всего математическим программированием называют задачи оптимизации с ограничениями, подчеркивая их отличие от задач безусловной оптимизации.}

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

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

_{Существуют более узкие постановки задачи линейного программирования – транспортная задача, задача о назначениях, задача целочисленного линейного программирования и другие.}

_{Если целевая функция сепарабельна, т.е. изменяется независимо по каждой переменной в отдельности, а ограничения – линейны, то задача называется задачей сепарабельного программирования.}

_{Если целевая функция квадратична, а ограничения – линейны, то задача называется задачей квадратичного программирования.}

_{Если целевая функция выпукла, а функции-ограничения образуют выпуклую допустимую область, то соответствующая задача носит название задачи выпуклой оптимизации.}

_{В случае функций общего вида говорят об общей задаче нелинейного программирования.}

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

_{Наконец, до сих пор, опять таки неявно, предполагалось, что вся исходная информация определена однозначно. Такие задачи называются детерминированными. Такие модели могут оказаться неадекватными реальным процессам, которые могут характеризоваться неполнотой, неточностью данных, на основе которых формируется модель.}

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

_{Однако неопределенность данных задачи может иметь и не вероятностный характер. В таких ситуациях говорят об оптимизации в условиях неопределенности. Методы решения в таких случаях основываются на теории нечетких множеств и так называемой нечеткой логике и объединяются под названием нечеткого математического программирования или нечеткой оптимизации.}

Задачи многокритериальной оптимизации

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

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

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

(3.28)

(3.29)

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

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

- упорядочение заданного множества критериев и последовательная оптимизация по каждому из них (этот подход рассмотрен ниже на примере метода последовательных уступок;

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

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

Определение 3.1. Вектор называется эффективным (оптимальным по Парето) решением задачи (3.28), (3.29), если не существует такого вектора , что

(3.30)

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

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

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

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

Рассмотрим один из таких методов решения многокритериальных задач - метод последовательных уступок.

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

Затем, исходя из практических соображений и принятой точности, назначается величина допустимого отклонения 8, > 0 (экономически оправданной уступки) критерия Z, и находится максимальное значение второго критерия Z'₂ при условии, что значение первого критерия не должно отклоняться от своего максимального значения более чем на величину допустимой уступки, т.е. решается задача:

Снова назначается величина уступки δ₂ > 0 по второму критерию, которая вместе с первой уступкой используется для нахождения условного максимума третьего частого критерия:

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

Пример 3.7. Решение задачи многокритериальной оптимизации методом последовательных уступок.

Решение. Пусть задача трехкритериальной оптимизации имеет вид

(3.31)

(3.32)

(3.33)

(3.34)

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

Для определенности будем считать, что допустимые уступки по первым двум критериям заданы: δ₁ = 3; δ₃ = 5/3.

Максимизируем функцию Z₃ в области допустимых решений, т.е. решаем одну критериальную задачу (3.31), (3.34). Это несложно сделать рассмотренным в главе 2 графическим методом решения задач линейного программирования (рис. 3.3).

Рис. 3.3

Максимум функции Z₁ при условиях (3.34) достигается в точке А области Q с координатами (1; 4), так что в данном случае

Переходим к максимизации функции Z, при условиях (3.34) и дополнительном ограничении, позволяющем учесть, что по критерию Z, нельзя уступать более чем на δ₁. Так как в нашем примере , то дополнительное ограничение будет иметь вид

(3.35)

Задачу (3.32), (3.34), (3.35) также решаем графически (рис. 3.4).

Получаем, что максимум функции Z₂ при условиях (3.34), (3.35) достигается в точке В части Q, области Q, так что

Теперь уступаем по критерию Z₂ на величину уступки 5₂= 5/3 и получаем второе дополнительное ограничение:

(3.36)

Максимизируем функцию Z₃ при условиях (3.34), (3.35) и (3.36). Решение этой задачи представлено на рис 3.5.

Рис. 3.4

Рис. 3.5

Таким образом, получаем оптимальное решение рассматриваемой трехкритериальной задачи (точка С на рис. 3.5):

x₁ = 2; х₂ = 3.

Соответствующие значения частных критериев при этом составляют:

Z₁ = 4; Z₂ = 7; Z₃ = -7.

Дата добавления: 2022-06-11; просмотров: 27; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!