Главная
страница 1страница 2 ... страница 8страница 9
Ф?????????? АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Медведева Н.С., Моисеева Ю.А., Степанов А.Г., Усикова И.В.

СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЯ

Оптимальные методы и теория принятия решений

Учебно ЁC методическое пособие

Санкт-Петербург

2008


УДК 681.3.06(075)

ББК 32.79

С
Системы поддержки принятия решения. Оптимальные методы и теория принятия решений: учеб.-метод. пособие/ Медведева Н.С., Моисеева Ю. А., Степанов А.Г., Усикова И.В.; ГУАП.  СПб., 2007.  00 с.
В учебно-методическом пособии рассматривается основные положения теории принятия решений и цикл лабораторных работ по дисциплине «Системы поддержки принятия решения» в части оптимальных методов и теории принятия решений. Излагается методика выполнения лабораторных работ и приводятся необходимые рекомендации. Учебно-методическое пособие предназначено для студентов, обучающихся по специальностям «Прикладная информатика в экономике», «Информационный сервис» и может быть использовано в составе дисциплины «Разработка управленческого решения» при подготовке по экономическим специальностям, для которых требуется изучение теории принятия решений.
Рецензент: профессор Международного банковского института доктор технических наук Кричевский М.Л.

Н.С. Медведева 2008

Ю.А. Моисеева 2008

А.Г. Степанов 2008

И.В. Усикова 2008
Содержание



Введение


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

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

Рис. 1. Используемая классификация систем поддержки принятия решения

Оптимальные методы

Методы поиска экстремумов функций

Экстремумом XE "?????????" § функции µ § на интервале µ § называется наибольшее или наименьшее значение функции относительно некоторой окрестности. Это значение может отличаться от наибольшего или наименьшего значения на всей области определения. Найти экстремум µ § ЁC это значит найти такое значение аргумента µ §, при котором функция имеет максимум или минимум (рис. 2. Экстремум функции на интервале определения).

Рис. 2. Экстремум функции на интервале определения

Традиционным методом поиска экстремума является дифференциальное исчисление XE "???????????????? ??????????" § (метод И. Ньютона). Необходимым условием существования экстремума дифференцируемой на интервале функции является равенство нулю первой ее производной. Соответствующая точка рассматривается как критическая. Достаточным условием существования максимума дифференцируемой на интервале функции является отрицательное значение второй производной функции в критической точке, а минимума - положительное значение второй производной. Если вторая производная в рассматриваемой точке равна нулю, то экстремум не существует, а критическая точка является точкой перегиба.

Предположим, что функция изменяет свое значение на интервале определения µ §, но имеет экстремум вне интервала. Тогда возникает задача поиска находящихся как раз на границах интервала максимального и минимального значения функции (рис. 2. Экстремум функции на интервале определения). Отметим, что первая производная функции на границах интервала определения в этом случае вовсе не обращается в нуль. Поэтому использование традиционного метода поиска экстремума (метода И. Ньютона) в данном случае оказывается невозможным.

Рис. 3. Экстремум на границе интервала определения

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

µ §


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

Достаточное условие существования локального экстремума формулируется следующим образом []: пусть функция µ § имеет критическую точку (µ §), определяемую за счет вычисления выражений

µ §

Тогда, если дифференциал второго порядка



µ §

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

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

В качестве примера рассмотрим функцию двух переменных µ §. Приравняем к нулю ее первые частные производные

µ §

Вычитая из первого уравнения второе, имеем µ §, откуда µ §. Подставляя µ § в выражения для частных производных, имеем µ §. Получившееся уравнение имеет три решения: 0, 1, -1. Тогда критическими точками являются µ §, µ § и µ §.



Вторые частные производные имеет вид

µ §


Следуя [], «разумным» образом выберем комбинацию приращений µ § и µ § равными +1 и ЁC1, поскольку такие значения соответствуют максимально возможному диапазону изменения аргументов при переходе от одной критической точки к другой. Результаты вычислений вторых частных производных и дифференциала второго порядка при различных комбинациях µ § и µ § сведены в таблицу 1.

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

Таблица 1. Расчеты критических точек

Критическая точка µ §µ §µ §µ §µ §µ §µ §µ §µ §(0,0)-2-2-2-21

-1

1

-11



1

-1

-1-8



0

0

80(1,1)



(-1,-1)10-2-2101

-1

1



-11

1

-1



-116

24

24



16

-2Учет ограничений на значения переменных

Существенный вклад в математическую теорию экстремальных задач был внесен Л.В. Канторовичем, впервые сформулировавшим и решившим задачу, позднее получившую название задачи линейного программирования XE "?????? ????????? ????????????????" §. Математическая постановка этой задачи сводится к поиску переменных, входящих в выражение линейной критериальной функции и, в общем случае, в неограниченное конечное количество дополнительных функций ограничений (тоже линейных), которые в частности могут представлять собой неравенства. Дальнейшее развитие идей Л.В. Канторовича привело к появлению теории математического программирования, расширившей класс используемых функций. Так в некоторых случаях удается решать задачи с нелинейными критериальными функциями (задачи квадратичного программирования, геометрического программирования и т. п.). Отметим, что термин программирование в данном случае используется только как название математического метода и непосредственного отношения к программированию на ЭВМ не имеет.

Рассмотрим простейшую задачу математического программирования, у которой имеется линейная целевая функция и линейные ограничения. Такая задача называется задачей линейного программирования XE "?????? ????????? ????????????????" §. Будем считать, что у этой задачи имеется µ § переменных и µ § ограничений. Тогда целевая функция µ §может быть записана в виде:

µ § (1)

Если по смыслу задачи целевая функция должна обращаться в минимум, то для получения выражения (1)) в ней достаточно поменять значения всех коэффициентов µ § на противоположные (µ §).

Набор ограничений может быть записан в виде:

µ § (2)


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

µ § (3)


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

Задача линейного программирования при µ § допускает достаточно наглядную геометрическую интерпретацию. Например, если задача поиска экстремума имеет вид

µ §

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



Распространенным методом решения задачи линейного программирования является так называемый симплекс ЁC метод. В его основе лежит так называемая симплекс-таблица, которая составляется по определенным правилам исходя из исходных данных задачи (1), 1)). Доказано, что, производя последовательные преобразования этой таблицы по определенным правилам, можно получить оптимальное решение задачи линейного программирования [].

В основе методов решения нелинейных задач с ограничениями лежит так называемый метод Лагранжа. Наличие ограничения сужает возможности отыскания экстремума. В этом случае, как правило, экстремум функции µ § не совпадает с локальным экстремумом, определенным с помощью классического метода и называется условным. Для решения подобных задач строится специальная функция, обычно называемая функцией Лагранжа XE "??????? ????????" §

µ §

µ §


Рис. 4. Графическая интерпретация метода линейного программирования

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

Набор множителей Лагранжа XE "????????? ????????" § µ § имеет определенный смысл, заключающийся в том, что их значение определяет величину изменения оптимального решения в зависимости от изменения соответствующего ограничения. Уравнения ограничений могут быть записаны в виде неравенств, например:

µ §


При решении таких задач приходится выполнять итеративную процедуру отыскания экстремума, задавая область допустимых значений переменных µ §. Экстремум целевой функции может достигаться в этом случае как внутри области, так и на ее границе. Для построения области допустимых решений следует записать уравнения линий уровня целевой функции ЁC множество точек плоскости, в которых целевая функция постоянна.

µ §


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

Использование Excel для поиска экстремумов функций

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

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

В качестве параметров режима (рис. 8) задаются методы поиска экстремума. Так, при установке флажка Линейная модель надстройка ищет экстремум симплекс-методом. Флажок Неотрицательные значения накладывает дополнительное ограничение на значения переменных задачи. Его установка эквивалентна введению ограничения µ §.

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

Рис. 5. Пункт меню Поиск решения

Рис. 6. Включение надстройки Поиск решения

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

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

Рис. 7. Главная форма надстройки Поиск решения

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

µ § (4)

На рис. 9 изображен рабочий лист Excel с данными задачи (1)). Для всех ячеек, предназначенных для хранения данных, был задан числовой формат с двумя знаками после запятой режимом Формат/ЯчейкиЎK/Число. Матрица µ § размещена в диапазоне ячеек B8:E16. Значения ограничений µ § находятся в диапазоне ячеек G8:G16. Весовые коэффициенты целевой функции µ § занесены в диапазон ячеек B5:E5. Кроме этого, для хранения переменных µ § зарезервирован диапазон ячеек B3:E3. Значения µ § предварительно были обнулены, однако это не является обязательным, поскольку система может начать поиск экстремума с любой начальной комбинации. Очевидно, что в данном случае µ §, µ §.



Рис. 8. Параметры надстройки Поиск решения

Выражение (1)) представляет собой ничто иное, как сумму µ § попарных произведений некоторых наборов чисел, которые должны быть заданы в табличной форме или рассчитаны средствами пакета Excel. Рассчитаем значение целевой функции µ § в ячейке F5. Ее программирование сводится к заданию выражения типа (1)), которое можно рассчитать непосредственно на основе формулы Excel =B3*B5+C3*C5+D3*D5+E3*E5. Тем не менее, по ряду причин, более удобно воспользоваться встроенной функцией СУММПРОИЗВ(B5:E5;$B$3:$E$3), которая автоматически определяет количество слагаемых µ § и дает результат вычислений в соответствии с (1)). Использование абсолютного формата записи диапазона ячеек, используемого для хранения µ §, не является обязательным, однако удобно для последующих действий, которые могут выполняться способом копирования.

Выражения, определяющие расход ресурсов µ § программируются в ячейки F8, F9,ЎK, F16 аналогично предыдущему с той только разницей, что в качестве первого аргумента функции СУММПРОИЗВ() выступает соответствующая строка матрицы µ §, а второй аргумент по-прежнему есть диапазон ячеек B3:E3, заданный в абсолютом формате и используемый для хранения переменных µ §.

Примечание. Остальная информация, нанесенная на рабочий лист (рис. 9), используется для пояснения принципа размещения данных. Она представляет собой либо текстовые строки, записанные в определенные ячейки, либо внедренные объекты и носит вспомогательный характер. Поэтому при повторении примера на ЭВМ она может быть опущена.

Рис. 9. Вариант размещения данных на рабочем листе

Выполненные ранее в операции (заполнение таблиц данными и программирование формул) позволяют полностью подготовиться собственно к решению задачи оптимизации. Теперь нам необходимо вызвать режим Сервис/Поиск решения. В открывшейся главной форме меню режима Поиск решения (рис. 7) надо указать адрес нашей целевой ячейки F5 и проверить или задать тип экстремума (в нашем случае Установить целевую ячейку равной максимальному значению). В окне Изменяя ячейки задаем адреса ячеек переменных µ § (в нашем случае B3:F3). Нажав кнопку Добавить в открывшейся таблице (рис. 10) Добавление ограничения в поле Ссылка на ячейку вводим адреса левых частей неравенств (1)) (в нашем случае F8:F16). Устанавливаем (сохраняем) требуемые знаки неравенств (в нашем случае ). Войдя в окно Ограничение, задаем адреса ячеек, содержащих значения µ § (в нашем случае G8:G16). Нажав кнопку Параметры, в открывшейся таблице (рис. 8) задаем режим Линейная модель и Неотрицательные значения, после чего нажимаем кнопку OK. Результат этих действий отображен на рис11.

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

Решение найдено. Все ограничения и условия оптимальности выполнены (имеет место в рассматриваемом случае).

Поиск не может найти подходящего решения.

Значения целевой ячейки не сходятся.

Если решение найдено, то на рабочем листе Excel в изменяемых ячейках находятся значения переменных µ § (в нашем случае 1,13; 0,00; 0,00; 3,10), обеспечивающие максимальное значение целевой функции (в нашем случае 33,95). Для сохранения результатов вычислений на рабочем листе необходимо выбрать пункт Сохранить найденное решение.

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

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

Рис. 10. Добавление ограничений

Рис. 11. Подготовленная к решению задача линейного программирования

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

Отчет по результатам (рис. 13. Отчет по результатам) содержит начальные (Исходно) и конечные (Результат) значения целевой функции и изменяемых ячеек, а также сводку результатов использования ресурсов. В этой сводке в столбце Статус символами связанное или несвязанное обозначаются соответственно полное или неполное использование соответствующего ресурса. В рассматриваемом примере полностью израсходованы Ресурс 3 и Ресурс 4.

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

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

Рис. 13. Отчет по результатам

Рис. 14. Отчет по устойчивости

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

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

Рис. 15. Отчет по пределам

Лабораторная работа №1. Методы поиска экстремумов с помощью надстройки Поиск решения пакета Excel

Задание


Установите у себя на машине надстройку Поиск решения и научитесь решать задачи поиска экстремума с ее помощью.

Порядок выполнения работы

Создайте новую рабочую книгу Excel.

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


следующая страница >>
Смотрите также:
Н. С., Моисеева Ю. А., Степанов А. Г., Усикова И. В. Системы поддержки принятия решения оптимальные методы и теория принятия решений Учебно ёc методическое пособие Санкт-Петербург 2008
1269.71kb.
9 стр.
Задачи и методы аналитического сопровождения экспертиз в парТИсипативных процессах стратегического управления
269.29kb.
1 стр.
Перспективы создания информационной системы поддержки принятия решений абитуриентами Г. И. Болтунов, А. Л. Лымарь
30.16kb.
1 стр.
Трехуровневая модель планирования и принятия решений
586.19kb.
5 стр.
Семинара «Дискретные модели и методы принятия решений»
37.14kb.
1 стр.
На выполнение работ по созданию информационной системы поддержки оперативного принятия решений на основе цифровых ситуационных карт шельфовых проектов
115.71kb.
1 стр.
Теоретические особенности принятия управленческого решения 2 1 Роль и место принятия решений в процессе управления 2
441.69kb.
2 стр.
Учебно-методическое пособие Санкт-Петербург 2007 ббк г
1412.38kb.
8 стр.
Технология принятия управленческих решений
1188.33kb.
7 стр.
Вопросы к зачёту «Теория принятия решений», «Управленческие решения»
10.79kb.
1 стр.
Программа конференции 7 апреля 2008 г. (2-й учебный корпус, малый зал) пленарное заседание
222.05kb.
1 стр.
Маркетинговые информационные системы
187.16kb.
1 стр.