Размещено на http://www.allbest.ru/

Оглавление

• Перечень условных обозначений, символов, сокращений и терминов
• Введение
• Раздел 1. Линейная оптимизация
• 1.1 Линейное программирование
• 1.2 Многокритериальная оптимизация
• Раздел 2. Методы решения задачи многокритериальной оптимизации
• 2.1 Метод последовательных уступок
• 2.2 Метод главного критерия
• 2.3 Метод свертывания критериев
• Раздел 3. Применение MATLAB и Excel для решения задач многокритериальной оптимизации
• 3.1 Пакет MATLAB
• 3.1.2 Toolboxes и его виды
• 3.1.3 Реализация генетического алгоритма в пакете MATLAB
• 3.2 Решение экономической модели с помощью инструмента MATLAB
• 3.3 Решение экономической задачи многокритериальной оптимизации с помощью MS Excel
• 3.3.1 Метод последовательных уступок
• 3.3.2 Метод главного критерия
• 3.3.3 Метод свертка критериев
• 3.4 Анализ полученных результатов
• Заключение
• Список использованной литературы
• Приложения

Перечень условных обозначений, символов, сокращений и терминов

ГА	Генетический алгоритм
ЛП	Линейное программирование
МО	Многокритериальная оптимизация
ЭВМ	Электронно-вычислительные машины
fitnessfun	Fitness function (функция полезности)
fun	Векторная функция векторного аргумента
gamultiobj	Multiobjective optimization using Genetic Algorithm
lb	lower (нижние границы)
MATLAB	Matrix Laboratory
max	Максимизация
min	Минимизация
MS Excel	Microsoft Excel
ub	upper (верхние границы)

Введение

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

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

Предмет исследования - оптимизация производства по выпуску продукции на основе математико-экономической модели косметического предприятия Nature Republic.

Объект исследования - оптимизация производства по выпуску продукции на предприятии.

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

Для достижения цели дипломной работы поставлены следующие задачи:

- рассмотреть основные понятия, принципы, структуру и особенности многокритериальной оптимизации линейного программирования;

- исследовать систему производства на исследуемом предприятии;

- оптимизировать задачу о производстве на основе изученных методов и с помощью инструментального пакета MATLAB;

- на основе данных анализа, разработать практические рекомендации по оптимизации производства предприятии Nature Republic.

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

Исследование проводилось на основе системно-функционального, комплексного научных подходов, с помощью научных методов: свертывания критериев, главного критерия, последовательных уступок.

Данная дипломная работа посвящена изучению методов оптимизации и практическому применению пакетов оптимизации для решения задач многокритериальной линейной оптимизации.

Раздел 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 неизвестными:

(1.1)

где все неизвестные могут принимать только неотрицательные значения:

(1.2)

и линейная функция от тех же переменных

(1.3)

называемая целевой функцией.

Требуется среди всех решений системы уравнений в (1.1) найти такое неотрицательное решение, при котором целевая функция в формуле (1.3) принимает наибольшее возможное значение.

Любое неотрицательное решение системы уравнений в (1.1) называют допустимым решением, а то допустимое решение, при котором целевая функция в (1.3) принимает наименьшее значение, называют оптимальным решением задачи линейного программирования в формулах (1.1)-(1.3). Кратко задачу формулируют так: найти вектор , минимизирующий целевую функцию в (1.3) при линейных ограничениях в (1.1) и (1.2).

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

(1.4)

так как если функция -Z принимает наибольшее значение при некоторых значениях переменных, то при тех же значениях переменных функция Z примет наименьшее возможное значение [33,47,48].

1.2 Многокритериальная оптимизация

Методы решения задач линейного программирования с одним критерием интенсивно разрабатывались в течение нескольких десятков лет. Но вскоре, по мере развития информатики и технологии, до сегодняшнего дня, можно с уверенностью сказать, что любая серьезная проблема характеризуется больше чем одним критерием. Можно понять, что задачи многокритериальной оптимизации (МО) возникают в тех случаях, когда имеется несколько целей, которые не могут быть отражены одним критерием (например, стоимость, надежность и т. п.). Лица, принимающие решения (ЛПР), в значительно большей степени, чем когда-либо, ощущают необходимость оценивать альтернативные решения с точки зрения нескольких критериев [28,51].

Результаты исследования задач планирования и управления показывают, что в реальной постановке эти задачи являются многокритериальными. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т.д. [51].

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

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

1. Разработка концепции оптимальности.

2. Доказательство существования решения, оптимального в соответствующем смысле.

3. Разработка методов нахождения оптимального решения.

Обозначим i-й частный критерий через , а область допустимых решений через 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]. Предположим, что все критерии максимизируются и пронумерованы в порядке убывания их важности. Вначале определяется максимальное значение , первого по важности критерия в области допустимых решений, решив задачу

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

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

Существенным недостатком метода последовательных уступок является то, что решение, полученное этим методом, может оказаться неоптимальным по Парето [37].

Рассмотрим пример, математическая модель трехкритериальной задачи имеет вид [51]:

Уступка по первому критерию , а по второму .

Решение:

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные . Для этого в ячейку А2 вводим подпись «Переменные», а соседние три ячейки В2, С2 и D2 вводим значения переменных. Это могут быть произвольные числа, например единицы или нули, далее они будут оптимизироваться.

рис. 2.1. Определение переменных значений

В третьей строке задаем целевые функции. В А3 вводим подпись «Целевые», а в В3 формулой «=2*B2+C2-3*D2» задаем первую целевую функцию . Аналогично в С3 и D3 вводим вторую и третью целевую функцию, вводя в С3 «=B2+3*C2-2*D2», а в D3 «=-B2+2*C2+4*D2».

рис.2.2. Определение целевых значений

Ячейка А5 будем называть «Ограничения».

Левые части ограничений распишем от B5:D7, правые части записываем в диапазон F5:F7. Вводим в Е5 формулу «=B5*$B$2+C5*$C$2+D5*$D$2», номера столбцов и номера строк ряда переменных зафиксировано, далее воспользуемся автозаполнением, чтобы заполнить ячейки Е6 и Е7.

рис.2.3. Определение ограничений

Предварительные действия завершены. Вызываем надстройку «Поиск решения» в меню «Данные».

На первом этапе оптимизируем первую целевую функцию. После открытия окна «Поиск решения» в поле «Оптимизировать целевую функцию» ставим курсор и делаем ссылку на ячейку «В3», щелкая по ней мышью. В окне появится $B$3. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Максимум».

После ставим курсор в поле «Изменяя ячейки переменных» и обводим ячейки с переменными В2, С2 и D2, выделяя ячейки с переменными. В поле появиться $B$2:$D$2.

В нижней части окна находится поле «Ограничения». Для того, чтобы ввести ограничения, нажимаем кнопку «Добавить», откроется окно «Добавление ограничения». В левом поле «Ссылка на ячейки» вводят ссылку на левую часть первого ограничения - ячейку «Е5», в центральном окне определяем знак «» и в правом «Ограничения» выбираем соответствующую правую часть первого ограничения - «F5». Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить», вводим «E6» «» и «F6». Вновь нажимаем «Добавить», вводим «E7» «?» и «F7».

Для ввода дополнительных ограничений вновь нажимаем «Добавить», ставим курсор в левое поле и обводим ячейки В2, С2 и D2 (результат $B$2:$D$2) в среднем окне ставим «» и в правом число 0.

рис. 2.4. Параметры поиска решения

Далее выбираем метод решения «Поиск решения линейных задач симплекс-методом». Для запуска вычислений нажимаем кнопку «Найти решение». Появляется надпись, что решение найдено.

Выбираем «Сохранить найденное решение» и «ОК» видим результат. В ячейках В2, С2 и D2 видны значения переменных соответствующие оптимальному решению: 11,2; 6,4 и 0. В ячейки В3 - значение целевой функции 28,8.

рис.2.5. Результат полученного решения

На втором этапе оптимизируется вторая целевая функция. Однако, первую, в соответствие с методом последовательных уступок, можно ухудшить первый критерий на величину не более, чем . По этой причине, на втором шаге, значения в ячейке В3 (где хранится первая целевая функция, которая максимизируется) может быть значение, не меньшее, чем 24,8 (=28,8-4). Для удобства, можно записать «Уступок» в сторонке.

Вызываем надстройку «Поиск решения», видно, что все прежние данные остались введенными. Меняем ссылку на целевую функцию. Ставим курсор в поле «Оптимизировать целевую функцию» и щелкаем по ячейке С3, в которой находится ссылка на вторую целевую функцию. Так, как вторая целевая минимизируется, то ставим флажок в поле напротив надписи «Минимум». Вводим дополнительное ограничение, связанное с уступкой по первому критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить», правее поля. В появившемся окне «Добавление ограничения» в трех окнах (слева на право) вводим данные «В3», «?», «С9».

Результат - переменные равны 10,2; 4,4; 0. Вторая целевая функция равна 23,4 (ячейка С3). Первая равна своему минимальному значению 24,8 (ячейка В3).

На третьем этапе делаем уступку по второму критерию. Величина уступки равна . Так, как вторая функция минимизируется, то ее значение не должно превышать 23,4+5=28,4. Вызываем надстройку «Поиск решения». Меняем ссылку на целевую функцию. Ставим курсор в поле «Оптимизировать целевую функцию» и щелкаем по ячейке D3, в которой находится ссылка на третью целевую функцию. Так, как третья целевая максимизируется, то ставим флажок в поле напротив надписи «Максимум». Вводим дополнительное ограничение, связанное с уступкой по второму критерию. Переводим курсор в поле «Ограничения» и нажимаем кнопку «Добавить». В появившемся окне «Добавление ограничения», вводим данные «С3», «?», «С10».

рис.2.6. Определение уступка

Результат - переменные равны 10,76; 6,62; 1,11. Целевые функции равны, соответственно, 24,8; 28,4 и 6,93. Это окончательный ответ. Все дополнительные условия соблюдены.

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

2.2 Метод главного критерия

Этот метод предполагает сведения задачи многокритериальной оптимизации к однокритериальной оптимизации. Для этого выбираем один из рассматриваемых критериев в качестве главного критерия, а остальные преобразовываются в ограничения [21].

В качестве главного критерия в различных областях часто выбирают:

1. Себестоимость

2. Объем производства

3. Производительность

4. Ресурсоемкость (металлоемкость, энергоемкость,...)

5. Сроки выполнения работы и др.

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

(2.6)

При этом все значении Х должны принадлежать рассматриваемому допустимому множеству. Наиболее часто этот способ употребляется в инженерной практике.

Преимущества метода главного критерия относятся простота интерпретации результатов, отсутствия высоких требований к математической подготовке экспертов, программному обеспечению и вычислительным средствам [51]. После того, как мы сведем задачу многокритериальной оптимизации к задаче однокритериальной оптимизации, мы получаем возможность использовать стандартные программные средства, в частности, такие как поиск решения в Microsoft Excel.

К основным недостатком метода относятся:

1) чрезмерное упрощение структуры задач;

2) не всегда можно выделить ярко выраженный главный критерий, иногда это сделать трудно или вообще нельзя;

3) возможность потери эффекта совокупного влияния нескольких второстепенных критериев;

4) ограничения для остальных критериев должны быть обоснованными, а не взяты кое-как;

5) возможность получения неэффективных решений;

6) даже если есть критерий, который гораздо важнее любого другого, то не факт, что в сумме остальные критерии не окажутся весьма значимыми. Особо ярко это может проявляться в задачах, где n велико [21,25,30,33,46].

В методе главного критерия, если задача имеет единственное допустимое решение, то оно является эффективным по Парето. Если же задача имеет более чем одно допустимое решение, то множество этих решений содержит эффективные по Парето решения [37,45,48,51]. Но оно также может содержать и слабо эффективные решения.

В связи с этим процедура поиска решения в общем случае включает два этапа:

1) нахождение множества допустимых решений;

2) выбор некоторого эффективного по Парето решения.

На практике, критерии очень часто имеют различные масштабы и шкал измерения, и тогда возникает необходимость нормировки этих критериев.

Нормировка критериев

Для приведения критериев к сопоставимому виду и обеспечения их эквивалентности используется нормировка:

(2.7)

при (2.8)

От значения критерия отнимаем минимальное значение этого критерия и делим полученную разность на разность между максимальным и минимальным значениями этого критерия [51]. Предполагается при этом, что минимальное и максимальное значение не совпадают. При такой нормировке, все нормированные значение будут лежать в интервале [0;1].

Рассмотрим в качестве примера такую задачу, предполагается, что необходимо организовать рекламную компанию по продвижению нового товара. Для этого могут быть использованы альтернативы . Критерии оптимальности - минимум затрат на рекламу, максимум доли рынка и объема продаж в течении заданного периода времени. - реклама, - доля рынка, - объем продаж.

Исходные данные записываются таким образом:

Рис. 2.8. Таблица исходных данных

Прежде чем решить задачу, нужно провести нормировку критериев. В качестве главного критерия берем критерию - затраты за рекламу, а критерия и превратим в ограничения. Поэтому для нормировки мы можем ограничиться только критериями и . Для второго критерия, минимальное значение будет 15, а максимальное - 35. Для третьего соответственно 50 и 75. В качестве примера, можно посчитать нормированное значение второго критерия для первой альтернативы:

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

рис.2.9. Нормировка критериев

Выберем такое ограничение, что частные критерия и должны быть не меньше 0,7 умноженное на максимальное значение этих критериев: .

рис. 2.10. Окончательный результат решения по методу главного критерия

Тогда этим ограничениям для критерия удовлетворяет альтернативы и . А для критерия альтернативы и . Единственная альтернатива, которая одновременно удовлетворяет ограничением по критерию и по критерию это альтернатива , которая в данном случае и выбирается в качестве оптимального решения.

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

2.3 Метод свертывания критериев

Метод свертывания критериев предполагает преобразование набора имеющихся частных критериев в один суперкритерий.

(2.8)

Т.е. мы получаем новый суперкритерий F, который является функций от частных критериев . В общем случае, функцию называют сверткой частных критериев [46,48,51].

К основным этапом свертывания относятся:

1. Обоснование допустимости свертки

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

- показатели результативности;

- показатели ресурсоемкости;

- показатели оперативности.

Критерии, которые мы сворачиваем, должны относиться к одной и той же группе, нельзя сворачивать критерии, которые относятся, например, один из них к показателям оперативности, а другой к показателям результативности. Т.е. для каждой группы свертывание частных критериев следует выполнять отдельно. При нарушении этого принципа теряется смысл критерия [30,33,51].

2. Нормировка критериев

Правила нормализации критериев, мы рассматривали ранее в предыдущем разделе.

3. Учет приоритетов критериев

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

4. Построение функции свертки

Для свертывания критериев, используют такие основные типы функций:

- Аддитивные функции свертки;

- Мультипликативные;

- Агрегированные, а также могут быть другие варианты сверток.

Аддитивная свертка

Аддитивную свертку критериев можно рассматривать как реализацию принципа справедливой компенсации абсолютных значений нормированных частных критериев [25,30,51]. В этом случае, суперкритерий обычно строятся как взвешенная сумма частных критериев

 (2.9)

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

Таблица 2.1. Таблица относительной важности критериев

	Относительная важность
1	Равная важность сравниваемых требований
3	Умеренное (слабое) превосходство одного над другим
5	Сильное (существенное) превосходство
7	Очевидное превосходство
8	Абсолютное (подавляющее) превосходство
2, 4, 6, 8	Промежуточные решения между двумя соседними оценками

Мультипликативная свертка

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

При использовании мультипликативных критериев не требуется нормировка частных критериев, и это является их преимуществом [30,33,45,46,48].

Выбор между аддитивными и мультипликативными критериями определяется важностью учета абсолютных или относительных изменений значений частных критериев.

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

(2.10)

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

Если первые m показателей надо увеличить, а остальные - уменьшить, то используют функцию агрегирования вида:

(2.11)

В числители находятся произведение тех критериев, значение которых нам надо максимизировать, а в знаменателе находятся произведение тех критериев, значение которых нам надо минимизировать. И поэтому мы получаем новый критерий, который нам надо будет максимизировать [1,6,9,48,51].

Методы свертывания критериев широко используются в решение задач многокритериальной оптимизации. Однако они имеют также проблемы и недостатки. В частности трудно обосновать выбор метода свертывания критериев, а от выбора метода часто зависит получаемый результат. Другим недостатком является трудность обоснование выбора весовых коэффициентов, часто для этого привлекается эксперты, проводятся опросы, потом обрабатываются полученные результаты, однако это требует много времени и затраты других ресурсов. Еще одна проблема связана с тем, что эти методы, как правила дает возможность компенсировать малые значения одних критериев большими значениями других, что часто бывает неприемлемо для конкретных решений [8,16,21,25].

Рассмотрим в качестве примера такую задачу:

Перед тем как преобразовывать эти критерии в 1, мы должны привести их в однородном состоянии. Т.е. в данном случае нужно максимизировать f2> f2' = -f2. И тогда получим: . После этого суммируем частных критериев в один, и можем дальше решить задачу обычным путем .

Также нужно учитывать и весовые коэффициенты, при этом их сумма должна быть = 1, и каждый из весовых коэффициентов должен быть неотрицательной величиной. Весовые коэффициенты распределяется по важности этих самих частных критериев . В данном случае, весовые коэффициенты будут распределяться следующим образом: 0,5; 0,2; 0,3.

После подсчета вместе с весовыми коэффициентами, мы получим целевую функцию такого вида: или .

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные . Для этого в ячейку А3 вводим подпись «Переменные», а соседние три ячейки В2, С2 и D2 вводим значения переменных. Это могут быть произвольные числа, например единицы или нули, далее они будут оптимизироваться. В нашем случае это единицы.

рис.2.11. Определение переменных, целевых и ограничений

В четвертой строке задаем целевую функцию. В А4 вводим подпись «Целевая», а в В4, С4, D4 наши значения.

Дальше, в ячейку F4 вводим формулу «=B4*B3+C4*C3+D4*D3», таким образом, задаем целевую функцию .

В ячейку F6, F7 и F8 вводим формулы

«=B6*$B$3+C6*$C$3+D6*$D$3», «=B7*$B$3+C7*$C$3+D7*$D$3», «=B8*$B$3+C8*$C$3+D8*$D$3»

соответственно.

После открытия окна «Поиск решения» в поле «Оптимизировать целевую функцию» ставим курсор и делаем ссылку на ячейку «F4». В окне появится $F$4. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Максимум».

После ставим курсор в поле «Изменяя ячейки переменных» и обводим ячейки с переменными В3, С3 и D3, выделяя ячейки с переменными. В поле появиться $B$3:$D$3.

В нижней части окна находится поле «Ограничения». Добавляем все необходимые ограничения, «F6» «» «F6», «F7:F8» «?» и «G7:G8».

Вводим дополнительное ограничение , и получим следующую формулу «B3:D3», «», «0».

рис.2.12. Параметры поиска решения

Далее выбираем метод решения «Поиск решения линейных задач симплекс-методом». Для запуска вычислений нажимаем кнопку «Найти решение». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и «ОК» видим результат.

рис.2.13. Окончательный результат решения по методу свертывания критериев

Существующие методы предназначены в основном для сравнения заданных альтернатив и выбора лучшей из них. Довольно часто критерии, по которым оцениваются альтернативы, противоречивы, для них используются разные методы и шкалы оценок.

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

matlab excel оптимизация экономический

Раздел 3. Применение MATLAB И Excel для решения задач многокритериальной оптимизации

3.1 Пакет MATLAB

Современная компьютерная математика предлагает целый набор интегрированных программных систем и пакетов программ для автоматизации математических расчетов: MATLAB, Eureka, Gauss, TK Solver!, Derive, Mathcad, Mathematica, Maple V и др. Среди них, MATLAB занимает одно из лидирующих мест.

MATLAB -- одна из старейших, тщательно проработанных и проверенных временем систем автоматизации математических расчетов, построенная на расширенном представлении и применении матричных операций. Это нашло отражение в названии системы -- MATrix LABoratory -- матричная лаборатория [14].

MATLAB является важным инструментом для решения широкого спектра научных и прикладных задач, в таких областях как: моделирование объектов и разработка систем управления, проектирование коммуникационных систем, обработка сигналов и изображений, измерение сигналов и тестирование, финансовое моделирование, вычислительная биология и для многокритериальной оптимизации в том числе [10,23].

В настоящее время MATLAB далеко вышла за пределы специализированной матричной системы и стала одной из наиболее мощных универсальных интегрированных инструментов. Слово «интегрированная» указывает на то, что в этой системе объединены удобная оболочка, редактор выражений и текстовых комментариев, вычислитель и графический программный процессор. В новой версии используются такие мощные типы данных, как многомерные массивы, массивы ячеек, массивы структур, массивы Java и разреженные матрицы, что открывает возможности применения системы при создании и отладке новых алгоритмов матричных и основанных на них параллельных вычислений и крупных баз данных [24,31,35].

В целом MATLAB -- это уникальная коллекция реализаций современных численных методов компьютерной математики, созданных за последние три десятка лет. Она вобрала в себя и опыт, правила и методы математических вычислений, накопленные за тысячи лет развития математики. Это сочетается с мощными средствами графической визуализации и даже анимационной графики. Систему с прилагаемой к ней обширной документацией вполне можно рассматривать как фундаментальный многотомный электронный справочник по математическому обеспечению ЭВМ -- от массовых персональных компьютеров до супер-ЭВМ [38,54].

MATLAB представляет собой основу всего семейства продуктов MathWorks и является главным инструментом для решения широкого спектра научных и прикладных задач, в таких областях как:

1) Математические расчеты;

2) Разработка алгоритмов;

3) Моделирование;

4) Анализ данных и визуализация;

5) Научная и инженерная графика;

6) Разработка приложений, включая графический интерфейс пользователя.

MATLAB развивался в течение нескольких лет, ориентируясь на различных пользователей. В университетской среде, он представлял собой стандартный инструмент для работы в различных областях математики, машиностроении и науки. В промышленности, MATLAB - это инструмент для высокопродуктивных исследований, разработок и анализа данных [55].

В MATLAB важная роль отводится специализированным группам программ, называемых Toolboxes. Они очень важны для большинства пользователей MATLAB, так как позволяют изучать и применять специализированные методы. Это своего рода пакет расширения, позволяющее быстро ориентировать систему на решение задач в той или иной предметной области: в специальных разделах математики, в физике и в астрономии, в области нейронных сетей и средств телекоммуникаций, а так же в математическом моделировании [38,54,55].

Этот пакет подходит для анализа многокритериальных экономических задач линейного программирования. Тщательно рассмотрим систему MATLAB и ее пакеты расширения.

Основные компоненты MATLAB

Система MATLAB состоит из пяти основных частей:

1. Язык MATLAB. Это язык матриц и массивов высокого уровня с управлением потоками, функциями, структурами данных, вводом-выводом и особенностями объектно-ориентированного программирования. Это позволяет как программировать в “небольшом масштабе” для быстрого создания черновых программ, так и в “большом” для создания больших и сложных приложений.

2. Среда MATLAB. Это набор инструментов и приспособлений, с которыми работает пользователь или программист MATLAB. Она включает в себя средства для управления переменными в рабочем пространстве MATLAB, вводом и выводом данных, а также создания, контроля и отладки М-файлов и приложений MATLAB.

3. Управляемая графика. Это графическая система MATLAB, которая включает в себя команды высокого уровня для визуализации двух- и трехмерных данных, обработки изображений, анимации и иллюстрированной графики. Она также включает в себя команды низкого уровня, позволяющие полностью редактировать внешний вид графики, также как при создании Графического Пользовательского Интерфейса (GUI) для MATLAB приложений.

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

5. Программный интерфейс. Это библиотека, которая позволяет писать программы на Си и Фортране, которые взаимодействуют с MATLAB. Она включает средства для вызова программ из MATLAB(динамическая связь), вызывая MATLAB как вычислительный инструмент и для чтения-записи МАТ-файлов [13,14,38,54].

3.1.2 Toolboxes и его виды

Toolboxes - это дополнительные специализированные пакеты MATLAB.

Виды Toolboxes:

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

2. Control System Toolbox - это пакет расширения для анализа, проектирования и разработки систем автоматического управления. Включает в себя всевозможные функции и графические приложения для работы с динамическими объектами и линейными замкнутыми системами управления.

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

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

5. Fuzzy Logic Toolbox - содержит инструменты для проектирования систем нечеткой логики. Пакет позволят создавать экспертные системы на основе нечеткой логики, проводить кластеризацию нечеткими алгоритмами, а также проектировать нечеткие нейросети.

6. Higher-Order Spectral Analysis содержит специальные алгоритмы для анализа сигналов с использованием моментов высшего порядка. Пакет предоставляет широкие возможности для анализа негауссовых сигналов, так как содержит алгоритмы, пожалуй, самых передовых методов для анализа и обработки сигналов.

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