Общая задача исследования операций
Однокритериальная и многокритериальная отпимизация.
Исследование операций — изучает применения количественных методов для управления сложными системами людей, машин, материалов, денег и информации. Методология исследования операций позволяет понять сущность управленческих проблем и разработать модели для оценки последствий принимаемых решений.
Общая задача исследования операций выглядит следующим образом:
f(x, y, z) → min
gi(x, y, z) ≤ 0, i = 1, . . . , m, (1,1)
x ∈ X, y ∈ Y, z ∈ Z,
где
• x — вектор контролируемых факторов,
• y — вектор случайных факторов,
• z — вектор неопределенных факторов,
а X, Y, Z есть подмножества некоторых векторных пространств. Если все эти пространства конечноменрые, то мы имеем задачу конечномерной оптимизации. Если хотя бы одно из этих пространств бесконечно-мерное, то задача (1.1) есть задача бесконечномерной оптимизации. Значение контролируемых факторов выбирается теми, кто принимает решение (оперирующей стороной). Случайные и неопределенные факторы — это неконтролируемые факторы для оперируюшей стороны. Разница между случайными и неопределенными факторами состоит в следующем. Вектор y — это случайный вектор с известным законом распределения. Например, y5 есть нормальная случайная величина с матожиданием m ∈ [m1, m2] и стандартным отклонением σ ∈ [σ1, σ2]. В противоположность, оперирующей стороне известны только области значений неопределенных факторов. Например, переменная z3 принимает значения из отрезка [1,7].
Важными разделами исследования операций являются:
• математическое программирование (X 6= ∅, Y = Z = ∅);
• стохастическое программирование (X 6= ∅, Y 6= ∅, Z = ∅);
• теория игр и робастная оптимизация (X 6= ∅, Z 6= ∅).
Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси.
Общая постановка задачи одномерной оптимизации заключается в следующем: дана некоторая функция f(x) от одной переменной x, необходимо определить такое значение x*, при котором функция f(x) принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек. Нахождение этих точек с заданной точностью можно разбить на два этапа. Сначала экстремальные точки отделяют, т.е. определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности .
Максимизация целевой функции эквивалента минимизации противоположной величины, поэтому, можно рассматривать только задачи минимизации.
Для решения задачи минимизации функции f(x) на отрезке [a, b] на практике, как правило, применяют приближенные методы. Они позволяют найти решения этой задачи с необходимой точностью в результате определения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации.
Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках.
Среди задач математического программирования самыми простыми и наиболее хорошо изученными являются так называемые задачи линейного программирования (линейной оптимизации).
Рассмотрим данный тип задач. Для них характерен тот факт, что целевая функция линейно зависит от , а также то, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.
Такие задачи часто встречаются на практике - например, при решении проблем, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т.д.
Решение задач линейной оптимизации может быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения задач данного типа является симплекс-метод. В случае лишь двух переменных успешно может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае n>2 применение графического метода невозможно.
При решении ряда оптимизационных задач требуется, чтобы значения неизвестных выражались в целых числах. К задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.) [5].
Многокритериальная оптимизация
Чтобы получить более полную характеристику достоинств и недостатков проектируемого объекта, нужно ввести больше критериев качества в рассмотрение. Как результат: задачи проектирования сложных систем всегда многокритериальные, так как при выборе наилучшего варианта приходится учитывать много различных требований, предъявленных к системе.
С привычной точки зрения задача со многими критериями решения не имеет, но к счастью это не так, всегда есть возможность одновременного удовлетворения всех заданных условий. Атак как практически любая подобная ситуация допускает разные компромиссные разрешения, то и подходы к их поиску многочисленны и весьма разнообразны.
Перечислим некоторые из подходов к задачам со многими критериями:
- метод уступок лицо, принимающее решения, подводится к выбору решения путем постепенного ослабления первоначальных требований, как правило, одновременно невыполнимых;
- метод идеальной точки в области допустимых значений неизвестных ищется такая их совокупность, которая способна обеспечить набор значений критериев, в том или ином смысле ближайший к наилучшему варианту;
- метод свертывания лицо, принимающее решения, сводит многокритериальную задачу к задаче с одним критерием;
- метод ограничений множество допустимых значений неизвестных уменьшается путем осмысленного введения дополнительных ограничений на заданные критерии;
- метод анализа иерархий на основании суждений экспертов оценивается вклад в общую оценку каждого критерия.
Концепция принятия решения в качестве первичного элемента деятельности рассматривает решение как сознательный выбор одной из ряда альтернатив, называемых, в зависимости от их конкретного содержания, стратегиями, планами, вариантами и т.п. Этот выбор производит лицо, принимающее решение и стремящееся к достижению определенных целей. В роли такого лица выступают отдельные люди или группы людей, обладающие правами выбора решения и несущие ответственность за его последствия.
Применение математических методов при принятии решений предполагает построение подходящей математической модели. Для задач оптимизации в условиях определенности, когда случайные и неопределенные факторы отсутствуют, компонентами такой модели являются множество X всех альтернативных решений, из которых и надлежит произвести выбор одного наилучшего, или оптимального решения, и описание предпочтений лица, принимающего решение. Для того чтобы была обеспечена возможность выбора, множество X должно содержать не менее двух решений.
В многокритериальной задаче оптимизации сравнение решений по предпочтительности осуществляется не непосредственно, а при помощи заданных на Xчисловых функций f1, f2, … fm, называемых критериями. Предполагается, что m 2: при m = 1 задача оптимизации является однокритериальной.
В задачах принятия индивидуальных решений критерии служат для выражения «интенсивности» существенных свойств (признаков) решений. В задачах принятия групповых решений критерий U характеризует «качество» (или предпочтительность) решений с точки зрения индивида i, входящего в группу {1, 2,…,m}.
По своему характеру критерии подразделяются на два типа: количественные и качественные. Критерий является количественным, когда его значения имеет смысл сравнивать, указывая, на сколько, или во сколько раз одно значение больше другого, и качественным, когда такие сравнения бессмысленны.