ГЛАВА 1. ПОНЯТИЕ И ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
Многие проблемы, возникающие в экономических исследованиях, планировании и управлении, будучи сформулированными математически, представляют собой задачи, в которых необходимо решить систему линейных алгебраических уравнений или неравенств и среди всех неотрицательных решений найти то решение, при котором линейная функция принимает наибольшее или наименьшее значение. Изучение методов исследования и решения математических задач указанного типа составляет содержание раздела математики, который называется линейным программированием [12,17].
Традиционный подход исследования операций предполагается наличие единственного критерия оценки качества решения. Однако, расширение области применения методов исследования операций привело к тому, что аналитики стали сталкиваться с задачами, в которых существенным оказывается наличие нескольких критериев оценк\и качества решения. Такие задачи носят название многокритериальной задачей оптимизации [36,51].
1.1. Линейное программирование
В настоящее время оптимизация практически неотъемлемая часть в науке, технике, экономике и в любой другой области человеческой деятельности.
Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях [44,46].
Поиски оптимальных решений привели к созданию специальных математических методов и уже в XVIII веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.) [45,48]. Однако до второй половины XX века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев – невозможно [46].
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач.
Методы оптимизации могут быть:
1) скалярными (оптимизация проводится по одному критерию);
2) векторными (оптимизация проводится по многим критериям);
3) поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.);
4) вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.);
5) теоретико-вероятностными, теоретико-игровыми и др. [45,46,48].
Наиболее часто используемым методом оптимизации является линейное программирование. Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования [4,29].
Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного подсчета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти незамеченной [15,18].
В 50-е гг. ХХ века независимо от Канторовича метод решения задачи линейного программирования (так называемый симплекс-метод) был развит американским математиком Дж. Данцигом, который в 1951 г. и ввел термин «линейное программирование».
Можно сказать, свое второе рождение линейное программирование получило с появлением электронно-вычислительных машин (ЭВМ). В то время началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования [29,32].
Слово «программирование» объясняют тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно определяют программу (план) действий некоторого объекта, например, промышленного предприятия. Слово «линейное» отражает линейную зависимость между переменными [12,18].
Линейное программирование находит широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем [4,17]. Многие распространённые классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку [2,12,18].
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
1) рационального использования сырья и материалов, задачи оптимизации раскроя;
2) оптимизации производственной программы предприятий;
3) оптимального размещения и концентрации производства;
4) составления оптимального плана перевозок, работы транспорта;
5) управления производственными запасами и многие другие, принадлежащие сфере оптимального планирования [4,12,18,29].
Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций [4].
В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения [32].
Стандартная задача линейного программирования
Основная задача линейного программир\ования выглядит следующим образом [47].
Дана система m линейных уравнений с n неизвестными:
{-(a_11 x_1+a_12 x_2+?+a_1n x_n?b_1,@a_21 x_1+a_22 x_2+?+a_2n x_n?b_2,@ ? ? ? ?@a_m1 x_1+a_m2 x_2+?+a_mn x_n?b_m,)+ (1.1)
где все неизвестные могут принимать только неотрицательные значения:
x_1?0,x_2?0,…,x_n?0 (1.2)
и линейная функция от тех же переменных
Z=c_1 x_1+c_2 x_2+?+c_n x_n (1.3)
называемая целевой функцией.
Требуется среди всех решений системы уравнений в (1.1) найти
такое неотрицательное решение, при котором целевая функция в формуле (1.3) принимает наибольшее возможное значение.
Любое неотрицательное решение системы уравнений в (1.1) называют допустимым решением, а то допустимое решение, при котором целевая функция в (1.3) принимает наименьшее значение, называют оптимальным решением задачи линейного программирования в формулах (1.1)-(1.3). Кратко задачу формулируют так: найти вектор x_1,x_2,…,x_n, минимизирующий целевую функцию в (1.3) при линейных ограничениях в (1.1) и (1.2).
Если в конкретной задаче будет необходимо найти наименьшее возможное значение некоторой линейной функции, как в формуле (1.3) при линейных ограничениях, то для приведения такой задачи к принятому нами виду основной задачи линейного программирования достаточно линейную функцию Z заменить противоположной ей функцией
-Z=?-c?_1 x_1-c_2 x_2-…-c_n x_n (1.4)
так как если функция –Z принимает наибольшее значение при некоторых значениях переменных, то при тех же значениях переменных функция Z примет наименьшее возможное значение [33,47,48].
1.2. Многокритериальная оптимизация
Методы решения задач линейного программирования с одним критерием интенсивно разрабатывались в течение нескольких десятков лет. Но вскоре, по мере развития информатики и технологии, до сегодняшнего дня, можно с уверенностью сказать, что любая серьезная проблема характеризуется больше чем одним критерием. Можно понять, что задачи многокритериальной оптимизации (МО) возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость, надежность и т. п.). Лица, принимающие решения (ЛПР), в значительно большей степени, чем когда-либо, ощущают необходимость оценивать альтернативные решения с точки зрения нескольких критериев [28,51].
Результаты исследования задач планирования и управления показывают, что в реальной постановке эти задачи являются многокритериальными. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т.д. [51].
Ранее, при исследовании проблемы многокритериальности часто все критерии, кроме одного, выбранного доминирующим, принимались в качестве ограничений, оптимизация проводилась по доминирующему критерию [36]. Такой подход к решению практических задач значительно снижает эффективности принимаемых решений. Здесь требуется найти точку области допустимых решений, которая минимизирует или максимизирует все эти критерии. В связи с этим, исследователи начали развивать имеющиеся теоритические и практические результаты методов решения задач с одним критерием таким образом, чтобы они были применимы к исследованию многокритериальных задач линейного программирования [51].
Ввиду этого в теории многокритериальной оптимизации понятие оптимальности получает различные толкования, и поэтому сама теория содержит три основных направления:
1. Разработка концепции оптимальности.
2. Доказательство существования решения, оптимального в соответствующем смысле.
3. Разработка методов нахождения оптимального решения.
Обозначим i-й частный критерий через , а область допустимых решений через Q. Учтем, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, и наоборот, мы можем сформулировать кратко задачу векторной оптимизации следующим образом:
Z(x)=(-(z_1 (x)@z_2 (x)@?@z_m (x) ))>max , при x?Q (1.5)
Если так смотреть, то по существу многокритериальная задача отличается от обычной задачи оптимизации только наличием нескольких целевых функций вместо одной. Но в отличие от задач оптимизации с одним критерием в многокритериальной оптимизации имеется неопределенность целей. Действительно, существование решения, максимизирующего несколько целевых функций, является редким исключением, поэтому с математической точки зрения задачи многокритериальной оптимизации являются неопределенными и решением может быть только компромиссное решение [51].
Например, выбирая работу, человек, как правило, руководствуется несколькими критериями. Допустим, кому-то хочется, чтобы одновременно выполнялись такие условия:
- заработная плата была как можно выше;
- условия работы были как можно комфортнее;
- место работы было как можно ближе к дому.
Другим примером задачи с многими критериями является модернизация производства, в процессе которой хочется достигнуть максимального роста эффективности с наименьшими затратами [28]. Очевидно, что невозможно достичь обеих целей одновременно, так как чем больше затраты, тем больше должно быть продукции и тем больше прибыль [36].
Еще один пример – выбор инвестиционного решения, когда хочется получить максимальный доход (или доходность) при наименьшем риске [51].
Примеры многокритериальности в экономике
Как ранее говорилось, в задачах математического программирования с одним критерием нужно определить значение целевой функции, соответствующее, например, минимальным затратам или максимальной прибыли. Однако, немного подумав, можно сказать, что практически в любой реальной ситуации обнаружим несколько целей, противоречащих друг другу [51].
Ниже будет показано, насколько широк диапазон проблем, которые могут быть адекватно сформулированы как многокритериальные, и какие характеристики следует использовать в качестве критериев.
1. Планирование производства:
– mах – суммарный чистый доход, минимальный чистый доход за любой период;
– min – число невыполненных заказов, сверхурочное время, запасы готовой продукции.
2. Выбор портфеля ценных бумаг:
– mах – доход, дивиденды;
– min – риск, отклонения от желаемого уровня разнообразия бумаг.
3. Составление сметы капиталовложений:
– mах – наличие средств, инвестиции в проекты, связанные с охраной окружающей среды, инвестиция в проекты в заданном регионе, инвестиции в проекты по заданной товарной специализации;
– min – спрос на капитальные вложения, ежегодные эксплуатационные расходы.
4. Управление лесным хозяйством:
– max – устойчивый урожай древесины, человеко-дни отдыха в лесу, человеко-дни охоты в лесу, ареал распространения диких животных, число месяцев выпаса домашних животных;
– min – превышения бюджета.
5. Управление попусками водохранилищ:
– max – выгоды от рекреации на водохранилище № 1, выгоды от зарегулирования стока ниже водохранилища № 1, количество энергии, вырабатываемой в бассейне реки, выгоды от рекреации на водохранилище № 2, прибыль от орошения земель ниже водохранилища № 2;
– min – недопоставки воды на коммунальные нужды в бассейне реки.
6. Формирование ревизионной службы в фирме:
– max – доход, время, отведенное на профессиональный рост
– min – рост численности персонала службы, уменьшение численности персонала службы, избыточные сверхурочные, недоиспользование квалификации кадров;
7. Транспортировка:
– max – производство по заданной технологии;
– min – стоимость, среднее время доставки грузов приоритетным клиентам, расход топлива.
Конечно, решения, которое одновременно удовлетворяло бы всем противоречивым требованиям, как правило, не существует. Но математика может помочь и при решении таких задач. Помощь эта состоит не в нахождении несуществующего решения, одновременно обращающего все критерии в максимум, а в отбрасывании заведомо плохих решений [28,37,51].
Оптимизация по Парето
Впервые проблему многокритериальной оптимизации рассмотрел итальянский экономист Вильфредо Парето в 1904 г. при математическом исследовании товарного обмена [37]. В дальнейшем интерес к проблеме многокритериальной оптимизации усилился в связи с разработкой и использованием вычислительной техники, и уже позднее стало ясно, что многокритериальные задачи возникают также и в технике, например, при проектировании сложных технических систем [51].
Согласно его концепции, общество находится в состоянии общего экономического равновесия и социальной эффективности распределения ресурсов, которое предполагает оптимальное распределение в сфере производства при минимальном использовании ресурсов и эффективное распределение в сфере потребления, обеспечивающее максимум удовлетворения потребностей. В. Парето считал, что в основе анализа общего равновесия должны лежать факты выбора потребителя, когда фиксируется лишь порядок предпочтения одного набора благ перед другими [36,37].
При решении большого числа практических задач приходится сталкиваться с необходимостью нахождения решений, удовлетворяющих нескольким, зачастую конфликтующим между собой, критериям. В связи с этим, решение задачи заключается не в нахождении какого-то одного решения, а в отыскании некоторого множества решений, каждое их которых будет превосходить другие хотя бы по одному критерию. Такие решения, как правило, называются оптимальными по Парето [36]. Необходимость отыскания целого множества решений чрезвычайно усложняет задачу оптимизации и делает практически непригодными большинство классических методов оптимизации. Задача усложняется еще и тем, что надо не только найти решения, максимально близкие к истинному множеству (или фронту) Парето, но и обеспечить максимально возможное различие между такими решениями (т.е. охватить возможно большую часть этого фронта).
Принципы многокритериальной оптимизации существенно отличаются от обычной оптимизации. Во втором случае (один критерий) целью решения задачи является нахождение глобального оптимального решения, дающего оптимальное значение для одной целевой функции. В случае нескольких критериев мы имеем соответственно несколько целевых функций, каждая из которых может иметь оптимальное значение при своем собственном наборе значений независимых переменных [28,37]. Если оптимальные решения для различных целевых функций существенно различны, то невозможно говорить об оптимальном решении всей задачи в целом. В этом случае мы получаем множество оптимальных решений, ни одно из которых не является оптимальным по сравнению с другими во всех смыслах (т.е. по все критериям). Это множество называют множеством решений оптимальных по Парето.
Проиллюстрируем это на примере, где нужно выбрать стратегию развития предприятия, критерии - ожидаемая прибыль в год (в смысле мат. ожидания из теории вероятностей), надёжность стратегии (вероятность того, что будет приемлемая для нас прибыль, хоть сколько-нибудь солидный доход) [37]. Допустим, у нас есть 5 стратегий:
Рис. 1.2. График оптимального плана развития предприятий
Стратегия 2 в среднем даёт больше прибыли, чем стратегия 1, при той же надёжности. Стало быть, стратегия 1 не может быть лучшей. Стратегия 3 по ожидаемой прибыли равноценна стратегии 2, но надёжнее. Стало быть, стратегия 2 тоже невыгодна. Стратегия 3 прибыльнее стратегии 4 при той же надёжность, то есть стратегия 4 тоже неоправданно. Остаются только стратегии 3 и 5. По одному критерию превосходит одна, по другому - другая.
Операции, оптимальные по Парето, не обязательно являются «самыми лучшими» - эти операции не являются худшими. Чтобы выбрать конкретное решение из Парето-оптимального множества, нужны дополнительные данные [21]. Выделение множества Парето ещё не даёт ответа на вопрос, какое решение оптимальное, но оно значительно упрощает применение алгоритмов, работающих с дополнительной информацией, поскольку сужает множество возможных вариантов [37,51].
В настоящее время линейная оптимизация является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения.
ГЛАВА 2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
Чтобы получить более полную характеристику достоинств и недостатков проектируемого объекта, нужно ввести больше критериев качества в рассмотрение. Как результат, задачи проектирования сложных систем всегда многокритериальные, так как при выборе наилучшего варианта приходится учитывать много различных требований, предъявленных к системе [28].
С привычной точки зрения задача со многими критериями решения не имеет, но к счастью это не так, всегда есть возможность одновременного удовлетворения всех заданных условий [51]. А так, как практически любая подобная ситуация допускает разные компромиссные разрешения, то и подходы к их поиску многочисленны и весьма разнообразны.
Перечислим некоторые из подходов к решению задач многокритериальной оптимизации:
1. Метод уступок – лицо, принимающее решения подводится к выбору решения путем постепенного ослабления первоначальных требований, как правило, одновременно невыполнимых.
2. Метод идеальной точки – в области допустимых значений неизвестных ищется такая их совокупность, которая способна обеспечить набор значений критериев, в том или ином смысле ближайший к наилучшему варианту.
3. Метод свертывая – лицо, принимающее решения сводит многокритериальную задачу к задаче с одним критерием.
Ниже, рассмотрим подробно этих методов решения задачи многокритериальной оптимизации [33,46,48,51].
2.1. Метод последовательных уступок
Метод последовательных уступок решения многокритериальных задач применяется в случае, когда частные критерии могут быть упорядочены в порядке убывающей важности [51]. Предположим, что все критерии максимизируются и пронумерованы в порядке убывания их важности. Вначале определяется максимальное значение Z_1^*, первого по важности критерия в области допустимых решений, решив задачу Z_1 (x)>max, при x?Q.
Затем назначается, исходя из практических соображений и принятой точности, величина допустимого отклонения ?_1>0 (экономически оправданной уступки) критерия Z_1 и отыскивается максимальное значение второго критерия Z_2при условии, что значение первого должно отклоняться от максимального не более чем на величину допустимой уступки, т.е. решается задача
Z_2 (x)>max,
Z_1 (x)?Z_1^*-?_1,
при x?Q.
Снова назначается величина уступки ?_2>0 по второму критерию, которая вместе с первой используется при нахождении условного экстремума третьего частного критерия и т.д. Наконец, выявляется экстремальное значение последнего по важности критерия Z_2 при условии, что значение каждого из первых m-1 частных критериев отличается от экстремального не более чем на величину допустимой уступки. Получаемое на последнем этапе решение считается оптимальным.
Существенным недостатком метода последовательных уступок является то, что решение, полученное этим методом, может оказаться неоптимальным по Парето [37].
Рассмотрим пример, математическая модель трехкритериальной задачи имеет вид [51]:
¦(Z_1=?2x?_1+x_2-?3x?_3>max;@Z_2=x_1+?3x?_2-?2x?_3>min;@Z_3=?-x?_1+?2x?_2+?4x?_3>max;)
{-(x_1+?3x?_2+?2x?_3?1;@?2x?_1-x_2+x_3?16;@x_1+?2x?_2?24;) +
x_n?0.
Уступка по первому критерию ?_1=4, а по второму ?_2=5.
Решение:
Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные x_1,x_2,x_3. Для этого в ячейку А2 вводим подпись «Переменные», а соседние три ячейки В2, С2 и D2 вводим значения переменных. Это могут быть произвольные числа, например единицы или нули, далее они будут оптимизироваться.
рис. 2.1. Определение переменных значений
В третьей строке задаем целевые функции. В А3 вводим подпись «Целевые», а в В3 формулой «=2*B2+C2-3*D2» задаем первую целевую функцию Z_1=?2x?_1+x_2-?3x?_3>max. Аналогично в С3 и D3 вводим вторую Z_2=x_1+?3x?_2-?2x?_3>min и третью Z_3=?-x?_1+?2x?_2+?4x?_3>max целевую функцию, вводя в С3 «=B2+3*C2-2*D2», а в D3 «=-B2+2*C2+4*D2».
рис.2.2. Определение целевых значений
Ячейка А5 будем называть «Ограничения».
{-(x_1+?3x?_2+?2x?_3?1;@?2x?_1-x_2+x_3?16;@x_1+?2x?_2?24;) +
Левые части ограничений распишем от B5:D7, правые части записываем в диапазон F5:F7. Вводим в Е5 формулу «=B5*$B$2+C5*$C$2+D5*$D$2», номера столбцов и номера строк ряда переменных зафиксировано, далее воспользуемся автозаполнением, чтобы заполнить ячейки Е6 и Е7.
рис.2.3. Определение ограничений
Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Данные».
На первом этапе оптимизируем первую целевую функцию. После открытия окна «Поиск решения» в поле «Оптимизировать целевую функцию» ставим курсор и делаем ссылку на ячейку «В3», щелкая по ней мышью. В окне появится $B$3. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Максимум».
