Оформление курсового проекта

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту на тему:

ФИНАЛЬНЫЕ ВЕРОЯТНОСТИ СОСТОЯНИЙ

Студент ______________________________ Набатников А.С.

подпись

Руководитель курсового проекта _______________ Жилкина Н.А.

подпись

Москва, 2014

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Московский государственный технический университет имени Н.Э. Баумана» Московский техникум космического приборостроения
(МТКП МГТУ им. Н.Э. Баумана)

УТВЕРЖДАЮ

Председатель ПЦК специальности 230115

Жилкина Н.А.

«_____»______________2014 г.

ЗАДАНИЕ

На выполнение курсового проекта

по дисциплине МДК.01.02 Прикладное программирование _______________

_____________________________________________________________________________

Студент________________________ Набатников А.С. ТМП 72 ____________________________

(фамилия, инициалы, индекс группы)

Руководитель_______________________ Жилкина Н.А. __________________________

(фамилия, инициалы)

График выполнения работы: 25% к 4 нед., 50% к 8 нед., 75% к 12 нед., 100% к 15 нед.

Тема курсового проекта

Финальные вероятности состояний ___________

Техническое задание

Написать программу для решения задачи нахождения предельной вероятности состояний с помощью уравнений Колмогорова __________

Оформление курсового проекта

3.1. Пояснительная записка на___ 26 ____ листах формата А4.

3.2. Перечень графического материала КП (плакаты, схемы, чертежи и т.п.) – схемы алгоритма программы

Дата выдачи задания «__ 2 __»_______ сентября ______2014 г.

Руководитель курсового проекта _________________________ Жилкина Н.А.

Содержание

1 Введение......................................................................................................................................... 3

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

3 Численный метод........................................................................................................................... 5

4 Ручной просчет............................................................................................................................... 8

5 Схема алгоритма программы...................................................................................................... 10

6 Инструкция по эксплуатации программы................................................................................. 14

7 Отладка.......................................................................................................................................... 15

8 Тестирование................................................................................................................................ 16

9 Заключение.................................................................................................................................... 18

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

Приложение А. Листинг программы............................................................................................ 20

Приложение Б. Результаты выполнения программы.................................................................. 23

1.ВВЕДЕНИЕ

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

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

Решение (удачное, неудачное, разумное, неразумное) - всякий определённый набор параметров, зависящих от человека.

Оптимальное - решение, которое по тем или другим признакам предпочтительнее других.

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

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

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

Марковский процесс (процесс без последействия) - случайный процесс, эволюция которого после любого заданного значения временного параметра t не зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот момент фиксировано (короче: "будущее" и "прошлое" процесса не зависят друг от друга при известном "настоящем").

2.ПОСТАНОВКА ЗАДАЧИ

Тема: Финальные вероятности состояний.

Требуется разработать программу для составления уравнений Колмогорова.

Входные данные отображены на рисунке 2.1

Рисунок 2.1 Входные данные программы

Минимальные системные требования:

- Windows 95,98,XP;

- 8 MB HDD;

- 4 MB ОЗУ;

- Мышь;

- Клавиатура;

- Дисплей.

3.ЧИСЛЕННЫЙ МЕТОД

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

Рисунок 3.1 Граф системы состояний случайного процесса

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

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

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

Рассуждая аналогично для других состояний системы , можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

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

Предельная вероятность состояния S_i имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S₀, т.е. p₀=0,5, то это означает, что в среднем половину времени система находится в состоянии S₀.

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

Эту систему можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния p_i, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы.

Описание метода. Пусть исходная система выглядит следующим образом

Матрица A называется основной матрицей системы, b — столбцом свободных членов.

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

Если хотя бы одно число , где то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть для любых

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (, где — номер строки):

где

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

4.РУЧНОЙ ПРОСЧЕТ

По графу запишем систему уравнений Колмогорова в общем виде

Вместо интенсивности потоков λij запишем их конкретные значения и получим искомую систему:

Чтобы найти финальные вероятности состояний, в уравнениях Колмогорова отбросим первое уравнения, а по остальным составим систему алгебраических уравнений:

Делим первое уравнение на 2, а второе на 3 и получим систему

Из третьего уравнения вычитаем первое

Отсюда получим p1=0,22, p2=0,11 и p0=0,67

5.СХЕМА АЛГОРИТМА ПРОГРАММЫ

6.ИНСТРУКЦИЯ ПО ЭКСПЛУАТАЦИИ

Программа работает на персональном компьютере (ПК) типа Intel Pentium 2 CPU 525 Hz с памятью (RAM) 128 Мб, жестким диском 10 Гб для решения данной поставленной задачи. Для работы в диалоговом режиме используется экран дисплея, клавиатура и манипулятор типа "мышь", так же может понадобиться принтер, если необходимо сделать печатный вариант результатов программы.

Для начала работы с программой, необходимо запустить файл run.exe. В открывшемся консольном окне, программа предложит ввести количество состояний (Рисунок 6.1).

Рисунок 6.1 – Ввод количества ребер

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

Рисунок 6.2 – Ввод данных и вывод результата

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

7.ОТЛАДКА

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

Во время отладки возможно обнаружить следующие ошибки:

1) синтаксические;

2) ошибки компоновки;

3) ошибки выполнения.

В процессе отладки программы были обнаружены синтаксические ошибки, такие как:

1) отсутствие символа ';' в конце некоторых команд;

2) неправильное написание имен переменных;

В процессе отладки программы были обнаружены ошибки выполнения, такие как:

1) неверное выделение памяти для динамического массива;

2) неверное обращение к элементам динамического массива;

Все ошибки были исправлены. Для проверки должно быть выполнено тестирование.

8.ТЕСТИРОВАНИЕ ПРОГРАММЫ

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

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

Тестирование в нормальных условиях

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

Тестирование программы приведено на рисунках 8.1 и 8.2.

Рисунок 8.1 – Ввод нормальных уловий

Рисунок 8.2 – Вывод результата

Тестирование в экстремальных условиях

Тестирование в экстремальных услових представлена на рисунке 8.3. Это тестирование включает в себя проверку работоспобоности программы за пределами граничных значений [2;4] ввода количества состояний.

Рисунок 8.3 – Ввод количества состояний

Тестирование в исключительных условиях

Тестирование в исключительных услових показан на рисунке 8.5.

Рисунок 8.5 – Тестирование в исключительных условиях

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

Листинг программа приведен в приложении А, а результаты ее выполнения – в приложении Б.

9.ЗАКЛЮЧЕНИЕ

В результате выполнения работы, была написана программа для решения уравнений Колмогорова.

К достоинствам программы можно отнести простату работы и небольшой вес.

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

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

1) ГОСТ 2.105-95 – Общие требования к текстовым документам.

2) Керниган Б.В. Ричи Д.М. Язык Си. “Вильямс”, 2009.

ПРИЛОЖЕНИЕ А

(обязательное)

Листинг программы

/*

***********************************************************************************

* Курсовая работа по предмету Математические методы. *

* Тема: Уравнения Колмогорова для вероятностных состояний. *

***********************************************************************************

* Задание: Написать программу для решения задачи нахождения предельной вероятности *

* состояний с помощью уравнений Колмогорова. *

***********************************************************************************

* Язык: C *

* Среда: CodeBlocks *

* Дата: 13.11.2014 года *

* Разработали: Набатников Александр, Пономарева Екатерина *

***********************************************************************************

* Формальные переменные: *

* matrix - матрица коэффициентов при неизвестных p; *

* lambda - вектор интенсивности ребер; *

* answer - вектор ответов; *

* path - матрица ребер (0 - начальная вершина, 1 - конечная вершина); *

* node - количество событий; *

* n - количество ребер; *

* i, j, k - счетчики циклов; *

* dev - делитель для строк матрицы при решении системы методом Гаусса; *

* sum - множитель для строк матрицы при решении системы методом Гаусса. *

************************************************************************************

*/

#include <stdio.h>

int main() {

float matrix[5][5] = { 0.0f, };

float lambda[8] = { 0.0f, };

float answer[5] = { 0, };

int path[8][2] = { 0, };

int node = 0;

int n, i, j, k;

float dev, sum;

while ((node < 2) || (node > 4)) //Цикл ввода количества состояний

{

printf("input count node: ");

scanf("%d", &node);

}

n = node == 2? node - 1: node; //Условие для двух состояний

(максимум два ребра)

for (i = 0; i < n * 2; ++i) //Цикл ввода ребер и их

{ интенсивности

printf("input start node: ");

scanf("%d", &path[i][0]);

printf("input finish node: ");

scanf("%d", &path[i][1]);

printf("input lambda: ");

scanf("%f", &lambda[i]);

}

fflush(stdin);

fflush(stdout);

for (i = 0; i < node; ++i) //Цикл формирования уравнений

for (k = 0; k < node; ++k) {

if (k == i) {

for (j = 0; j < n * 2; ++j)

if (path[j][0] == i)

matrix[i][i] += -lambda[j];

}

else {

for (j = 0; j < n * 2; ++j)

if ((path[j][0] == k) && (path[j][1] == i)) {

matrix[i][k] = lambda[j];

break;

}

}

}

//Замещение последнего уравнения нормирующим условием (p1 + p2 +... + pn = 1)

for (i = 0; i <= node; ++i)

matrix[node - 1][i] = 1.0f;

for (i = 0; i < node - 1; ++i) { //Метод Гаусса

dev = matrix[i][i];

if (dev!= 0.0f)

for (j = i; j < node + 1; ++j)

matrix[i][j] /= dev;

for (k = i + 1; k < node; ++k) {

sum = -matrix[k][i];

for (j = i; j < node + 1; ++j)

matrix[k][j] += matrix[i][j] * sum;

}

}

k = 0;

for (i = node - 1; i >= 0; --i) { //Цикл формирования ответа

answer[i] = matrix[i][node];

for (j = 0; j < k; ++j)

answer[i] -= answer[k + i - j] * matrix[i][k + i - j];

++k;

answer[i] /= matrix[i][node - k];

}

for (i = 0; i < node; ++i) //Цикл печати ответа

printf("P(%d) = %5.2f\n", i, answer[i]);

getchar();

return 0;

}

ПРИЛОЖЕНИЕ Б

(обязательное)

Результаты выполнения программы

Результаты работы программы приведены на рисунках Б.1, Б.2 и Б.3.

Рисунок Б.1 – Ввод количества состояний

Рисунок Б.2 – Ввод значение ветвей

Рисунок Б.3 – Вывод результата