Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Аналитический раздел

1.1 Общая постановка задачи

1.2 Классические задачи принятия решений

1.3 Многостадийный процесс

1.4 Задача линейного программирования

1.5 Задача о распределении ресурсов

1.6 Транспортная задача

2. Конструкторский раздел

2.1 Сценарий работы программы

2.2 Расчет функции прогнозируемой прибыли

2.3 Предлагаемый алгоритм работы программы

2.4 Диаграмма классов

2.5 Спецификация основных классов

2.6 Требования к БД

2.7 Концептуальная модель базы данных

2.8 Спецификации таблиц

2.9 Вычисление расстояния по GPS-координатам

2.10 Развертывание системы

2.11 Функциональная декомпозиция системы по уровням

3. Технологический раздел

3.1 Требования к вычислительной системе

3.2 Выбор СУБД

3.3 Выбор среды разработки

3.4 Выбор языка программирования

3.5 Используемые технологии

3.6 Пользовательский интерфейс

3.7 Развертывание системы

3.8 Функциональная декомпозиция системы по уровням

4. Исследовательский раздел

4.1 Исследование зависимости времени работы алгоритма от числа учащихся

4.2 Нагрузочное тестирование

5. Организационно-экономический раздел

5.1 Организация и планирование процесса разработки

5.2 Расчет трудоемкости выполнения работ

5.3 Расчет количества исполнителей

5.4 Календарный план-график разработки программного продукта

5.5 Расчет стоимости программного продукта

5.6 Расчет экономической эффективности

6. Промышленная экология и безопасность

6.1 Анализ вредных и опасных факторов

6.2 Расчет системы освещенности

6.3 Расчет искусственного освещения

Заключение

Список использованных источников

Введение

Современная педагогика характеризует термином “дополнительное образование” всю ту сферу образования, которая находится за пределами общеобразовательного государственного стандарта.

Школьники могут получать дополнительное образование как в частных компаниях, некоммерческих структурах или непосредственно в самих школах. В России действует множество образовательных центров, где учащиеся могут пройти обучение по различным дисциплинам и изучить выбранный курс. Ежегодное количество обучающихся в таком учреждении может превышать десятки тысяч человек. (Например, компания ФТК). При создании подобного образовательного центра могут возникнуть некоторые организационные проблемы: как контролировать учебный процесс, учитывать оплату занятий, совершать массовое оповещение родителей о каких-либо новостях, иметь быстрый доступ к основной информации, касающейся сотрудников компании и др.

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

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

Кроме вышеперечисленных организационных проблем, которые могут быть решены грамотным хранением информации и предоставлением легкого доступа к ней как сотрудникам образовательного учреждения, так и его клиентам, могут возникнуть более сложные проблемы, которые требуют их исследования и алгоритмической реализации. Таковой, например, является проблема распределения учеников по группам перед началом процесса обучения. После того, как компания набрала для обучения большое количество учащихся, число которых может иметь порядок тысячи, следует проблема оптимального их распределения по группам так, чтобы прибыль для компании была наибольшей. Например, если в 4 близлежащих образовательных центрах будут 4 малые (3-5 человек) группы по одному и тому же предмету, то затраты на преподавателей и аренду помещения можно сократить почти в 4 раза, если соединить все эти группы в одну, разместив в одном, наиболее подходящем для учащихся, образовательном центре. Сэкономленная на этом прибыль уже является хорошим основанием для исследования этой проблемы и поиска её решения. Сейчас подобные проблемы в компаниях решаются сотрудниками компании без помощи каких-либо алгоритмов, но с использованием интуиции и примерном представлении о данной проблеме.

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

1. Аналитический раздел

1.1 Общая постановка задачи

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

Входные данные:

· Список клиентов (учащихся)

· Список образовательных центров

· Данные GPSместа жительства клиентов

· Минимальные и максимальные размеры групп для всех курсов

· Список предпочтений для каждого клиента учиться в том или ином образовательном центре (должен быть представлен списком весов)

· Данные GPS образовательных центров

· Заработные платы преподавателей

· Функция, осуществляющая расчет прибыли для текущих параметров системы

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

Выходные данные:

· Такое распределение учащихся по группам, чтобы функция прибыли принимала максимальное значение

· Значение функции прибыли

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

1) Как задавать функцию прибыли для конкретного распределения учащихся по образовательным центрам (ОЦ). Вывод формулы приведен в конструкторском разделе, пункт 2.2.

2) Реализация алгоритма (поиска наиболее приемлемого распределения учащихся по ОЦ), используя начальное распределение. Алгоритм приведен в пункте 2.3.2.

1.2 Классические задачи принятия решений

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

· генерирование альтернативных вариантов решения;

· их оценку по заданному критерию эффективности;

· выбор из них наилучшего.

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

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



где Y - множество параметров, называемых входными,

X - множество параметров, называемых выходными,

- знак декартова произведения.

Если отношение является функцией, то следует пользоваться отображением:

Тогда формулировка задачи принятия решения будет:

Пусть Y - множество исходных данных.

Конкретизация элемента y₀Y приводит в дальнейшем к получению решения с конкретными числовыми параметрами, зависящими от y₀.

Множество неопределённостей обозначим H, в нём элемент hH характеризует свойство действующих случайных возмущений или степень незнания параметров задачи.

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

Собственно, решение задачи обозначим x, а всё множество возможных решений - X.

Построим на перечисленных множествах выходную функцию:

определяющую структуру и содержание задачи принятия решений.

Зададим оценочную функцию



которая отображает принимаемые решения на множество оценок. Эта функция частично или полностью упорядочена отношением .

Введём функцию допустимости (толерантности)

определяющую предельные значения качества решения.

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

Заданы элемент y₀Y и множество U_fU.

Требуется определить такой элемент u₀U_f и соответствующий ему элемент x₀X, при которых для всех hHбудет выполняться неравенство

Таким образом, шестёрка определяет задачу нахождения удовлетворительных решений. Для наглядной иллюстрации этой задачи рассмотрим последовательность выполняемых в процессе решения операций, отобразим её ориентированным графом (рисунок1). Маршрут из начальной вершины О в конечную вершину F, удовлетворяющий для каждого hH и управления u0Uf, является решением задачи.

Задачу принятия оптимальных решений сформулируем следующим образом. Дан элемент y0Y и подмножество Uf. Требуется определить такой элемент u*Uf и соответствующий ему элемент x*X, при которых для всех hH и для всех uUf(u u*) будет выполняться неравенство



Рисунок 1. Граф поиска дополнительного решения

1.3 Многостадийный процесс

Многостадийные процессы - это такие процессы, в которых решения принимаются на каждой из последовательных стадий.

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

При рассмотрении вопросов динамического программирования принята следующая терминология:

а) стадия - единичный элемент, на которые делится весь процесс во времени или в пространстве; ступень - часть стадии. В любом случае стадия и ступень - это математические конструкции, применяемые для представления в дискретном виде непрерывной переменной;

б) состояние системы характеризуется совокупностью переменных, последние описывают состояние системы на любой стадии процесса;

в) переход от стадии к стадии и от состояния к состоянию описывается функциональными уравнениями;

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

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

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

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

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

1.4 Задача линейного программирования

Перед решением задачи составляем её математическую модель.

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

Принцип составления математической модели.



Рисунок 2. Функциональная схема

1. Выбирают переменные задачи.

Переменными задачи называются величины, которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = ().

2. Составляют систему ограничения задачи.

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

В общем виде система записывается в виде

(1)

3. Задают целевую функцию.

Целевая функция - это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти.

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

(2)

и условию неотрицательности 0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =

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

Множество допустимых решений образует область допустимых решений задачи (ОДР).

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

Каноническая форма задачи линейного программирования

Математическая модель задачи должна иметь каноническую форму.

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

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

перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства () и (-1) для неравенства () дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть:

 = - ((3)

Общий вид канонической формы:

(4)

Решение задачи линейного программирования симплекс-методом

Симплекс-метод известен с 1947 года, когда появилась первая публикация Джона Данцига, посвященная этому методу. В советской литературе 60-80-х гг. прошлого столетия этот метод был известен также как метод последовательного улучшения плана.

За прошедшие с тех пор годы было предложено не только много разновидностей симплекс-метода, учитывающих особенности различных подклассов задачи ЛП (блочные задачи, задачи со слабо заполненной матрицей условий A ={ai, j}), но и несколько принципиально иных методов решения задачи ЛП. Некоторые из предложенных методов в теоретическом плане, например, с точки зрения характеристики сложности алгоритма, превосходят симплекс-метод (известно, что симплекс-метод обладает экспоненциальной сложностью, т.е. имеет экспоненциальную оценку трудоемкости на всем классе задач ЛП, тогда как такие алгоритмы, как метод эллипсоидов Хачияна (советского математика) и метод Крамаркара (американского исследователя) характеризуются полиномиальной сложностью). И, тем не менее, по утверждению многих специалистов в теории линейного программирования симплекс-метод и после десятилетий всесторонней апробации с точки зрения алгоритмической реализации и универсальности применимости на классе задач ЛП остается наиболее предпочтительным, а потому наиболее распространенным методом решения задач ЛП.

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

Название метода от латинского simplecx - простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.

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

1.5 Задача о распределении ресурсов

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

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

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

Опишем типичную задачу распределения ресурсов в общем виде.

Имеется начальное количество средств , которое необходимо распределить в течение n лет между s предприятиями. Средства , выделенные в k-м году i-му предприятию, приносят доход в размере и к концу года возвращаются в количестве. В последующем распределении доход может либо участвовать (частично или полностью), либо не участвовать.

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

Следовательно, в качестве показателя эффективности процесса распределения ресурсов за n лет принимается суммарный доход, полученный от s предприятий:

.(5)

Количество ресурсов в начале k-го года будем характеризовать величиной (параметр состояния). Управление на k-м шаге состоит в выборе переменных , обозначающих ресурсы, выделяемые в k-м году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид

(6)

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

Требуется определить ns неотрицательных переменных , удовлетворяющих условиям (2.2) и максимизирующих функцию (2.1).

Вычислительная процедура ДП начинается с введения функции , обозначающей доход, полученный за п--k+1 лет, начиная сk-го года до конца рассматриваемого периода, при оптимальном распределении средств между s предприятиями, если в k-м году распределялось средств. Функции для удовлетворяют функциональным уравнениям (1.5), которые запишутся в виде

(7)

При согласно (1.5) получаем

.(8)

Далее необходимо последовательно решить уравнения(7) и(8)для всех возможных . Каждое из этих уравнений представляет собой задачу на оптимизацию функции, зависящей отsпеременных. Таким образом, задача сns переменными сведена к последовательности n задач, каждая из которых содержитs переменных. В этой общей постановке задача по-прежнему сложна (из-за многомерности) и упростить ее, рассматривая как ns-шаговую задачу, в данном случае нельзя. В самом деле, попробуем это сделать. Пронумеруем шаги по номерам предприятий сначала в 1-м году, затем во 2-м и т. д.:



и будем пользоваться одним параметром для характеристики остатка средств.

В течение k-го года состояние к началу любого шага (i=l, 2,.... s) определится по предыдущему состоянию с помощью простого уравнения . Однако по истечении года, т. е. к началу следующего года, к наличным средствам необходимо будет добавить средств и, следовательно, состояние в начале -го шага будет зависеть не только от предшествующего ks-го состояния, но и от всех s состояний и управлений за прошлый год. В результате мы получим процесс с последействием. Чтобы исключить последействие, приходится вводить несколько параметров состоянии; задача на каждом шаге остается по-прежнему сложной из-за многомерности.

1.6 Транспортная задача

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом.

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

Различают два типа транспортных задач: по критерию стоимости и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из баз(запасы), соответственно,а общее количество имеющегося в наличии груза-:

;(9)

заказы каждого из потребителей (потребности) обозначим соответственно, а общее количество потребностей - :

,(10)

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

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

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Таблица 1. Таблица перевозок

Пункты Отправления	Пункты назначения	Запасы
			…
			…
			…
…	…	…	…	…	…
			…
Потребности			…		Или

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

Очевидно, переменные должны удовлетворять условиям:

Формула 11. Транспортная задача

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

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

Совокупность тарифов также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

Таблица 2. Таблица стоимостей

Пункты Отправления	Пункты назначения	Запасы
			…
					…
					…
…	…	…	…	…	…
					…
Потребности			…		Или

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

(12)

Требуется в области допустимых решений системы уравнений (11) найти решение, минимизирующее линейную функцию (12)

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

Если данную задачу попытаться свести к транспортной, то в качестве типов ресурсов мы будем иметь лишь один тип - людей, а в качестве пунктов назначения - образовательные центры. В транспортной задаче мощности стоков и истоков заданы заранее. В нашем же случае мощность истока равна числу клиентов, а мощность каждого стока не может быть найдена, поскольку заранее неизвестно, сколько людей запишется в каждый образовательный центр. Также в транспортной задаче предполагается, что стоимость перевозки каждого ресурса одного вида до одного и того же пункта назначения одинакова. У нас же это число будет варьироваться для каждого клиента, так как расстояние от одного клиента до конкретного ОЦ отличается от расстояния между другим клиентом и тем же ОЦ. Следовательно, данную задачу нельзя свести к транспортной.

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

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

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

2. Конструкторский раздел

2.1 Сценарий работы программы

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

Шаг 1. Администратор, запустив программу, загружает информацию о клиентах, курсах и образовательных центрах из базы данных.

Шаг 2. Создание начального распределения клиентов по ОЦ, состоящее из списка записей, каждая из которых хранит в себе информацию об ученике и информацию об определенном количестве образовательных центров, в которых ученик может обучаться. Это число администратор может изменять, но, по умолчанию, оно равняется трём. Таким образом, в дальнейшем при создании распределения для каждого ученика будут рассматриваться лишь 3 ближайших к его дому образовательных центра. Чтобы каждый ученик вносил наибольший вклад в функцию прогнозируемой прибыли, он будет распределен к тому ОЦ, к которому живет ближе всего. Этот ОЦ должен стоять первым в списке образовательных центров для каждого клиента. Для этого для каждого ученика производится сортировка соответствующих ему центров в порядке возрастания расстояния от клиента до ОЦ.

Шаг 3. После того, как распределение создано, каждый ученик однозначно определен учиться в конкретном ОЦ, но группы еще не сформированы. В каждом ОЦ по каждому курсу рассчитывается число учеников, которые хотят записаться на данный курс. Используя данные о минимальном и максимальном размере групп для каждого курса, производится расчет возможного числа полных групп (размер которых равен максимальному размеру группы для данного курса). Возможно, после этого шага у некоторых центров для некоторых курсов останутся нераспределенные учащиеся. Для каждого ОЦ для каждого курса смотрим, можно из оставшихся людей собрать еще одну группу. Число людей в этой группе должно быть не меньше, чем минимальный размер группы для данного курса. Если можно, увеличиваем число созданных групп на единицу, а число нераспределенных на данный курс в данном ОЦ клиентов приравнивается к 0. Иначе, это число будет равным числу оставшихся нераспределенных клиентов.

Теперь известно точное число людей, оставшихся нераспределенными для каждого ОЦ для каждого предмета. Но привязки конкретного человека к конкретной группе еще не создано. Чтобы прибыль была наибольшей, выгодней оставить нераспределенными тех, кто находится дальше всех от данного ОЦ. Для каждого ОЦ для каждого курса создается список клиентов, которые хотят записаться на данный курс. Эти списки сортируются в порядке уменьшения расстояния от ОЦ до места жительства ученика. Если число нераспределенных клиентов для данного ОЦ данного курса n_ij не равно 0, то первые n_ij клиентов в этом списке отмечаются как нераспределенные. Остальных клиентов отмечаем как распределенных. Начальное распределение клиентов по группам создано.

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

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

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

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

Рисунок 3. Нераспределенные ученики по курсу “Математика 5 класс”

При таком распределении при формировании только одной группы, например, в образовательном центре под номером 7, будет набрана полная группа путем переброски людей из соседних. И это будет оптимальный шаг, если пытаться формировать только 1 группу. Но после этого шага останутся клиенты, которых мы уже не сможем скомпоновать в одну группу, так как они будут находиться слишком далеко друг от друга. Оптимальным же шагом при этой ситуации будет одновременное создание двух групп (в 5 и 11 образовательных центрах). И это, действительно, принесет больше прибыли, т.к. почти все нераспределенные клиенты запишутся на курсы.

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

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

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

2.2 Расчет функции прогнозируемой прибыли

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

Где H - множество сформированных групп во всех ОЦ по данному курсу

- зарплата преподавателя в группе с индексом по j_му предмету.

- стоимость обучения на j_ом курсе.

N - число образовательных центров.

S - множество детей, распределенных по группам.

P_ijk - вероятность обучения k_го клиента на j_ом курсе в i_ом ОЦ

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

где M - количество курсов обучения

2.3 Предлагаемый алгоритм работы программы

Шаг 1. Загрузка информации о клиентах, курсах и образовательных центрах в приложение из базы данных “Intellect”.

Шаг 2. Формирование начального распределения учащихся по ОЦ. Для каждого клиента формируется список центров, в которых он может обучаться. Расчет расстояний от каждого клиента до этих ОЦ. Расчет весов с использованием линейной интерполяции для каждой пары клиент-ОЦ (вес - это вероятность того, что клиент запишется на курсы в данный ОЦ) с учетом статистических данных за предыдущий год.

Шаг 3.Формирование групп для текущего распределения (Описано в пункте 2.3.1).

Шаг 4. Нахождение значения функции прогнозируемой прибыли F по формуле для данного распределения D.

Шаг 5. Поиск нового распределения D₁ для которого ищется значение функции прибыли F₁. Если такое распределение было найдено, запоминаем его в качестве исходного распределения. Запоминаем значение функции прибыли F=F₁. Повторяем шаг 5. Иначе, переход к шагу 6.

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

Шаг 7. Отображение полученного распределения, статистических данных, полученного значения функции прибыли.

Рисунок 4. Укрупненная блок-схема алгоритма работы программы

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

Шаг 1. Для каждого ОЦ по каждому предмету формируется одна группа из N человек.

Шаг 2. Для каждого ОЦ по каждому предмету высчитывается число групп: n = [N/n_imax], где n_imax - максимальный размер группы для i-го предмета.

Шаг 3. Зная число групп в каждом ОЦ по каждому предмету, распределяем из N клиентов n*n_imax клиентов по группам таким образом, что остаются нераспределенными те клиенты, которые:

· Максимально удалены от данного ОЦ (значения весов и, соответственно, вклад в функцию прогнозируемой прибыли минимальны)

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

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

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

Шаг 1. Нахождение значения прибыли от текущего распределения

Шаг 2. Формирование списка из образовательных центров, в которых можно сформировать новую группу по данному курсу

Шаг 3. Если список пуст, возвращаем текущее значение прибыли и текущее распределение. Конец работы алгоритма

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

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



Рисунок 5. Блок-схема алгоритма поиска нового распределения

2.4 Диаграмма классов

Диаграмма классов с указанием уровней логики представлена на рис. 6.

2.5 Спецификация основных классов

Таблица 3. Класс «ClientsDistribution»

Класс «ClientsDistribution»
Имя члена/метода	Модификатор доступа	Описание
Client[] clients	+	Массив записей клиентов на курсы (хранится пара ID клиента и ID курса)
Course[] courses	+	Список курсов
EducationCenter[] centers	+	Список ОЦ
Relation[][] distribution	+	Массив возможных распределений (для каждого клиента хранятся ближайшие ОЦ, в которых он может учиться)
boolDataLoaded	-	True, если данные загружены
boolInitialDistributionMade	-	True, если создано начальное распределение
double relatedDistance	-	Максимально допустимое расстояние от ОЦ до места жительства клиента, в метрах
int numOfRelatedCenters	-	Количество центров, в которых может обучаться каждый клиент. Служит для ускорения работы алгоритма. Все равно клиент не будет учиться в удаленных ОЦ
LoadData()	+	Загрузить данные из базы
MakeInitialDistribution()	+	Создать начальное распределение
GetCurrentDistribution()	+	Получить текущее распределение (для дальнейшего его отображения на карте Москвы)
GetClientsCoordinates	+	Возвращает координаты клиента поегоID
GetCurrentIncome()	+	Подсчитывает прогнозируемую прибыль для текущего распределения
FindOptDistribution()	+	Запускает алгоритм поиска “оптимального” распределения

Рисунок 6. Диаграмма классов

Таблица 4. Класс «MoscowMap»

Класс «MoscowMap»
Имя члена/метода	Модификатор доступа	Описание
double dolgota1, shirota1, dolgota2, shirota2	-	Координаты GPS левого верхнего и правого нижнего углов карты Москвы. Нужны для масштабирования карты и аппроксимации местоположения
int Width	+	Ширина карты, в пикселях
int Height	+	Высота карты, в пикселях
getCurrentCoordinates()	+	Получает gps координаты по координатам пикселя
GetCurrentDistribution()	+	Возвращает изображение с текущим распределением клиентов
GetIntCoordinates()	-	Получает координаты пикселя по gps-координатам
GetEmptyMap()	+	Возвращает пустую карту

Таблица 5. Класс «GPS»
Класс «GPS»
Имя члена/метода	Модификатор доступа	Описание
ConvertToRadians()	-	Конвертирует значение из градусов в радианы
get_fi()	-	Вычисляет угол, который вдальнейшем используется для нахождения расстояния между двумя точками по их gps координатам
get_S_yandex()	+	Вычисляет расстояние по gps координатам

Таблица 6. Класс «Client»
Класс «Client»
Имя члена/метода	Модификатор доступа	Описание
Int32 ID	+	ID клиента
double Dolgota	+	GPS координаты долготы
double Shirota	+	GPS координаты широты
Int32 CourseID	+	ID курса, к которому относится данная запись

Таблица 7. Класс «Course»
Класс «Course»
Имя члена/метода	Модификатор доступа	Описание
Int32 ID	+	ID курса
Double Cost	+	Стоимость курса
Int32 MinGroupSize	+	Минимальный размер группы по данному курсу
Int32 MaxGroupSize	+	Максимальный размер группы по данному курсу

Таблица 8. Класс «EducationCenter»
Класс «EducationCenter»
Имя члена/метода	Модификатор доступа	Описание
Int32 ID	+	ID образовательного центра
double Dolgota	+	GPS координаты долготы
double Shirota	+	GPS координаты широты

Таблица 9. Класс «OneClientDistribution»
Класс «OneClientDistribution»
Имя члена/метода	Модификатор доступа	Описание
Int32 ClientID	+	ID клиента
Int32 CenterID	+	ID образовательного центра, к которому он относится
Int32 CourseID	+	ID курса, на который записан
boolisDistributed	+	True, если клиент уже распределен в какую-то группу
Int32 relatedCenter	+	Коэффициент, который позволяет учитывать учащихся, которые вносят корреляцию

Таблица 10. Класс «Relation»
Класс «Relation»
Имя члена/метода	Модификатор доступа	Описание
Int32 ID	+	ID ОЦ в списке связанных для данного клиента ОЦ
Double S	+	Расстояние для данного ОЦ
Double P	+	Весовой коэффициент - вероятность того, что клиент будет ходить именно в этот ОЦ

2.6 Требования к БД

· Возможность получения доступа через интернет

· В БД должен быть предусмотрен поиск, изменение и удаление записей

· Авторизация при помощи логина и пароля. Разграничение прав доступа. Возможность регистрироваться и восстанавливать забытый пароль.

· Возможность использовать администраторам сайта “Панель администратора”, через которую возможно изменение и удаление базовых элементов системы, а также получение более детальной информации о базе данных

2.7 Концептуальная модель базы данных

Каждой таблице в базе данных соответствует своя сущность на ER-диаграмме. Всего 12 сущностей, 11 из которых являются сильными (или “нормальными”). Сущность “Курс” является слабой сущностью, так как её существование зависит от другой сущности “Обобщенный курс”.

Каждый тип сущности на ER-диаграмме представляется в виде отдельного прямоугольника с указанным внутри именем сущности, причем прямоугольники сущностей слабых типов рисуются двойной линией. [6]

Описанные сущности и их связи представлены на ER-диаграмме на рис. 7.

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

Рисунок 7. ER-диаграмма

2.8 Спецификации таблиц

Таблица 11. Таблица образовательных центров (ОЦ)
Таблица «Образовательные центры»
Название атрибута	Тип	Комментарий
Адрес ОЦ	VARCHAR(100)	город, улица, дом, корпус, строение
Долгота	VARCHAR(80)	Gps-координаты ОЦ
Широта	CHAR(20)	Gps-координаты ОЦ

Таблица 12. Таблица с информацией о клиентах, записавшихся на курсы до набора групп
Таблица «Клиенты с бонусом»
Название атрибута	Тип	Комментарий
ФИО ребенка	VARCHAR(100)	фамилия, имя и отчество ученика, записывающегося на курсы
ФИО родителя	VARCHAR(100)	фамилия, имя и отчество родителя, обычно матери ученика
Телефон родителя	CHAR(20)
Сегодняшняя дата	DATE	дата создания этой записи. Учитывается при наборе групп. Если клиент записался больше, чем за месяц до начала курса, ему предоставляется скидка
Долгота	float	Gps-координаты места жительства
Широта	float	Gps-координаты места жительства

Таблица 13. таблица с записями о клиентах, записавшихся на курс тогда, когда группы еще не набраны
Таблица «Записи клиентов с бонусами»
Название атрибута	Тип	Комментарий
ID клиента с бонусом	INT
ID обобщенного курса	INT	ID курса, на который хочет записаться потенциальный клиент
Таблица 14. Таблица клиентов
Таблица «Клиенты»
Название атрибута	Тип	Комментарий
ФИО клиента	VARCHAR(100)	Фамилия, имя и отчество обучающегося
Название школы	VARCHAR(80)	школа, в которой обучается клиент на данный момент
Телефон клиента	CHAR(20)	телефон ученика
ФИО родителя	VARCHAR(100)
Телефон родителя	CHAR(20)

Таблица 15. Таблица, содержащая основную информацию о каждом преподавателе
Таблица «Преподаватели»
Название атрибута	Тип	Комментарий
ID предмета	INT	ID обучаемого предмета
ФИО преподавателя	VARCHAR(100)	фамилия, имя и отчество преподавателя
Телефон	CHAR(20)	телефон преподавателя
Опыт работы	INT	стаж сотрудника, в годах
Место работы	VARCHAR(100)	последнее или текущее место работы преподавателя

Таблица 16. Таблица курсов с уже конкретно заданными датами занятий
Таблица «Группы»
Название атрибута	Тип	Комментарий
ID преподавателя	INT	ID того преподавателя, который будет вести данный курс
ID обобщенного курса	INT	ID обобщенного курса, но основе которого построен данный курс
Дата начала	DATE	дата первого занятия
Дата окончания	DATE	дата последнего занятия
Дата родительского собрания	DATETIME

Таблица 17. Таблица обобщенных курсов. Имеет всю информацию о каждом курсе

Таблица «Обобщенные курсы»
Название атрибута	Тип	Комментарий
ID предмета	INT	предмет обучения, к которому относится данный курс (математика, физика и т.д.)
Название курса	VARCHAR(100)	полное название курса. Например “Web-дизайн и язык HTML”
Минимальное значение класса	INT	класс, ученики которого уже способны осваивать данный курс
Максимальное значение класса	INT	наибольшее значение класса, ученики которого могут изучать выбранный курс
Количество часов, в семестр	INT	какое количество часов в семестре имеет выбранный курс
Количество часов в неделю	REAL	суммарное количество часов обучения по данному курсу в неделю
Стоимость за месяц	MONEY	месячная стоимость обучения
Бонусная стоимость за месяц	MONEY	месячная стоимость обучения при единоразовой оплате всего семестра
Минимальный размер группы	INT	минимальное количество людей в группе. Если в группе людей меньше, занятия не начинаются
Максимальный размер группы	INT	наибольшее количество людей в группе. Если записывается больше людей, группа делится на 2 подгруппы

Таблица 18. Таблица платежей, сделанных клиентами
Таблица «Платежи»
Название атрибута	Тип	Комментарий
ID клиента	INT	ID клиента, осуществившего платеж
ID курса	INT	ID курса, оплата за которого сделан платеж
Стоимость	MONEY	сумма платежа
Дата оплаты	DATE	дата внесения платежа
Оплаченные часы	INT	количество оплаченных часов за семестр

Таблица 19. Таблица пользователей, работающих с сайтом

Таблица «Пользователи»
Название атрибута	Тип	Комментарий
Логин	INT	логин пользователя
Имя	INT	имя пользователя
Фамилия	MONEY	фамилия пользователя
Приоритет	DATE	уровень доступа пользователя к системе
Пароль	INT

Таблица 20. Таблица уроков. Содержит информацию о времени проведения каждого запланированного занятия

Таблица «Уроки»
Название атрибута	Тип	Комментарий
ID курса	INT	ID курса, к которому относится данное занятие
Дата	INT	дата проведения занятия
Время начала	MONEY	время начала занятия
Время окончания	DATE	время окончания занятия

Таблица 21. Таблица различных дисциплин, по которым ведутся курсы

Название атрибута	Тип	Комментарий
Название	VARCHAR(50)	Название дисциплины, по которой ведется обучение

Таблица 22. Таблица с информацией о каждом ученике за конкретное занятие

Название атрибута	Тип	Комментарий
ID урока	INT	ID того урока, к которой относится эта запись
ID клиента	INT	ID ученика, кому посвящена данная запись
Присутствие	BIT	Отметка о том, посетил ли ученик данное занятие
Домашнее задание	BIT	Отметка о том, выполнил ли ученик домашнее задание для данного занятия
Отметка	varchar(100)	Оценка, а так же замечания и пометки, сделанные ученику за урок

2.9 Вычисление расстояния по GPS-координатам

Через любые две точки на поверхности сферы, если они не прямо противоположны друг другу (то есть не являются антиподами), можно провести уникальный большой круг. Две точки, разделяют большой круг на две дуги. Длина короткой дуги - кратчайшее расстояние между двумя точками. Между двумя точками-антиподами можно провести бесконечное количество больших кругов, но расстояние между ними будет одинаково на любом круге и равно половине окружности круга, или pi*R, где R - радиус сферы.



Рисунок 8. Вычисление расстояния по gps координатам

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

Существует три способа расчета сферического расстояния большого круга.

1. Сферическая теорема косинусов

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

- широта и долгота двух точек в радианах

- разница координат по долготе

- угловая разница

Формула 15. Сферическая теорема косинусов.

Для перевода углового расстояния в метрическое, нужно угловую разницу умножить на радиус Земли (6372795 метров), единицы конечного расстояния будут равны единицам, в которых выражен радиус (в данном случае - метры).[7]

2. Формула гаверсинусов

Используется, чтобы избежать проблем с небольшими расстояниями. [7]

Формула 16. Формула гаверсинусов

3. Модификация для антиподов

Предыдущая формула также подвержена проблеме точек-антиподов, чтобы ее решить используется следующая ее модификация. [7]

Эллипсоид Красовского - земной эллипсоид, определенный из градусных измерений в 1940 г. под руководством Ф. Н. Красовского. Размеры эллипсоида: большая полуось (радиус экватора) 6 378 245 м. Эллипсоид Красовского принят для применения в геодезических и картографических работах в России взамен ранее применявшегося в этих работах земного эллипсоида Бесселя, размеры которого оказались ошибочными. Будем использовать значение его радиуса для вычисления расстояния между 2 объектами в зависимости от значения угловой разницы.

Для вычисления расстояния между двумя точками в Москве будем использовать формулу гаверсинусов и значение радиуса экватора 6378245 м. [2]

3. Технологический раздел

3.1 Требования к вычислительной системе

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

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

микропроцессор пятого или шестого поколения (производителей AMD, Intel)

16 MB ОЗУ

20 Мб на диске

остальное используемое оборудование должно удовлетворять требованиям, накладываемым выбранной ОС семейства Microsoft Windows

Рекомендуемые требования к серверу:

микропроцессор шестого поколения и выше (производителей AMD, Intel), например, семейства процессоров Bloomfield (2008г.) использующий микроархитектуру IntelNehalem

4000 MB ОЗУ

50 Мб на диске

остальное используемое оборудование должно удовлетворять требованиям, накладываемым выбранной ОС семейства Microsoft Windows

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

Операционная система Windows 7, Windows Vista, Windows Server 2008 или Windows Server 2008 R2

установка роли веб-сервера (IIS) и требуемых служб

библиотеки: ASP.NET уже содержит полный набор элементов управления и библиотек классов

Требования к машине клиента:

Компьютер с доступом в интернет и установленным браузером (данное приложение было протестировано в браузерах IE (версия 9.0.8112.16421) и Opera (версия 11.60)

Желательно наличие установленной программной платформы Microsoft Silver Light (версия 4.0.50917.0)

3.2 Выбор СУБД

Для решения поставленной задачи СУБД должна отвечать следующим требованиям:

реляционная модель представления данных,

поддержка многопользовательского режима работы,

работа на платформе Windows 2000 и выше.

Предъявленным требованиям отвечают следующие СУБД:

Microsoft SQL Server 2008 R2,

Oracle,

IBM DB-2.

СУБД DB-2 может обслуживать до 64 000, а Oracle до 10 000 одновременно работающих пользователей [8]. Использование их в рамках данного проекта является не целесообразным расходованием ресурсов.

MicrosoftSQLServer 2008 R2 -- новая версия решения управления базами данных от компании Microsoft, которая предоставляет комплексную платформу управления информацией и бизнес-аналитики. SQL Server 2008 R2 предоставляет надежную платформу для управления бизнес-данными и построения бизнес-приложений. Решение SQLServer 2008 R2 построено на основе SQLServer 2008, отличаясь улучшенным масштабированием, более эффективными технологиями, а также расширенными возможностями для самостоятельного бизнес-анализа и составления отчетов.

Из выше перечисленного следует, что в данном проекте лучше всего использовать СУБД MSSQLServer 2008 R2.

3.3 Выбор среды разработки

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