Музыкальный салон

Аннотация

   Данный  документ является пояснительной запиской к курсовому проекту по дисциплине «Технология разработки программных продуктов» на тему «Музыкальный салон». Необходимо разработать программный продукт, котрый сможет автоматизировать работу персонала музыкального магазина, музыкального салона.

   Основными разделами пояснительной записки являются:

   - Расчётная часть, содержащая постановку  задачи, требования к программному  средству, требования к составу  и параметрам технических средств,  информационное обеспечение задачи;

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

   - Графическая часть, содержащая  алгоритм решения задачи.

   Пояснительная записка состоит из __ страниц, __ иллюстраций, __ таблиц и _ приложений.

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

   Разработка  программного средства осуществлялась на компьютере: процессор Intel Core 2 Duo 6300, частота 1,86 Ггц, оперативная память 2 Гб, под управлением операционной системы Microsoft Windows Seven Ultimate, в среде разработки Borland C++ Builder 7. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание

Аннотация…………………………………………………………………………………...2

Введение……………………………………………………………………………………..4

1 Расчетная  часть…………………………………....………………………………………5

    1.1 Постановка задачи …………………………………………...…………..……….5

    1.2 Математическая модель…………………………………………………………  6

    1.3 Описание метода решения задачи……………………………………...………..6

    1.4 Информационное обеспечение ……..…………………………………...…........9 

2 Описательная  часть……………………………………………………………….............10

    2.1 Алгоритм решения задачи……………………….……………..…………….…..10

    2.2 Описание программы……………………………………………..………….…..10

    2.3 Контрольный пример………………………………………………………...…..12

    2.4 Инструкция пользователя………………………………………………….….…13

Заключение……………………………………………………………………..……….…..14

Список  сокращений…………………………………………………………………..…….15

Список  литературы…………………………………………………………….......……….16

Приложения…………………………………………………………………….………...…17 

 

    Введение

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

   Целью курсового проектирования является:

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

   - разработать техническую документацию  к разработанному программному  средству.

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

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

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

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

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

   

1. Расчетная часть
1. Постановка задачи

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

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

   Нормальная форма игры. Игра - это совокупность следующих множеств: множества игроков, множества стратегий этих игроков и множества выплат этим игрокам. В теории игр игру можно представить в виде матрицы размерностью m x n, называемой платежной матрицей. Платежная матрица — это запись в матричной форме денежных платежей/полезностей. В клетках матрицы указываются платежи, или стоимостные оценки ожидаемых исходов при принятии данной стратегии и возникновении определенного состояния внешней среды. Платежи могут иметь смысл положительных результатов или доходов, а также отрицательных результатов или расходов. В пером случае задача решается на максимизацию дохода, во втором — на минимизацию расходов. 

   A=   ₍₁₎

   A_ij – платёжная матрица размерностью m x n.

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

   α = max min a_ij – максимум из минимумов по строкам (максимин);

   β = min max a_ij – минимум из максимумов по столбцам (минимакс). 
 
 

2.  Математическая модель

  Если  α ≤ β, тогда такая игра имеет  седловую точку. Если платёжная матрица  не имеет седловой точки, то поиск  решения игры приводит к применению сложной стратегии состоящей  в случайном применении двух и  более стратегий с разными  частотами. Такая сложная стратегия  называется смешанной. В игре матрица, которой имеет размерность m x n Стратегии первого игрока задаються набором вероятностей, с которыми он применяет свои чистые стратегии.

           (2)

  Аналогично  вводяться вероятности второго  игрока.

           (3) 

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

            (4)

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

3. Описание  метода решения задачи

  Найти гарантированный выигрыш, определяемый нижней ценой игры α = max(ai), которая указывает на максимальную чистую стратегию. Верхняя цена игры β = min(bj).  
Если отсутствует седловая точка, так как a<>b, тогда цена игры находится в пределах α <= y <= β. Найти решение игры в смешанных стратегиях.  
Математические модели пары двойственных задач линейного программирования можно записать так:  
найти минимум функции f(x) при ограничениях:  
a₁₁u₁+a₂₁u_2+…+a_m1u_m >= 1  
a₁₂u₁+a₂₂u_2+…+a_2mu_m >= 1  
… 
a_n1u₁+a_n2u_2+…+a_nmu_m >= 1  
αx₂+βx₃ >= 1  
F(x) = u₁+u₂+…+u_m = min  
найти максимум функции F(y) при ограничениях:  
a₁₁z₁-a₁₂z₂+…+a_1nz_n <= 1  
a₂₁z₁-a₂₂z₂+…+a_2nz_n <= 1  
a_m1z₁-a_m2z₂+…+a_mnz_n <= 1   
Ф(y) = z₁+z₂+…+z_n = max  
Решить эти системы симплексным методом.  
Решить прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.  
Определить минимальное значение целевой функции F(X) = u₁ + u₂ + … + u_m при следующих условиях-ограничений.  
a₁₁u₁+a₂₁u_2+…+a_m1u_m >= 1  
a₁₂u₁+a₂₂u_2+…+a_m2u_m >= 1 
a₁₃u₁+a₂₃u_2+…+a_m3u_m >= 1  
Для построения первого опорного плана систему неравенств привести к системе уравнений путем введения дополнительных переменных (переход к канонической форме).  
a₁₁x₁ + a₂₁x₂ + a₃₁x₃ + a₄₁x₄ + a₅₁x₅-a₆₁x₆ + a₇₁x₇ + a₈₁x₈ = 1  
a₁₂x₁ + a₂₂x₂ + a₃₂x₃ + a₄₂x₄ + a₅₂x₅-a₆₂x₆ + a₇₂x₇ + a₈₂x₈ = 1  
a₁₃x₁ + a₂₃x₂ + a₃₃x₃ + a₄₃x₄ + a₅₃x₅-a₆₃x₆ + a₇₃x₇ + a₈₃x₈ = 1  
Если задача решается на минимум или элементы единичной матрицы отрицательны, свести задачу к нахождению максимума. Для этого умножить все строки на (-1) и искать первоначальный опорный план.  
-a₁₁x₁ - a₂₁x₂ - a₃₁x₃ + a₄₁x₄ + a₅₁x₅-a₆₁x₆ + a₇₁x₇ + a₈₁x₈ = 1  
-a₁₂x₁ - a₂₂x₂ - a₃₂x₃ + a₄₂x₄ + a₅₂x₅-a₆₂x₆ + a₇₂x₇ + a₈₂x₈ = 1  
-a₁₃x₁ - a₂₃x₂ - a₃₃x₃ + a₄₃x₄ + a₅₃x₅-a₆₃x₆ + a₇₃x₇ + a₈₃x₈ = 1  

     Таблица 1  - матрица коэффициентов A = a(ij) 

 

  Базисные  переменные - это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.  
Решить систему уравнений относительно базисных переменных: x₆, x₇, x₈.  
Полагая, что свободные переменные равны 0, получаем первый опорный план.

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

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

  Если в индексной строке находятся отрицательные коэффициенты, то текущий опорный план неоптимален.  
В качестве ведущего выбрать столбец, соответствующий переменной, у которой наибольший коэффициент по модулю.  
После этого вычислить значения D_i по строкам как частное от деления:  
          
и из них выбрать наименьшее. 
Разрешающий элемент находится на пересечении ведущего столбца и ведущей строки.  
Сформировать следующую часть симплексной таблицы.  
Вместо переменной x в план 1 войдет переменная x₆ .  
Строка, соответствующая переменной x₆  в плане 1, получена в результате деления всех элементов строки x₁ плана 0 на разрешающий элемент.  
В остальных клетках столбца x₆ плана 1 записать нули.  
Таким образом, в новом плане 1 заполнены строка x₆  и столбец x₆ .  
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.  
Для этого выбрать из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент.  
НЭ = СЭ - (А*В)/РЭ  
СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.  
Интерации заканчиваются тогда, когда индексная строка не содержит отрицательных элементов следовательно найден оптимальный план.