Министерство образования и науки Республики Казахстан
Павлодарский государственный университет им. С. Торайгырова
Факультет физики математики и информационных технологий
Кафедра вычислительной техники и программирования
КУРСОВАЯ РАБОТА
По дисциплине «Теоретические основы компьютерных систем»
Тема:
«Системы принятия решений»
2005
1. Теоретическое задание
1.1 Введение
Наша жизнь пронизана решениями. Их так много и принимаем мы их так часто, что в большинстве случаев этого просто не осознаем. Лишь наиболее важные и трудные решения как-то выделяются и становятся предметом анализа. Но даже м в сложных случаях большинство из нас почему-то считают, что как-нибудь с ситуацией самостоятельно, без посторонней помощи. Между тем, это не всегда так. Сегодня совершенно очевидно, что не оптимальность решений, принимаемых в жизнедеятельности и производстве, лишает нас значительной доли возможностей и ресурсов. И чем сложнее ситуация, тем больше потери. Именно способность принимать целенаправленные решения выделяет человека из окружающего живого мира. Однако как часто приходится удивляться тому, сколь не оптимальны бывают наши решения.
А ведь принятию решений можно учиться. Есть специальная наука, которая носит название «Теория принятия решений». Познав ее, мы станем гораздо лучше принимать свои решения.
Сравнительно недавно появилось одно важное обстоятельство: в жизнь входят ЭВМ нового поколения, которые весьма «дружелюбно» настроены по отношению к пользователю – с ними «можно вести диалог», можно перебирать и сравнивать множество вариантов, они позволили создать человеко-машинные комплексы, специально предназначенные для принятия решений. Человек и машина прекрасно дополняют друг друга. Машина несравненна в скорости перебора вариантов, а человек прекрасно ориентируется в целях и оценках окончательных решений. Все выше сказанное подготовило почву для такой науки, как теория принятия решений.
1.2 Структура процесса принятия решения
У всех проблем принятия решений есть что-то общее, и из этого общего следует выделить компоненты, составляющие проблему принятия решений.
Каждое решение, в некоторой определенной исходной ситуации, допускает по меньшей мере два возможных варианта и обуславливает определенные последствияэтих вариантов. Причем существует лишь одна исходная ситуация, решений и их последствий может быть несколько – по меньшей мере два. Теперь следует оценить возможные варианты решений и (или) их последствия. После чего решение вполне подготовлено и остается только исполнить соответствующее действие. Процесс принятия решений можно считать законченным лишь тогда, когда мы после его завершения обобщим и запомним опыт наших положительных и отрицательных действий, приобретем какие-то знания.
Таким образом, процесс принятия решений можно разбить на следующие этапы:
– исследовать собственно проблему;
– уяснить исходную ситуацию;
– сформировать возможные варианты решения;
– описать последствия этих вариантов решения;
– оценить возможные варианты решений и (или) последствия этих решений;
– выбрать оптимальное решение;
– обобщить накопленный опыт принятия решения.
Данная структура процесса принятия решения наглядно изображена на рисунке 1.1.
Рисунок 1.1 – Структура процесса принятия решения
1.3 Исходная ситуация
Мы установили, что прежде чем приступить к анализу составляющих общей проблемы принятия решения, важно уяснить исходную ситуацию, то есть ситуацию, в которой оказывается лицо, принимающее решение, перед началом работы.
Чтобы сформулировать представление об исходной ситуации надо ответить на следующие вопросы.
– Кто должен или обязан (или хочет) решать?
– Где, то есть на (в) каком месте, в каком окружении (среде), при каких обстоятельствах и граничных условиях предстоит принимать решение?
– Когда (до какого срока, как часто) требуется принять решение?
– Как (каким образом или в какой форме, чем) должно быть выражено решение?
– Что обуславливает решение? В чем его цель, замысел? Для чего оно служит? Зачем его надо принимать?
1.4 Возможности принятия решения
Теперь настало время исследовать, как построено поле решений (множество возможных решений), как следует его изучать, обозревать и как (при необходимости) можно его расширить. Каждое решение имеет, по меньшей мере, два варианта решений. Существуют проблемы, которые имеют только два варианта рения – две альтернативы. Однако многие проблемы имеют очень большое число возможных решений.
Важная отличительная черта хорошей подготовки решения – ясность того, какие решения возможны. Однако существует множество служебных и личных проблем, которые поначалу недостаточно нам известны, в то время как полное, исчерпывающее знание их имеет большое значение. В таких случаях надо изучить проблему, придумать больше вариантов решений, используя какой-нибудь метод.
В дальнейшем мы будем придерживаться двух рабочих правил.
1. Все возможные решения, которые нам известны, следует наглядно сопоставить между собой.
2. Перечень возможных решений надо исследовать на полноту и при необходимости пополнить.
Для поиска новых вариантов решений можно использовать один из следующих методов: дерево решений; морфологические таблицы; конференции идей.
Для представления возможных вариантов решений и проверки их на полноту иногда используют метод дерево решений. С помощью дерева решений сложное решение иерархически расчленяется на элементы, причем эти решения становятся все более конкретными по мере того, как ветвление продвигается в низ.
Рассмотрим другую форму представления, которая позволяет произвести проверку возможных вариантов решений не их полноту. Он основан на ключевом понятии морфологическая таблица. Каждая клетка которой получается комбинацией значений некоторых характерных параметров проблемы. Каждая клетка представляет определенный тип решения с выбранными характеристиками. Некоторые клетки могут быть уже заполнены начальными вариантами решений, некоторые нет. Перед каждой не заполненной клеткой таблицы задаться вопрос: существуют ли варианты решений проблемы с такими характеристиками. Таким образом, можно значительно расширить множество известных вариантов решений.
Другим способом расширить поле возможных решений и на деле охватить все мыслимые варианты решений служит конференция идей. Во время конференции идей вокруг одной и той же проблемы определенное время группируется много идей, это происходит вследствие того, что большое число людей одновременно обдумывают одну и туже проблему и взаимно возбуждают друг у друга генерацию идей.
1.5 Последствия решений
Выяснить последствия наших решений означает, по сути, заглянуть в будущее. Один способов сделать это прогнозирование. Методы прогнозирования можно разделить на две группы: математическая оценка тенденций и экспертное прогнозирование.
Принцип математической оценки тенденцийзаключается в математическом описании закономерности некоторого процесса, наблюдаемого в прошлом, так, чтобы параметр времени tвходил как переменная. Тогда, если переменой tпридать значение, выходящее за пределы настоящего и уходящее в будущее, то с помощью такой модели можно распространить (экстраполировать) наблюдавшуюся в прошлом закономерность развития на будущее.
Применяя метод экспертного прогнозирования, совершено сознательно исходят из предположения, что в будущем процессы в основном протекают таким же образом, как и до сих пор. Сознательно учитывают возможность скачков в процессах развития. Наиболее известный метод Делфи. Делфи– это метод опроса. Собрание специалистов по прогнозированию формулирует вопрос, относящийся к будущему. Этот вопрос в письменном виде предлагается нескольким экспертам в данной области. Собранные ответы обобщаются и сводятся в наглядную сопоставимую таблицу. Обзор возвращается экспертам. Таким образом, они узнают, что по этому вопросу предложили другие специалисты. Собственная точка зрения эксперта может как совпадать с мнением большинства, так и значительно отклоняться от нее. Потом повторяют еще несколько раз данный опрос. В результате этого выявляется самый правдоподобный прогноз.
1.6 критерий решений.
На пути подготовки решения мы уже продвинулись довольно далеко и стоим перед необходимостью оценить резного рода возможные решения по их последствиям.--PAGE_BREAK--
Мы уже собрали возможные решения, упорядочили их, систематизировали и расширили. Теперь перед нами стоит задача расположить их по степени значимости, чтобы затем отыскать оптимальное решение. В этом именно и состоит поставленная нами задача подготовки решения. Каждая оценка требует установление критериев. Количество критериев может быть как одно, так и больше одного. По этой причине выделяют одно критерийную и много критерийную оценку.
В дальнейшем нас будет интересовать два вопроса: как найти правильный критерий для принятия решения и каким образом, в рамках данного критерия, найти целесообразные масштабы для оценки тех или иных решений?
Критерии решений очень тесно связаны с последствиями решений. Если попробовать сгруппировать последствия решений на основании небольшого числа принципов, если при этой попытке упорядочения, одновременно их объединить и обобщить, то можно получить критерии решений. Обычно выделяют следующие типы критериев:
– технические критерии;
– технико-экономические критерии;
– социологические критерии;
– психологические критерии;
– эстетические критерии;
– социальные критерии.
Обратимся теперь к шкале оценке выбранного критерия. Выделяют следующие виды шкал:
– точные числа;
– приближенные числа;
– относительные числа;
– очки, пункты;
– оценки, пункты.
Если проблема имеет много критериев, то чтобы вычислить общую оценку из оценок по разным критериям, необходимо дать каждому критерию коэффициент, равный его значимости и показывающий его удельный вес в общей картине оцени. После этого можно вычислит общую оценку, равную суме произведения всех оценок на их удельный вес.
1.7 Поиск решения
Самый общий способ поиска оптимального решения заключается в поиске такого варианта решения, при котором общая оценка принимает самое благоприятное значение. Если число вариантов конечно-то их можно перебрать, а если бесконечно, то можно приблизиться к оптимальному варианту до заданной точности. Для нахождения оптимального решения часто используется методы математического программирования и теории оптимизации.
Также для поиска лучшего решения используется голосование, методы сравнения, дерево решений, графоаналитический метод, статистические методы, теория игр, решающие таблицы и многие другие методы предназначенные для частых случаев.
1.8 Извлечение уроков из принимаемых решений
После того как решение найдено, важно собрать и сохранить на будущее накопленный багаж знаний. Он поможет в дальнейшем при принятии решения, уточнит и ускорит его.
Особенно просто это получается при фиксированных правилах принятия решения. В правилах, которые сформулировали мы сами или получили от других лиц, например, в виде бинарных решающих матриц или решающих таблиц. Эти методы можно применять в случаях часто повторяющихся однотипных решений, когда, как в рассматриваемых ситуациях, меняются лишь параметры.
2. Практическое задание
2.1 Задание
Фирма рекламирует свою продукцию с использованием четырех средств: телевизора, радио, газет и афиш. Из различных рекламных экспериментов, которые проводились в прошлом, известно, что эти средства приводят к увеличению прибыли соответственно на 10, 3, 7 и 4 дол. в расчете на 1 дол., затраченный на рекламу. Распределение рекламного бюджета по различным средствам, подчинено следующим ограничениям:
а) полный бюджет не должен превосходить 500000 дол.;
б) следует расходовать не более 40% бюджета на телевидение и не более 20% бюджета на афиши;
в) вследствие привлекательности для подростков радио на него следует расходовать, по крайней мере, половину того, что планируется на телевидение.
Сколько средств следует направить на каждый вид рекламы, чтобы прибыль была максимальной.
2.2 Математическая модель
Решение представляется, как описание – сколько тратиться средств на каждый тип рекламы, при чем средства не могут быть отрицательными, т.е. нельзя забирать средства. Обозначим их как свободные переменными в соответствии с формулой 2.1.
/>(2.1)
где xi – объем денежных средств идущих на рекламу i-го типа;
n – количество типов рекламы, используемый предприятием.
Так как предприятие использует только четыре вида рекламных средств – телевиденье, радиовещание, газета, афиша-то nравно четырем.
Критерием задачи, и значит целевой функцией, является прибыль, приносимая рекламой. Нашей задачей максимизировать эту прибыль.
На основе данных, полученных из задания, можно построить целевую функцию в соответствии с формулой 2.2.
/>(2.2)
где W – целевая функция – прибыль от;
x1 – средства затраченные на телевизионную рекламу;
x2 – средства затраченные на радио рекламу;
x3 – средства затраченные на газетную рекламу;
x4 – средства затраченные на афишную рекламу.
В задание есть следующие ограничения: полный бюджет не должен превосходить 500 000 дол., т.е. /> дол.; следует расходовать не более 40% бюджета на телевидение и не более 20% бюджета на афиши, т.е. /> и />; вследствие привлекательности для подростков радио на него следует расходовать, по крайней мере, половину того, что планируется на телевидение, т.е. />.
Полученная система изображена на формуле (2.3).
/>(2.3)
Теперь надо избавиться от неравенства и перейти к равенству. Для этого введем неотрицательные фиктивные переменные, которые уравновесят не равенство (2.3).
/>(2.4)
На основе формул (2.1), (2.2) и (2.4), постоем математическую модель данной задача.
/>(2.5)
2.3 Метод решения
Существует много методов решения ЗЛП. Большинство из них предназначены для частных случаев. Графический метод – очень нагляден, но предназначен для задач, у которых количество базисных переменных не более двух. Эвристический метод может справиться с ЗЛП не традиционного вида, хотя заранее не может гарантировать результат. Транспортный метод также хорош, но применим для задач частного случая.
Наша задача является общим видом ЗЛП, поэтому необходимо решать ее универсальным методом. Таковым является симплекс метод – он решается все ЗЛП, имеющие решения.
Симплекс метод имеет следующий канонический вид математической модели.
Дано:
– n свободных переменных. Их значение мы можем выбирать сами. Предположим их равными нулю.
– m базисных переменных. Их значение определяется по линейному уравнению от свободных переменных, но т. к. свободные члены равны нулю, то базисные переменные равны значению свободных членов уравнений.
– Целевая функция выражена через линейное уравнение от свободных переменных.
Этот метод предназначен для нахождения минимума, поэтому чтобы найти максимум, надо в место /> использовать />
Приведем математическую модель нашей задачи в каноническом виде. продолжение
--PAGE_BREAK--
/>(2.6)
Математическая модель одновременно является начальным опорным решением. Оно оформляется в соответствии с таблицей 2.1.
Таблица 2.1
Своб. чл.
Свободная
переменная 1
…
Свободная
переменная j
…
Свободная
переменная n
W
Число
Число
Число
Число
Число
Число
Базисная переменная 1
Число
Число
Число
Число
Число
Число
…
Число
Число
Число
Число
Число
Число
Базисная переменная j
Число
Число
Число
Число
Число
Число
…
Число
Число
Число
Число
Число
Число
Базисная переменная m
Число
Число
Число
Число
Число
Число
Об оптимальности решения судят по значению коэффициентов в уравнении целевой функции. Решение оптимально только когда все значению коэффициентов в уравнении целевой функции не положительные.
Чтобы найти оптимальное решение необходимо переходить к новому базису так, чтобы коэффициентов в уравнении целевой функции стали отрицательными или нулевыми.
Переход к новому базису осуществляют по правилу прямоугольника по средствам разрешающего столбца и разрешающей строки. Разрешающий столбец берут тот, в котором коэффициентов в уравнении целевой функции больше нуля. Разрешающею строкой берут ту, в которой отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно.
В итоге после нескольких переходов к новому базису мы приходим к оптимальному решению: все свободные переменные равны нулю, все базисные переменные и целевая функция равны свободным членам.
2.4 Описание программы
2.4.1 Абстрактный класс симплекс таблицы
Программа имеет на главной форме таблицу. Она предназначена только для ввода начальных условий задачи, а все вычисления проводятся в специальном созданном классе TSimplex, который интегрирует в себе как данные о состоянии таблицы, так и методы для обработки этих данных. Таким образом, все вычисления выполняются в пределах данного класса и чтобы описать принцип и алгоритм работы программы надо описать этот класс.
2.4.2 Свойства класс TSimplex
Класс TSimplex имеет следующие свойства:
– n, m: integer – соответственно число свободных и число базисных переменных;
– w, b:array of extended – массивы, содержащие соответственно свободные члены и коэффициенты целевой функции;
– wb: extended – свободный член целевой функции;
– FTit, BTit: array of string – соответственно названия свободных и базисных переменых;
– a: array of array of extended – матрица коэффициентов линейных функций базисных переменых;
– result: TNextResult – результат последней операции;
– ir, jr: integer – соответственно разрешающая строка и разрешающий столбец;
– history: TStack – история о предыдущих операциях, позволяет вернуться назад.
Для полной ячности надо описять тип TNextResult и класс TStack.
Тип TNextResult описывает результат последней операции.
TNextResult = (nrFound=0, nrOporOk, nrOporFail, nrOptimOk, nrOptimFail, nrStackEmputy),
где nrFound – найдено решение;
nrOporOk – найден способ, как заменит базис, чтобы приблизиться к опорному решению;
nrOporFail – невозможно найти опорное решение, т.е. и вся задача не имеет решения;
nrOptimOk – найден способ, как заменит базис, чтобы приблизиться к оптимальному решению;
nrOptimFail – невозможно найти оптимальное решение, т.е. и вся задача не имеет решения;
nrStackEmputy – стек с историей о предыдущих ходах пуст, т.е. невозможно сделать шаг назад.
Клас TStack – стек, хранящий историю о сделанных шагах, позволяет откатить положение вычисления назад.
TIJ = record i, j: integer end;
TStack = class
top: integer; продолжение
--PAGE_BREAK--
stackIJ: array [0..1000] of TIJ;
end;
2.4.3 Методы класса TSimplex
Класс TSimplexимеет следующие методы:
– procedurenewBase– позволяет перейти к новому базису, причем разрешающая строка и разрешающий столбец указывается в свойствах ir, jr;
– functionnext: TNextResult– находит следующий шаг к опрорному решению или если оно найдено к оптимальному решению, причем сохраняет в свойстве historyпроделанный путь;
– procedureback– возвращается на один шаг назад, используя свойство history.
2.5 Решение
На основе начальных данных математической модели нашей задачи (2.6), построим симплекс таблицу в соответствии с рисунком 2.1.
/>
Рисунок 2.1 – Опорное решение
Т.к. свободные члены не отрицательные, то это опорное решение, на основе него мы получим оптимальное решение.
Т.к. есть коэффициенты в уравнении целевой функции, которые больше нуля, то решения не оптимально и поэтому надо перейти к новому базису.
Выберем разрешающим столбцом x1т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 10.
Выберем разрешающей строкой y2т. к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (0 / 0,6 = 0).
Выделим разрешающий столбец, строку и элемент.
Переедем к новому базису в соответствии с рисунком 2.2 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:
/>
Рисунок 2.2 – Первый шаг
Т.к. есть коэффициенты в уравнении целевой функции, которые больше нуля, то решения не оптимально и поэтому надо перейти к новому базису.
Выберем разрешающим столбцом x3т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 13,66.
Выберем разрешающей строкой y4т.к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (0 / 13,66 = 0).
Выделим разрешающий столбец, строку и элемент.
Переедем к новому базису в соответствии с рисунком 2.3 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:
/>
Рисунок 2.3 – Второй шаг
Т.к. есть коэффициенты в уравнении целевой функции, которые больше нуля, то решения не оптимально и поэтому надо перейти к новому базису.
Выберем разрешающим столбцом x2 т.к. коэффициентов целевой функции в этом столбце больше нуля и больше всех остальных положительных коэффициентов целевой функции, он равен 37.
Выберем разрешающей строкой y1т.к. отношение свободного члена к числу в соответствующей строке и разрешающем столбце минимально и не отрицательно (500000 / 5 = 100000).
Выделим разрешающий столбец, строку и элемент.
Переедем к новому базису в соответствии с рисунком 2.4 по правилу, высчитывая новые коэффициенты по правилу прямоугольника:
/>
Рисунок 2.4 – Оптимальное решение
Т.к. есть коэффициенты в уравнении целевой функции, которые больше нуля, то это решения оптимальное.
Ответ: />
Заключение
В данной курсовой я узнал об основе теории принятия решения, также научился находить решение задачи линейного программирования в общем случае.
Список используемых источников
Кремер Н.Ш., Путко Б.А. и др. Исследование операций в экономике. Учебное пособие. М.: Юнити, 1997
Федосеев В.В., Гармаш А.Н. и др. Экономико-математические методы и прикладные модели. М.: Юнити, 2001
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986
Житников С.А., Биржанова З.Н. и др. Экономико-математические методы и модели. Караганда: издательство КЭУ, 1998
Замков О.О., Толстопятенко А.В. Математические методы в экономике. М.: ДИС, 1997
Колемаев В.А. Математическая экономика. М., 1998
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1998
Лопатников Л.И. Экономико-математический словарь. М.: Наука, 1987
Малыхин В.И. Математическое моделирование экономики. М., 1998
Мельник М.М. Экономико-математические методы в планировании и управлении материально-техническим снабжением. – М.: Высшая школа, 1990
Нусупбеков С.И., Устенова О.Ж. Математические методы моделирования экономических систем. Алматы: Эверо, 2002
Спирин А.А., Фомин Г.П. Экономико-математические методы и модели в торговле. – М.: Экономика, 1988