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

То, что вы здесьпрочтете в большинстве своем чушь. Тем не менее в некоторых местах по моемумнению присутствуют здравые мысли, к сожалению таких мест получилось не так ужи много L Невздумайте сдавать это там, где проблемами теории расписаний занимаютсясерьезно. Тем, кто захочет написать что-либо лучше этого, настоятельнорекомендую почитать книгу Ху. Т. “Целочисленное программирование и потоки всетях ”, кроме этого пожалуй стоит почитать лекцииВМиК по теории оптимизации Н.М. Новиковой (где это в инете лежит, не помню).Сейчас активно занимаюсь проблемами теории оптимизации, так что кому тожеинтересна эта тема, то всегда рад пообщаться. Пишите leb@metacom.ru.

Содержание

Введение. 8

1. Описание технологическойобласти. 10

1.1. Формулировка задачисоставления расписания. 10

1.1.1. Общая формулировказадачи составления расписаний. 10

1.1.2. Формулировка задачисоставления раписания в применении к расписанию учебных занятий. 11

1.2. Анализ существующего ПО.. 12

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

2. Разработка математическоймодели и практическая реализация системы автоматического составления расписания. 16

2.1. Математическая модельрасписания в вузе. 16

2.1.1. Обозначения. 16

2.1.2. Переменные. 18

2.1.3. Ограничения. 19

2.1.4. Целевая функция. 21

2.2. Методы решенияпоставленной задачи. 22

2.2.1. Полностьюцелочисленный алгоритм. 23

2.2.2 Прямой алгоритмцелочисленного программирования. 28

2.2.3. Техника полученияначального допустимого базиса. 32

2.3. Особенностипрактической реализации системы.. 36

2.3.1. Выбор модели. 36

2.3.2. Описание входнойинформации. 39

2.3.3. Разработкаинформационного обеспечения задачи. 41

2.3.4. Особенностиформирования ограничений математической модели задачи составления расписания. 44

2.4. Результатыработы программы.. 45

2.5. Анализполученных результатов. 49

Выводы.. 50

Литература. 51

Приложение 1. Возможностипрограммных продуктов систем составления расписаний. 52

Приложение 2. Листингпрограммного модуля методов решения задачи автоматического составлениярасписания. 61

Введение

Качество подготовкиспециалистов в вузах и особенно эффективность использованиянаучно-педагогического потенциала зависят в определенной степени от уровняорганизации учебного процесса.

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

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

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

1. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКОЙ ОБЛАСТИ1.1.Формулировка задачи составления расписания

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

1.1.1.Общая формулировка задачи составления расписаний

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

1.1.2.Формулировка задачи составления раписания в применении к расписанию учебныхзанятий.

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

Поэтому при переносе общейтеории расписаний на расписание учебных занятий были сделаны следующиедопущения:

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

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

- модель времени в системе является дискретной; всераспределение предполагается периодически повторяющимся на протяжениинекоторого временного интервала;

- все задания выполняются за одинаковое время, котороепринимается за единицу дискретизации временного интервала;

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

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

1.2. АнализсуществующегоПО

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

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

- учет пожеланий преподавателей;

- закрепление обязательных аудиторий;

- указание желательных аудиторий;

- учет перехода между корпусами;

- объединение групп в потоки по любой совокупности дисциплин;

- разбиение на подгруппы;

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

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

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

Из приведенного списка пожалуй только программа "Методист" болееили менее соответствует требуемой функциональности программного продуктасоставления расписания в вузе. Такое положение вещей легко объясняется тем, чтошкольное образование на сегодняшний день более "стандартизовано" (всмысле организации учебного процесса), чем вузовское. Такая стандартизацияведет к большому объему потенциального рынка продаж программного обеспечения иокупаемости разработки путем продажи большого числа копий продукта посравнительно низкой цене.

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

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

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

- расписание составляется из расчета не более двух пар в день(что вполне подходит для случая вечерней формы обучения);

- все пары проводятся в одном корпусе;

- задача ставится в терминах линейного программирования;

- дальнейшая декомпозиция модели не производится;

- все коэффициенты модели и искомые переменные целочисленны;

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

2.Разработка математической модели и практическая реализация системыавтоматического составления расписания2.1. Математическаямодель расписания в вузе

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

2.1.1.Обозначения

ГРУППЫ

В вузе имеется Nучебных групп, объединенных в Rпотоков; r – номерпотока, r = 1, ..., R, k_r – номер учебной группы в потоке r, k_r = 1, …, G_r.

Разбиение на групп на потоки осуществляется исходя изпринципов:

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

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

3. Количество потоков не лимитируется.

ЗАНЯТИЯ

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

Обозначим:

t – номер рабочего дня недели, t Є T_kr, где

T_kr –множество номеров рабочих дней для группы k_r;

j – номер пары,j = 1 ,…, J;

J – общееколичество пар.

С каждойучебной группой k_r потока r в течение недели, согласно учебномуплану, проводится W_kr занятий,из которых S_rлекционных и Q_krпрактических. Обозначим:

s_r – номердисциплины в списке лекционных занятий для потока r, s_r = 1 ,…,S_r;

q_kr – номердисциплины в списке практических занятий для группы k_r, q_kr = 1 ,…, Q_kr.

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

ПРЕПОДАВАТЕЛИ

Пустьp – номер(имя) преподавателя, p =1 ,…, P. Введем врассмотрение булевы значения и :

1, если на потоке r лекцию sr читает преподаватель p; 0 – в противном случае;

1, если в группе kr практическое занятие qkr проводит преподаватель p; 0 – в противном случае;

=

Учебнаянагрузка преподавателей планируется до составления расписания занятий, вследствиечего на данном этапе величины и можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P,задана также его аудиторная нагрузка - N_p часов в неделю.

АУДИТОРНЫЙФОНД

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

{A_1r} – множество аудиторий для лекций на потоке r;

{A_2r} – множество аудиторий для практических занятий на потоке r;

A_1r – число элементов множества {A_1r};

A_2r – число элементов множества {A_2r};

A_1r + A_2r –число аудиторий объединения множеств {A_1r}∩{A_2r}.

Аудиторный фонд определяется до началасоставления расписания, поэтому множества можно считать заданными.

2.1.2.Переменные

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

Введем следующие искомые булевы переменные:

1, если на потоке r в день t на паре j читается лекция sr; 0 – в противном случае;

1, если на потоке r в день t на паре j у группы kr проводится практическое занятие qkr; 0 – в противном случае;

=

=

В случае составления расписания для групп вечерней формыобучения J=2. Обобщение модели на все формы обучения см.[1], стр. 669.

2.1.3.Ограничения

Для каждой группы k_r должны выполняться все видыаудиторной работы в течение недели:

(1)

В любой день t на каждой паре j для каждой группы k_rможет проводиться не более одного занятия:

(2)

Каждые лекция s_r и практическое занятие q_krсоответственно для всех потоков r и всех групп k_r могутпроводиться не более одного раза в любой день t:

(3)

Если переменные и увязывают все виды занятий с временем их проведения, то произведения и связывают время проведения с именемпреподавателя.

В каждый день t и в каждой паре j преподаватель p может вестине более одного занятия по одной дисциплине на одном потоке или в одной группе:

(4)

Каждый преподаватель p в течение недели долженпровести аудиторные занятия:

(5)

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

(6)

(7)

Кроме того, для всех совокупностей пересекающихся множеств{A_1r} и {A_2r} должны выполняться условия:

(8)

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

2.1.4.Целевая функция

Чтобы полноценно вести научную, учебно-методическую работу,готовиться к занятиям, преподаватель вуза должен иметь свободное время. Этоусловие недостаточное, но необходимое. Очевидно, что свободным временем ондолжен располагать не в “рваном” режиме, каковым, например, являются “окна”между занятиями со студентами, а по возможности в полностью свободные рабочиедни. Этому эквивалентна максимизация аудиторной нагрузки преподавателей в тедни, когда они ее имеют (см. (5)). Однако при этомпретензии на свободное время у преподавателей неравны, так как у них разныйтворческий потенциал. Поэтому необходимо ввести весовые коэффициенты,посредством которых должен учитываться соответствующий статус преподавателя –его ученые степени и звание, занимаемая должность, научно-общественнаяактивность и т.п. В некоторых случаях можно на основании экспертных оценокиспользовать индивидуальные весовые коэффициенты, учитывающие другие факторы.

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

Рассмотрим выражение для величины аудиторной нагрузки вдень t преподавателя p:

(9)

Вводятся ограничения вида:

	(10)

где M – произвольное положительное достаточно большое число; -искомая булева переменная.

Из (10) вытекает, что если , то =1, и если , то =0.

С учетом указанного выше содержательного смысла критерияоптимизации в дополнительных ограничениях (10), а также вводя весовыекоэффициенты статуса преподавателя , получаем искомый критерий оптимальности:

	(11)

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

2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

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

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

В связи с этим в качестве методов решения были выбраныописанные в [2] модификации симплекс-метода для случая задачи целочисленноголинейного программирования. В общем случае количество операций симплекс-методане допускает полиномиальной оценки (был даже показан класс задач, для которыхколичество операций составляет O(eⁿ)), но для случая нашей задачи среднеечисло операций допускает полиномиальнуюоценку: O(n³m^1/(n-1)) (n – количество переменных; m – количество ограничений).

2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

Этот алгоритм назван полностью целочисленным, потому чтоесли исходная таблица состоит из целочисленных элементов, то все таблицы,получающиеся в процессе работы алгоритма, содержат только целочисленныеэлементы. Подобно двойственному симплекс-методу, алгоритм начинает работать сдвойственно допустимой таблицы. Если a_i0 (i = 1 ,…, n+m; a_i0 – коэффициенты целевой функции) –неотрицательные целые, то задача решена. Если для какой-нибудь строки a_i0

Пусть задана задача целочисленного линейногопрограммирования:

максимизировать

при условиях

(12)

Условия (12) могут быть записаны как

	(13)

Предположим, что для t=0 (т.е. для исходнойтаблицы) все a_ij – целые и столбцы (j = 1 ,…, n) – лексикографически положительны. Тогда все столбцы на протяжениивычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительногоограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначаетнаибольшее целое число, не превосходящее x. Для любого числа y(положительного или отрицательного) и положительного можно записать:

(14)

где (r_y – неотрицательный остаток от деления нацело y на). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.

Вводимое дополнительное неравенство должно выполняться прилюбом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице(опуская индекс строки) с a₀

	(15)

где x – соответствующая компонента вектора , а - текущие небазисныепеременные. Можно выразить x, a_{0 и} a_j,используя введенное выше представление (14):

(16)

(17)

Подставив выражения (16) и (17) в (15) и переставив члены,получим:

(18)

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

(19)

.

Целочисленная слабая переменная s являетсянеотрицательной. Действительно, если бы s было отрицательным, т.е.принимало бы значения -1, -2, …, тоумножение на сделалобы всю правую часть уравнения (18) отрицательной, в то время как левая частьнеотрицательна.

Рассмотрим два случая и . Для и . Подставляя в уравнение (19) выражение для x из (15),получим:

	(20)

Полученное уравнениеесть не что иное как отсечение Гомори. Для имеем и уравнение (19)приобретает вид:

(21)

Уравнение (21) должно выполняться для любого целочисленногорешения задачи (12). Заметим, что если a₀ в уравнении (21).Потому уравнение (21) может использоваться в качестве ведущей строки всимплекс-методе. В частности, всегда можно выбрать достаточно большим,так чтобы ведущий элемент в строке (21) сталравным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять наскорость сходимости алгоритма. Прежде всего опишем самалгоритм. В качестве начального необходимо взять двойственно допустимоерешение, которое можно получить добавлением ограничения x_n+m+1=M – x₁ - - … - x_n 0, где M – достаточнобольшая константа, и проведением одной итерации с добавленной строкой и слексикографически минимальным столбцом, взятыми вкачестве ведущих. Алгоритм состоит из следующих шагов:

Шаг 0. Начать с двойственнодопустимой матрицы A⁰ в уравнении (13), элементы которой – целыечисла (матрица A⁰ может содержать и нецелые элементы, обэтом см. [2], стр. 306).

Шаг 1. Среди строк с a_i0i₀0 (i=1, …, n+m), то задачарешена.)

Шаг 2. Выбрать (правило выбора будетописано дальше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Шаг 3. Провести шагдвойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться кшагу 1.

Доказательство конечности алгоритма см.[2], стр. 303-304.

Правило выбора формулируетсяследующим образом.

Шаг 0. Пусть строка сномером v является производящей.

Шаг 1. Пусть - лексикографическиминимальный столбец среди столбцов с a_vj

Шаг 2. Для каждого a_vj - наибольшее целое,такое, что (лексикографическименьше).

Шаг 3. Пусть , а (строка v -производящая). Тогда

.

Шаг 4. Положить для a_vj

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

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

2.2.2Прямой алгоритм целочисленного программирования

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

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

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

максимизировать

(22)

при условиях

,

(целые) (k=1,…,n),

где a_0j, a_ij и a_i0 – целые числа и a_i00.

(23)

Предположим, что столбец выбран в качествеведущего и строка v – ведущая строка в итерации симплекс-метода, т.е. для всех строк I, в которых a_is>0.Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим ктаблице отсечение Гомори, полученное из строки v:

где J – множество индексов небазисных переменных в (22), s_k –новая (базисная) слабая переменная и - неопределенная(временно) положительная константа.

Заметим, что если положить = a_vs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,

Это означает, что прямая допустимость таблицы сохраниться, еслииспользовать отсечение (23) в качестве ведущей строки. Во-вторых, , т.е. ведущий элемент равен 1 (если отсечение используетсякак ведущая строка). Легко удостовериться (путем исследования формул изменениябазисных переменных), что преобразование симплексной таблицы с единичнымведущим элементом сохраняет целочисленность элементов симплексной таблицы.

Эти идеи послужили основанием прямого алгоритма вцелочисленном программировании:

Шаг 0. Начать со столбцовой таблицы, в которой a_i00 (i1) и все элементы a_0j, a_ijи a_i0 – целые.

Шаг 1. Проверить выполнение условий a_0j0 (j1); если они выполнены, то конец,текущее базисное решение оптимально; если нет – перейти к шагу 2.

Шаг 2. Выбрать ведущий столбец s с a_0si₀/a_is среди строк с a_is> 0. Эта строка служит производящей дляотсечения Гомори.

Шаг 3. Получить отсечение Гомори из производящей строки идописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23),где .

Шаг 4. Произвести преобразование таблицы, используяотсечение (23) как ведущую строку. Слабая переменная s_k в (23)станет небазисной. Вернуться к шагу 1.

Доказательство конечности алгоритма см.[2], стр. 346-353.

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

(24)

Строка v может стать производящей тогда и только тогда, когда

(25)

где определяется из условия

Определим множество V(s) как совокупность строк,удовлетворяющих условию (25).

Следующие два правила представляют собой примеры допустимыхправил выбора производящей строки:

Правило 1.

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

2. Если список пуст или не содержитни одного индекса из V(s), вернуться к 1.; в противном случае найти в списке первый индекс vV(s). Выбрать строку v какпроизводящую. Вывести из списка индекс v и все предшествующие емуиндексы. Перейти к 3.

3. Последовательно выбирать строку v, взятую в 2.,как производящую, до тех пор, пока vV(s). Как только vV(s), вернуться к 2.

Правило 2.

1. Пусть V_t(s) – множество V(s),соответствующее t-й таблице. Если V_t(s) содержит более одного элемента: V_t(s) = {v₁, v₂, …, v_k+2}, то в качестве производящей выбрать такую строку , что в последовательности множеств V₁(s₁), V₂(s₂), …, V_t(s) строка появилась раньше (непозднее) остальных и затем сохраняласьвплоть до V_t(s); перейти к 2.

2. Последовательно выбирать строку v, взятую в 1.,до тех пор, пока . Как только , вернуться к 1.

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

2.2.3.ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА

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

Пусть задача линейного программирования записана вканонической форме:

минимизировать

при условиях

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

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

то, добавив слабую переменную в каждое неравенство, получим:

Если b_i0, то s_i можноиспользовать в качестве начальных базисных переменных.

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

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

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

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

минимизировать

при условиях

где все b_i неотрицательны.

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

минимизировать

,

при условиях

-z

Если вычесть все уравнения, содержащие b_i,из -формы, получим:

(26)

-z

где Система (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. Описание реквизитов входной информации

1

M

M

M

M

1

Н_пр-та (fk)

1

M

1

M

1

1

1

M

M

1

2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯРАСПИСАНИЯ

Составление ограничений (1) – (7) математической моделизадачи составления расписания является достаточно тривиальной задачей, решаемойс помощью несложных SQL – запросови не требующей предварительного анализа входной информации. Поэтому подробнеелишь остановимся на ограничениях вида (8).

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

Рассмотрим случай линейного расположения пересекающихсямножеств (см. рис. 2.).

Рис.2. Линейно пересекающиесямножества

В случае такого расположения множеств аудиторий дляпроведения занятий общее число ограничений вида (8) будет n-1, где n – количество множеств. Описанное выше расположениепересекающихся множеств может быть названо линейным, так как при этом n пересекающихся множеств расположены как бы в линию. Можно рассмотреть случай, когдамножества пересекают друг друга произвольным образом (см .рис. 3.).

Рис.3. Произвольнопересекающиеся множества

Число ограничений вида (8) в этом случае можно уменьшить,проведя формирование этих ограничений по аналогии со случаем линейногорасположения множеств. Для этого необходимо предположить, что, например,множества B и D, пересекающиеся с A, являются одним множеством,определить область пересечения такого множества с множеством A, после чего провести те же самыедействия с получившейся областью пересечения.

Подробнее об этом см. [2], стр. 210.

2.4. Результаты работы программы

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

Ядро системы и интерфейсная часть былинаписаны на Delphi 6.0.Методы решения и алгоритмы формирования ограничений написаны с использованиемобъектно-ориентированнных технологий, что позволит в будущем легкоинкапсулировать их в дальнейшие модификации системы, не нарушая целостностивзаимодействия различных алгоритмов. Текст объектов методов решения задачиприведен в приложении 2. База данных была реализована на СУБД Oracle 8i, запросы к ней осуществляются на языке PL/SQL.

Исходные данные задачи заносятся втаблицы базы данных с помощью запросных форм. Одна из таких форм приведена нарис. 3.

Рис.3.Форма занесения исходных данных

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

Рис.4. Пример расписания занятий

Алгоритмы решения задачи былипротестированы на различных выборках исходных данных. Тестированиепроизводилось на ЭВМ с процессором IntelPentium 350 Мгц,СУБД Oracle 8i был установлен на двухпроцессорномсервере: 2 CPU Intel Pentium II350 Мгц, ОЗУ 384 Мб; в качестве канала связи использовалась LAN с пропускной способностьюдо 100 Мбит/с. В качестве тестовых исходных данных были использованы какреальные данные о группах, преподавателях и читаемых предметах вечерней формыобучения ЧГУ на 1999/2000 учебные годы, так и случайно формируемые исходныеданные (читаемым предметам случайным образом определяли аудитории дляпроведения занятий). В среднем производилось от 5 до 10 тестов длякаждой тестируемой размерности исходных данных. В результате получили данные,приведенные в таблице 2. На рисунке 5. приведен график зависимости среднеговремени решения задачи от количества читаемых предметов и количества групп.

2.5. Анализ полученных результатов

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

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

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

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

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

ЛИТЕРАТУРА

1. Лагоша Б.А., Петропавловская А.В.Комплекс моделей и методов оптимизации расписания занятий в вузе // Экономика имат. методы. 1993. Т. 29. Вып. 4.

2. Ху Т.Целочисленное программирование и потоки в сетях. М.: Мир, 1979.

3. Лебедев С.С. Модификация методаБендерса частично целочисленного линейного программирования // Экономика и мат.методы. 1994. Т. 30. Вып. 2.

4. Лебедев С.С., Заславский А.А.Использование специального метода ветвей и границ для решения целочисленнойобобщенной транспортной задачи // Экономика и мат. методы. 1995. Т. 31. Вып. 2.

5. Заславский А.А. Использованиестратегии расслоения переменных в общих задачах целочисленного линейногопрограммирования // Экономика и мат. методы. 1997. Т. 33. Вып. 2.

6. Лебедев С.С. О методе упорядочивающейиндексации целочисленного линейного программирования // Экономика и мат.методы. 1997. Т. 33. Вып. 2.

7. Лебедев С.С., Заславский А.А.Модифицированный метод пометок для задач булева программирования // Экономика имат. методы. 1998. Т. 34. Вып. 4.

8. Заславский А.А. Комбинированныйметод решения задач о рюкзаке // Экономика и мат. методы. 1999. Т. 35. Вып. 1.

Приложение1. Возможности программных продуктов систем составления расписаний.

1. Система АВТОР-2+

Система АВТОР-2+ предназначена для быстpогои удобного составления расписаний занятий и сопровождения их в течение всегоучебного года.
АВТОР-2+ - универсальная система. Есть несколько версий программы,рассчитанные на любые учебные заведения:

- сpедниеи специализиpованные (математические, языковые и т.п.) школы, лицеи, гимназии;

- техникумы, училища иколледжи;

- ВУЗы с одним учебнымкорпусом;

- ВУЗы с несколькимиучебными корпусами (с учетом переездов между корпусами).

АВТОР-2+ позволяет максимально облегчить и автоматизиpовать сложный тpуд составителей расписания. Системапомогает легко стpоить, коppектиpовать и pаспечатыватьв виде удобных и наглядных документов:

- pасписания занятий классов (учебных групп);

- расписания пpеподавателей;

- расписание аудиторий(кабинетов);

- учебные планы;

- тарификацию.

АВТОР-2+ имеет пpиятный дизайн идpужеcтвенный сеpвис. Программа достаточно проста в освоении. Имеется подробноеруководство, в котором описаны все возможности и способы работы с программой.
Программа работает на любых IBM-совместимых компьютерах, начиная с486DX с оперативной памятью 4Mb (и выше), занимает около 1 Mb на жестком диске.Операционная система: MS DOS, либо WINDOWS 95/98.
Время работы зависит от размерности учебного заведения и мощностикомпьютера. Полный расчет и оптимизация расписания школы среднего размера (30классов, 60 преподавателей, две смены) идет около 15 минут на компьютере типаCeleron-400.

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

АВТОР-2+ позволяет:

- оптимизировать"окна" в расписании;

- учитывать требуемыйдиапазон дней/часов как для классов, так и дляпреподавателей;

- оптимально pазмещать занятия по кабинетам (аудиториям) с учетомособенностей классов, предметов, пpеподавателей и вместимости кабинетов;

- учитывать хаpактеp pаботы и пожелания как штатных сотpудников, так исовместителей-почасовиков;

- легко соединять("спаpивать") несколько классов (учебныхгрупп) в потоки пpи пpоведении любых занятий;

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

- вводить (помимоосновных пpедметов) спецкуpсы и факультативы;

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

Пожеланию заказчика АВТОР-2+ модифициpуется под условияконкретного учебного заведения.

2. Система “Расписание” ver 4.0 Москва – ЛинТех

Необходимо сразу жеотметить, что программа “Расписание” ориентирована на составление школьногорасписания, использование в ВУЗ`ах и колледжахвозможно лишь с некоторыми оговорками. Составление расписания производится врамках комплекса условий, которые определяются на шагах ввода исходных данных.Полный перечень возможных условий приведен ниже:

- Ограничен максимальныйномер урока – т.е. количество уроков, максимально допустимое в день;

- Равномерностьраспределения нагрузки преподавателей между днями расписания;

- Равномерностьраспределения нагрузки классов между днями расписания;

- Контроль окон врасписании преподавателей;

- Программа учитывает то обстоятельство, что классы могутпроизвольно объединяться и дробиться (классы могут объединяться в потоки или жедробиться на более мелкие подгруппы, причем эти подгруппы, в свою очередь,могут служить основой для объединения в более крупные группы. Пример:в школе №1859 есть 2 старших класса, но в каждом из этих классовесть две подгруппы по специализации, занятия по общеобразовательным предметампроводятся сразу для всего класса, а предметы по специализации – отдельно. Нопоскольку подгруппы по специализации слишком малы, а преподавателей не хватает,по некоторым предметам подгруппы 11а и 11б также могут объединяться (например,на ин.яз.) – это усложняет обеспечении непрерывностирасписания для классов (необходимо обеспечивать непрерывность расписания длякаждой из подгрупп);

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

- Условие привязкипреподавателей к аудитории – отдельные преподаватели имеют “свою” аудиторию, вкоторой проводят все свои занятия;

- Наличие “плавающей”смены – когда время начала первого урока точно не определено, т.к. оноформируется динамически, в зависимости от освобождения связанных с соответствующим классов, преподавателей, аудиторий;

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

- Наличие комбинированныхпредметов – типа “ин.яз./информатика”“информатика/труд” и т.п. - когда класс разбивается на подгруппы;

- Условие привязкипредметов к аудиториям – проведения занятий по отдельным предметам возможнолишь в строго определенной аудитории или списке аудиторий (физкультура, труд ит.п.);

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

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

- Иногда при составлениирасписания требуется учитывать тот нюанс, что по некоторым предметам расписаниеизвестно заранее –в этом случае такие занятия вводятсякак неперемещаемые (фиксированные);

- Контроль запрещенныхкомбинаций предметов, приходящихся на один день расписания класса – например,нежелательно, чтобы “физическая культура” и “труд” проводились в один и тот жедень;

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

- Наличие классов,привязанных к аудиториям – основная масса занятий для таких классов проводитсяименно в этой аудитории, за исключением тех занятий, для которых требуетсяспециализированная аудитория;

- Необходимостьрасстановки занятий по отдельным предметам по два занятия подряд (“парами”,“спарками”), причем это условие может быть жестким (ни в коем случае неразрывать “спарки” занятий), а может носить предпочтительный характер (если неполучается перемещать по два занятия, “спарку” можно разрывать);

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

3. Система “Методист”

Выпускается в двухверсиях.

Версия virtual.

Выпускается без модуляавтоматического составления расписания. Возможности версии virtual:

- быстрыйпоиск в списках преподавателей, аудиторий, классов (групп), дисциплин, корпусов;

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

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

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

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

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

- возможность просмотра,печати и редактирования готового расписания с проверкой корректности изменений(занятость ауд., преп., групп/подгрупп, ...);

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

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

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

- в любой момент можноперейти на версию стандарт;

Методист– стандарт.

Помимо возможностей версии virtual включает в себя:

- Модуль автоматическогосоставления расписания;

- Распределение иконтроль учебной нагрузки ;

- Учет методическихрекомендаций и личных пожеланий преподавателей ("окна", метод. дни,теннис по четвергам, день рождения сына, ...);

- Cтрогое выдерживание последовательности прохождения дисциплины (лекции- 2 час., практические - 4 час., лабораторные ...);

- Составление расписаниядля любого типа учебного заведения: недельное или семестровое (от 1 до 23недель);

- Учет объединения групп(классов) в потоки и/или разбиение их на подгруппы;

- Закрепление специальныхаудиторий (компьютерные классы, лингафонные кабинеты, бассейн,...);

- Учет занятостипреподавателей и аудиторий (совместительство, использование общей учебной базы);

- Учет времени переходовмежду корпусами;

- Выходные и праздничныедни - общие и для отдельных учебных групп (национальные, религиозные,государственные праздники);

- Указание причин"неудачного назначения" занятий (занята аудитория, преподавательназначен в нежелательный для него день недели) с возможностью их"ручного" исправления;

- Возможностьмногократного автоматического "улучшения" расписания;

- Возможность изменениязначимости учитываемых при составлении расписания факторов;

- Возможность введенияприоритетов преподавателей - степени учета их индивидуальных пожеланий;

Ограничения функциональности“Методиста”:

- многосменные расписанияограничены максимальным кол-вом уроков в день – 7;

- занятия всегданачинаются с первого урока / пары (при необходимости возможно назначение напервую пару "свободного занятия" );

- не учитывется времяперемен (например для проверки возможности переходамежду корпусами);

- не учитывается"уровень сложности" занятий для их рационального распределения понеделе (хотя имеется возможность делать это косвенным образом) ;

- продолжительностьзанятий постоянна (невозможно составление расписания для 30 мин. урока вмладших и 45 мин. - в старших классах).

Приложение2. Листинг программного модуля методоврешения задачи автоматического составления расписания

uses

SysUtils;

type MyArray= array ofarray of real;

MyArray_X =array of longint;

procedureStep_Dual_simplex(var a:MyArray; m,n,i1,j1:integer);

{производит одиншаг двойственного симплекс-метода,

ведущий элемент - a[i1,j1]}

vari,j:integer;

b,b1:array of real;

begin

SetLength(b,m);Setlength(b1,n);

for i:=0 to m-1 do b[i]:=a[i,j1];

for i:=0 to n-1 do b1[i]:=a[i1,i];

for i:=0 to m-1 do

for j:=0 to n-1 do begin

if (i=i1) and (j=j1) then a[i,j]:=1/b[i1]

else

if (i=i1) then a[i,j]:=b1[j]/b[i1]

else

if (j=j1) then a[i,j]:=-b[i]/b[i1]

else a[i,j]:=a[i,j]-b[i]*b1[j]/b[i1];

end;

for i:=0 to n-1 do a[i1,i]:=0;a[i1,j1]:=-1;

Finalize(b);Finalize(b1);

end;

function Lexikogr_few(a:MyArray;m,n:integer;i,i1:integer):boolean;

{первый столбец лексикографическименьше второго}

var j:integer;

begin

Lexikogr_few:=false;

j:=0;

while (a[j,i]=a[j,i1]) and (j

if (j

end;

functionFind_nu(a:MyArray;m,n:integer; i,i1:integer):longint;

{i - индекс лексикографическиминимального столбца}

varj:integer;

begin

Find_nu:=1;

j:=0;

while (a[j,i]=a[j,i1]) and (j

if (j0) then Find_nu:=Round(Int(a[j,i1]/a[j,i]));

end;

procedureFull_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

{Полностьюцелочисленный алгоритм задачи линейного целочисленного

программирования,

см. Ху Т. "Целочисленноепрограммирование и потоки в сетях", стр. 300-309,

a - матрица размером m+n+2*n+1, по аналогии:

Требуется найти максимум

z= - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3 >= 14

8x1 + 11x2 + 9x3 >= 12

9x1 + 6x2 + 3x3 >=10,

тогда матрица абудет выглядеть:

1 10 14 21

0 -1 0 0

0 0 -1 0

0 0 0 -1

-14 -2 -2 -7

-12 -8 -11 -9

-10 -9 -6 -3

0 0 0 0,

процедура возвращает вектор X, первые mкомпонент которого - искомое решение,

если последняякомпонента вектора = 1, то решения не существует или оно = бесконечности}

vari,i1:integer;

j,j1:integer;

alfa:real;

begin

repeat

i:=1;

while (i=0) do Inc(i); {производящая строка}

if i

j:=1;

while (j=0) do Inc(j);

if j

for i1:=1 ton-1 do if (a[i,i1]

минимальный столбец}

{выбор альфа}

if j

{Writeln(i,' ',j);readln;}

alfa:=0;

for i1:=1 to n-1 do if a[i,i1]

begin

j1:=Find_nu(a,m,n,j,i1);

if (j1>0) and (-a[i,i1]/j1>alfa) thenalfa:=-a[i,i1]/j1;

end;

{writeln(alfa,' ',i,' ',j);readln;}

{получение отсечения Гомори}

for i1:=0to n-1 do if a[i,i1]>0 then a[m-1,i1]:=round(Int(a[i,i1]/alfa))

else begin

a[m-1,i1]:=round(Int(a[i,i1]/alfa));

if Frac(a[i,i1]/alfa)0 then a[m-1,i1]:=a[m-1,i1]-1;

end;

Step_Dual_simplex(a,m,n,m-1,j);

end;

end;

until (i>=m-1) or (j>=n);

for i:=0 to m-1 do x[i]:=round(a[i,0]);

if j>=n then x[m-1]:=1 else x[m-1]:=0;

end;

procedure Step_One_Simplex(vara:MyArray; m,n,i:integer);

var i1,i2:integer;

{Один шагпрямого целочисленного метода (производящая строка - последняя

i - производящий столбец)}

begin

for i1:=0 to m-2 doa[i1,i]:=a[i1,i]/(-a[m-1,i]);

for i2:=0 to n-1 do

for i1:=0 to m-2 do

if i2ithen a[i1,i2]:=a[i1,i2]+a[i1,i]*a[m-1,i2];

end;

procedureDirect_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:integer);

{Прямойцелочисленный алгоритм задачи целочисленного линейного программирования,

см. Ху Т. "Целочисленное программированиеи потоки в сетях", стр. 344-370,

a - матрица размером m+n+3*n+1 по аналогии:

требуется максимизировать

z = x1 + x2 + x3

-4x1 + 5x2 + 2x3

-2x1 + 5x2

3x1 - 2x2 + 2x3

2x1 - 5x2

тогда матрица абудет выглядеть:

0 -1 -1 -1

4 -4 5 2

5 -2 5 0

6 3 -2 2

1 2 -5 0

0 -1 0 0

0 0 -1 0

0 0 0 -1

10 1 1 1 - вэтой строке первое число - грубая max суммы небазисныхпеременных

0 0 0 0 -строка для отсечения Гомори,

алгоритм работает только при a[i,0]>=0

возвращает вектор X - на месте единичнойматрицы искомое решение,

если в последнейкомпоненте единица - ошибка при расчетах}

vari,j,i1,j1:integer;

bool:boolean;

b,b1,b2:array of byte;

r:real;

begin

SetLength(b,m);SetLength(b1,m);

for i:=0 to m-1 do b1[i]:=0;

{проверка условия оптимальности}

bool:=false;

for j:=1 to n-1 do if a[0,j]

while bool do begin

{поиск производящего столбца}

bool:=false;j1:=0;

for j:=1 to n-1 do begin

if a[m-2,j]>0 then

begin

for i:=0 to m-3 do a[i,j]:=a[i,j]/a[m-2,j];

if not bool then begin j1:=j;bool:=true;end else ifLexikogr_few(a,m,n,j,j1)

then j1:=j;

end;

end;

{поиск производящей строки}

for j:=1to n-1 do

if a[m-2,j]>0 then

for i:=0 to m-3 do a[i,j]:=a[i,j]*a[m-2,j];

for i:=0 to m-1 do b[i]:=0;

i:=1; while (i

i1:=i;

while (i

if (a[i,j1]>0)and (a[i,0]/a[i,j1]

Inc(i);

end;

if i1

if a[i1,0]/a[i1,j1]

b[i1]:=1;

for i:=1 to m-2 do

if(a[i,j1]>0) and (a[i,0]/a[i,j1]

for i:=1 to m-2 do if (b[i]=1) and (b1[i]=1) then i1:=i;

end;

{формирование отсечения Гомори}

for i:=0 to n-1 do if a[i1,i]>0then a[m-1,i]:=round(Int(a[i1,i]/a[i1,j1]))

else begin

a[m-1,i]:=round(Int(a[i1,i]/a[i1,j1]));

ifFrac(a[i1,i]/a[i1,j1])0 then a[m-1,i]:=a[m-1,i]-1;

end;

Step_One_Simplex(a,m,n,j1);

end;

bool:=false;

if i1

b2:=b1;b1:=b;b:=b2;

for j:=1 to n do if a[0,j]

end;

{for j1:=0 to n-1 do Write(a[0,j1]:1:0,' ');Writeln;readln;}

end;

for i:=0 to m-2 do x[i]:=round(a[i,0]);

if i1>=m-1 then x[m-1]:=1 else x[m-1]:=0;

Finalize(b);Finalize(b1);

end;