РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ КОНКУРЕНТНОГО РЫНКА НА КЛАСТЕРНЫХ СИСТЕМАХ Авторы: Е.В. Болгова, А.С. Кириллов, Д.В. Леонов Научный. - презентация

1 РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ КОНКУРЕНТНОГО РЫНКА НА КЛАСТЕРНЫХ СИСТЕМАХ Авторы: Е.В. Болгова, А.С. Кириллов, Д.В. Леонов Научный руководитель: к.т.н., доцент кафедры МОИС ОГУ М.Ю. Нестеренко Оренбургский Государственный Университет Математический факультет

2 Введение В данной работе рассматривается подход к решению вычислительно-сложной задачи – построение оптимальной коалиции и распределение выигрыша в кооперативных играх для n игроков. Так же представлена схема параллельного алгоритма решения поставленной проблемы и проанализированы полученные результаты работы программной реализации алгоритма.

3 Основные понятия Обозначим через N множество всех игроков, N ={1, 2,..., n}, а через K любое его подмножество. Функция v(K) называется характеристической функцией игры, причем всего таких функций 2 n. Система {N, v} называется кооперативной игрой. Дележом X={x 1, x 2,…,x n } называется распределение выигрышей игроков, удовлетворяющее следующим условиям: 1) xi v( i ), i N (индивидуальной рациональности); 2) = v(N) (коллективной рациональности).

4 Модель конкурентного рынка Примером конкурентного рынка может служить конкуренция производителей программного обеспечения Для задания кооперативной игры требуется n·(n-1) матрица размера

5 Задание кооперативной игры A xy =

6 Матрицы выигрышей коалиций

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

8 Нахождение дележа Вычисление дележа производится по принципу Шепли по следующей формуле:

9 Схема работы параллельного алгоритма

10 График изменения эффективности

11 Зависимость времени работы от количества процессоров

12 Зависимость теоретической и практической эффективности от количества процессоров

13 Заключение Была рассмотрена идея сведения кооперативных игр к множеству биматричных для игроков с большим числом стратегий и предложен свой способ задания и решения кооперативных игр. Разработан и программно реализован параллельный алгоритм. После запуска программы на кластере ОГУ был проведен анализ полученных результатов.

14 Спасибо за внимание Вопросы