АВТОМАТИЗИРОВАННАЯ ЛАБОРАТОРНАЯ РАБОТА «ПРИНЯТИЕ КООПЕРАТИВНЫХ РЕШЕНИЙ» - Студенческий научный форум

IV Международная студенческая научная конференция Студенческий научный форум - 2012

АВТОМАТИЗИРОВАННАЯ ЛАБОРАТОРНАЯ РАБОТА «ПРИНЯТИЕ КООПЕРАТИВНЫХ РЕШЕНИЙ»

 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение

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

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

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

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

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

В рамках проекта были описаны основные теоретические вопросы Теории кооперативных игр. Разработаны и реализованы алгоритмы расчетов С-ядра, N-ядра, вектора Шепли, векторов Эксцессов, проверки игры на выпуклость, методики проведения лабораторной работы. Так же была реализована автоматизированная система «Принятие кооперативных решений».

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

1 Определение проблемы и постановка задачи

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

  • Антагонистические игры (Моделирование систем, раздел теория игр);
  • ППП Решения задач линейного программирования (Исследование операций);
  • Simplexwin 3.1 (Исследование операций);
  • TORA (Исследование операций) и т.д.

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

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

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

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

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

2 Некоторые вопросы кооперативного принятия решений 

2.1 Кооперативные игры

В разрабатываемой автоматизированной лабораторной работе «Принятие кооперативных решений» рассматривается игра трех лиц. Изначально игра представляется в нормальной форме. Нормальная форма представления игры  лиц ( =3), представлена ниже: ,

где  - количество игроков;

       - множество стратегий  -го игрока;

        - функция выигрыша  -го игрока.

В ситуации   -й игрок получает величину  Цель каждого игрока  - максимизировать свой выигрыш.

Любое подмножество  множества  называется коалицией. Коалиция может состоять из одного игрока или быть пустой. Множество всех возможных коалиций равно  [1].

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

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

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

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

2.2 Характеристическая функция

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

Рассмотрим игру  лиц  с непротивоположными интересами, в которой выигрыши игроков трансферабельны.

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

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

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

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

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

Пусть в игре  образовалась коалиция .  То, что игроки из  действуют совместно, означает, что стратегиями этой коалиции являются всевозможные стратегии входящих в нее игроков, то есть элементы множества [2]:

где  - стратегия i - го игрока.

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

Цель коалиции  - подходящим выбором своей стратегии  добиться возможно большего выигрыша [21]:

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

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

Будем предполагать, что для любого     существует.

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

 - игра в форме характеристической функции [1].

2.3 С-ядро

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

Так как любой дележ из С-ядра недоминируем, то ни у кого из игроков (также и коалиций) не будет возражений против реализации этого.

Теорема: Для того чтобы дележ  ( - множество всех дележей в игре) принадлежал С-ядру, необходимо и достаточно, чтобы для любой коалиции  выполнялось неравенство[1]:

     .                                                            (2.2)

Следствие: С-ядро любой игры  является замкнутым выпуклым многогранником. Из-за жесткости условия, определяющего С-ядро, оно часто бывает пустым [1].

Игра  с тремя игроками имеет не пустое С-ядро тогда и только тогда, когда:

2.4 N-ядро

Необходимо иметь решение, которое бы принадлежало ядру, если С-ядро не пусто. N-ядро является таким решением, оно занимает центральное положение внутри С-ядра [6]. N-ядро представляет собой решения кооперативных игр, основанные на минимизации степени неудовлетворённости выигрышем подмножеств участников игры (коалиций).

Дана игра . Задано множество дележей . Любому дележу  поставим в соответствие вектор  [1]: для всех собственных коалиций   .                               

На множестве  существует единственное распределение , такое, что для любого  вектор  предпочтительнее в смысле лексиминного порядка  вектора . Дележ  называют N-ядром игры [1].

Интуитивно N-ядро представляет распределение выигрыша, на котором степень неудовлетворённости самых неудовлетворенных коалиций, измеряемая величиной их эксцесса, будет наименьшей.

2.5 Вектор Шепли

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

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

Для игры  вектор Шепли  распределяет прибыль  максимальной коалиции следующим образом [1]: ,

где s- размер коалиции S,

          - средняя маргинальная прибыль игрока i, взятая по всем коалицям .

Т.к. вектор Шепли является дележом, то

.

2.6 Вектор эксцессов 

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

Для произвольных  и ее вектора выигрышей  эксцессом коалиции  относительно вектора  называется разность [2]:

.

Эта разность выражает отрицательную относительную полезность выигрыша для коалиции .

Вектор значений эксцессов , называется вектором эксцессов для , при этом  [1].

2.7 Выпуклость игры

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

Определение. Кооперативная игра  является выпуклой, если она удовлетворяет одному из двух эквивалентных свойств [1]:

и/или

где по соглашению      

3 Алгоритмы определения некоторых значений игры

3.1 Алгоритм расчета характеристической функции игры

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

Рассмотрим кооперативную игру трех лиц (N=3). В такой игре у нас есть семь различных коалиций игроков: {X}, {Y}, {Z}, {XY}, {XZ}, {YZ}, {XYZ}.

На первоначальном этапе кооперативная игра задана в нормальной форме. Исходные данные:

  • стратегии игроков X, Y, Z;
  • функции выигрышей игроков , и .

Этап второй: Чтобы перейти от нормальной формы игры к форме игры в форме характеристической функции, необходимо найти характеристическую функцию для каждой коалиции. Для этого сначала необходимо решить 6 антагонистических игр (для промежуточных коалиций) [1].

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

где i - номер стратегии игрока ,

      j - номер совместной чистой стратегия коалиции  .

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

,

где i - номер стратегии игрока y,

      j - номер совместной чистой стратегия коалиции  .

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

,

где i - номер стратегии игрока ,

      j - номер совместной чистой стратегия коалиции  .

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

,

где i - номер совместной чистой стратегия коалиции  ,

      j - номер стратегии игрока .

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

,

где i - номер совместной чистой стратегия коалиции  ,

      j - номер стратегии игрока y.

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

,

где i - номер совместной чистой стратегия коалиции  ,

      j - номер стратегии игрока x.

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

Алгоритм решения антагонистической игры методом линейного программирования представлен ниже в пункте 3.3.

Этап четвертый: Характеристическая функция максимальной коалиции N  определяется как максимальное значение функции выигрыша всех трех игроков, определенной на множестве всех возможных стратегий:

 

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

Алгоритм распознавания формул представлен в пункте 3.2.

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

На диаграмме (рисунок 3.1) представлен алгоритм получения значения характеристической функции игры.

На рисунке 3.2 представлена декомпозиция этапа «Определить характеристическую функцию коалиции» алгоритма получения значения характеристической функции игры. На диаграмме представлен алгоритм нахождения характеристической функции для определенной коалиции игры.

3.2 Алгоритм распознавания формул для трех переменных

Алгоритм распознавания формул для трех переменных предназначен для преобразования формулы, помещенной в массив символов. При этом предполагается, что:

  • имена переменных начинаются с символов английского алфавита и содержат только символы и цифры;
  • символы вводятся только большими буквами;
  • в формуле используются только 5 арифметических операций: «+» - сложение, «-» - вычитание, «*» - умножение, «/» - деление, «^» - возведение в степень;
  • в формуле допустимо использование скобок вида ´(´,´)´;
  • в формуле допустимо использование следующих функций: COS - косинус, SIN - синус, ABS - по модулю, LN - натуральный логарифм, EXP - экспонента, SQRT - корень квадратный (вводить функцию необходимо так, чтобы она занимала 4 позиции, а недостающие символы заменять пробелами);
  • в случае если алгоритм не может обработать формулу, то в качестве результата выдается "ERROR".

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

Суть алгоритма заключается в следующем [12]:

Шаг 1: Преобразование выражения в польскую запись.

После того, как пользователь ввел формулу, просматривается исходная строка символов слева направо, если встречается:

  • 1.Символ английского алфавита, значит, мы имеем переменную - считываем ее имя и помещаем в результирующую строку.
  • 2.Цифра, значит мы имеем число - считываем его полностью и помещаем в результирующую строку.
  • 3.Открывающаяся скобка ´(´ - помещаем ее на стек.
  • 4.Закрывающаяся скобка ´)´:
  • 4.1.переносим операции со стека в результирующую строку до момента пока не сняли со стека ´(´, а открывающуюся скобку в результат не помещаем;
  • 4.2.если открывающаяся скобка так и не встретилась, значит, в исходном выражении неправильно расставлены скобки, тогда помещаем в результат "ERROR" и выходим из алгоритма.
  • 5.Операция:
  • 5.1.переносим в результат операции с вершины стека до тех пор, пока стек не пуст и приоритет текущей операции меньше либо равен приоритету операции находящейся на вершине стека;
  • 5.2.затем помещаем текущую операцию на стек;
  • 5.3.после окончания прохода по исходному массиву, переносим операции, оставшиеся на стеке, в результат;
  • 5.4.если на стеке осталась открывающаяся скобка, значит, в обрабатываемом выражении содержится ошибка, а, следовательно, помещаем в результат "ERROR".
  • 6. Функция:
  • 6.1. считываем 4 позиции;
  • 6.2. далее аналогично этапам 5.1 - 5.4.

Шаг 2: Вычисление выражения представленного в польской записи.

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

  • 1) обрабатываемый элемент - переменная, помещаем ее значение на стек;
  • 2) обрабатываемый элемент - число, помещаем его на стек;
  • 3) обрабатываемый элемент - операция, снимаем со стека два элемента, и выполняем операцию, полученный результат помещаем на стек;
  • 4) обрабатываемый элемент - функция, снимаем со стека элемент, и выполняем вычисление, полученный результат помещаем на стек.

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

Описанные алгоритмы формально представлены на рисунках 3.3, 3.4 и 3.5.

На рисунке 3.3 показана общая схема алгоритма распознавания формул для трех переменных.

На рисунке 3.4 более детально представлен шаг алгоритма распознавания формул для трех переменных «Преобразовать выражение в польскую запись».

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

           

3.3 Алгоритм решения антагонистической игры методом линейного программирования

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

Применение данного метода для антагонистической игры имеет некоторые особенности:

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

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

Для моделирования работы алгоритма решения платежной матрицы методом линейного программирования  была построена диаграмма, представленная на рисунке 3.6.

3.4 Алгоритм расчета  С-ядра

В автоматизированной лабораторной работе «Принятие кооперативных решений» для нахождения С-ядра игры трех (N=3) лиц был разработан  следующий алгоритм.

Идея алгоритма заключается в пошаговом выполнении определенных этапов:

На  первом этапе  необходимо проверить наличие С-ядра.

Для того, чтобы определить, имеет ли игра С-ядро, проверим выполнение пяти условий (2.3)-(2.7).

Если все условия выполняются, следовательно, игра имеет С-ядро.

На втором этапе необходимо определить С-ядро игры (если оно существует).

Для нахождения С-ядра необходимо найти множество дележей:,

для которых выполняются следующие ограничения (2.2):

На третьем этапе для удобства расчетов перейдем к новым переменным (по прибыли от коопераций).

Тогда система ограничений примет следующий вид:      ,                             

На четвертом этапе необходимо построить симплекс треугольник и определить количество точек С-ядра.

Координаты вершин треугольника равны: (k,0,0), (0,k,0), (0,0,k),

где . Прямые (3.2), (3.3), (3.4) ограничивающие область С-ядра параллельны соответствующим сторонам треугольника, т.е прямая a+b параллельна стороне ab, прямая b+c параллельна стороне bc, а прямая a+c параллельна стороне ac.

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

На пятом этапе рассчитаем координаты полученных ранее точек.

Правые части уравнений (3.1), (3.2), (3.3), (3.4) далее будем называть abc, ab, ac и bc соответственно. Т.е a+b+c назовем abc, a+b назовем ab и т.д. по аналогии.

Если условие (ab+bc+ac)/2 = abc  выполняется, то С-ядро - единственная точка. Координаты которой рассчитываются по формулам:

a=ac+ac-abc,

b=bc-abc+ab,

c=abc-ab.

Если выполняется условие:

(ac+bc<abc),                                                          (3.5)

или (ab+ac<abc),                                                          (3.6)

или (ab+bc<abc),                                                          (3.7)

то С-ядро - это отрезок с координатами:

k=0,                                                                  (3.8)

                l=kl,                                                                  (3.9)

m=abc-l,                                                         (3.10)

 

k=0,                                                               (3.11)

m=km,                                                           (3.12)

l=abc-m,                                                       (3.13)

где 1)  k=c, l=a, m=b в случае если выполняется условие (3.5).

  • 2) k=a, l=c, m=b в случае если выполняется условие (3.6).
  • 3) k=b, l=c, m=a в случае если выполняется условие (3.7).

Если одновременно выполняются условия:

(ab+ac>=abc),                                                     (3.14)

(ab+bc>=abc),                                                    (3.15)

(ac+bc>=abc),                                                    (3.16)

то С-ядро ограничено тремя точками, которые рассчитываются по формуле:

l=abc-km,                                                     (3.17)

                       k=abc-m-l,                                                    (3.18)

m=abc-kl,                                                      (3.19)

где для первой точки k=a,l=b,c=m. Для второй точки k=c,b=l,a=m. Для третей точки k=b,l=a,c=m.

Если выполняется одно из условий (3.14) - (3.16), то по формулам (3.17) - (3.19) можно рассчитать координаты соответствующей точки.

Если выполняются два из условий (3.14)  - (3.16) и одно из условий (3.5) - (3.7), то С-ядро ограничено четырьмя точками. Координаты точек будут рассчитываться по формулам (3.8) - (3.13) и (3.17) - (3.19) для соответствующих ограничений.

           Если выполняется одно из условий (3.14)  - (3.16) и два из условий (3.5) - (3.7), то С-ядро ограничено пятью точками. Координаты точек будут рассчитываться по формулам (3.8) - (3.13) и (3.17) - (3.19) для соответствующих ограничений.

Если одновременно выполняются условия (3.5) - (3.7), то С-ядро ограничено шестью точками. Координаты точек рассчитываются по формулам (3.8) - (3.13).

Если выполняется одно из условий (3.5) - (3.7), то по формулам (3.8) - (3.13) можно рассчитать координаты соответствующей точки.

На шестом этапе осуществляем переход от новых переменных к переменным  и получаем С-ядро игры.

Переход осуществляется путем увеличения соответствующих координат  всех точек на значения , , . Т.е. 

a+ ,

b+ ,

c+ .

 

Ниже наглядно представим описанный выше алгоритм.

На рисунке 3.7 представлен общий алгоритм расчета С-ядра игры.

На рисунке 3.8 представлена декомпозиция этапа алгоритма С-ядра игры «Проверить наличие С-ядра».

На рисунке 3.9 представлена декомпозиция этапа алгоритма расчета С-ядра «Расчет С-ядра в новых переменных».

3.5 Расчет  N-ядра

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

На  первом этапе необходимо проверить наличие С-ядра.

Если С-ядро существует, то переходим на второй этап. Иначе N-ядро определяется как центр «анти С-ядра»:

x = ,      y = ,        z = .                  

На втором этапе для определения координат N-ядра, используем формулы:

                                          x = ,        y = ,         z =  ,

где  - количество граничных точек C-ядра;

        - координаты точек N-ядра;

   - координаты i-ой вершины, рассчитанного ранее С-ядра.

3.6 Алгоритм расчета вектора Шепли

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

Для определения   воспользуемся следующей формулой:.

Для определения   воспользуемся следующей формулой:.

Для определения   воспользуемся следующей формулой:,

где  (i=1..3) - значения вектора Шепли

        - значения характеристической функции игры.

3.7 Алгоритм расчета векторов эксцессов

В рамках разрабатываемого проекта рассчитывается вектор эксцессов для вектора Шепли и для N-ядра.

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

где  - значения характеристической функции игры;

(i=1..3) - значения вектора Шепли.

Вектор эксцессов для N-ядра рассчитывается по следующей формуле:,

 где  - значения характеристической функции игры;

        (i=1..3) - координаты N-ядра.

3.8 Проверка выпуклости игры

Алгоритм проверке игры на выпуклость осуществляется в три этапа:

На первом этапе проверим условие для первого игрока:.

На втором этапе проверим условие для второго игрока:.

На третьем  этапе проверим условие для третьего игрока:

,

где  - значения характеристической функции

Если хоть одно условие не выполняется, то игра не выпукла.

4 Методика проведения лабораторной работы

  Цель лабораторной работы:

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

Алгоритм проведения лабораторной работы:

  • 1. Получение варианта задания у преподавателя;
  • 2. Запуск системы «Принятие кооперативных решений»;
  • 3. Определение характеристической функции:

3.1. При выборе пользователем пункта меню «Рассчитать характеристическую функцию»:

  • 3.1.1. Система открывает перед пользователем форму, где необходимо ввести все данные для расчета характеристической функции:

            3.1.2. Пользователь вводит количество стратегий каждого игрока; 

а. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлогает ввести данные заново, очистив соответствующие поля.

б. Если пользователь заполнил не все требуемые системой поля система уведомляет об этом пользователя и предлагает ему ввести недостающие данные.

3.1.3. Пользователь определяет размерности массивов данных путем нажатия на кнопку «Запомнить размерность»;

Если  пользователь перешёл  к вводу элементов массивов данных после ввода количества стратегий игроков, не нажав на кнопку «Запомнить размерность», система уведомляет пользователя о том, что размерности массивов данных не заданы и предлагает пользователю нажать на кнопку «Заполнить размерность».

3.1.4.   Пользователь вводит стратегии для игроков X, Y и Z;

а. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

3.1.5. Пользователь вводит функцию для нахождения элементов платежной матрицы;

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

3.1.6. Пользователь выбирает коалиции игроков, играющие друг против друга;

3.1.7. Получить искомую матрицу пользователь может путем нажатия на кнопку «Рассчитать»;

3.1.8. Система выводит платежную матрицу и соответствующую цену игры после нажатия пользователем на кнопку;

3.1.9. Для нахождения следующих пяти платежных матриц и цен игр пользователь возвращается к шагу 3.1.5 шесть раз;

3.1.10. При помощи нажатия на кнопку «Записать», введенные данные сохраняются системой для последующих вычислений;

3.2. При выборе пользователем пункта меню «Ввод характеристической функции»:

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

3.2.2. Пользователь вводит значения характеристической функции;

а. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

3.2.3. При помощи нажатия на кнопку «Записать», введенные данные сохраняются системой для последующих вычислений;

4. Пользователь переходит на вкладку «Рассчитать С-ядро»:

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

б. Если С-ядро не существует, система сообщает об этом пользователю.

4.1. Система предлагает заполнить поля ограничений для новых переменных (по прибыли от кооперации: a, b, c, a+b, a+c, b+c, a+b+c).

  4.2. Пользователь заполняет поля ограничений для новых переменных: a, b, c, a+b, a+c, b+c, a+b+c.

a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

4.3. Система считывает введенные пользователем значения ограничений для новых переменных (a, b, c, a+b, b+c, c+a, a+b+c) и сравнивать их с уже рассчитанными ранее системой значениями данных (этих же) переменных(a, b, c, a+b, b+c, c+a, a+b+c).

a. Если пользователь определил неправильно рассчитанные данные, система сообщает пользователю ему об этом и просит повторно ввести ограничения для новых переменных.

4.4.  Система прорисовывает область симплекс треугольника.

4.4. Система прорисовывает прямые заданные уравнениями a+b<=Vx, b+a<=Vy, c+a<=Vz.

4.5. Система рассчитывает количество точек ограничивающих область С- ядра.

4.6. Система предлагает вести координаты точек С-ядра в новых переменных.

4.7. Пользователь заполняет поля для ввода координат точек С-ядра в новых переменных.

            a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

4.8. Система считывает введенные  пользователем значения координат точек в новых переменных и сравнивать их с уже рассчитанными ранее системой значениями.

            a. Если пользователь определил неправильно рассчитанные данные, система сообщает об этом пользователю и просит повторно ввести координаты точек.

4.9. Система предлагает перейти к исходным переменным и записать С-ядро.

4.10. Пользователь заполняет поля для ввода координат вершин С-ядра.

a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

4.11. Система считывает введенные пользователем значения координат вершин С-ядра и сравнивает их с уже рассчитанными ранее системой значениями.

            a. Если пользователь определил неправильно рассчитанные данные, система сообщает об этом  пользователю и просит повторно определить вершины С-ядра.

4.12. Система должна выводить сообщение «С-ядро определено верно», если определенные пользователем значения совпадают со значениями рассчитанными системой.

5. Пользователь переходит к проверке функции на выпуклость, нажав на кнопку «Проверка на выпуклость».

5.1. Система предлагает пользователю определить: выпукла или вогнута функция.

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

            a. Если пользователь неправильно определил: выпукла или вогнута функция, система сообщает пользователю об этом и предлагает ему заново определить состояние функции.

6. Пользователь переходит к расчету N-ядра.

6.1. Система предлагает ввести координаты N-ядра.

6.2. Пользователь вводит координаты N-ядра:

a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

6.3. Система считывает определенные пользователем значения координат N-ядра и сравнивает их с уже рассчитанными ранее системой значениями.

                a. Если пользователь определил неправильно рассчитанные данные, система сообщает пользователю об этом и просит повторно определить координаты точек.

7. Пользователь переходит на вкладку «рассчитать вектор Шепли»

7.1. Система предлагает ввести координаты вектора Шепли.

7.2. Пользователь вводит значения вектора Шепли.

      a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

7.3. Система считывает определенные пользователем значения вектора Шепли и сравнивает их с уже рассчитанными ранее системой значениями.

a. Если пользователь определил неправильно рассчитанные данные, система сообщает пользователю об этом и просит повторно ввести координаты точек.

8. Пользователь переходит на вкладку «Рассчитать вектор Эксцессов»;

8.1 Система предлагает ввести координаты векторов Эксцессов для N-ядра и для вектора Шепли.

8.2 . Пользователь вводит значения векторов Эксцессов для N-ядра и для вектора Шепли.

           a. Если пользователь ввел некорректные данные, система уведомляет его об этом и предлагает ввести данные заново, очистив соответствующие поля.

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

8.3 Система считывает определенные пользователем значения векторов Эксцессов и сравнивает их с уже рассчитанными ранее системой значениями.

            a. Если пользователь определил неправильно рассчитанные данные, система сообщает ему об этом и просит повторно ввести координаты точек.

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

a. Если в ходе решения лабораторной работы, студентом был пропущен какой-либо этап вычислений, система не предоставит итоговый отчет о проделанной работе, а выдаст сообщение «Не все этапы решений пройдены! Вернитесь к пропущенным шагам для завершения работы».

 

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

На диаграмме представленной ниже отражено взаимодействие между объектами  пользователь и система. В роли пользователя выступает студент, а в роли системы - разрабатываемая автоматизированная лабораторная работа. 

На рисунке 4.1 представлен алгоритм проведения лабораторной работы разрабатываемой системы.

5 Описание программной реализации системы

5.1 Назначение автоматизированной системы

Автоматизированная лабораторная работа «Принятие кооперативных решений»  предназначена для проведения лабораторной работ в рамках курса «Моделирования систем». Так же автоматизированная лабораторная работа может применена  в любой другой дисциплине, которая включает изучение «Теории игр».

Автоматизированная лабораторная работа «Принятие кооперативных решений» предназначена для:

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

5.2 Функциональные возможности системы

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

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

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

На рисунке 5.1 приведены функции разрабатываемой системы.

5.3 Описание интерфейса

Интерфейс автоматизированной системы "Принятие кооперативных решений" разработан с учетом всех условий выполнения лабораторной работы по предмету «Моделирование систем» (раздел «Теория игр»):

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

На рисунке 5.2 представлена главная форма автоматизированной системы. Данная форма содержит:

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

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

  • ввод значений характеристической функции игры;
  • расчет значений характеристической функции игры.

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

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

Если же пользователем были пропущены некоторые поля для ввода или вообще не заполнены, то система выдает сообщение об ошибке. Если была нажата кнопка «Выход», но не нажата перед этим кнопка «Запомнить», система выдает соответствующее сообщение.

На рисунке 5.4 представлена форма для расчета характеристической функции игры.

Форма содержит:

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

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

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

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

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

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

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

  • пользователь пропустил ввод каких-либо данных;
  • пользователь неправильно ввел формулу для расчета характеристической функции;
  • пользователь неправильно выбрал играющих друг против друга коалиций игроков или вообще пропустил этот шаг;
  • пользователь пропустил нажатие кнопки «Запомнить размерность».

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

Вторым этапом является расчет С-ядра. Для перехода на соответствующую форму необходимо выбрать пункт меню "С-ядро" на главной форме. Но если С-ядра не существует, то система выдаст соответствующее сообщение «С-ядро отсутствует!» и не откроет форму. На рисунке 5.5 изображена форма для расчета С-ядра.

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

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

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

  • поля для ввода значений координат С-ядра;
  • кнопка "Проверить", с помощью нажатия на которую пользователь может проверить правильность рассчитанных значений координат С-ядра;

 

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

 

Если значения координат точек введены пользователем неверно, то система выдает сообщение об ошибке «Точки введены не верно!»

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

После определения значений координат С-ядра необходимо перейти к этапу проверки игры на выпуклость (рисунок 5.7).

Кнопка "Проверить" служит для проверки правильности выбранного решения. После нажатия на нее система выдает сообщение о правильности выбора пользователя «Верно! Игра не выпукла!» а затем открывает форму для проверки правильности определения неравенств и ограничений (рисунок 5.8);

Кнопка «Проверить» служит для проверки правильности произведенных расчетов. При нажатии на данную кнопку система проверяет правильность введенных пользователем данных и выдает соответствующие сообщения.

Следующим этапом является расчет значений координат N-ядра. Форма для работы с N-ядром также содержит поля для ввода значений координат N-ядра, а также кнопку "Проверить", при нажатии на которую система проверяет правильность введенных пользователем данных и выдает соответствующее сообщение «N-ядро рассчитано верно!»;

Если пользователь нажал на кнопку «Проверить», но перед этим не ввел значения в поля для ввода данных или ввел их не полностью, то система выдает ошибку.

На следующем этапе пользователю необходимо рассчитать значения вектора Шепли. Переход к данному этапу осуществляется с помощью пункта меню на главной форме с соответствующим названием. Форма изображена на рисунке 5.9.

Кнопка «Проверить» служит для проверки правильности произведенных расчетов. При нажатии на данную кнопку система проверяет правильность введенных пользователем данных и выдает соответствующие сообщения «Вектор Шепли рассчитан верно!» или «Вектор Шепли рассчитан неверно!»;

Если пользователь нажал на кнопку «Проверить», но перед этим не ввел значения в поля для ввода данных или ввел их не полностью, то система выдает ошибку.

 Одним из-за заключительных этапов лабораторной работы является расчет векторов эксцессов для вектора Шепли и для N-ядра. Для перехода на данный этап необходимо выбрать пункт меню "Вектор эксцессов" на главной форме (рисунок 5.2).

 После чего откроется форма для расчета значений векторов эксцессов (рисунок 5.10), но только в том случае, если на предыдущих этапах были успешно рассчитаны значения вектора Шепли и N-ядра, иначе система выдает сообщение «Для расчета векторов эксцессов сначала необходимо рассчитать вектора Шепли и N-ядра! Вернитесь к пропущенным этапам!».

Заключительным этапом лабораторной работы является просмотр отчета о результатах выполнения лабораторной работы, который можно просмотреть, нажав на кнопку «Все выполнено!» (рисунок 5.2).

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

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

 

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

 

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

Заключение

Результатом работы является автоматизированная лабораторная работа «Принятие кооперативных решений».

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

В процессе работы были достигнуты следующие результаты:

  • 1.исследован теоретический материал по кооперативным играм;
  • 2.изучен метод польской записи;
  • 3.построен алгоритм распознавания формулы для трех переменных;
  • 4.разработан и реализован алгоритм построения характеристической функции;
  • 5.разработан и реализован алгоритм определения С-ядра игры;
  • 6.реализован алгоритм определения N-ядра;
  • 7.реализован алгоритм вычисления вектора Шепли;
  • 8.реализован алгоритм вычисления векторов эксцессов;
  • 9.разработан и реализован алгоритм проверки выпуклости игры;
  • 10. разработан алгоритм выполнения лабораторной работы;
  • 11. проведен обзор аналогов;
  • 12. выполнена программная реализация системы;
  • 13. проведено тестирование программного продукта;
  • 14. осуществлено практическое внедрение АС.

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

Программная реализация системы выполнена с помощью языка Pascal на платформе Delphi 7.0.

Была произведена апробация системы среди студентов групп 426 - 1,2. В результате апробации были выявлены и устранены все недочеты системы.

На данный момент автоматизированная система «Принятие кооперативных решений» используется для проведения лабораторных работ по предмету «Моделирование систем» (раздел «Теория игр») на кафедре АОИ. Помимо этого, программный продукт может быть использован для проведения занятий и по другим предметам, которые включают в свою программу изучение теории игр.

Имеется акт о внедрении на кафедре АОИ.

Список используемых источников

  • 1.Салмина Н.Ю. Моделирование систем: Учебное пособие. - Томск: Томский государственный университет систем управления и радиоэлектроники, 2003. - 197 с.
  • 2.Оуэн Г., Теория игр, пер. с англ., М., 1971.
  • 3.Вендров А.М., Проектирование программного обеспечения экономически информационных систем: Учебник - 2-е изд., перераб. и доп. - М.: Финансы и статистика,2006 - 544с.
  • 4.Дж. Рамбо, М. Блаха, UML 2.0 Объетно-ориентированое моделирование и разработка. 2-е изд., - СПб.: Питер,2007. - 544 с.: ил
  • 5.А. В. Ахо, Р. Сети, Д. Д. Ульман. Компиляторы: принципы, технологии и инструменты. М.: «Вильямс», 2003. С. 51.
  • 6.БондареваО.Н., "Теория ядра вигреnлиц",Вестник Ленинградского университета. Серия мат., мех., астр., 1962, №13(3),141-142
  • 7.Программирование в Delphi. Характеристика Delphi и ее место а современном мире // [Электронный ресурс]. - Режим доступа к сайту:www. pascal-programm.narod.ru/DelphiHarakteristika.html
  • 8.Мир ПК // [Электронный ресурс]. - Режим доступа к сайту:www.pkks.ucoz.ru/index/kharakteristiki_proekta_delphi/0-49
  • 9.Методические указания по преддипломной практике и дипломированию для студентов специальности 230102 «Автоматизированные системы обработки информации и управления», И.И. Веберова, 2010 г.
  • 10. Данилов Н.Н., Игровые модели принятия решений. - Кемерово, 1981.
  • 11. Технико-экономическое обоснование стоимости программных систем: методические указания по выполнению экономической части дипломного проекта для студентов специальности 230102 «Автоматизированные системы обработки информации и управления» / Ю.П. Ехлаков, Б.А. Рыбалов; Томский государственный университет систем управления и радиоэлектроники, Кафедра автоматизации обработки информации. - Томск :, 2007. - 86 с.
  • 12. Официальный сайт «Программирование» [Электронный ресурс] - Режим доступа ксайту: http://trubetskoy1.narod.ru/ppn.html.
  • 13. Официальный сайт «Библиотека программиста» [Электронный ресурс] - Режим доступа к сайту: http://www.coders-library.ru/books-page-informatika-algoritms.
Просмотров работы: 92