Общая задача линейной оптимизации
заключается в нахождении максимума (минимума)
линейной целевой функции. Вид целевой
функции и ограничений описываются формулами
(1.1-1.4).
, (1.1)
при ограничениях:
, (1.2)
, (1.3)
(1.4)
где
- целевая функция, критерий оптимальности
или линейная форма;
x - вектор неизвестных;
- коэффициенты целевой функции;
- коэффициенты ограничений;
- величины правых частей ограничений.
Вектор значений неизвестных
, удовлетворяющих условию задачи
(1.1) – (1.4) , называется допустимым решением
или допустимым планом задачи линейной
оптимизации. Совокупность всех допустимых
планов называется множеством допустимых
планов. Допустимое решение
называется оптимальным, если оно
обеспечивает максимальное (или, в зависимости
от условий задачи, - минимальное) значение целевой
функции.
Решение задач линейной оптимизации
может быть получено без особых затруднений
(естественно, при корректной формулировке
проблемы). Классическим методом решения
задач данного типа является симплекс-метод.
В случае лишь двух переменных успешно
может использоваться также графический
метод решения, обладающий преимуществом
наглядности. Очевидно, в случае n>2 применение графического
метода невозможно.
При решении ряда
оптимизационных задач требуется, чтобы
значения неизвестных
выражались в целых числах.
К задачам подобного типа относятся те,
в которых требуется определить необходимые
для принятия решений значения физически
цельных объектов (машин, агрегатов различного
типа, людей, транспортных единиц и т.д.
и т.п.). Такие задачи относятся к задачам
целочисленной оптимизации. Математическая
модель задачи линейной целочисленной
оптимизации также определяется формулами
(1.1) – (1.4), но в данном случае налагается
дополнительное требование целочисленности
всех (или части) неизвестных. Если требование
целочисленности распространяется лишь
на часть неизвестных величин задачи,
то такая задача называется частично целочисленной
[5].
1.4 Многокритериальная
оптимизация
Чем больше критериев качества
вводится в рассмотрение, тем более полную
характеристику достоинств и недостатков
проектируемого объекта можно получить.
Таким образом, задачи проектирования
сложных систем всегда многокритериальны,
так как при выборе наилучшего варианта
приходится учитывать много различных
требований, предъявленных к системе (объекту).
С привычной точки зрения задача
со многими критериями решения не имеет - далеко не всегда есть возможность
одновременного удовлетворения всех заданных
условий. Поэтому, когда говорят о решении
многокритериальной задачи, имеют в виду
какой-нибудь компромисс между изначально
противоречивыми требованиями. Атак как
практически любая подобная ситуация
допускает разные компромиссные разрешения,
то и подходы к их поиску многочисленны
и весьма разнообразны.
Перечислим некоторые из подходов
к задачам со многими критериями
[6]:
- метод уступок - лицо, принимающее решения (руководитель), подводится к выбору решения
путем постепенного ослабления первоначальных
требований, как правило, одновременно невыполнимых;
- метод идеальной точки - в области допустимых значений неизвестных ищется такая их совокупность, которая способна обеспечить набор значений критериев, в том или ином смысле ближайший к наилучшему, как правило, недосягаемому (в так называемой точке утопии);
- метод свертывания - лицо, принимающее решения (руководитель), сводит многокритериальную задачу к задаче с одним критерием;
- метод ограничений - множество допустимых значений неизвестных уменьшается путем осмысленного введения дополнительных ограничений на заданные критерии;
- метод анализа иерархий - на основании суждений экспертов оценивается вклад в общую оценку каждого критерия.
Концепция принятия (выработки)
решения в качестве первичного элемента
деятельности рассматривает решение как
сознательный выбор одной из ряда альтернатив,
называемых, в зависимости от их конкретного
содержания, стратегиями, планами, вариантами
и т. п. Этот выбор производит лицо, принимающее
решение и стремящееся к достижению определенных
целей. В роли такого лица выступают отдельные
люди или группы людей, обладающие правами
выбора решения и несущие ответственность
за его последствия.
Применение математических
методов при принятии решений предполагает
построение подходящей математической
модели, формализованно представляющей
проблемную ситуацию, т. е. ситуацию выбора
решения. Для задач принятия решений (задач
оптимизации) в условиях определенности,
когда случайные и неопределенные факторы
отсутствуют, компонентами такой модели
являются множество X всех (альтернативных)
решений, из которых и надлежит произвести
выбор одного наилучшего, или оптимального
решения, и описание предпочтений лица,
принимающего решение. Для того чтобы
была обеспечена возможность (свобода)
выбора, множество X должно содержать
не менее двух решений.
В многокритериальной задаче
оптимизации сравнение решений по предпочтительности
осуществляется не непосредственно, а
при помощи заданных на X числовых функций f1, f2, … fm, называемых
критериями (а также показателями качества
или эффективности, критериальными функциями,
целевыми функциями и т. п.). Предполагается,
что m ≥2: при m = 1 задача оптимизации
является однокритериальной.
Для каждого критерия fi на числовой
прямой указывается подмножество, из которого
он принимает свои значения. Считается, что каждое решение х полностью
характеризуется соответствующей (векторной)
оценкой, т. е. вектором f(x). Поэтому выбор
оптимального решения из множества всех
решений X сводится к
выбору оптимальной оценки из множества
достижимых оценок.
В задачах принятия индивидуальных
решений критерии служат для выражения
«интенсивности» существенных свойств
(признаков) решений. В задачах принятия
групповых решений критерий U характеризует
«качество» (или предпочтительность) решений
с точки зрения индивида i, входящего
в группу {1, 2, ..., m}. Например,
если решений конечное число и индивид i все их проранжировал
(упорядочил по предпочтительности), то
можно принять Fi(x′) = 1
для наиболее предпочтительного решения х′, fi(x′′) =
2 - для следующего по предпочтительности
решения х", и т. д.
По своему характеру критерии
делятся на количественные и качественные.
Грубо говоря, критерий является количественным,
когда его значения имеет смысл сравнивать,
указывая, на сколько или во сколько раз
одно значение больше другого, и качественным,
когда такие сравнения бессмысленны [7].
1.5 Методы экспертного
анализа
Основная идея экспертных методов
состоит в том, чтобы использовать интеллект
людей, их способность искать и находить
решение слабо формализованных задач.
В теории экспертных оценок разработан
ряд методов проведения экспертизы. Рассмотрим
основные методы экспертного анализа.
1.5.1 Метод попарного сравнение
объектов (метод Саати) [5]. Часто затруднительно
напрямую оценить важность некоторого
объекта среди ряда других. Подобная ситуация
может иметь место при наличии объектов
различной природы. Например, среди ранжируемых
показателей эффективности могут быть
показатели, имеющие определенное стоимостное
выражение, а также показатели этического,
эстетического рода и т.п. Указанное затруднение
преодолевается посредством попарного
сравнения объектов по степени их влияния
на достижение цели. При этом эксперт должен
вынести суждение о том, насколько с точки
зрения достижения цели один объект важнее
второго. Анализируя совокупность объектов,
эксперт определяет численное предпочтение
одного объекта перед другим по некоторой
заранее выбранной шкале отсчета. Простым
примером может служить выбор места работы
выпускником ВУЗа. Выпускник должен оценить,
насколько для него уровень оплаты труда,
например, важнее, чем перспективы продвижения
по служебной лестнице и т.д.
Пусть эксперт анализирует
объектов. Сравнивая их попарно между
собой, он определяет
чисел
, каждое из которых характеризует,
по мнению эксперта, относительную значимость
- го объекта по сравнению с
- м. Величина
представляет оценку (приближенное
значение) истинной значимости
сравниваемых объектов. Совокупность
экспертных оценок можно записать в виде
квадратной матрицы
(1.5)
Элементы этой матрицы (относительные
значимости объектов) можно рассматривать
как отношения истинных важностей
(1.6)
При оценке относительных значимостей
используется обычно девятибалльная
шкала представленная в таблице 1.1.
Таблица 1.1. Девятибалльная
шкала относительной важности объектов.
Степень важности |
Определение |
Пояснения |
1 |
Объекты одинаково важны |
Оба объекта вносят одинаковый
вклад в достижение цели |
3 |
Один объект немного важнее
другого |
Есть основания предпочесть
один объект другому, но их нельзя считать
неопровержимыми |
5 |
Один объект существенно важнее
другого (сильное превосходство) |
Существуют веские свидетельства
того, что один из объектов более важен |
7 |
Один объект явно важнее другого |
Имеются неопровержимые свидетельства
превосходства одного объекта над другим |
9 |
Один объект абсолютно важнее
другого |
Превосходство одного объекта
над другим не вызывает сомнения |
2, 4, 6, 8 |
Значения, приписываемые промежуточным
суждениям |
Используются, когда выбор между
двумя соседними нечетными числами затруднителен |
Из формулы (1.6) следует, что
из общего числа всех элементов матрицы
попарного сравнения независимыми являются
лишь
. Во-первых, диагональные элементы
матрицы равны единице. Во-вторых, при
изменении порядка сравнения оценка относительной
значимости объекта должна меняться на
обратную:
(1.7)
Это означает, что элементы
матрицы попарного сравнения, расположенные
симметрично относительно главной диагонали,
представляют собой взаимно обратные
числа.
Выбор решения выполняется
в следующем порядке. Сначала эксперты
заполняют матрицы парных сравнений. Затем
для каждой матрицы определяются оценки
предпочтения альтернатив над другими,
то есть находятся суммы строк матриц
по формуле (1.8):
(1.8)
где k – число экспертов;
n – количество альтернатив.
После этого определяются обобщенные
оценки предпочтения альтернатив над
другими (с учетом мнения всех экспертов)
– и находится сумма всех оценок
. Находятся веса альтернатив по формуле
(1.9):
(1.9)
Лучшей считается альтернатива,
имеющая наибольший вес.
1.5.2 Метод приписывания баллов
(метод ранга) [1]. Этот метод основан на
том, что эксперты оценивают важность
частного критерия по шкале от 0 до 10. При
этом разрешается оценивать важность
дробными величинами или приписывать
одну и ту же величину из выбранной шкалы
нескольким критериям.
Обозначим через hik - балл i-го эксперта
для k-критерия, тогда
(1.10)
где
- сумма баллов i - ой строки;
m – количество критериев.
rik - называют весом, подсчитанным
для k - критерия i - м экспертом.
Отсюда, учитывая, что
, где L - количество экспертов, получим
веса альтернатив:
(1.11)
Как и в методе попарного сравнения,
лучшей считается альтернатива, имеющая
наибольший вес.
2 АЛГОРИТМИЧЕСКИЙ
АНАЛИЗ ЗАДАЧИ