Разработка математической модели и ПО для задач составления расписания (стр. 8 из 12)

где

Система (26) являетсядиагональной относительно

Первая фазасимплекс-метода состоит в минимизации

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

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

Подробнее об алгоритме можно прочитать в [2], стр. 53.

2.3. ОСОБЕННОСТИ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИСИСТЕМЫ

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

2.3.1. ВЫБОР МОДЕЛИ

Модель данных – это совокупность соглашений о способах исредствах формализованного описания объектов и их связей, имеющих отношение кавтоматизации процессов системы. Вид модели и используемые в ней типы структурданных отражают концепцию организации и обработки данных, используемую в СУБД,поддерживающей модель, или в языке системы программирования, на которомсоздается прикладная программа обработки данных.

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

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

ИЕРАРХИЧЕСКИЙ СПОСОБ ОРГАНИЗАЦИИ

Иерархическая БД состоит из упорядоченного набора деревьев; болееточно, из упорядоченного набора нескольких экземпляров одного типа дерева. Типдерева состоит из одного 'корневого' типа записи и упорядоченногонабора из нуля или более типов поддеревьев (каждое из которых являетсянекоторым типом дерева). Тип дерева в целом представляет собой иерархическиорганизованный набор типов записи.

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

СЕТЕВОЙ СПОСОБОРГАНИЗАЦИИ

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

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

Тип связи определяется для двух типов записи: предка ипотомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка иупорядоченного набора экземпляров типа записи потомка. Для данного типа связи Lс типом записи предка P и типом записи потомка C должны выполняться следующиедва условия:

1. Каждый экземпляр типа P являетсяпредком только в одном экземпляре L;

2. Каждый экземпляр C являетсяпотомком не более, чем в одном экземпляре L.

РЕЛЯЦИОННЫЙ СПОСОБ ОРГАНИЗАЦИИ

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

1. Слишком сложно пользоваться;

2. Фактически необходимы знания офизической организации;

3. Прикладные системы зависят от этойорганизации;

4. Их логика перегружена деталямиорганизации доступа к БД.

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

В структурной части модели фиксируется, что единственнойструктурой данных, используемой в реляционных БД, является нормализованноеn-арное отношение.

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

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

После предварительного анализа математической моделисистемы и способов организации данных, а также имеющегося на рынке ПО(иерархический и сетевые способы организации предполагают объектно -орентированный подход к организации данных и на сегодняшний день имеются такиеСУБД (например, Jasmin или Informix Dynamic Server), но на момент разработки возможности их использования не было, в то же время существуют очень “мощные” реляционные СУБД (к примеру Oracle8i)) выбор был сделан впользу реляционного способа организации хранения данных.

2.3.2.ОПИСАНИЕ ВХОДНОЙ ИНФОРМАЦИИ

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

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

Таблица 2. Описание реквизитов входной информации

Наименование реквизитов	Характеристика реквизитов
входных документов	Тип	Макс. длина	Точность
Фамилия, имя, отчество преподавателя; Контактный телефон преподавателя; Ученая степень; Ученое звание; Кафедра; Название группы; Численный состав группы; Название читаемого курса; Количество аудиторных часов; Номера аудиторий; Информация об аудиториях; Название предмета, читаемого преподавателем; Номер группы, где читается предмет; Информация об аудиториях, где читается предмет.	текстов. текстов. текстов. текстов. текстов. текстов. числов. текстов. числов. числов. текстов. текстов. числов. текстов.	100 10 50 50 50 50 2 50 2 3 50 50 3 50