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

Виды классификаций задач принятия решений

Наиболее общими и существенными признаками классификации задач принятия решений в соответствии с [5] являются:

1. Степень определенности информации.

• Задачи принятия решений в условиях определенности.

• Задачи принятия решений в условиях вероятностной определенности (в условиях риска).

• Задачи принятия решений в условиях неопределенности.

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

• Задачи принятия решений по априорным данным.

• Задачи принятия решений по апостериорным данным.

3. Количество целей.

• Одноцелевые задачи принятия решений.

• Многоцелевые задачи принятия решений.

4. Количество лиц, принимающих решение.

• Индивидуальные задачи принятия решений.

• Групповые задачи принятия решений.

5. Содержание решений.

• Экономические задачи принятия решений.

• Политические задачи принятия решений.

• Военные задачи принятия решений.

• Другие виды.

6. Значимость и длительность действия решений.

• Долговременные задачи принятия решений.

• Среднесрочные задачи принятия решений.

• Краткосрочные задачи принятия решений.

 

Нерациональное поведение при принятии решений

1. Суждение по представительности. Люди часто судят о вероятности того, что объект А принадлежит к классу В только по похожести А на типовой объект класса В. Они почти не учитывают априорные вероятности, влияющие на эту принад­лежность. В одном из опытов испытуемым дали краткие опи сания субъектов из группы в составе 100 человек и попросили определить вероятности того, что рассматриваемый субъект является юристом или инженером при условиях: 1) в группе 70 инженеров и 30 юристов; 2) в группе 30 инженеров и 70 юри­ стов. Ответы были примерно одинаковы. В других эксперимен тах было показано, что люди ориентируются только на пред­ставительность, не учитывая даже размер выборки, по которой выносится суждение.

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

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

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

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

 

Принятие решений в условиях риска

 

Задача о назначениях.

 

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

Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:

1 этап:

1 Формализация проблемы в виде транспортной таблицы

2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки

3 Повторить ту же процедуру для столбцов

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

2 этап:

1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.

2 Зачеркнуть оставшиеся нулевые значения данного столбца

3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным

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

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

5 Зачеркнуть оставшиеся нули в данной строке

6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным

Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6

Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.

3 этап: (Если решение является недопустимым)

1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице

2 Найти наименьший из элементов, через которые не проходит ни одна прямая

3 Вычесть его из всех элементов, через которые не проходят прямые

4 Прибавить его ко всем элементам, лежащим на пересечении прямых

5 Элементы, через которые проходит только одна прямая, оставить неизменными

В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново

 

Транспортная задача.

 

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.

 

Постановка задачи

 

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

 

Задача о ранце

 

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

Содержание [убрать]

1 Разновидности

2 Решение

3 Задача о ранце с возможностью бесконечного выбора предметов

3.1 Формулировка

3.2 Решение

3.3 Реализация

4 Задача о ранце с возможностью единичного выбора предмета

4.1 Решение

4.2 Реализация

5 См. также

6 Ссылки

7 Литература

[править]Разновидности

 

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

Каждый предмет можно использовать только один раз.

[править]Решение

 

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

 

 

Задача коммивояжера.

 

Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

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

Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач.

 

Задача управлення запасами

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

 

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

 

Спрос можно удовлетворить

 

путем однократного создания запаса на весь рассматриваемый период времени

или

 

посредством создания запаса для каждой единицы времени этого периода.

Эти два случая соответствуют избыточному запасу (по отношению к единице времени) и недостаточному запасу (по отношению к полному периоду времени).

 

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

 

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

 

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

Метод анализа иерархий.

Метод Анализа Иерархий (МАИ) — математический инструмент системного подхода к сложным проблемам принятия решений. МАИ не предписывает лицу, принимающему решение (ЛПР), какого-либо «правильного» решения, а позволяет ему в интерактивном режиме найти такой вариант (альтернативу), который наилучшим образом согласуется с его пониманием сути проблемы и требованиями к ее решению. Этот метод разработан американским математиком Томасом Саати, который написал о нем книги, разработал программные продукты и в течение 20 лет проводит симпозиумы ISAHP (англ. International Symposium on Analytic Hierarchy Process). МАИ широко используется на практике и активно развивается учеными всего мира. В его основе наряду с математикой заложены и психологические аспекты. МАИ позволяет понятным и рациональным образом структурировать сложную проблему принятия решений в виде иерархии, сравнить и выполнить количественную оценку альтернативных вариантов решения. Метод Анализа Иерархий используется во всем мире для принятия решений в разнообразных ситуациях: от управления на межгосударственном уровне до решения отраслевых и частных проблем в бизнесе, промышленности, здравоохранении и образовании. Для компьютерной поддержки МАИ существуют программные продукты, разработанные различными компаниями. Анализ проблемы принятия решений в МАИ начинается с построения иерархической структуры, которая включает цель, критерии, альтернативы и другие рассматриваемые факторы, влияющие на выбор. Эта структура отражает понимание проблемы лицом, принимающим решение. Каждый элемент иерархии может представлять различные аспекты решаемой задачи, причем во внимание могут быть приняты как материальные, так и нематериальные факторы, измеряемые количественные параметры и качественные характеристики, объективные данные и субъективные экспертные оценки [1]. Иными словами, анализ ситуации выбора решения в МАИ напоминает процедуры и методы аргументации, которые используются на интуитивном уровне. Следующим этапом анализа является определение приоритетов, представляющих относительную важность или предпочтительность элементов построенной иерархической структуры, с помощью процедуры парных сравнений. Безразмерные приоритеты позволяют обоснованно сравнивать разнородные факторы, что является отличительной особенностью МАИ. На заключительном этапе анализа выполняется синтез (линейная свертка) приоритетов на иерархии, в результате которой вычисляются приоритеты альтернативных решений относительно главной цели. Лучшей считается альтернатива с максимальным значением приоритета.

Дерево принятия решений.

 

На рис. 3 задача принятия решения графически представлена в виде так называемого дерева принятия решений.

Рис. 3. Часть дерева принятия решений

Для иллюстрации введенных выше понятий рассмотрим типичную ветвь дерева. Двигаясь слева направо, ЛПР должно сначала либо выбрать эксперимент стоимостью, либо не проводить экспериментов, что обозначается через, а соответствующие затраты (нулевые) –. При условии выбора данного эксперимента наблюдается исход. Эксперимент приводит к различным исходам, вероятности появления которых описываются с помощью распределения условных вероятностей. Если исход известен, должно быть выбрано следующее решение. После такого выбора наличие внешних условий задается распределением условных вероятностей, где индекс r относится к эксперименту, t обозначает исход, а i – решение. В результате этих шагов получается исход х. Вероятность различных исходов численно выражается через распределение условных вероятностей, где индекс j относится к внешним условиям. Относительная предпочтительность возможных rerс0e0сtorerpidjsrtiprtijp

исходов задается функцией полезности u(x).

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

 

 

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

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

 

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

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

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

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

· выбор внутрисистемных независимых переменных, которые должны адекватно описывать допустимые проекты или условия функционирования системы и способствовать тому, чтобы все важнейшие технико-экономические решения нашли отражение в формулировке задачи;

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

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

Все оптимизационные задачи имеют общую структуру. Их можно классифицировать как задачи минимизации(максимизации) M-векторного векторного показателя эффективности W_m(x), m=1,2,...,M, N-мерного векторного аргумента x=(x₁,x₂,...,x_N), компоненты которого удовлетворяют системе ограничений-равенств h_k(x)=0, k=1,2...K, ограничений-неравенств g_j(x)>0, j=1,2,...J, областным ограничениям x_li<x_i<x_ui, i=1,2...N.

Все задачи принятия оптимальных решений можно классифицировать в соответствии с видом функций и размерностью W_m(x), h_k(x), g_j(x) и размерностью и содержанием вектора x:

· одноцелевое принятие решений - W_m(x) - скаляр;

· многоцелевое принятие решений - W_m(x) - вектор;

· принятие решений в условиях определенности - исходные данные - детерминированные;

· принятие решений в условиях неопределенности - исходные данные - случайные.

Наиболее разработан и широко используется на практике аппарат одноцелевого принятия решений в условиях определенности, который получил название математического программирования. Более подробно задачи линейного программирования (W(x), h_k(x), g_j(x) - линейны) изложены в главе 2, нелинейного программирования (W(x), h_k(x), g_j(x) - нелинейны) - в главе 3, целочисленного программирования (x - целочисленны) - в главе 4, динамического программирования (x - зависят от временного фактора) - в главе 5.

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

Методы принятия многоцелевых решений изложены в 7 главе.

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

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

· возможность неоднозначности результатов;

· возможность неоднозначности способов достижения результатов, то есть свобода выбора.

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

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

· анализ исходной ситуации;

· анализ возможностей выбора;

· выбор решения;

· оценка последствий решения и его корректировка.