Методы и задачи дискретного и линейного программирования

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Брянский государственный технический университет

Кафедра «Компьютерные технологии и системы»

Дисциплина: «Управление в социально-экономических системах»

Семестровая работа

Реферат по дисциплине:

«Управление в социальных и экономических системах»

Студент гр. 14Ин (мг):

Хотмиров В.В.

Преподаватель:

Лозбинев Ф.Ю.

Брянск 2015г



Оглавление

дискретный линейный программирование решение

• Вопрос 9. Вычислительная техника и программные средства в управлении социально-экономических систем
• Вопрос 20. Методы и задачи дискретного программирования. Задачи целочисленного программирования. Методы отсечения Гомори. Метод ветвей и границ. Задача о назначениях. Венгерский алгоритм
• Вопрос 25. Методы многокритериальной оценки альтернатив. Классификация методов. Множества компромиссов и согласия, построение множеств. Функция полезности. Аксиоматические методы многокритериальной оценки. Прямые методы многокритериальной оценки альтернатив. Методы нормализации критериев. Характеристики приоритета критериев. Постулируемые принципы оптимальности (равномерности, справедливой уступки, главного критерия, лексикографический). Методы аппроксимации функции полезности. Деревья решений. Методы компенсации. Методы аналитической иерархии. Методы порогов несравнимости. Диалоговые методы принятия решений. Качественные методы принятия решений (вербальный анализ)
• Вопрос 16. Задачи линейного программирования. Постановка и геометрическая интерпретация задач линейного программирования. Методы линейного программирования. Прямые и двойственные задачи математического программирования. Симплекс-метод. Многокритериальные задачи линейного программирования
• Список литературы

• Вопрос 9. Вычислительная техника и программные средства в управлении социально-экономических систем
• Введение
• В основу настоящей программы положены следующие дисциплины: математическая экономика; статистические методы прогнозирования в экономике; финансовый менеджмент; системный анализ и исследование операций; теория и методы принятия решений; теория управления; математическое программирование; дискретная оптимизация; информационные системы и технологии.
• Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по управлению, вычислительной технике и информатике при участии Института проблем управления РАН, Института системного анализа РАН, Московского государственного института стали и сплавов и Воронежского государственного технического университета.
• 1. Общие вопросы теории управления социально-экономическими системами
• Предмет теории управления. Управленческие отношения и понятие организационного управления. Цели управления. Дерево целей. Специфика работы с целевой информацией. Критерии эффективности и ограничения при достижении цели. Управление в сложных системах. Понятие обратной связи и ее роль в управлении. Формализация и постановка задач управления. Основные структуры и методы управления социально-экономическими системами: административно-организационные, экономические, социально-психологические и др. Специфика управления социальными и экономическими системами. Математическое и имитационное моделирование. Роль человека в управлении социальными и экономическими системами.
• Системный подход к решению социальных и экономических проблем управления. Основные понятия системного подхода: система, элемент, структура, среда. Свойства системы: целостность и членимость, связность, структура, организация и самоорганизация, интегрированные качества. Организация как система. Основные понятия социологии организаций и социальной психологии: власть, лидерство, коммуникации, авторитет, стили руководства.
• Понятие функций управления и их классификация, общие и специфические функции, стратегическое планирование в организационных системах управления, тактическое и оперативное планирование, оперативное управление, организация и информационное взаимодействие, модели и методы принятия решений, принятие решений в условиях риска и неопределенности, использование экспертных оценок при принятии решений, консультационная деятельность при принятии решений, психологические аспекты принятия и реализации решений, особенности коллективного принятия решений, особенности принятия решений в условиях чрезвычайных ситуаций, переговоры и выборы, личность и коллектив как объекты управления.
• Общество как социально-экономическая система. Социальная структура общества, социальные институты, их функции и взаимодействие. Связь социальных и экономических аспектов управления. Принципы и критерии формирования структур управления в социально-экономических системах. Основные типы организационных структур (линейные, функциональные, комбинированные, матричные), их эволюция и развитие. Особенности формирования программно-целевых структур управления на различных уровнях иерархии.
• 2. Информационные технологии в системах управления социально-экономическими системами
• Понятие информации, ее свойства и характеристики, особенности использования информации о состоянии внешней среды и объекта управления в организационных системах управления с обратной связью; особенности создания и использования информационного обеспечения систем организационного управления, информационное обеспечение в условиях чрезвычайных ситуаций.
• Понятие эффективности управления. Методы оценки деятельности и эффективности управления. Задачи анализа и синтеза механизмов функционирования и управления социально-экономическими системами.
• Методы получения и обработки информации для задач управления, экспертные процедуры и процедуры прогнозирования.
• Подготовка и принятие управленческих решений. Автоматизированные системы поддержки принятия управленческих решений.
• Вычислительная техника и программные средства в управлении социально-экономическими системами.
• Метод моделирования и его использование в исследовании и проектировании систем управления. Понятие модели, классификация моделей. Границы и возможности формализации процедур управления социальными и экономическими системами. Модели систем: статические, динамические, концептуальные, топологические, формализованные (процедуры формализации моделей систем), информационные, логико-лингвистические, семантические, теоретико-множественные и др.
• Экономико-математические методы и модели. Производственные функции. Модели Леонтьева, Эрроу--Дербе, Неймана--Гейла и др.
• Принципы, модели, методы и средства проектирования и развития организационных систем.
• Управление в сложных системах, обратная связь и ее роль в управлении, энтропия и информация как характеристики разнообразия и управления, принцип необходимого разнообразия, индивидуальное и типовое проектирование организационных систем, алгоритмизация задач управления и обработки данных, представление знаний, проектирование систем обработки данных в организационных системах, информационное обеспечение организационных систем, информационные языки и классификаторы, программное обеспечение организационных систем, его особенности, резервирование программных модулей и информационных массивов, защита информации.
• 3. Математические основы, модели и методы управления социально-экономическими системами
• Методы исследования операций и область их применения для решения задач управления социально-экономическими системами. Характеристика основных задач исследования операций, связанных с теорией массового обслуживания, теорией очередей и управлением запасами.
• Постановка задач математического программирования. Оптимизационный подход к проблемам управления социально-экономическими системами. Допустимое множество и целевая функция. Формы записи задач математического программирования. Классификация задач математического программирования.
• Задачи линейного программирования. Постановка и геометрическая интерпретация задач линейного программирования. Методы линейного программирования. Прямые и двойственные задачи математического программирования. Симплекс-метод. Многокритериальные задачи линейного программирования.
• Модели и численные методы безусловной оптимизации. Классификация методов безусловной оптимизации. Скорости сходимости. Методы первого порядка. Градиентные методы. Метод Ньютона и его модификации. Квазиньютоновские методы. Конечно-разностные методы. Методы нулевого порядка: методы покоординатного спуска, Хука--Дживса, сопряженных направлений, методы деформируемых конфигураций, симплексные методы.
• Нелинейные задачи математического программирования. Локальный и глобальный экстремум, условия оптимальности, условия Куна--Таккера. Задачи об условном экстремуме и метод множителей Лагранжа. Методы проектирования. Метод проекции градиента. Метод условного градиента. Методы сведения задач с ограничениями к задачам безусловной оптимизации. Методы внешних и внутренних штрафных функций. Комбинированный метод проектирования и штрафных функций. Метод зеркальных построений. Метод скользящего допуска.
• Задачи стохастического программирования. Стохастические квазиградиентные методы. Методы стохастической аппроксимации. Методы с операцией усреднения. Методы случайного поиска. Стохастические задачи с ограничениями вероятностной природы. Стохастические разностные методы.
• Методы и задачи дискретного программирования. Задачи целочисленного линейного программирования. Методы отсечения Гомори. Метод ветвей и границ. Задача о назначениях. Венгерский алгоритм.
• Основы теории графов: определение графа, цепи, циклы, пути, контуры. Связные и сильно связные графы. Матрица смежности графа. Матрица инцинденций дуг и ребер графов. Деревья. Плоские графы. Кратчайшие пути и контуры. Алгоритмы Форда и Данцига. Циркуляция максимальной величины и потенциалы перестановок. Поток максимальной величины. Алгоритм Форда--Фалкерсона. Задачи распределения ресурса на сетях и графах.
• Метод динамического программирования для многошаговых задач принятия решений. Принцип оптимальности Беллмана. Основное функциональное уравнение. Вычислительная схема метода динамического программирования.
• Предмет и основные понятия теории игр. Применение теории игр для оптимизации управленческих решений. Понятие стратегии и решения игры. Равновесия: в доминантных стратегиях, максиминное, Нэша, Байеса, Штакельберга. Матричные игры. Игры с непротиворечивыми интересами. Кооперативные игры.
• Постановка задач принятия решений. Этапы решения задач. Экспертные процедуры. Методы получения экспертной информации. Шкалы измерений, методы экспертных измерений. Методы опроса экспертов, характеристики экспертов. Методы обработки экспертной информации, оценка согласованности мнений экспертов.
• Методы многокритериальной оценки альтернатив. Классификация методов. Множества компромиссов и согласия, построение множеств. Функция полезности. Аксиоматические методы многокритериальной оценки. Прямые методы многокритериальной оценки альтернатив. Методы нормализации критериев. Характеристики приоритета критериев. Постулируемые принципы оптимальности: равномерности, справедливой уступки, главного критерия, лексикографический. Методы аппроксимации функции полезности. Деревья решений. Методы компенсации. Методы аналитической иерархии. Методы порогов несравнимости. Диалоговые методы принятия решений. Качественные методы принятия решений (вербальный анализ).
• Принятие решений в условиях неопределенности. Виды неопределенности. Статистические модели принятия решений. Критерии Байеса--Лапласа, Гермейера, Бернулли--Лапласа, максиминный (Вальда), минимаксного риска Сэвиджа, Гурвица, Ходжеса--Лемана и др.
• Принятие коллективных решений. Теорема Эрроу и ее анализ. Правила большинства, Кондорсе, Борда. Парадокс Кондорсе. Расстояние в пространстве отношений. Современные концепции группового выбора.
• Модели и методы принятия решений при нечеткой информации. Нечеткие множества. Основные определения и операции над нечеткими множествами. Нечеткое моделирование. Задачи математического программирования при нечетких исходных условиях. Нечеткие отношения, операции над отношениями, свойства отношений. Принятие решений при нечетком отношении предпочтений на множестве альтернатив. Принятие решений при нескольких отношениях предпочтения.
• Социально-экономическое прогнозирование. Задачи, роль и виды прогнозирования, классификация прогнозов по цели прогнозирования, виду объектов прогнозирования, горизонту прогнозирования, масштабности прогнозирования. Оценка надежности прогнозирования. Временные ряды и их анализ. Характеристики динамики социально-экономических явлений. Модели временных рядов, анализ компонентного состава рядов, тренды, критерии и методы выявления трендов. Алгоритмы выделения трендов. Модели кривых роста в социально-экономическом прогнозировании. Основные виды кривых роста, методы их выбора и идентификации параметров. Оценка качества прогнозных моделей. Критерии качества прогнозов. Методы и модели выявления и анализа периодических колебаний в динамических рядах. Статистические методы, фильтрация и анализ спектров. Адаптивные модели и методы прогнозирования. Особенности адаптивных моделей, их виды, методы построения. Модели стационарных и нестационарных временных рядов, их виды и методы построения.
• Основы теории активных систем. Понятия активной системы и механизма функционирования. Механизмы планирования в активных системах. Неманипулируемость процедур планирования. Принцип открытого управления и оптимальность правильных механизмов управления. Механизмы стимулирования в детерминированных активных системах и активных системах с неопределенностью. Согласованность оптимального решения. Базовые механизмы распределения ресурсов, активной экспертизы, конкурсные, многоканальные, противозатратные. Проблемы и методы идентификации организационных систем на основе ретроспективной, текущей и экспертной информации с учетом активности управляемых субъектов. Методы моделирования механизмов функционирования активных систем. Имитационные игры как инструмент исследования организационных механизмов и метод активного обучения.
• Управление проектами. Специфика проектно ориентированных организаций. Цели, задачи и этапы управления проектами. Методы сетевого планирования и управления. Механизмы управления проектами. Стратегическое планирование. Реформирование и реструктуризация предприятий. Модели и механизмы внутрифирменного управления.
• Управление трудовыми ресурсами в организационных системах. Цели и задачи управления, планирование трудовых ресурсов, подбор, подготовка и расстановка кадров, оценка деловых качеств управленческого персонала, использование трудовых ресурсов, стили работы руководства, конфликтные ситуации, требования к кадрам управления в условиях чрезвычайных ситуаций.
• Задачи и методы финансового анализа. Наращение и дисконтирование. Эффективная ставка. Потоки платежей. Финансовая эквивалентность обязательств. Типовые приложения. Кредитные расчеты. Оценка инвестиционных процессов. Отбор инвестиционных проектов. Финансовые расчеты на рынке ценных бумаг. Математические основы финансового анализа в условиях риска и неопределенности. Риски и их измерители. Функция полезности. Задача об оптимальном портфеле ценных бумаг. Модели задач оптимизации рискового портфеля.
• Вопрос 20. Методы и задачи дискретного программирования. Задачи целочисленного программирования. Методы отсечения Гомори. Метод ветвей и границ. Задача о назначениях. Венгерский алгоритм

Многие задачи ИСО, такие, как распределение ресурсов, сетевого планирования и управления, календарного планирования, описываются математическими моделями ДП.

Рассмотрим задачу вида:

Здесь , G- некоторое множество n-мерного пространства . Если множество G является конечным или счетным, то условие (3) - это условие дискретности. В таком случае данная задача является задачей дискретного программирования (ЗДП).

Если вводится ограничение - целые числа, то приходят к задаче целочисленного программирования, которая является частным случаем ЗДП.

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

Если компоненты вектора Х могут принимать только 2 значения-0 или 1, то - задача булевского программирования.

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

Решение соответствующей ЗЛП без требования целочисленности Х*=(0,5; 0; 4,5), а искомое целочисленное решение Х*=(2; 2; 5).

Если множество G конечно, то наиболее простой метод решения задачи состоит в прямом переборе. Суть метода: в любом порядке перебираются множества возможных значений Х и для каждого значения вычисляется значение целевой функции f(Х). Далее находится наибольшее (наименьшее) значение f(Х*), которое будет соответствовать оптимальному решению Х*ОG. Однако в реальных задачах хотя G и конечно, но его размерность бывает очень большой, и такой перебор становится практически невозможным.

Поэтому для решения ЗДП разрабатываются специальные методы, основанные на принципе целенаправленного перебора, которые позволяют сократить полный перебор. Методы решения ЗДП по принципу подхода к проблеме делятся на 3 группы:

1. Методы отсечения, или отсекающих плоскостей

2. Метод ветвей и границ

3. Методы случайного поиска и эвристические методы

1. задачи целочисленного программирования

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

Задачи и методы, относящиеся к перечисленному кругу вопросов, в литературе именуются по-разному. Наибольшее распространение получил термин «целочисленное программирование», однако встречаются и такие как «дискретное программирование», реже «комбинаторное (или диофантово) программирование».

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

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

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

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

1.3. Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или - или», «если - то» и т. п.).

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Приведем примеры целочисленных задач линейного программирования.

Пример. Задача о ранце. Имеется m-вектор ограниченных ресурсов

,

которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз обладает следующими свойствами: 1) неделимостью; 2) полезностью ; 3) расходом i-го ресурса для перевозки единицы j-го груза . Выбрать такой номер груза для перевозки, при котором максимизируется общая полезность рейса (суммарная стоимость перевезенных за рейс грузов).

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

Сопоставление расходов ресурсов каждого типа для транспортировки единицы груза и их наличия приводит к ограничению

Общая полезность рейса определяется значением функции

Частным случаем задачи является задача о ранце, в которой любой из заданного набора предметов может быть выбран или нет. Тогда математическая модель примет следующий вид:

Максимизировать

при условиях

Пример. В области

найти максимум функции

.

Решим задачу геометрически (Рис. 1). Область поиска экстремума - многоугольник OABCD. Так как линия уровня целевой функции параллельна стороне BCмногоугольника, экстремум достигается в вершинах и , а также в любой точке отрезка BC и равен 7. Нас интересуют лишь точки с целочисленными координатами, поэтому ни B, ни C не являются допустимым решением задачи. Округлив значение координат точек B и C, получим точку (4; 3), не принадлежащую области поиска. Легко показать, что целочисленный оптимум достигается в точках M(2; 3) и N(3; 2) и равен 5. Обе точки находятся внутри области поиска.

Рисунок 1

Несостоятельность округления подчеркивается также следующими соображениями. Несмотря на то, что целочисленные переменные обычно выражают количество неделимых предметов, возможны и другие типы спецификации этих переменных. Так в задаче о ранце решение представляется булевой переменной (x = 0 или x = 1). В этом случае бессмысленно оперировать дробными значениями величины x и процедура округления является логически неприемлемой.

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

2. Методы отсечения гомори

Алгоритм метода Гомори для решения полностью целочисленной задачи линейного программирования. Рассмотрим полностью целочисленную задачу линейного программирования:

,

Алгоритм Гомори состоит из следующих этапов.

2.1. Решается ЗЛП с отброшенным условием целочисленности.

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

2.3. Строится дополнительное ограничение, отсекающее часть области, в которой содержится оптимальное решение ЗЛП и не содержитсяни одногодопустимого решения целочисленной задачи.

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

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

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

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

Для лучшего понимания существа вопроса обратимся к наглядной иллюстрации случая п=2. Ограничения задачи определяют на плоскости некоторый многоугольник М, в вершине х*⁽¹⁾ которого, если не учитывать условия целочисленности, достигается максимум целевой функции. Внутри этого многоугольника имеется конечное множество точек, которым соответствуют решения с целочисленными значениями переменных (на рисунке они обозначены кружочками). Три прямые, соответствующие трем дополнительным линейным ограничениям. Каждая из прямых отсекает часть области допустимых решений. Так, после отсечения части области прямой оптимальной оказывается вершина х*⁽²⁾, затем х*⁽³⁾, и, наконец, оптимальной становится целочисленная вершина х*.

Основное в алгоритме - составление дополнительного ограничения, т. е. отсекающей гиперплоскости, которая называется правильным отсечением. Правильное отсечение должно удовлетворять следующим условиям:

1) быть линейным;

2) отсекать найденное оптимальное нецелочисленное решение ЗЛП;

3) не отсекать ни одной из целочисленных точек целочисленной задачи.

3. Метод ветвей и границ

Метод ветвей и границ (англ. branch and bound) -- общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной икомбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Метод ветвей и границ впервые предложили в 1960 году Ленд и Дойг^[1] для решения задач целочисленного программирования.

Общая идея метода может быть описана на примере поиска минимума функции на множестве допустимых значений переменной . Функция и переменная могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти

4. Венгерский метод

Этот метод впервые был предложен венгерским математиком Эгервари в 1931г. Длительное время работа оставалась малоизвестной. В 1953г. Математик Г. Кун перевел эту работу на английский язык, заново открыв её для специалистов, раз вил идеи Эгервари и усовершенствовал метод, который в честь первого автора и был назван венгерским.

Первоначально венгерский метод был применен к задаче выбора.

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

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

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

Введем следующие понятия.

4.1. Нулевые элементы матрицы называются независимыми нулями, если для любого строка и столбец, на пересечении которых расположен элемент , не содержат другие нули (для всех ).

4.2. Две прямоугольные матрицы и называются эквивалентными (~ ), если

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

4.3. Элементы, расположенные в выделенных строках или столбцах, называются выделенными элементами.

Вопрос 25. Методы многокритериальной оценки альтернатив. Классификация методов. Множества компромиссов и согласия, построение множеств. Функция полезности. Аксиоматические методы многокритериальной оценки. Прямые методы многокритериальной оценки альтернатив. Методы нормализации критериев. Характеристики приоритета критериев. Постулируемые принципы оптимальности (равномерности, справедливой уступки, главного критерия, лексикографический). Методы аппроксимации функции полезности. Деревья решений. Методы компенсации. Методы аналитической иерархии. Методы порогов несравнимости. Диалоговые методы принятия решений. Качественные методы принятия решений (вербальный анализ)

Методы многокритериальной оценки альтернатив. Классификация методов.

При применении большинства методов возникают две основные проблемы: как получить оценки по отдельным критериям и как объединить, агрегировать эти оценки в общую оценку полезности альтернативы. В типичном методе принятия решения роли трех участников (или групп участников) - лиц, принимающих решение (ЛПР), экспертов и консультантов - определены следующим образом. Консультанты (иногда вместе с ЛПР) разрабатывают обычно перечень критериев. При этом определяется, как измерять уровень качества по каждому критерию, т. е. как строить шкалу измерений. Чаще всего используют балльные шкалы (от 1 до 10 или от 0 до 1).

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

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

Прямые методы. В них зависимость общей полезности альтернативы от оценок по отдельным критериям известна заранее. Чаще всего используется вид зависимости, при котором определяются численные показатели важности критериев (т. е. их удельный вес), умножаемые на оценки по критериям. Этот метод называется методом «взвешенной суммы оценок критериев». Из других прямых методов необходимо назвать метод «дерева решений». Через просмотр всех вариантов выбора определяются альтернативные варианты решения. Для каждого альтернативного варианта подсчитываются вероятности осуществления, которые умножаются на его ценность в деньгах.

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

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

Аксиоматические методы определяют ряд свойств, которым должна удовлетворять зависимость общей полезности альтернативы от оценок по отдельным критериям. Эти свойства проверяются путем получения информации от ЛПР. В соответствии с этой информацией делается вывод о той или иной форме зависимости.

Человеко-машинные методы применяются в том случае, когда модель проблемы известна частично. Человек, используя ЭВМ, определяет желаемые соотношения между критериями.

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

Функция полезности

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

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

Функция полезности -- соотношение между объемами потребляемых благ и уровнем полезности, достигаемой при этом потребителем. Математически функция полезности выглядит следующим образом:

где f -- символ функции; U -- уровень полезности; Q_X, Q_Y -- количество товаров Х и Y, потребленных за определенный период. В данную функцию можно включить любое количество переменных. Эта функция демонстрирует, что полезность, получаемая человеком, зависит только от количества потребляемых благ. Различают предельную и совокупную полезность блага.

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

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

Аксиоматические методы многокритериальной оценки

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

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

Функция, которая каждой альтернативе в многокритериальной задаче принятия решения сопоставляет действительное число, называется суперкритерием, если альтернативы, которым окажутся сопоставлены большие значения суперкритерия, объявляются строго более предпочтительными для ЛПР.

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

Прямые методы многокритериальной оценки альтернатив.

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

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

Методы компенсации

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

Поверхностью безразличия (при наличии двух критериев - кривой безразличия) ЛПР называется множество альтернатив, представляющихся ему равноценными.

Происхождение название методов (методы компенсации) связано с тем, что при построении кривой безразличия пытаются выяснить, какое изменение значения одного критерия ЛПР считает равноценным заданному изменению значения другого.

Картой безразличия ЛПР называется символически изображенная совокупность всех поверхностей безразличия, снабженная указанием на то, каким поверхностям безразличия принадлежат лучшие для ЛПР альтернативы.

Если карта безразличия ЛПР построена, любую пару альтернатив легко сравнить между собой.

Сравнение альтернатив методом компенсации в случае полностью замещаемых для ЛПР критериев.

Критерии называются полностью замещаемыми для ЛПР, если фиксированное изменение значения одного критерия ЛПР равноценным образом компенсирует всегда одним и тем же изменением значения другого.

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

Таблица 1. Способы нормализации

Нормализация	Математическое выражение
Сведение к безразмерным величинам
Приведение к одной размерности	,
Смена ингредиента	,
Естественная нормализация
Нормализация сравнения
Нормализация Савиджа

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

Принципы принятия решений в многокритериальных задачах.

Принцип равномерности.

Он провозглашает целесообразным выбор такого варианта решения, принадлежащего области компромиссов, при котором достигалась бы некоторая «равномерность» показателей по всем локальным критериям.

Используются следующие реализации принципа равномерности: принцип равенства, принцип квазиравенства и принцип максмина (maxmin).

Принцип равенства.

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

В общем виде эта модель расписывается следующим образом:

f_l , f₂ , f₃ -- некоторые локальные критерии (к примеру, f_l -- быстродействие, f₂ -- объем оперативной памяти и т.д.);

Принцип квазиравенства.

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

Принцип максимина -- maxmin.

Формально он может быть записан с помощью следующей записи:

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

Принцип справедливой уступки.

Он основан на сопоставлении прироста и убыли величин локальных критериев. Когда два или более вариантов находятся в области компромиссов (а только такие ситуации мы и рассматриваем), то при переходе от одного варианта к другому один (или несколько) локальный критерий может возрастать, другой (другие) может убывать. Данный принцип и основан на сопоставлении суммарной прибыли и суммарной убыли. Если суммарная прибыль превышает суммарную убыль, то новый вариант предпочтительнее старого, старый вариант отбрасывается и ведется сопоставление оставшегося варианта с новым вариантом. В том случае, если суммарная прибыль меньше суммарной убыли, то отбрасывается новый вариант, а старый вариант сравнивается со следующим вариантом. В том случае, если убыль равняется прибыли, то эти варианты равнозначны.

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

Принцип абсолютной уступки.

Формально он может быть выражен с помощью следующего выражения:

В этом выражении J⁽⁺⁾ -- подмножество мажорируемых, т.е. увеличиваемых, критериев; I^{( -)} -- подмножество минорируемых, т.е. уменьшаемых, критериев. Причем, как следует из определения, ?f_j > 0, ?fi <0, ?f_j ?f_i -- абсолютное значение величин приращения, | -- символ «такой, при котором». Лучшим по принципу абсолютной уступки считается компромисс, при котором абсолютное значение суммы снижения одного или нескольких критериев не превышает абсолютного значения суммы приращений оставшихся критериев.

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

Принцип относительной уступки.

Формально он может быть записан с помощью следующего выражения:

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

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

Или, для случая трех критериев: для каждой строчки вычисляется произведение:

и среди этих произведений ищется максимум -- это и будет лучший вариант по данному компромиссу.

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

Принцип выделения одного оптимизируемого критерия. Этот принцип является самым простейшим: один из локальных критериев объявляется главным и только по нему ищется наилучшее решение. На остальные локальные критерии могут накладываться (или не накладываться) ограничения.

Формально этот принцип может быть записан следующим образом:

Принцип последовательной уступки.

Пусть теперь локальные критерии имеют различную важность и пусть, также, самым важным является критерий f₁, вторым по важности является критерий f₂, третьим -- f₃ и т. д.

Сначала отыскивается вариант, обращающий критерий f₁ в максимум. После этого, исходя из некоторых соображений (например, из точности, с которой мы знаем значение f₁), на критерий f₁ накладывается некоторая «уступка» ?f₁ и при ограничении f_1max - ?f₁ выбирается вариант, обращающий в максимум второй по важности критерий f₂. Совершенно аналогично на критерий f₂ может быть наложена «уступка» ?f₂, и при соблюдении условий

выбирается вариант, обращающий в максимум следующий по важности критерий f₃, и т. д.

Деревья решений

Дерево принятия решений (также могут назваться деревьями классификации или регрессионными деревьями) -- используется в области статистики и анализа данных для прогнозных моделей. Структура дерева представляет собой следующее: «листья» и «ветки». На ребрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах -- атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе.

Каждый лист представляет собой значение целевой переменной, измененной в ходе движения от корня по листу. Каждый внутренний узел соответствует одной из входных переменных. Дерево может быть также «изучено» разделением исходных наборов переменных на подмножества, основанные на тестировании значений атрибутов. Это процесс, который повторяется на каждом из полученных подмножеств. Рекурсия завершается тогда, когда подмножество в узле имеет те же значения целевой переменной, таким образом, оно не добавляет ценности для предсказаний. Процесс, идущий «сверху вниз», индукция деревьев решений (TDIDT)^[1], является примером поглощающего «жадного» алгоритма, и на сегодняшний день является наиболее распространенной стратегией деревьев решений для данных, но это не единственная возможная стратегия. В интеллектуальном анализе данных, деревья решений могут быть использованы в качестве математических и вычислительных методов, чтобы помочь описать, классифицировать и обобщить набор данных, которые могут быть записаны следующим образом:

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

Качественные методы принятия решений

Общие черты неструктуризованных проблем

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

Пример 1.

К неструктуризованным можно отнести следующие проблемы.

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

2) Редакции журнала нужно выработать систему оценивания поступающих рукописей и создать для этой цели анкету для рецензентов, отражающую основные критерии, принятые редакцией: новизна материала, соответствие профилю журнала, отсутствие ошибок, качество изложения материала и т.п.

3) Абитуриенту необходимо выбрать вуз для поступления. При этом, для него важны критерии: конкурс, трудность экзаменов, престижность профессии и др.

Неструктуризованные проблемы имеют следующие общие черты:

1) Они являются проблемами уникального выбора, т.е. каждый раз проблема является новой для ЛПР либо обладает новыми особенностями, по сравнению с встречавшимися.

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

4) Общая оценка рассматриваемого варианта может быть получена только на основе субъективных предпочтений ЛПР.