Некорректно поставленные задачи

Реферат

по СМПР на тему:

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

 

 

Выполнил: ст. 440М гр.

Авраменко Екатерина

Проверил: Трончук

Алексей Адамович

 

Харьков 2008

 

Оглавление

 

Введение

1. Принятие решений в условиях определенности

1.1 Определение

1.2.Классификация

1.3 Определенность

1.4 Методы

2. Некорректно поставленные задачи

3. Регуляризирующие алгоритмы

4. Адаптивные регуляризирующие алгоритмы

Вывод

Список использованных источников

 

Введение

 

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

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

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

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

 

Принятие решений в условиях определенности

 

Определение

 

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

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

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

 

Классификация

Управленческие решения целесообразно группировать на основе классификационных признаков, приведенных на рис. 1. (Ист. №5)

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

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

 

 

Рис. 1. Классификация управленческих решений

 

Управленческие решения должны быть: эффективными, своевременными, рациональными, обоснованными и реально осуществимыми.

 

Определенность

 

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

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

Методы

 

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

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

Формализуемые решения принимаются на основе соответствующих математических методов (алгоритмов). Математическая модель задачи оптимизации формализуемого решения включает следующие элементы:

1. заданную оптимизируемую целевую функцию (критерий управляемости): Ф=F(x₁,x₂,:,x_n), где x_j (j=1,2,:,n) - параметры, учитываемые при принятии решения (отражающие ресурсы принятия решений);

2. условия, отражающие ограниченность ресурсов и действий ЛПР при принятии решений: g_i(x_j)<a_i, k_i (x_j)=b_i; c_j<x_j<d_i, i=1,2,:,m; j=1,2,:, n.

Непременным требованием для решения задачи оптимизации является условие n>m.

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

Основными являются следующие классы методов:

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

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

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

4. методы теории игр (принятие решений с помощью определения стратегии в тех или иных состязательных задачах);

5. методы теории расписаний (принятие решений с помощью разработки календарных расписаний выполнения работ и использования ресурсов);

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

7. методы многокритериальной (векторной) оптимизации (принятие решений при условии существования многих критериев оптимальности решения)

и другие методы. (Ист. №9)

 

Некорректно поставленные задачи

 

В качестве основного объекта рассматривается операторное уравнение: Az = u , где A - линейный оператор, действующий из гильбертова пространства Z в гильбертово пространство U. Требуется найти решение операторного уравнения z, соответствующее заданной неоднородности (или правой части уравнения) u.

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

Французским математиком Ж. Адамаром были сформулированы следующие условия корректности постановки математических задач, которые мы рассмотрим на примере записанного операторного уравнения. Задача решения операторного уравнения называется корректно поставленной (по Адамару), если выполнены следующие три условия (условия корректности):

1) задача имеет решение при любых допустимых исходных данных (решение существует ∀u ∈U);

2) каждым исходным данным u соответствует только одно решение (решение единственно);

3) решение устойчиво (если u n →u ,  , Az = u , то z n →z).

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

Второе условие означает, что исходных данных достаточно для однозначной определённости решения задачи. Эти два условия обычно называют условиями математической определённости задачи. Условие 2) обеспечивается тогда и только тогда, когда оператор A является взаимно однозначным (инъективным). Условия 1) и 2) означают, что существует обратный оператор  , причем его область определения D( ) (или множество значений оператора A, R(A)) совпадает с U.

Условие 3) означает, что обратный оператор  является непрерывным, т.е. “малым” изменениям правой части u соответствуют “малые” изменения решения z. Третье условие обычно трактуется как физическая детерминированность задачи. Это объясняется тем, что исходные данные физической задачи, как правило, задаются с некоторой погрешностью; при нарушении же третьего условия как угодно малые возмущения исходных данных могут вызывать большие отклонения в решении.

Задачи, не удовлетворяющие хотя бы одному условию корректности, называются некорректными задачами (или некорректно поставленными). Более того, Ж. Адамар считал, что только корректные задачи должны рассматриваться при решении практических задач. Однако хорошо известны примеры некорректно поставленных задач, к изучению и численному решению которых приходится прибегать при рассмотрении многочисленных прикладных задач. Нужно отметить, что устойчивость и неустойчивость решения связаны с тем, как определяется пространство решений Z. Выбор пространства решений (в том числе и нормы в нем) обычно определяется требованиями прикладной задачи. Задачи могут быть некорректно поставленными при одном выборе нормы и корректно поставленными при другом.

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

Хорошо известным примером некорректно поставленной задачи является интегральное уравнение Фредгольма 1-го рода. Пусть оператор A имеет вид:

 

 

Пусть ядро интегрального оператора K(x, s) - функция, непрерывная по совокупности аргументов x ∈[c, d], s ∈[a,b], а решение z(s) - непрерывная на отрезке [a,b] функция. Тем самым, можно рассматривать оператор A как действующий в следующих пространствах: A :C[a,b]→ C[c, d]. (Пространство C[a,b] состоит из функций, непрерывных на отрезке [a,b]. Норма z ∈C[a,b]определяется как ). Покажем, что в этом случае задача решения интегрального уравнения является некорректно поставленной. Для этого нужно проверить условия корректности постановки задачи:

1) Существование решения для любой непрерывной на [c, d] функцииu(x) . На самом же деле, это не так: существует бесконечно много непрерывных функций, для которых решения нет.

2) Единственность решения. Это условие выполняется в том и только в том случае, если ядро интегрального оператора замкнуто.

Первые два условия корректности эквивалентны условию существования обратного оператора  с областью определения D( )=C[c,d]. Если ядро интегрального оператора замкнуто, то обратный оператор существует, однако область его определения не совпадает с C[c,d].

3) Устойчивость решения. Это означает, что для любой последовательности  последовательность z n → . Устойчивость эквивалентна непрерывности обратного оператора  при условии, что обратный оператор существует. В данном случае это не так, что видно из следующего примера. Пусть последовательность непрерывных функций  , n=1, 2, …, такая, что  на промежутке  и обращается в нуль вне данного интервала, max| z (s) |=1, s∈[a, b], а последовательность чисел d → 0 +0 .

4) Такая функция может быть выбрана, например, кусочно-линейной. Тогда для любого x ∈[c, d]

 

 

при

Последовательность функций  равномерно, т.е. по норме C[c,d], сходится к  = 0.

Хотя решение уравнения  в этом случае  = 0 , последовательность  не стремится к  , так как .

Интегральный оператор A является вполне непрерывным при действии из  в

, при действии из C[a,b] в  и при действии из C[a,b] в C[c,d]. (Пространство

 состоит из функций, интегрируемых с квадратом на отрезке [a,b]. Норма z∈  определяется как  ). Это означает, что любую ограниченную последовательность этот оператор преобразует в компактную. Компактная последовательность по определению обладает тем свойством, что из любой ее подпоследовательности можно выделить сходящуюся. Легко указать последовательность  , , из которой нельзя выделить сходящуюся в C[a,b] подпоследовательность. Например,

 

 

Нормы всех членов этой последовательности равны 1 в  , но из любой подпоследовательности этой последовательности нельзя выделить сходящуюся, поскольку  . Очевидно, что эта последовательность состоит из непрерывных на [a,b] функций и равномерно (по норме C[a,b]) ограничена, но из этой последовательности нельзя выделить сходящуюся в C[a,b] подпоследовательность (тогда она сходилась бы и в , поскольку из равномерной сходимости следует сходимость в среднем). Если предположить, что оператор  является непрерывным, то легко прийти к противоречию. Для существования обратного оператора достаточно потребовать, чтобы прямой оператор A был инъективным. Очевидно, что, если оператор B: C[c,d]→C[a,b] непрерывный, а оператор A вполне непрерывный, то BA :C[a,b] →C[a,b] - тоже вполне непрерывный оператор. Но тогда, поскольку для любого n , то последовательность  компактна, что неверно. Оператор, обратный к вполне непрерывному оператору, не может быть непрерывным. Аналогичное доказательство может быть проведено для любых бесконечномерных банаховых (т.е. полных нормированных) пространств.

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

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

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

Пусть дана система линейных алгебраических уравнений (СЛАУ):

 

 

Система может и не иметь решений. Гаусс и Лежандр в начале XIX века ввели метод наименьших квадратов, а именно, вместо решения СЛАУ предложили минимизировать квадратичный функционал (невязку):

 

 

 - сопряженная (транспонированная) матрица. Поскольку матрица  неотрицательно

определена, то Ф(x)- выпуклый функционал. Для выпуклого функционала задача отыскания  эквивалентна отысканию стационарной точки, т.е. решения уравнения Ф'(x) = 0 . Легко видеть, что Ф' (x) = 2 ⋅ ( Ax − b), Ф''(x) = 2 ⋅ A ≥0.

 

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

 

 

В конечномерном случае легко доказать, что для любого вектора b система нормальных

уравнений всегда имеет решение (для исходного же уравнения это не обязательно), которое называется псевдорешением системы Ax = b . Псевдорешение может быть неединственным (если определитель det( A) =0; если же det( A) ≠0, то псевдорешение единственно). Множество псевдорешений образует аффинное (или линейное) подпространство и является выпуклым и замкнутым.

Если же система Ax =b имеет решение, то оно совпадает с решением системы  Ax = b . В этом случае minФ(x) =μ=0. Если же minФ(x) =μ>0, система Ax = b не имеет решений, но, какуже указывалось выше, имеет псевдорешение (возможно, неединственное). Число μ обычноназывается мерой несовместности системы Ax = b .

Определение.Нормальное псевдорешение  системы Ax = b – это псевдорешение с

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

Можно привести много др. примеров классических математических задач, являющихся некорректными при совершенно естественном выборе понятий меры точности как для исходных данных задачи, так и для возможных решений: решение систем линейных алгебраических уравнений с определителем, равным нулю; задача оптимального планирования; решение интегральных уравнений 1-го рода; задача аналитического продолжения; суммирование рядов Фурье; большое число краевых задач для уравнении с частными производными. (Ист. №10)