8. Многокритериальные оптимизационные задачи
8.1. Определение коэффициентов веса каждого критерия
Рассмотренные выше решения оптимизационных задач выполнялись по одному критерию (по одной целевой функции). На практике не всегда удается свести задачу к одному критерию, поскольку желаемых целей может быть несколько. Задачи, в которых оптимизация проводится по нескольким критериям, называют задачами многокритериальной оптимизации. Такая оптимизация представляет собой попытку найти компромисс между принятыми критериями. Важным моментом нахождения такого компромисса является назначение коэффициентов веса каждого критерия. В конечном итоге решение многокритериальной задачи сводится к оптимизации по одному обобщенному критерию, в который входят все принятые критерии со своими весовыми коэффициентами. Существует достаточно много способов определения весовых коэффициентов. Рассмотрим один из них, а именно, способ экспертных оценок. Суть этого способа заключается в следующем. Пусть для решения оптимизационной задачи приняты, например, три критерия (критерий А , критерий В и критерий С ). Собирается группа экспертов – специалистов в той области, к которой относится оптимизационная задача. Пусть группа экспертов состоит, например, из трех человек (1-й эксперт, 2-й эксперт и 3-й эксперт). Каждому эксперту предлагается оценить в баллах от 0 до 1 каждый критерий. При этом выдвигается условие, чтобы сумма баллов каждого эксперта по всем критериям была бы равна 1. В табл. 8.1 представлены результаты экспертизы. В качестве весового коэффициента i -го критерия ( i=A, B, C ) принимается среднее 95
значение оценок каждого эксперта по этому критерию (последняя строка табл. 8.1).
| Т а б л и ц а 8.1 | ||||
| К р и т е р и и | ||||
| Эксперты | А | В | С | Сумма |
| 1-й | 0,2 | 0,2 | 0,6 | 1,0 |
| 2-й | 0,4 | 0,3 | 0,3 | 1,0 |
| 3-й | 0,3 | 0,2 | 0,5 | 1,0 |
| Коэф.веса | 0,3 | 0,23 | 0,47 | 1,0 |
8.2. Оптимизация по обобщенной целевой функции
Одним из возможных решений многопараметрической задачи является оптимизация по обобщенной целевой функции, в которую входят все принятые к рассмотрению критерии со своими весовыми коэффициентами. Эта обобщенная функция записывается следующим образом:
| s | α | k | Z | k | |
| Z об = ∑ | → max, | (8.1) | |||
| k = 1 Z k норм | |||||
Z k – k -я целевая функция, выражающая k -й критерий; Z k норм – нормированное значение k -й целевой функции; α k – коэффициент веса k -й целевой функции; s – количество целевых функций (принятых критериев). Если k -я целевая функция максимизируется, перед ней под знаком суммы ставится плюс. Если k -я целевая функция минимизируется, перед ней под знаком суммы ставится минус. Весовые коэффициенты могут быть определены, например, с помощью экспертных оценок (см. п. 8.1). Нормированное значение k -й целевой функции Z k норм принимается по результатам решения оптимизационной задачи только по одному k –му критерию. Целевые функции в общем случае имеют разные единицы измерения. Поэтому в (8.1) введено деление каждой целевой функции 96
на ее нормированное значение. Такое действие приводит все целевые функций к единой размерности (к относительным единицам, о.е.). Составление ограничений и граничных условий для многокритериальной задачи не имеет специфических особенностей по сравнению с однокритериальной задачей. Пример 13 . Рассмотрим задачу распределения ресурсов ( примеры 1 и 2), в которой требуется определить оптимальный выпуск изделий трех видов ( х 1 , х 2 и х 3 ), обеспечивающий предприятию максимальную прибыль при минимальном расходе энергетических ресурсов. Решение . Решение задачи только по критерию максимальной прибыли выполнено ранее (см. приложение П.3) и дало следующий результат: х 1 =0, х 2 =10, х 3 =10, прибыль Z 1 =230 у.е. Решим эту задачу с учетом только второго критерия – минимального расхода энергоресурсов. Подлежащая минимизации целевая функция, представляющая собой затраты энергоресурсов на выпуск продукции, имеет следующий вид:
| Z 2 = 2 х 1 + 2 х 2 +3 х 3 → min. | (8.2) |
Из системы ограничений исключаем неравенство, ограничивающее расход энергоресурсов (2 х 1 +2 х 2 +3 х 3 < 50), поскольку левая часть этого неравенства стала целевой функцией. В результате имеем следующую систему ограничений, состоящую из трех неравенств:
| 6 х 1 + 5,5 х 2 + 4 х 3 < 100, | (8.3) |
| 4 х 1 + 6 х 2 + 8 х 3 < 150, | |
| х 1 + х 2 + х 3 > 15. | |
| Условия целочисленности переменных | |
| х i – целое, i =1, 2, 3 | (8.4) |
| и граничные условия | |
| х i > 0, i =1, 2, 3 | (8.5) |
остаются без изменений. Решение задачи по 2-му критерию Z 2 → min приведено в приложении П.6 и дает следующий результат: 97
х 1 =0, х 2 =15, х 3 =0, расход энергии Z 2 = 30 е.э. (единиц энергии). Для решения двухкритериальной задачи сформируем обобщенную целевую функцию Z об = α 1 Z 1 / Z 1норм — α 2 Z 2 / Z 2норм → max. Предположим, что в результате экспертных оценок получены следующие весовые коэффициенты: α 1 = 0,6 и α 2 = 0,4. Обобщенная целевая функция будет иметь следующий вид Z об =0,6(8 х 1 + 11 х 2 + 12 х 3 ) / 230 – 0,4(2 х 1 + 2 х 2 + 3 х 3 ) / 30. Система ограничений остается в виде (8.3), условие целочисленности переменных – в виде (8.4), граничные условия – в виде (8.5). Решение рассматриваемой двухкритериальной задачи приведено в приложении П.6 и дает следующий результат: х 1 =4, х 2 =1, х 3 =16; обобщенная целевая функция Z об = 0,6 . 235 / 230 + 0,4 . 58 / 30 = 0,28 о.е. Результаты решений (значения переменных х 1 , х 2 , х 3 ), полученных при максимизации прибыли ( Z 1 → max), минимизации энергетических ресурсов ( Z 2 → min) и максимизации обобщенной целевой функции ( Z об → max), приведены в табл. 8.2. Т а б л и ц а 8.2
| Z 1 → max | Z 2 → min | Z об → max | |
| х 1 | 0 | 0 | 4 |
| х 2 | 10 | 15 | 1 |
| х 3 | 10 | 0 | 16 |
Видно, что результат решения двухкритериальной задачи отличается от результатов решения задачи по каждому из двух критериев. 98
Геометрическая интерпретация и графическое решение задач линейного программирования.
Если одна из этих задач обладает оптимальным решением, то и двойственная к ней задача также имеет оптимальное решение. Причем экстремальные значения соответствующих линейных форм равны: .
Решение транспортной задачи методом потенциалов
Сепарабельное программирование.
Целевое программирование. Метод весовых коэффициентов.
11. Целевое программирование. Метод приоритетов.
Задачи линейного программирования. Ограничения и дополнительные переменные. Стандартная форма задачи ЛП и ее базисные решения.
Геометрическая интерпретация и графическое решение задач линейного программирования.
15. Симплекс-метод решения задач линейного программирования. Алгоритм симплекс-метода (Метод Гаусса-Жордана).
Графический способ решения задачи ЛП показывает, что оптимальное решение этой задачи всегда ассоциируется с угловой точкой пространства решений.
Это является ключевой идеей при разработке общего алгебраического симплекс — метода для решения любой задачи линейного программирования.
Переход от геометрического способа решения задачи ЛП к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу ЛП к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
Стандартная форма задачи ЛП необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями).
Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений.
Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.
Алгоритм:
Шаг 0. Составление исходной симплекс таблицы.
Шаг 1. Находится начальное допустимое базисное решение.
Шаг 2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.
Шаг 3. На основе условия допустимости выбирается исключаемая переменная.
Шаг 4. Методом Гаусса–Жордана вычисляется новое базисное решение. Переход к шагу 2.
Условие оптимальности. Вводимой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая наибольший отрицательный (положительный) коэффициент в z – строке. Если в z – строке есть несколько таких коэффициентов, то выбор вводимой переменной делается произвольно. Оптимальное решение достигнуто тогда, когда в z – строке все коэффициенты при небазисных переменных будут неотрицательными (неположительными)
Условие допустимости. Как в задаче максимизации, так и в задаче минимизации, в качестве исключаемой выбирается базисная переменная, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если базисных переменных с таким свойством несколько, то выбор исключаемой переменной выполняется произвольно. Вычисление нового базисного решения основывается на методе исключения переменных (методе Гаусса–Жордана).
В следующей таблице, которая пока совпадает с начальной таблицей задачи ЛП, определим ведущий столбец, ассоциируемый с вводимой переменной, и ведущую строку, ассоциируемую с исключаемой переменной. Элемент, находящийся на пересечении ведущего столбца и ведущей строки, назовем ведущим.
16. Искусственное начальное решение. М-метод. Двухэтапный метод.
Искусственное начальное решение.
В простом симплексе при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми.
В задачах линейного программирования, где все ограничения являются неравенствами типа «=»?
Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются.
Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод и двухэтапный метод.
Для объяснения двухэтапного метода объясним сначала концепцию М-метода.
Пусть задача ЛП записана в стандартной форме. Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введём искусственную переменную Ri, которая далее войдёт в начальное базисное решение. Но поскольку эта переменная искусственна (другими словами, не имеет никакого «физического смысла» в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.
Переменная Ri, с помощью достаточно большого положительного числа М, штрафуется путём ввода в целевую функцию выражения –MRi в случае максимизации целевой функции и выражения +MRi – в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведёт к нулевому значению переменной Ri.
При использовании М-метода следует обратить внимание на следующие два обстоятельства.
1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это «индикатор» того, что задача не имеет допустимого решения.
2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой.
Алгоритм двухэтапного метода.
Двухэтапный метод полностью лишён тех недостатков, которые присущи М-методу. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведётся поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.
Этап 1. Задача ЛП записывается в стандартной форме, а в ограничения добавляются необходимые искусственные переменные (как и в М-методе) для получения начального базисного решения. Решается задача ЛП минимизации суммы искусственных переменных с исходными ограничениями (r=R1+R2+…Rk). Если минимальное значение этой новой целевой функции больше нуля, значит, исходная задача не имеет допустимого решения, и процесс вычислений заканчивается. (Напомним, что положительные значения искусственных переменных указывают на то, что исходная система ограничений несовместна.) Если новая целевая функция равна нулю, переходим ко второму этапу.
Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.
17. Двойственная задача. Принцип построения. Соотношения двойственности.
Исходную задачу линейного программирования будем называть прямой. Двойственная задача — это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи.