книги / Математические методы принятия решений

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

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

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

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

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

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

Сущность интерактивного подхода состоит в том, чтобы облегчить че­ ловеку участие в процессе поиска решения на основе корректировки этого процесса. Интерактивные процедуры дают возможность для эффективно­ го разделения труда: компьютер выполняет то, что он делает лучше всего (обрабатывает данные), ЛПР, получив новую информацию, разрабатывает методы для получения лучшего решения.

Тем не менее главная роль остается за человеком, ибо правильная постановка задачи, грамотная формулировка модели являются залогом успешного результата, который невозможно получить без понимания по­ строения алгоритмов решения задач математического программирования

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

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

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

В части I книги «Математическое программирование» рассмотрены сетевые задачи, а также динамическое программирование как один из спо­ собов решения задач на условный экстремум и теория игр с нулевой сум­ мой, использующая линейное программирование для получения решения.

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

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

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

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

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

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

Книга состоит из двух частей. В части I (главы 1-5) изложены задачи математического программирования и родственные им.

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

Вглаве 2 рассмотрен наиболее хорошо изученный раздел математи­ ческого программирования —линейное программирование. Здесь же рас­ смотрены и частные случаи задач линейного программирования —транс­ портные задачи и задачи целочисленного линейного программирования. Рассмотрены дробно-линейное программирование и анализ устойчивости оптимального решения задачи линейного программирования при неопре­ деленности параметров задачи.

Вглаве 3 описаны сетевые (потоковые) задачи (задачи о кратчай­ ших путях, о максимальных потоках, о многопродуктовых потоках, задача коммивояжера), показаны их особенности и преимущества по сравнению

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

Вглаве 4 рассмотрены основы динамического программирования

иэлементы теории игр с нулевой суммой.

Вглаве 5 представлены некоторые направления развития методов ре­ шения задач математического программирования: параметрическое про­ граммирование; решение многопродуктовых сетевых задач; один из эври­ стических методов решения сетевых задач; метод штрафных (барьерных) функций; метод проекции градиента; целевое программирование; пара­ метрическое программирование; многокритериальное линейное програм­ мирование.

Вчасти II (главы 6-10) изложены статистические методы принятия

решений.

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

Вглаве 7 изложены методы регрессионного и конфлюэнтного анализа, служащие основой статистических методов принятия решений. Отмечено, что нестрогий учет погрешностей исходных данных приводит к регресси­ онному парадоксу, когда по одним и тем же исходным данным можно

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

Вглаве 8 описаны способы учета погрешностей вектора признаков

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

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

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

икоррекции ошибки прогнозов.

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

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

Автор благодарит всех коллег, способствовавших выходу этой кни­ ги, в частности ректора МГТУ им. Н.Э. Баумана И. Б. Федорова, Уче­ ный совет научно-учебного комплекса «Фундаментальные науки» МГТУ им. Н.Э.Баумана и его председателя Б.П.Назаренко, начальника Учеб­ ного управления МГТУ им. Н. Э. Баумана В. И. Авдееву и многих других, а также рецензентов, высказавших полезные замечания.

ЧАСТЬ I

МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ

Нужно много учиться, чтобы немного знать.

Шарль Монтескье

Г л а в а 1

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

§ 1.1. Общие положения математического программирования

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

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